Container với std :: vector và std :: thiết lập các thuộc tính?

Question

Có thùng chứa nào trong thế giới C++ có các đặc tính này không?

• Elements là duy nhất và ra lệnh với sự giúp đỡ của một so sánh tùy
• cung cấp một nhà điều hành truy cập ngẫu nhiên.

Tôi hiện đang thu thập dữ liệu của mình thành std::set<C,COMPARATOR> và sau đó thực hiện std::copy(_set.begin(),_set.end(),std::back_inserter(_vec)) để có thể truy cập ngẫu nhiên vào bộ sưu tập đã sắp xếp. Kích thước tuy nhiên có thể đi vào hàng trăm triệu.

Answer 1

Nếu Boost là một lựa chọn, có một cái nhìn tại flat_set in the Containers library.

Giao diện cho flat_set giống hệt như của std::set nhưng nó cung cấp lặp truy cập ngẫu nhiên, giống như 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]; 

Nếu bạn đang bị mắc kẹt với các thư viện chuẩn, bạn có thể sử dụng một sắp xếp vector cho mục đích này. Thư viện chuẩn thực sự cung cấp rất nhiều thuật toán trong tiêu đề <algorithm> cho phép bạn thực hiện khá nhiều thứ mà bạn có thể thực hiện với một số set với dải lặp được sắp xếp.

Answer 2

Không rằng tôi nhận thức được. Tuy nhiên, với hàng trăm triệu phần tử và một số truy cập được sắp xếp, bạn có thể muốn biểu diễn bộ nhớ của mình gọn gàng và liên tục, thậm chí còn có nhiều yêu cầu hơn cho lớp container của bạn.

Tôi muốn đi với std::vector và sử dụng phương pháp mà bạn đã mô tả hoặc bất kỳ thuật toán sắp xếp khác. Có thể bạn sẽ không cần std::set sau đó, vì vậy bạn có thể giải phóng bộ nhớ.

Answer 3

Không có trong chuẩn C++ thư viện, không có. Bạn có thể có set/priority_queue để đặt hàng hoặc vector/deque để truy cập ngẫu nhiên.

Nhưng không có gì để ngăn chặn bạn từ viết wrapper của riêng bạn xung quanh vector mà chỉ đơn giản thực thi trật tự là. Nó không phải là nhiều mã ở tất cả. Một số chức năng mẫu:

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); 
    } 
};