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

通常，使用排序的std::vector 比std::set 更有效.有谁知道一个库类sorted_vector，它基本上和std::set有类似的接口，但是将元素插入到排序的向量中(这样就没有重复了)，使用二分查找find元素等?

我知道编写起来并不难，但最好不要浪费时间并使用现有的实现.

更新: 使用排序向量而不是集合的原因是:如果您有数十万个小集合，每个集合仅包含 10 个左右的成员，则更节省内存只需使用排序的向量.

解决方案

Boost.Container flat_set

<块引用>

Boost.Container flat_[multi]map/set 容器是基于 Austern 和 Alexandrescu 指南的基于有序向量的关联容器.这些有序向量容器最近也受益于向 C++ 添加移动语义，大大加快了插入和擦除时间.平面关联容器具有以下属性:

• 比标准关联容器更快的查找
• 迭代速度比标准关联容器快得多.
• 小对象的内存消耗更少(如果使用了 shrink_to_fit，则对于大对象)
• 提高缓存性能(数据存储在连续内存中)
• 不稳定的迭代器(插入和擦除元素时迭代器失效)
• 无法存储不可复制和不可移动的值类型
• 比标准关联容器更弱的异常安全性(复制/移动构造函数在擦除和插入中移动值时可能抛出)
• 比标准关联容器更慢的插入和擦除(特别是对于不可移动的类型)

现场演示:

#include <boost/container/flat_set.hpp>#include <iostream>#include <ostream>使用命名空间标准；主函数(){boost::container::flat_set<int>小号；s.插入(1)；s.插入(2)；s.插入(3)；cout <<(s.find(1)!=s.end()) <<结束；cout <<(s.find(4)!=s.end()) <<结束；}

<小时><块引用>

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

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

templateflat_set(首先输入迭代器，最后输入迭代器，常量比较 &比较=比较()，const allocator_type &a = allocator_type());

<块引用>

效果:使用指定的比较对象和分配器构造一个空集，并插入范围 [first, last) 中的元素.

复杂度:如果范围 [first, last) 已经使用 comp 排序，则在 N 中呈线性，否则为 N*log(N)，其中 N 是 last - first.

Often, it is more efficient to use a sorted std::vector instead 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 find elements, etc.?

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.

解决方案

Boost.Container flat_set

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)

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: If you want a sorted vector, it is likely better to insert all the elements, and then call std::sort() once, after the insertions.

boost::flat_set can do that automatically:

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.