是否有一个sorted_vector类，它支持insert（）等？ [英] Is there a sorted_vector class, which supports insert() etc.?

问题描述

通常，使用排序的 std :: vector 而不是 std :: set 。有没有人知道一个库类 sorted_vector ，它基本上有一个类似于 std :: set 的接口，排序的向量（以便没有重复），使用二进制搜索 find 元素等。

更新：要使用的原因是什么？一个排序的向量，而不是一个集合是：如果你有成千上万的小集合每个只包含10个左右的成员，它是更内存高效只使用排序的向量。

解决方案

Boost.Container flat_set

Boost.Container flat_ [multi]基于有序向量的关联容器基于奥斯本和亚历山大的准则。这些有序矢量容器最近也受益于将移动语义添加到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：如果你想要一个排序的向量，最好插入所有的元素，然后在插入后调用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 * 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.

  这篇关于是否有一个sorted_vector类，它支持insert（）等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！