정렬되지 않은 맵 <string, vector <string>>에 find()를 사용하면 C++에서 순서가 지정된 맵과 동일한 시간이 걸립니다.

Question

문자열과 벡터의 순서가 비 연속 인 un_map<string,vector<string> >이 있습니다. 찾기 기능을 사용하여 특정 문자열을 검색하는 동안 :

find((un_map[A].begin(),un_map[A].end(),field)==un_map[A].end()) 

정렬되지 않은 맵에 대한 찾기 기능의 실행의 시간 및지도를 주문하면 같은 온다. 아무도 왜 그렇게 설명 할 수 있습니까? 지금까지 정렬되지 않은 맵은 해시로 인해 순서가 지정된 맵보다 훨씬 빠릅니다. 찾기 기능을 최적화하고 싶습니다. 도와주세요

Answer 1

std::find은 반복기의 증분 만 사용하여 모든 컨테이너에서 표준 반복을 사용하여 검색합니다. 그래서 여기서 복잡성은 O (n)입니다.

컨테이너를 기반으로 요소를 빠르게 검색하려면 find 컨테이너 메소드를 호출해야합니다.

std::unordered_map::find O (1)의 검색 복잡성. 사용자가 지적 했으므로 해시를 사용하기 때문입니다.

std::map::find 검색 복잡성은 이진 검색을 사용하기 때문에 O (log (n))입니다.