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::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屋！