map과 unorderd_map 사이의 구현 차이점

Question

C++ 프로그램을 평범한 C로 다시 작성합니다. 이것은 map을 사용하여 입력시 단어의 수를 계산하는 아주 간단한 프로그램입니다. 정적 크기의 해시 테이블 (구조체의 크기와 링크 된 노드 목록에 대한 포인터 배열 포함)을 사용하고 있습니다. 내가 주로 해시 함수를 사용하여 정렬되지 않은 버전을 구현 한 C

#if 1  // switch between 1 and 0 
# include <tr1/unordered_map> 
    typedef std::tr1::unordered_map<std::string,int> map_t; 
#else 
# include <map> 
    typedef std::map<std::string,int> map_t; 
#endif 

에 재 작성 다음과 같은 부분에 문제가있어, 나는이 방법

#if 1 // switch between 1 and 0 
    int hash_function(const char *key, int size); 
#else 
    #define hash_function(key, size) ....... 
#endif 

을 사용하지만, 지금은 방법이해야 아무 생각이 없다 내가 테이블을 정렬하고 테이블의 정적 크기를 가지기 때문에 매크로 모양이 좋아 보인다. 나는지도에 대한 경험이 없으므로이를 구현하는 기존의 방법이 있는지 모르겠습니다.

테이블을 2 차원 배열로 사용하고 간단한 행렬로 사용하고 위에서 아래로 열을 채우려는 아이디어가 있습니다.

다시 말하지만,이 작업을 수행하는 데있어 기존의 방식보다 나은 점이 있습니까?

Answer 1

잘 정리 된 해시 맵은 모든 요소를 ​​순서대로 처리하는 추가 링크 목록이있는 일반 해시 맵입니다. 트릭은 모든 삽입 및 제거시이 링크 된 목록을 올바르게 유지하는 것입니다. 해시 함수는 b/w 및 순서가 변경되지 않고 정렬되지 않은 해시 맵을 변경 (필요)하지 않습니다.

2 차원 배열 아이디어의 주된 문제점은 대부분이 낭비되는 n*sizeOfHashTable 공간을 소비한다는 것입니다.

정렬 된 맵을 구현하는 경우 일반적으로 이진 검색 트리와 같은 정렬 된 데이터 구조를 사용하고 정렬하는 키에 연관된 값이 있어야합니다. 그런 다음 해시 함수를 전혀 사용하지 않습니다.