是否有支持 insert() 等的 sorted_vector 类？

Boost.Container flat_set

Boost.Container flat_[multi]map/set 容器是基于 Austern 和 Alexandrescu 指南的基于有序向量的关联容器。这些有序向量容器最近也受益于向 C++ 添加移动语义，大大加快了插入和擦除时间。平面关联容器具有以下属性： 比标准关联容器更快的查找比标准关联容器快得多的迭代。减少小对象的内存消耗（如果使用了 shrink_to_fit，则对于大对象） 提高缓存性能（数据存储在连续的内存中） 不稳定的迭代器（插入和擦除元素时迭代器无效） 不可复制和不可移动的值类型不能存储 比标准关联容器更弱的异常安全性（复制/移动构造函数在擦除和插入中移动值时会抛出） 比标准关联容器更慢的插入和擦除（特别是对于不可移动类型）

Live demo：

#include <boost/container/flat_set.hpp>
#include <iostream>
#include <ostream>

using namespace std;

int main()
{
    boost::container::flat_set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    cout << (s.find(1)!=s.end()) << endl;
    cout << (s.find(4)!=s.end()) << endl;
}

jalf：如果你想要一个排序的向量，最好插入所有元素，然后在插入之后调用一次 std::sort() 。

boost::flat_set 可以自动做到这一点：

template<typename InputIterator> 
flat_set(InputIterator first, InputIterator last, 
         const Compare & comp = Compare(), 
         const allocator_type & a = allocator_type());

效果：使用指定的比较对象和分配器构造一个空集，并插入范围 [first, last) 中的元素。复杂性：如果范围 [first, last) 已经使用 comp 排序，则与 N 成线性关系，否则为 N*log(N)，其中 N 是 last - first。

---

这样一个容器不是标准库的一部分的原因是它效率低下。使用向量进行存储意味着如果在向量中间插入了某些东西，则必须移动对象。在每次插入时都这样做会变得不必要地昂贵。 （平均而言，每次插入都必须移动一半的对象。这非常昂贵）

如果您想要一个已排序的向量，最好插入所有元素，然后在插入后调用 std::sort() 一次。

---

我认为 STL 中没有“排序容器”适配器，因为已经有适当的关联容器来保持排序，几乎适用于所有情况。老实说，我能想到的拥有排序 vector<> 容器的唯一原因可能是与需要排序数组的 C 函数互操作。当然，我可能会遗漏一些东西。

如果您觉得排序的 vector<> 更适合您的需求（意识到将元素插入向量的缺点），这里是 Code Project 的实现：

一个符合 STL 的排序向量 作者：Martin Holzherr

我从来没有使用过它，所以我不能保证它（或它的许可证——如果有的话）。但是快速阅读这篇文章，看起来作者至少为容器适配器做出了很大的努力，以拥有一个合适的 STL 接口。

似乎值得仔细看看。

---

如果您决定自己推出，您可能还想查看 boost:ublas。具体来说：

#include <boost/numeric/ublas/vector_sparse.hpp>

并查看坐标向量，它实现了值和索引的向量。此数据结构支持 O(1) 插入（违反排序），但随后按需排序 Omega(n log n)。当然，一旦它被排序，查找是 O(logn)。如果数组的一部分已排序，算法会识别这一点并仅对新添加的元素进行排序，然后进行就地合并。如果您关心效率，这可能是您能做的最好的事情。

---

Alexandresu 的 Loki 有一个排序的向量实现，如果你不想经历滚动你自己的相对微不足道的努力。

http://loki-lib.sourceforge.net/html/a00025.html

---

Here 是我多年来一直在生产代码中使用的 sorted_vector 类。它具有重载，可让您使用自定义谓词。我已经将它用于指针容器，这在很多用例中都是一个非常好的解决方案。

---