问题描述
通常,使用排序的std::vector
比std::set
更有效.有谁知道一个库类sorted_vector
,它基本上和std::set
有类似的接口,但是将元素插入到排序的向量中(这样就没有重复了),使用二分查找find
元素等?
我知道编写起来并不难,但最好不要浪费时间并使用现有的实现.
更新: 使用排序向量而不是集合的原因是:如果您有数十万个小集合,每个集合仅包含 10 个左右的成员,则更节省内存只需使用排序的向量.
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 <
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.
解决方案
#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;
}
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());
这篇关于是否有支持 insert() 等的 sorted_vector 类?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!