c++ - 是否有支持 insert() 等的 sorted_vector 类？

Question

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

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

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

Answer 1

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可以自动做到这一点:

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.