👱‍♀️ ansohxxn

👱‍♀️ ansohxxn

개인적인 필기 노트

[STL 컨테이너] map & unordered_map & multimap

Date:     Updated:

카테고리:

태그:

🔔 map 컨테이너

#include <map>

  • Associative Container 中 하나로, 키(Key), 값(Value) 구조를 따른다. 키는 값에 대응되며 한 쌍으로 함께 보관한다.
  • Key 는 중복 저장될 수 없다.
    • 같은 Key가 원소로 이미 들어있다면 나중에 오는 insert는 무시된다.
  • 자동으로 원소들이 순서대로 정렬되어 들어간다.

벡터, 리스트 같이 원소들의 연속된 순서에 의미를 가지는 Sequence Container 가 아닌, Key 로서 접근에 의미를 가지는 Associative Container이다.

함수

map 의 원소는 std::pair 타입이다.

  • begin()
    • 시작 반복자 리턴
  • end()
    • 끝의 바로 다음 반복자 리턴
      • 컨테이너의 맨 끝에 빈 곳에 대한 반복자를 리턴한다.
  • insert(std::pair)
    • (key, value) 형태로 원소 추가
      • 반드시 std::pair 객체를 전달해야 한다.
      • std::pair 객체는 단순히 2개의 객체를 멤버로 가지는 C++ 표준 객체이다. 
        template <class T1, class T2>
struct std::pair {
T1 first;
T2 second;
};
      • first는 Key가 되고 second는 Value가 될 것이다.
    • 중복 원소는 허락하지 않으므로 기존 Key가 이미 있다면 insert 하지 않고 무시한다.
  • erase(key)
    • key 값에 대응하는 원소를 삭제
  • clear()
    • 맵의 모든 원소 삭제
  • find(key)
    • key 값에 해당하는 반복자를 리턴한다.
    • key 값을 찾지 못한다면 end()를 호출한다.
      • 맨 끝에 빈 곳에 대한 반복자를 리턴
  • count(key)
    • key 값에 해당하는 원소들의 개수 리턴
  • empty()
    • map이 비어있으면 true, 아니면 false 리턴
  • size()
    • 원소의 총 개수 리턴


원소 추가하는 방법 3가지

map 컨테이너는 원소를 pair 타입 객체로 추가해야 한다.

  1. std::pair 👉 템플릿 구체화 해주기 
      map<string, int> map;
  map.insert(pair<string, int>("식빵", 5));
  2. std::make_pair 함수 👉 간편하게 std::pair 객체를 만들어 리턴해준다. 
      map<string, int> map;
  map.insert(make_pair("식빵", 5));
  3. []연산자 사용 👉 <map> 헤더에 연산자 오버로딩이 되어 있다. 
      map<string, int> map;
  map["식빵"] = 5;
  • 원소의 Value를 수정, 바꿔주려면 []을 사용하자.
    • insert를 사용하면 기존 키가 있는 경우 insert가 무시되기 때문이다.


원소 탐색 : []주의사항, find

find(key) : 해당 키에 해당하는 원소의 반복자를 리턴한다. 못찾으면 end()</u 리턴

  • [] 사용시 주의 사항
    • []로 맵에 없는 Key를 참조하면 자동으로 값의 디폴트 생성자를 호출해서 원소를 추가해버린다.
      • ex) cout << map["식빵"]
        • 현재 map에 “식빵”이라는 key가 없는데도 불구하고 디폴트 값인 0으로 (“식빵”, 0) pair를 원소로 추가해버린다
        • 0이 출력됨
      • 사실 이를 이용할 수도 있음. 없는 key라면 value가 0 으로 자동 추가되어 0을 리턴할테니까 이를 논리 연산식에 이용할 수도 있음.
        • 또 이를 활용하여 Key에 따른 개수를 저장할 때는 map[Key]++만 해줄 수 있다. 기존 Key 가 없다면 1 로 저장될 것이고 원래 기존 Key가 있다면 그 Value 값을 1 증가시키는 것이니 Key 에 따른 총 개수가 Value로 저장되게 된다.
  • 따라서 Key를 참조해야할 때는 find()을 사용하는게 더 안전하다. 
    auto itr = map.find(key);
  • Key 를 못 찾았을 때 
    if (map.find(key) == map.end())


for-each문

map<string, int> map;
for (auto & elem : map)
{
    cout << elem.first << " : " << elem.second << endl;
}
  • map 컨테이너의 원소는 pair 객체이므로
    • for-each문의 elem은 pair객체라는 것에 주의하자.
      • elem.first : Key
      • elem.second : Value


🔔 multimap 컨테이너

map과 다르게 중복 Key를 허락한다.

  • 중복 Key 가 있어도 insert 연산을 무시하지 않는다.

