在STL中有一个排序的容器 [英] Is there a sorted container in STL

问题描述

ALL，

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

Is there a sorted container in STL? What I mean is following:

我有一个std :: vector，其中Foo是一个自定义类。我还有一个比较器比较类Foo的字段。

I have an std::vector where Foo is a custom made class. I also have a comparator of some sort which will compare the fields of the class Foo.

现在，在我的代码我在做什么：

Now, somewhere in my code I am doing:

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

这将根据我在比较器中定义的规则对向量进行排序。

which will sort the vector according to the rules I define in the comparator.

现在我想在该向量中插入Foo类的元素。
如果我可以只写：

Now I want to insert an element of class Foo in that vector. If I could I would like to just write:

 mysortedvector.push_back( Foo() );

会发生什么是矢量将把这个新元素根据比较器到其位置。

and what would happen is that the vector will put this new element according to the comparator to its place.

相反，现在我必须写：

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

这只是浪费时间，因为向量已经排序，新的元素。

which is just a waste of time, since the vector is already sorted and all I need is to place the new element appropriately.

现在，由于我的程序的性质，我不能使用std :: map<>因为我没有键/值对，只是一个简单的向量。

Now, because of the nature of my program, I can't use std::map<> as I don't have a key/value pairs, just a simple vector.

如果我使用stl :: list，我需要在每次插入后调用sort。

If I use stl::list I again need to call sort after every insertion.

感谢您提供的任何建议。

Thank you for any suggestions you can provide.

推荐答案

是的， std :: set ， std :: multiset ， std :: map 和 std :: multimap 全部使用 std :: less 作为默认比较操作。所使用的底层数据结构通常是平衡的二叉搜索树，例如红黑树。因此，如果您向这些数据结构添加一个元素，然后遍历所包含的元素，则输出将按照排序顺序。将N个元素添加到数据结构的复杂度将是O（N log N），或者与使用任何常见的O（log N）复杂度排序对N个元素的向量排序相同。

Yes, std::set, std::multiset, std::map, and std::multimap are all sorted using std::less as the default comparison operation. The underlying data-structure used is typically a balanced binary search tree such as a red-black tree. So if you add an element to these data-structures and then iterate over the contained elements, the output will be in sorted order. The complexity of adding N elements to the data-structure will be O(N log N), or the same as sorting a vector of N elements using any common O(log N) complexity sort.

在你的具体情况下，由于你没有键/值对， std :: set 或 std :: multiset 可能是您最好的选择。

In your specific scenario, since you don't have key/value pairs, std::set or std::multiset is probably your best bet.

这篇关于在STL中有一个排序的容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！