STL中是否有排序的容器？

Question

ALL，

STL中是否有排序的容器？ 我的意思是如下：

我有一個std :: vector，其中Foo是一個自定義的類。我也有一個比較類的比較，它將比較Foo類的字段。

現在，某個地方在我的代碼我做：

std::sort(myvec.begin(), myvec.end(), comparator); 

將根據我在比較中定義的規則排序向量。

現在我想在該向量中插入Foo類的元素。 如果我可以，我想這樣寫：

mysortedvector.push_back(Foo()); 

，並會發生什麼樣的是，向量將根據比較它的地方把這個新元素。

相反，現在我必須寫：

myvec.push_back(Foo()); 
std::sort(myvec.begin(), myvec.end(), comparator); 

這只是浪費時間，因爲載體已經排序，所有我需要的是新的元素適當的地方。由於我的程序的性質，我不能使用std :: map <>，因爲我沒有鍵/值對，只是一個簡單的向量。

如果我使用stl :: list我需要在每次插入後再次調用排序。

非常感謝您提供任何建議。

Answer 1

是，std::set，std::multiset，std::map和std::multimap使用std::less作爲默認的比較操作的所有排序。所使用的基礎數據結構通常是平衡二叉搜索樹，如紅黑樹。因此，如果您向這些數據結構添加元素，然後遍歷包含的元素，則輸出將按排序順序排列。將N個元素添加到數據結構的複雜度將爲O（N log N），或者與使用任何常見的O（log N）複雜度排序對N個元素的向量進行排序相同。

在您的特定情況下，由於您沒有鍵/值對，因此std::set或std::multiset可能是您最好的選擇。

Answer 2

我不認爲功能存在於STL，一個std ::向量只能與排序分區，nth_element，stable_partition，partial_sort，stable_sort和排序。

您可以創建但是性病的包裝::矢量

​​3210