std :: vector 및 std :: set 속성을 가진 컨테이너?

Question

C++ 세계에 이러한 속성이있는 컨테이너가 있습니까?

• 요소는 독특하고
• 는 랜덤 액세스 연산자를 제공하는 사용자 정의 비교기의 도움으로 정렬됩니다.

저는 현재 주문 컬렉션에 랜덤 액세스를 가질 수있을 수있는 std::copy(_set.begin(),_set.end(),std::back_inserter(_vec))을 나중에 std::set<C,COMPARATOR>에 내 데이터를 수집하고 있습니다. 그러나 크기는 수억 수억 개가 될 수도 있습니다.

Answer 1

부스트가 옵션 인 경우 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> 헤더에 많은 알고리즘을 제공합니다.이 알고리즘을 사용하면 정렬 된 반복자 범위가있는 set으로 수행 할 수있는 모든 작업을 수행 할 수 있습니다.

Answer 2

나는 알고 있습니다. 그러나 수억 개의 요소와 일부 액세스 권한을 사용하면 메모리 표현을 작고 연속적으로 만들 수 있으므로 컨테이너 클래스에 더 많은 요구 사항이 필요합니다.

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