C++ 是否有支持 insert() 等的 sorted_vector 类？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2710221/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is there a sorted_vector class, which supports insert() etc.?
提问by Frank
Often, it is more efficient to use a sorted std::vectorinstead of a std::set. Does anyone know a library class sorted_vector, which basically has a similar interface to std::set, but inserts elements into the sorted vector (so that there are no duplicates), uses binary search to findelements, etc.?
通常，使用 sortedstd::vector而不是 a更有效std::set。有谁知道一个库类sorted_vector，它基本上具有与 类似的接口std::set，但是将元素插入到排序向量中（这样没有重复），对find元素使用二分搜索等？
I know it's not hard to write, but probably better not to waste time and use an existing implementation anyway.
我知道写起来并不难，但最好不要浪费时间并使用现有的实现。
Update:The reason to use a sorted vector instead of a set is: If you have hundreds of thousands of little sets that contain only 10 or so members each, it is more memory-efficient to just use sorted vectors instead.
更新：使用排序向量而不是集合的原因是：如果您有数十万个小集合，每个集合仅包含 10 个左右的成员，那么仅使用排序向量会更节省内存。
回答by Evgeny Panasyuk
Boost.Container flat_[multi]map/set containers are ordered-vector based associative containers based on Austern's and Alexandrescu's guidelines. These ordered vector containers have also benefited recently with the addition of move semantics to C++, speeding up insertion and erasure times considerably. Flat associative containers have the following attributes:
- Faster lookup than standard associative containers
- Much faster iteration than standard associative containers.
- Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
- Improved cache performance (data is stored in contiguous memory)
- Non-stable iterators (iterators are invalidated when inserting and erasing elements)
- Non-copyable and non-movable values types can't be stored
- Weaker exception safety than standard associative containers (copy/move constructors can throw when shifting values in erasures and insertions)
- Slower insertion and erasure than standard associative containers (specially for non-movable types)
Boost.Container flat_[multi]map/set 容器是基于 Austern 和 Alexandrescu 指南的基于有序向量的关联容器。这些有序向量容器最近也受益于向 C++ 添加移动语义，大大加快了插入和擦除时间。扁平关联容器具有以下属性：
- 比标准关联容器更快的查找
- 比标准关联容器快得多的迭代。
- 小对象的内存消耗更少（如果使用了shrink_to_fit，则大对象的内存消耗更少）
- 改进的缓存性能（数据存储在连续内存中）
- 不稳定的迭代器（插入和擦除元素时迭代器失效）
- 无法存储不可复制和不可移动的值类型
- 比标准关联容器更弱的异常安全（复制/移动构造函数可以在擦除和插入中移动值时抛出）
- 比标准关联容器更慢的插入和擦除（特别是对于不可移动类型）
现场演示：
#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: If you want a sorted vector, it is likely better to insert all the elements, and then call std::sort() once, after the insertions.
jalf：如果你想要一个排序的向量，最好插入所有元素，然后在插入后调用 std::sort() 一次。
boost::flat_setcan do that automatically:
boost::flat_set可以自动做到这一点：
template<typename InputIterator>
flat_set(InputIterator first, InputIterator last,
const Compare & comp = Compare(),
const allocator_type & a = allocator_type());
Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the range [first, last).
Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N*log(N), where N is last - first.
效果：使用指定的比较对象和分配器构造一个空集，并插入范围 [first, last) 中的元素。
复杂性：如果范围 [first, last) 已经使用 comp 排序，则在 N 中呈线性，否则N*log(N)，其中 N 是 last - first。
回答by jalf
The reason such a container is not part of the standard library is that it would be inefficient. Using a vector for storage means objects have to be moved if something is inserted in the middle of the vector. Doing this on everyinsertion gets needlessly expensive. (On average, half the objects will have to be moved for each insertion. That's pretty costly)
这种容器不是标准库的一部分的原因是它效率低下。使用向量进行存储意味着如果在向量中间插入了一些东西，则必须移动对象。在每次插入时都这样做会变得不必要的昂贵。（平均而言，每次插入都必须移动一半的对象。这非常昂贵）
If you want a sorted vector, it is likely better to insert all the elements, and then call std::sort()once, after the insertions.
如果您想要一个排序的向量，最好插入所有元素，然后在插入后调用std::sort()一次。
回答by Michael Burr
I think there's not 'sorted container' adapter in the STL because there are already the appropriate associative containers for keeping things sorted that would be appropriate to use in nearly all cases. To be honest, about the only reason I can think of off the top of my head for having a sorted vector<>container might be to interoperate with C functions that expect a sorted array. Of course, I may be missing something.
我认为 STL 中没有“排序容器”适配器，因为已经有适当的关联容器来保持排序，几乎适用于所有情况。老实说，关于我能想到的拥有排序vector<>容器的唯一原因可能是与需要排序数组的 C 函数进行互操作。当然，我可能会遗漏一些东西。
If you feel that a sorted vector<>would be more appropriate for your needs (being aware of the shortcomings of inserting elements into a vector), here's an implementation on Code Project:
如果您觉得 sortedvector<>更适合您的需求（意识到将元素插入向量的缺点），这里是 Code Project 上的一个实现：
I've never used it, so I can't vouch for it (or its license - if any is specified). But a quick read of the article and it looks like the author at least made a good effort for the container adapter to have an appropriate STL interface.
我从未使用过它，所以我不能保证它（或它的许可证 - 如果有的话）。但是快速阅读文章，看起来作者至少为容器适配器具有适当的 STL 接口做出了很好的努力。
It seems to be worth a closer look.
似乎值得仔细研究一下。
回答by Neil G
If you decide to roll your own, you might also want to check out boost:ublas. Specifically:
如果您决定推出自己的产品，您可能还想查看 boost:ublas。具体来说：
#include <boost/numeric/ublas/vector_sparse.hpp>
and look at coordinate_vector, which implements a vector of values and indexes. This data structure supports O(1) insertion (violating the sort), but then sorts on-demand Omega(n log n). Of course, once it's sorted, lookups are O(logn). If part of the array is sorted, the algorithm recognizes this and sorts only the newly added elements, then does an inplace merge. If you care about efficiency, this is probably the best you can do.
并查看coordinate_vector，它实现了值和索引的向量。该数据结构支持 O(1) 插入（违反排序），但随后按需排序 Omega(n log n)。当然，一旦它被排序，查找是 O(logn)。如果对数组的一部分进行了排序，则算法会识别出这一点并仅对新添加的元素进行排序，然后进行就地合并。如果您关心效率，这可能是您能做的最好的事情。
回答by Lance Diduck
Alexandresu's Loki has a sorted vector implementation, if you dont want to go through the relativley insignicant effort of rolling you own.
Alexandresu 的 Loki 有一个排序向量实现，如果你不想经历滚动你自己的相对无关紧要的努力。
回答by moodboom
Hereis my sorted_vector class that I've been using in production code for years. It has overloads to let you use a custom predicate. I've used it for containers of pointers, which can be a really nice solution in a lot of use cases.
这是我多年来一直在生产代码中使用的 sorted_vector 类。它有重载让您可以使用自定义谓词。我已经将它用于指针容器，这在很多用例中都是一个非常好的解决方案。
