STL中是否有分类的容器? [英] Is there a sorted container in the STL?
问题描述
STL中是否有分类的容器?
Is there a sorted container in the STL?
我的意思是:我有一个std::vector<Foo>
,其中Foo
是一个定制类.我还有一个比较器,它将比较类Foo
的字段.
What I mean is following: I have an std::vector<Foo>
, 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 defined in the comparator.
现在,我想将类Foo
的元素插入该向量.如果可以的话,我想写:
Now I want to insert an element of class Foo
into 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.
推荐答案
是的, std::multiset
, 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屋!