C ++에서 HashMap을 사용하는 가장 좋은 방법은 무엇입니까?

C ++에서 HashMap을 사용하는 가장 좋은 방법은 무엇입니까?

---

STL에 HashMap API가 있다는 것을 알고 있지만 이에 관한 좋은 예제가있는 훌륭하고 철저한 문서를 찾을 수 없습니다.

좋은 예가 감사하겠습니다.

---

표준 라이브러리에는 정렬 및 정렬되지 않은 맵 ( std::map및 std::unordered_map) 컨테이너가 포함됩니다. 정렬 된 맵에서 요소는 키를 기준으로 정렬되며 삽입 및 액세스는 O (log n)에 있습니다. 일반적으로 표준 라이브러리는 내부적 으로 순서가 지정된지도에 빨간색 검은 색 나무 를 사용 합니다. 그러나 이것은 구현 세부 사항 일뿐입니다. 순서가없는 맵에서 삽입 및 액세스는 O (1)에 있습니다. 해시 테이블의 또 다른 이름 일뿐입니다.

(순서)가있는 예 std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

산출:

23
키 : hello 값 : 23

컨테이너에서 주문이 필요하고 O (log n) 런타임에 문제가 없다면을 사용하십시오 std::map.

그렇지 않으면 실제로 해시 테이블 (O (1) 삽입 / 액세스) std::unordered_map이 필요한 경우 std::mapAPI 와 유사한 (예 : 위의 예에서는 검색하고 바꿔야 map함 unordered_map) 체크 아웃하십시오 .

unordered_map용기가 도입 된 C ++ 11 표준 개정. 따라서 컴파일러에 따라 C ++ 11 기능을 활성화해야합니다 (예 : GCC 4.8을 사용 -std=c++11하는 경우 CXXFLAGS 에 추가 해야 함).

C ++ 11 릴리스 이전에도 unordered_map네임 스페이스에서 GCC가 지원 되었습니다 std::tr1. 따라서 이전 GCC 컴파일러의 경우 다음과 같이 사용하려고 시도 할 수 있습니다.

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

또한 부스트의 일부입니다. 즉, 더 나은 이식성을 위해 해당 부스트 헤더 를 사용할 수 있습니다 .

---

A hash_map는 표준화 목적으로 사용되는 것의 오래된 표준화되지 않은 버전입니다 unordered_map(원래 TR1에 있으며 C ++ 11 이후 표준에 포함됨). 이름에서 알 수 있듯이 std::map기본적으로 순서가 정렬되지 않은 것과 다릅니다. 예를 들어 from에서 begin()를 통해 반복하는 경우 end()키 ¹ 별로 순서대로 항목을 가져 오지만 unordered_mapfrom에서 begin()를 통해 반복 end()하면 a에서 항목을 가져옵니다. 다소 임의의 순서.

는 unordered_map일반적으로 일정 복잡성을 미칠 것으로 예상된다. 즉, 삽입, 조회 등은 일반적으로 테이블에있는 항목 수에 관계없이 기본적으로 고정 된 시간이 걸립니다. 은 std::map아주 삽입하거나 항목이 성장 검색하는 시간을 의미하지만 - 항목의 수가 저장되는에 로그의 복잡성이 서서히 지도가 커짐을. 예를 들어, 백만 개의 항목 중 하나를 조회하는 데 1 마이크로 초가 걸리는 경우 2 백만 개의 항목 중 하나를 검색하는 데 약 2 마이크로 초, 4 백만 개의 항목 중 하나에 대해 3 마이크로 초, 8 백만의 하나에 대해 4 마이크로 초가 소요될 것으로 예상 할 수 있습니다. 아이템 등

실제적인 관점에서 볼 때 그것은 실제로 전체 이야기가 아닙니다. 본질적으로 간단한 해시 테이블의 크기는 고정되어 있습니다. 범용 컨테이너의 가변 크기 요구 사항에 맞추는 것은 쉽지 않습니다. 결과적으로 (잠재적으로) 테이블을 확장하는 작업 (예 : 삽입)은 잠재적으로 느리게 진행됩니다 (즉, 대부분 상당히 빠르지 만 주기적으로 느리게 진행됩니다). 테이블 크기를 변경할 수없는 조회는 일반적으로 훨씬 빠릅니다. 결과적으로 대부분의 해시 기반 테이블은 삽입 횟수와 비교하여 많은 조회를 수행 할 때 최상의 상태를 유지하는 경향이 있습니다. 많은 양의 데이터를 삽입하는 경우 테이블을 한 번 반복하여 결과를 검색합니다 (예 : 파일에서 고유 단어 수 계산)std::map (아직 계산 복잡도는 다르므로 파일의 고유 단어 수에 따라 다름)

---

^{1std::less<T> 기본적으로 맵을 생성 할 때 순서는 세 번째 템플릿 매개 변수에 의해 정의됩니다 .}

---

컴파일 오류를 생성하는 데 필요한 포함을 생략하지 않는보다 완전하고 유연한 예는 다음과 같습니다.

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

포인터로 미리 정의되어 있지 않으면 키에 특히 유용하지는 않습니다. 일치하는 값은 그렇지 않습니다! 그러나 일반적으로 키에 문자열을 사용하므로 키 선언에서 "const void *"대신 "string"을 사용하면이 문제가 해결됩니다.

---

std::unordered_mapGCC stdlibc ++ 6.4에서 해시 맵 을 사용하는 증거

이것은 https://stackoverflow.com/a/3578247/895245 에서 언급 되었지만 다음 대답 에서는 C ++의 std :: map 안에 어떤 데이터 구조가 있습니까? GCC stdlibc ++ 6.4 구현에 대한 추가 증거를 다음과 같이 제공했습니다.

• 클래스에 GDB 단계 디버깅
• 성능 특성 분석

다음은 해당 답변에 설명 된 성능 특성 그래프의 미리보기입니다.

사용자 정의 클래스 및 해시 함수를 사용하는 방법 unordered_map

이 대답은 그것을 해결합니다 : C ++ unorder_map 커스텀 클래스 유형을 키로 사용

발췌 : 평등 :

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

해시 기능 :

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

---

표준 템플릿을 계속 사용하면서 클래스를 해시하는 방법을 찾으려는 사람들에게는 간단한 해결책이 있습니다.

1. In your class you need to define an equality operator overload ==. If you don't know how to do this, GeeksforGeeks has a great tutorial https://www.geeksforgeeks.org/operator-overloading-c/

2. Under the standard namespace, declare a template struct called hash with your classname as the type (see below). I found a great blogpost that also shows an example of calculating hashes using XOR and bitshifting, but that's outside the scope of this question, but it also includes detailed instructions on how to accomplish using hash functions as well https://prateekvjoshi.com/2014/06/05/using-hash-function-in-c-for-user-defined-classes/

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

3. So then to implement a hashtable using your new hash function, you just have to create a std::map or std::unordered_map just like you would normally do and use my_type as the key, the standard library will automatically use the hash function you defined before (in step 2) to hash your keys.

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}

참고URL : https://stackoverflow.com/questions/3578083/what-is-the-best-way-to-use-a-hashmap-in-c