지도와 무순지도 중에서 선택하는 방법은 무엇입니까? 선택,해야 map또는 unordered_map? unordered_map더 많은 메모리를 차지하므로

문자열을 키로 사용하여 데이터를 매핑한다고 가정 해 보겠습니다. 무엇 용기는 내가 선택,해야 map또는 unordered_map? unordered_map더 많은 메모리를 차지하므로 메모리가 문제가되지 않고 속도가 문제라고 가정 해 보겠습니다.

unordered_map일반적으로 O (n)의 최악의 경우 O (1)의 평균 복잡도를 제공해야합니다. 어떤 경우에 O (n)에 도달합니까? map시간 은 언제 보다 효율적 unordered_map입니까? n이 작을 때 발생합니까?

unordered_map기본 haser Vs와 함께 STL 을 사용한다고 가정합니다. 지도. 문자열은 키입니다.

매번 개별 요소에 액세스하지 않고 요소를 반복하려는 경우 선호해야 map합니까?

답변

실제로 메모리에 문제가 없으면 unordered_map단일 요소 액세스를 원하면 항상 더 빠릅니다.

최악의 경우는 이론적이며 모든 요소를 ​​설명하는 단일 해시에 바인딩됩니다. 이것은 실질적인 관련이 없습니다. 는 unordered_map느린 즉시 동일한 해시에 속하는 적어도 로그 N 요소에서 가지고 가져옵니다. 이것은 또한 실질적인 관련이 없습니다. 일부 특수 시나리오에서는보다 균일 한 배포를 보장하는 특정 해싱 알고리즘을 사용할 수 있습니다. 특정 패턴을 공유하지 않는 일반 문자열의 경우 함께 제공되는 일반 해시 함수도 unordered_map마찬가지입니다.

정렬 된 방식으로지도를 탐색 (반복자 사용)하려면을 사용할 수 없습니다 unordered_map. 반대로, map이를 허용 할뿐만 아니라 키의 근사치를 기반으로지도에서 다음 요소를 제공 할 수도 있습니다 ( lower_bound및 upper_bound메서드 참조 ).

답변

                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions
                       |                  | O(n) when hash is the same for any key
                       |                  |
Insertion time         | log(n)+rebalance | Same as search
                       |                  |
Deletion time          | log(n)+rebalance | Same as search
                       |                  |
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases.
                       | not possible or  |
                       | too slow. Or when|
                       | order is required|

답변

어떤 경우에 O (n)에 도달합니까?

모든 입력 자극에 대해 동일한 해시 값을 생성 하는 잘못된 해시 함수가있는 경우 (즉, 충돌 생성) …

어떤 컨테이너를 선택 했어야하나요?

항상 요구 사항 및 데이터 종류 / 양에 대한 질문입니다.

지도가 무순지도보다 시간 효율성이 더 좋은시기는 언제입니까?

그것은 단지 다른 구조입니다. 일반적인 사용 사례에 따라 그중 하나를 사용하도록 선택하는 것이 좋습니다 (사용중인 데이터의 종류와 양을 고려).

n이 작을 때 hppaen입니까?

데이터 양이 적은 경우 모든 것이 특정 STL 구현에 의존합니다. 따라서 때로는 일반 벡터 / 배열도 연관 컨테이너보다 빠를 수 있습니다.

답변

어떤 컨테이너를 선택 했어야하나요? unorder_map은 더 많은 메모리를 차지하므로 메모리가 문제가되지 않고 속도가 문제라고 가정 해 봅시다.

프로필을 작성하고 결정합니다. unordered_map일반적으로 더 빠르지 만 경우에 따라 다릅니다.

어떤 경우에 O (n)에 도달합니까?

해싱이 좋지 않고 여러 요소가 동일한 저장소에 할당되는 경우.

지도가 무순지도보다 시간 효율성이 더 좋은시기는 언제입니까? n이 작을 때 발생합니까?

아마도 그렇지 않을 것입니다.하지만 정말로 관심이 있다면 프로필을 작성하십시오. 작은 크기의 컨테이너가 프로그램의 병목 현상이 될 가능성은 거의 없습니다. 어쨌든 단순한 vector선형 검색이 이러한 경우 더 빠를 수 있습니다.

결정할 때 가장 중요한 것은 순서 지정의 요구 사항과 반복기 무효화의 부족입니다. 둘 중 하나가 필요하면 map. 그렇지 않으면 unordered_map.

답변

std :: map 내부적으로 균형 BST에 요소를 저장합니다. 따라서 요소는 정렬 된 키 순서로 저장됩니다.

std :: unordered_map 해시 테이블을 사용하는 요소를 저장합니다. 따라서 요소는 정렬 된 순서로 저장되지 않습니다. 임의의 순서로 저장됩니다.

메모리 사용량 :

unorder_map은 해시 테이블을 저장하기위한 공간이 필요하기 때문에 메모리 사용량은 map에 비해 unordered_map에서 더 많습니다.

요소 검색을위한 시간 복잡성 :

std :: map에서 요소를 검색하는 시간 복잡도는 O (log n)입니다. 최악의 경우에도 요소는 BST (Balanced Binary Search Tree)로 내부적으로 저장되기 때문에 O (log n)입니다.

반면 std :: unordered_map에서 검색을위한 최상의 경우 시간 복잡도는 O (1)입니다. 해시 코드 함수가 좋지 않으면 최악의 복잡성은 O (n) 일 수 있습니다.

답변