원소 탐색시

  • [] 연산자를 사용할 수 없다.
    • 중복 Key를 허용하므로 map['a'] 하면 어떤 value를 리턴해야 하는지 모호하기 때문에.
  • find()함수를 사용하여 리턴할 경우 중복된 원소들 중 아무거나 리턴한다.
    • 즉 라이브러리마다 어떤게 리턴될지 모름. 가장 먼저 나오는 Key의 Value가 나올 수도 있고 등등… 기준이 다 다르다.
  • std::equal_range 함수 사용
    • 멀티 맵의 Key값을 인자로 받은 후 이 키에 대응되는
      • 중복 원소들의 중 첫번째 원소의 반복자(begin)와
        • first
      • 중복 원소들의 중 마지막 원소의 반복자(end)를
        • second
      • std::pair형태로 리턴해준다. 
        auto range = m.equal_range("식빵"); // Key가 식빵인 원소들의 맨 앞 반복자와 맨 끝 반복자를 pair로 리턴한다.

for (auto itr = range.first; itr != range.second; ++itr) {  // "식빵" 키를 가진 원소들을 출력 
  std::cout << itr->first << " : " << itr->second << " " << std::endl;
}

        💎출력💎

식빵 : 1
식빵 : 30
식빵 : 6


🔔 unordered_map 컨테이너

  • 사용 방법은 map과 같다.

map과 다르게 정렬되지 않으며 해시 함수를 사용하여 원소를 탐색한다.

  • 그래서 원래는 <unordered_map>가 아닌 <hashmap> 으로 지으려고 했으나 그런 이름을 가진 헤더가 많아 그냥 이렇게 지었다고 한다. tmi
  • 원소를 해시 함수로 찾으니까 정렬될 필요가 없음
    • Hash
      • 해시 함수 값이 동일하게 나오면 같은 상자 안에 저장된다.
        • 동일한 원소끼리는 당연히 해시 함수 리턴 값이 같으니 같은 상자 안에 저장되지만
        • 서로 다른 원소끼리도 우연히 해시 함수 값이 같으면 같은 상자 안에 저장될 수 있다.
          • 해시 충돌
  • 해시 함수로 리턴값만 받아 바로 주소 찾아가면 되므로 탐색 시간이 \(O(1)\) 상수시간 밖에 안걸린다.
  • But 해시 충돌이 많이 일어나 한 상자 안에 서로 다른 원소들이 몰려서 저장되게 되면 해당 상자 안에서 찾고자 하는 원소를 탐색해야 하므로
    • 최악의 경우 모든 원소가 한 곳에 모였을 때 \(O(N)\) 시간이 걸릴 수 있다.


내가 만든 클래스를 unordered_map 의 원소로 넣고 싶을 때

  • 내 클래스에 맞는 직접 해시 함수를 만들어 주어야 한다.
    • 내 클래스
      • 정렬은 하지 않으니 < 연산자 오버로딩은 필요 없음
      • 해시 충돌이 일어날 때를 대비해 같은 상자 안에 있는 원소들끼리 비교해야 하므로 == 연산자 오버로딩도 해주어야 한다.
    • hash 템플릿 구조체를 내 클래스 타입으로 특수화
      • unordered_map은 해시 함수 계산을 위해 hash 객체를 사용하기 때문에
      • hash를 내 클래스 타입으로 특수화 하여 () 연산자 오버로딩을 한다. 
        namespace std 
{
template <>
struct hash<MyClass> {
    size_t operator()(const MyClass& myclass) const {
        hash<string> hash_func;  // C++에서 제공하는 string의 해시 함수 포인터

        return myclass.m_data1 ^ (hash_func(m_data2));
     }
};
}
      • XOR (비트연산) 하도록 사용자 정의를 해주었다.
        • 해시 함수 리턴값은 myclass.m_data1 ^ (hash_func(m_data2)) 의 결과가 된다.
      • 참고로 C++ 표준 클래스를 특수화 할 때는 namespace std 안에서 해주어야 한다.

C++ 은 int, double, string 등등 기본 데이터 타입들에 대한 해시 함수 포인터를 제공해주므로 이를 활요하면 된다. hash<T> hash_func


map 과 unordered_map 의 차이

  • map은 정렬 되어있는 상태에서 탐색을 하므로 \(O(logN)\) 시간이 걸린다. 평균도 최악도!
  • hashmap은 해시 함수로 탐색을 하므로 평균 \(O(1)\) 상수 시간이 걸려 매우 빠르지만 해시 충돌이 너무 많이 일어나는 최악의 경우 \(O(n)\) 로 그냥 map보다 더 오래걸릴 수 있다.
  • 원소의 개수가 많을수록 해시충돌이 일어날 확률도 높아지므로
    • 원소의 개수가 적고 빠른 성능을 원할 땐 unordered_map
    • 원소의 개수가 많아 안정성을 원할 땐 map


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기

참고