有没有一个sorted_vector类，它支持插入（）等？
通常，使用sorting的std::vector而不是std::set会更高效。 有没有人知道一个库类sorted_vector ，它基本上有一个类似std::set接口，但插入元素到sorting的向量（所以没有重复），使用二进制search来find元素等？
我知道这不难写，但最好不要浪费时间，而是使用现有的实现。
更新：使用sorting向量而不是集合的原因是：如果您有几十万个只包含10个左右成员的小集合，那么只需使用sorting向量就可以提高内存效率。
Boost.Container flat_set
Boost.Container flat_ [multi] map / set容器是基于Austern和Alexandrescu指导方针的基于有序向量的关联容器。 这些有序的vector容器最近还向C ++添加了移动语义，大大加速了插入和删除时间。 平面关联容器具有以下属性：
- 比标准关联容器更快速的查找
- 比标准关联容器迭代快得多。
- 对于小对象（如果使用了shrink_to_fit，对于大对象）的内存消耗更less
- 改进的高速caching性能（数据存储在连续内存中）
- 非稳定的迭代器（插入和删除元素时迭代器无效）
- 不可复制和不可移动的值types不能被存储
- 比标准关联容器更弱的exception安全性（在擦除和插入中移动值时，复制/移动构造函数可能会抛出exception）
- 比标准关联容器（特别适用于不可移动types）更慢的插入和删除
现场演示 ：
#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：如果你想要一个sorting的向量，最好插入所有的元素，然后在插入之后调用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进行了sorting，则以N为线性，否则N * log（N） ，其中N是last – first。
这种容器不属于标准库的原因是效率低下。 使用vector存储意味着如果在vector的中间插入了某些东西，则必须移动对象。 这样做每一个插入得到不必要的昂贵。 （平均而言，每个插入对象的一半将被移动，这相当昂贵）
如果你想要一个sorting的向量，最好插入所有的元素，然后在插入之后调用std::sort() 一次 。
我认为在STL中没有“sorting的容器”适配器，因为已经有适当的关联容器来保存事物的sorting，几乎适用于所有情况。 说实话，我可以想到的唯一理由是有一个sortingvector<>容器可能是与C函数进行互操作，这些函数需要一个sorting的数组。 当然，我可能会错过一些东西。
如果你觉得一个已sorting的vector<>会更适合你的需要（意识到插入元素到vector中的缺点），下面是一个Code Project的实现：
- 符合STL的sorting向量Martin Holzherr
我从来没有使用它，所以我不能保证它（或其许可证 – 如果指定的话）。 但是快速阅读这篇文章，看起来作者至less为容器适配器提供了一个合适的STL接口。
这似乎值得仔细看看。
如果你决定推出你自己的，你可能还想看看boost：ublas。 特别：
#include <boost/numeric/ublas/vector_sparse.hpp>
并查看coordinate_vector，它实现了值和索引的向量。 这个数据结构支持O（1）插入（违反sorting），但是然后分类按需Omega（n log n）。 当然，一旦sorting，查找是O（logn）。 如果对数组的一部分进行sorting，则algorithm会识别该数组，然后仅对新添加的元素进行sorting，然后进行就地合并。 如果你关心效率，这可能是你能做的最好的。
Alexandresu的Loki有一个sorting的向量执行，如果你不想通过滚动你自己的相对繁琐的努力。
这是我已经在生产代码中使用了多年的sorted_vector类。 它有重载让你使用自定义谓词。 我已经将它用于指针的容器，这在很多用例中都是非常好的解决scheme。
