類似於矢量的數據類型，但已排序

是否有類似矢量或隊列的數據類型，您可以在其中輕鬆添加項目，但是如果添加項目，它們會自動按正確順序插入？類似於矢量的數據類型，但已排序

如果你知道它是什麼而不必實際搜索並找到它，還有一種簡單的方法可以從矢量或隊列中刪除一個項目？

來源

2011-04-28 node ninja

「按正確順序插入」根據...？ – GManNickG 2011-04-28 07:07:29

就像它們是整數一樣，排序。 – 2011-04-28 07:11:32

你檢查過'std :: set'嗎？ – Naveen 2011-04-28 07:12:35

這聽起來像你正在尋找set而不是一個載體。它將根據自然順序排序（<運營商）。要按值刪除元素，請致電erase。

或者，您也可以對矢量使用sort對元素進行排序。如果你需要隨機訪問元素，那麼你會需要這種方法;排序後的容器不提供隨機訪問。可以使用binary_search。

來源

2011-04-28 07:14:17

我不知道這樣的容器。

std::sort存在，您可以在其中指定排序功能，但直接將項目實際插入右邊位置通常更有效。

如果你總是這樣做，那麼你必須解決的唯一「問題」是將一個項目添加到已排序的列表中，這可以在線性時間內以最差的方式完成。

請注意，std::vector<T>::insert()將迭代器作爲參數來指示插入的位置。你可能想寫一個返回這樣一個迭代器的方法findPosition()。然後，寫一個sorted_insert()方法是微不足道的，併成爲類似：

std::vector<int>::iterator findPosition(int v); 
void sorted_insert(std::vector<int>& vec, int v) { vec.insert(findPosition(v), v); } 

void foo() 
{ 
    std::vector<int> vec; 
    sorted_insert(vec, 4); 
}

來源

2011-04-28 07:11:24 ereOn

或者你可以使用'std :: set' ...（我現在覺得有點笨拙） – ereOn 2011-04-28 07:17:41

我喜歡兩個人也認爲我「有點笨」的事實：D – ereOn 2011-04-28 08:35:29

聽起來像是你想std::set或std::multi_set。

來源

2011-04-28 07:14:10 GManNickG

取決於你需要什麼，你爲什麼需要它。

不，在標準庫中，沒有「已排序」的向量或隊列。你有2種選擇，如果你想使用僅標準庫：

排序容器上的每個插入（矢量或隊列）/刪除
實現自己的插入/刪除，通過實施insertion sort

另一種選擇是使用地圖或設置，它們是否會成爲你的問題好（因爲我們不知道它是什麼）

另一種選擇是尋找一些第三方的lib - 我猜boost將有這樣的容器，但我不知道這一點。「

」如果你知道它是什麼，還有一種簡單的方法可以從矢量或隊列中刪除一個項目「 - 你是什麼意思？你有一個迭代器或？或者它的索引？更新時我會編輯我的答案（：

來源

2011-04-28 07:14:52

類似於矢量的數據類型，但已排序

回答

相關問題