c++ - STL 中是否有排序容器？

Question

STL 中有排序容器吗？

我的意思是:我有一个 std::vector<Foo> , 其中 Foo是一个定制的类。我也有某种比较器，它将比较类的字段 Foo .

现在，我正在代码中的某个地方:

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

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

现在我想插入一个 Foo 类的元素进入那个 vector 。如果可以的话，我只想写:

 mysortedvector.push_back( Foo() );

然后 vector 会根据比较器将这个新元素放到它的位置。

相反，现在我必须写:

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

这只是浪费时间，因为 vector 已经排序，我只需要适本地放置新元素。

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

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

Answer 1

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

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