어떤 STL 구조를 사용해야합니까?

고유하지 않은 키 - 값 쌍을 저장할 솔루션이 필요합니다. 키 (공간 효율성)를 반복하고 싶지 않고 조회 속도에 집중하려고합니다 (새 데이터를 삽입하는 효율은 그다지 중요하지 않습니다). 나는 std :: multimap을 여기에서 사용할 것이다. 하지만 몇 가지 범위 기준을 충족시키는 키를 찾아야합니다.어떤 STL 구조를 사용해야합니까?

가장 복잡한 예 : 키는 문자열이며 값은 중요하지 않습니다. "Lol"로 시작하는 모든 값을 찾고 싶습니다. 또는 "bar"와 "foo"사이에있는 모든 값을 찾고 싶습니다.

멀티 맵으로 처리 할 수 있습니까? 두 번째 생각은 값의 벡터를 가리키는 정렬 된 벡터를 사용하는 것입니다. 다음과 같은 것 :

std::vector<std::string, std::vector<T>> sorted_vec;

그런 다음 검색 기준을 쉽게 충족 할 수 있습니다. 그러나 나는 조회의 수행에 정말로 관심이있다. 올바른 접근 방법입니까?

출처

2013-04-07 Dejwi

벡터의 정렬 된지도가 당신이 묘사하는 선상에있는 것처럼 보이지만 충분히 유용하다고 확신하지 못합니다. – WhozCraig

삽입이 중요하지 않다면, 후자가 rb-tree 기반이기 때문에''vector''가''map''보다 선호 될 것이라고 생각합니다. ''struct foo {}; 벡터 ;''OK 일 것입니다. – gongzhitaao

예, std :: multimap을 사용할 수 있습니다. 범위 기반 쿼리를 완료하려면 헤더 파일 알고리즘에서 std :: lower_bound 및 std :: upper_bound 두 알고리즘을 사용할 수 있습니다.

출처

2013-04-07 03:28:50

lower_bound와 upper_bound에 실수를했다고 생각합니다. 두 알고리즘은 멀티 맵 반복기에 효과적이지 않습니다. 대신 multimap :: lower_bound 및 multimap :: upper_bound를 사용하십시오. –

먼저, Dejwi는 "bar와 foo 사이의 키"가 필요하므로 [equal_range] (http://en.cppreference.com/w/cpp/container/multimap/equal_range)가 lower_bound + upper_bound보다 좋을 것입니다. 둘째로, 그는 "lookup의 성능에 대해 정말로 신경을 써야한다."- 멀티 맵은 좋지 않은 선택이다. 정렬 된 벡터는 더 나은 지역성으로 인해 더 빠를 것이다. –

또는 "bar"와 "foo"사이에있는 모든 값을 확인하고 싶습니다.

당신이 부스트가있는 경우, 내가 boost::flat_map (그것은 단지 헤더 전용 라이브러리)을 사용하는 것이 좋습니다는 - 그것은 sorted vector inside을 유지합니다. 일반적으로 더 양호한 검색/지역성으로 인해 std :: map보다 조회가 좋습니다.

그렇지 않으면 당신은 Patricia trie를 사용해야합니다

vector<pair<string,value>> 
or 
vector<pair<string,vector<value>>> //(for re-use of keys) 
// instead of pair, you may use just struct if you concerned with lexicographical compare

플러스 std::sort

플러스 표준 : equal_range/lower_bound

출처

2013-04-07 02:46:45

를 사용합니다.

비표준 임에도 불구하고 one in libstdc++이 있습니다.

표준 컨테이너를 사용해야한다면 정렬 된 벡터 솔루션이 가장 적합하다고 생각합니다.

출처

2013-04-07 02:51:50 tmyklebu

어떤 STL 구조를 사용해야합니까?

답변

관련 문제