부스트 multi_index : 비 고유 키의 고유 값 검색

Question

boost::multi_index_container

struct Elem { 
    A a; 
    B b; 
    C c; 
}; 

기본 키 (데이터베이스 의미에서)는 a과 b의 composite_key입니다. 다른 키는 다양한 유형의 쿼리를 수행하기 위해 존재합니다.

이제 c의 모든 다른 값 집합을 검색해야합니다. 이 값들은 모두 으로 는이 아니라은 고유하지만 또는 std::unique을 사용하여 모든 항목을 반복합니다. 가 c의 다른 값의 수는 < <가 전체 항목 수 (예 : 10 ~ 1000).

이 결과를보다 효율적으로 얻는 간단한 방법이 누락 되었습니까?

Answer 1

나는 Boost.MultiIndex 문서를 훑어 보았으므로 원하는 것을 할 수있는 방법을 찾지 못했습니다. 나는 그것이 가능한지 알고 싶어합니다.

아마도 가장 좋은 방법은 multi_index_container과 함께 std::map<C, size_t> (또는 해시지도)을 유지하고 둘 모두를 "동기화"상태로 유지하는 것입니다.

맵은 C 값과 발생 횟수 (빈도)를 연관시킵니다. 그것은 본질적으로 C 값의 막대 그래프입니다. multi_index_container에 Elem을 추가 할 때마다 히스토그램에서 해당 빈도를 증가시킵니다. multi_index_counter에서 Elem을 제거하면 히스토그램의 해당 빈도가 감소합니다. 빈도가 0이되면 히스토그램에서 해당 항목을 삭제합니다.

별개의 C 값 집합을 검색하려면 히스토그램에서 <key,value> 쌍을 반복하고 각 쌍의 key 부분을 살펴보십시오. std::map을 사용하면 별개의 C 값이 정렬됩니다.

명백한 C 값의 집합을 한 번만 (또는 드물게) 검사하려고한다면 위에서 설명한 방법이 과도 할 수 있습니다. 더 간단한 접근법은 모든 C 값을 std::set<C>에 삽입 한 다음 집합을 반복하여 고유 한 C 값을 검색하는 것입니다.

당신은 뚜렷한 C의 집합이 C의 총수보다 훨씬 작다고 말했습니까? 따라서 std::set<C> 접근 방식은 C를 std::vector으로 복사하고 벡터를 정렬 한 다음 std::unique을 실행하는 것보다 훨씬 적은 공간을 낭비해야합니다.

집합에 복사하는 시간의 복잡도와 벡터에 복사하는 시간을 비교하고 정렬 한 다음 unique을 실행 해 봅시다. N을 C 값의 총 수라고하고, M을 다른 C 값의 수라고합시다. 내 생각에 정해진 접근법은 O (N * log (M))의 시간 복잡성을 가져야합니다. M은 작고 더 높은 N을 사용하여 많이 성장하지 않기 때문에 복잡성은 효과적으로 O (N)이됩니다. 반면, 정렬 + 고유 기법은 O (N * log (N))의 시간 복잡성을 가져야합니다.