是否有sorted_vector类,它支持insert()等？

Question

通常,使用排序std::vector而不是a 更有效std::set.有没有人知道一个库类sorted_vector,它基本上有一个类似的接口std::set,但插入元素到排序的矢量(所以没有重复),使用二元搜索find元素等？

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

更新:使用排序向量而不是集合的原因是:如果您有数十万个小集合,每个集合只包含10个左右的成员,那么使用排序向量代替更高内存效率.

Answer 1

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>

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线性,否则为N*log(N),其中N为last- first.

Answer 2

这样的容器不是标准库的一部分的原因是它效率低下.使用向量进行存储意味着如果在向量的中间插入了某些内容,则必须移动对象.在每次插入时执行此操作会不必要地昂贵.(平均而言,每次插入都需要移动一半的物体.这非常昂贵)

如果你想要一个有序矢量,最好插入所有元素,然后在插入后调用std::sort() 一次.

Answer 3

我认为STL中没有'sorted container'适配器,因为已经存在适当的关联容器,用于保存在几乎所有情况下都适合使用的事物.说实话,关于我能想到排序vector<>容器的唯一原因可能是与期望排序数组的C函数互操作.当然,我可能会遗漏一些东西.

如果您认为排序vector<>更适合您的需求(意识到将元素插入向量中的缺点),这里是Code Project的一个实现:

• 符合STL标准的排序向量作者:Martin Holzherr

我从来没有使用它,所以我不能保证(或许可证 - 如果有的话).但是快速阅读文章并且看起来作者至少为容器适配器做了很好的努力以获得适当的STL接口.

似乎值得仔细研究.