具有 std::vector 和 std::set 属性的容器？

Question

C++ 世界中是否存在具有这些属性的容器？

元素是独一无二的，并在可定制比较器的帮助下排序
提供随机访问运算符。

我目前正在将我的数据收集到 std::set<C,COMPARATOR> 中，然后执行 std::copy(_set.begin(),_set.end(),std::back_inserter(_vec)) 以便能够随机访问有序集合。然而，规模可能会达到数亿。

Answer 1

如果可以选择 Boost，请查看 flat_set in the Containers library。

flat_set 的接口与 std::set 的接口相同，但它提供随机访问迭代器，如 std::vector:

#include <boost/container/flat_set.hpp>

[...]

boost::container::flat_set<int> c;
c.insert(1);
c.insert(2);
c.insert(3);
c.insert(4);

// unfortunately, no operator[] on the container itself,
// but the iterator is random access
int third_element = c.begin()[2];

如果您受困于标准库，您可以为此使用排序的 vector。标准库实际上在 <algorithm> header 中提供了很多算法，这些算法允许你做几乎任何你可以用带有排序迭代器范围的 set 做的事情。

Answer 2

None 我知道。但是，对于数以亿计的元素和一些有序的访问，您可能希望您的内存表示紧凑且连续，这对您的容器提出了更高的要求 class.

我会选择 std::vector 并使用您描述的方法或任何其他排序算法。之后您可能不需要 std::set，因此您可以释放内存。

Answer 3

不在标准 C++ 库中，不。您要么有 set/priority_queue 用于订购，要么有 vector/deque 用于随机访问。

但是没有什么可以阻止您围绕 vector 编写自己的包装器，它只是强制执行排序。根本没有那么多代码。一些示例函数：

template <typename T, typename COMP = std::less<T>>
class sorted_vec {
    std::vector<T> vec_;

public:
    // random access
    using iterator = typename std::vector<T>::iterator;
    T& operator[](size_t idx) { return vec_[idx]; }

    iterator begin() { return vec_.begin(); }
    iterator end() { return vec_.end(); }

    // insertion
    void push(const T& val) {
        vec_.insert(std::lower_bound(vec_.begin(), vec_.end(), COMP{}),
                    val);
    }
};

具有 std::vector 和 std::set 属性的容器？

Container with std::vector and std::set properties ?

c++

c++11

containers