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

2022-01-17 00:00:00 set sorting vector c++ stl

通常,使用排序的std::vectorstd::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.

相关文章