STL中是否有分类容器？

我的意思是：我有一个std :: vector< Foo>,其中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,我再次需要在每次插入后调用sort.

解决方法:

是,std::set,std::multiset,std::map和std::multimap都使用std::less作为默认比较操作进行排序.使用的基础数据结构通常是平衡的二叉搜索树,例如红黑树.因此,如果向这些数据结构添加元素,然后迭代所包含的元素,则输出将按排序顺序排列.将N个元素添加到数据结构的复杂性将是O(N log N),或者与使用任何公共O(log N)复杂度排序对N个元素的向量进行排序相同.

在您的特定场景中,由于您没有键/值对,std :: set或std :: multiset可能是您最好的选择.