C++ 기초 개념 10-2 : 맵(map), 셋(set), unordered_map, unordered-set

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요!

---

연관 컨테이너 (Associative Container)

연관 컨테이너는 Key - Value 구조를 가진 컨테이너를 의미한다. set 은 key 값만 가지고 만든 집합이고, map 은 key-value 페어를 이용한다.

multiset 은 중복값을 허용하는 set, multimap 은 중복 키값을 허용하는 map 이다.

 

 

set

template <typename T>
void print_set(std::set<T>& s) {
  // 셋의 모든 원소들을 출력하기
  std::cout << "[ ";
  for (typename std::set<int>::iterator itr = s.begin(); itr != s.end();
       ++itr) {
    std::cout << *itr << " ";
  }
  std::cout << " ] " << std::endl;
}

set 은 BidirectionalIterator 를 이용하고, 원소를 정렬된 상태로 유지한다. 또한 내부적으로 자가 균형 이진 탐색 트리(self-balancing binary search tree)인 레드 블랙 트리로 구현되어 있어, 삽입과 삭제가 O(logN) 에 이루어진다.

원소의 유무를 사용할때는 find 또는 count 를 사용한다.

 

 

사용자 정의 클래스 객체를 셋에 넣을 때

위에서 set 에 삽입한 원소들은 자동으로 정렬된 상태를 갖는다고 이야기 했다. 또한 내부 구현에 레드 블랙 트리가 쓰인다고 설명하기도 했다. 이는 set 에서 원소들을 정렬할 때 연산자(operator <) 가 필요하다는 뜻이다! 따라서 우리가 직접 만든 클래스를 set 에 넣는다면, 우리가 직접 만든 클래스의 객체들을 서로 비교해 줄 수 있는 연산자를 오버로딩해 주어야 한다. 예시를 보자.

bool operator<(const Todo& t) const {
  if (priority == t.priority) {
    return job_desc < t.job_desc;
  }
  return priority > t.priority;
}

 

혹은  다음과 같이, 클래스에 내부적으로 operator < 같은 연산자를 오버로딩하지 않고, set 을 선언할 때 비교할 함수나 함수 객체(functor) 를 인자로 넣어주면 된다. 사실 이 경우가 확장성이 더 좋아 자주 사용되는 패턴이다.

struct TodoCmp {
  bool operator()(const Todo& t1, const Todo& t2) const {
    if (t1.priority == t2.priority) {
      return t1.job_desc < t2.job_desc;
    }
    return t1.priority > t2.priority;
  }
};


// ...
int main() {
  std::set<Todo, TodoCmp> todos;
  // ...
}

todos 라는 set 을 만들어줄때, Todo 객체를 어떻게 비교할 것인지를 TodoCmp 이라는 Functor 를 통해 알려주고 있다!

 

 

map

map 은 set 과 거의 똑같은 자료구조이다. 차이점은, 키에 대응되는 값(value) 까지 std::pair 를 통해 보관한다는 점이다.

다만 주의해야 할 점은 [ ] 연산자이다. 다음의 예시를 보자.

 

std::cout << "류현진 방어율은? :: " << pitcher_list["류현진"] << std::endl;

위의 코드에서, 실제로 류현진에 대응되는 값이 없으면, map 은 value 타입에 맞는 기본값을 그냥 만들어 버린다. 혹은 pitcher_list["류현진"] = 1.0 을 하면, 대응되는 키가 없을 때는 생성, 있을 때는 업데이트를 수행한다.

따라서 원소를 찾거나 삽입시 find 나 count 같은 함수를 이용해 존재 유무를 체크해 주는 것이 좋다.

 

template <typename K, typename V>
void search_and_print(std::map<K, V>& m, K key) {
  auto itr = m.find(key);
  if (itr != m.end()) {
    std::cout << key << " --> " << itr->second << std::endl;
  } else {
    std::cout << key << "은(는) 목록에 없습니다" << std::endl;
  }
}

 

 

multiset / multimap

multiset 과 multimap 은 중복을 혀용한다는 점이 기존의 set, map 과 다르다.

multimap 에 키값이 1인 원소들이 여러개일때, find 를 통해 키값이 1 인 요소들의 값(value) 를 출력하면, 해당 값이 라이브러리에 따라 다르게 나온다! 만약 해당 키값을 가지는 value 를 전부 출력할 때는 equal_range( ) 를 사용한다.

 

  auto range = m.equal_range(1);
  for (auto itr = range.first; itr != range.second; ++itr) {
    std::cout << itr->first << " : " << itr->second << " " << std::endl;
  }

추가적으로 multiset 과 multimap 에서 주의해야 할 것은, 삭제이다. 키값이 1인 원소가 여러 개라고 하자. 만약 키값을 기준으로 삭제를 하면, 한 개가 지워지는 것이 아니라 키값이 1인 모든 원소가 삭제되어 버린다!

 

 

unordered_set, unordered_map

unordered_set 과 unordered_map 은 원소들이 정렬이 되어 있지 않고, 해시함수를 이용해 값을 저장하고 탐색해 탐색, 삽입, 삭제가 O(1) 에 이루어진다.

만약 우리가 직접 만든 클래스를 넣고 싶다면, 맞춤형 hash 함수를 정의해야 한다. 해시 함수는 size_t 를 리턴타입으로 가진다(아니면 명시적으로 int64_t 를 리턴 타입으로 지정해도 된다).

 

// Todo 해시 함수를 위한 함수객체(Functor)
// 를 만들어줍니다!
namespace std {
template <>
struct hash<Todo> {
  size_t operator()(const Todo& t) const {
    hash<string> hash_func;

    return t.priority ^ (hash_func(t.job_desc));
  }
};
}  // namespace std

위의 코드에서는 기본적으로 제공하는 hash_func 을 이용해 string 인 job_desc 를 해시하고, int 타입인 priority 와 XOR 연산을 취해 주었다. 참고로, const 를 붙여주지 않으면 컴파일 에러가 난다. 해시함수는 내부 원소값을 변경하지 않아야 하기 때문이다.

hash 클래스가 namespace std 안에 정의되어 있는 이유는 (이미 위에서 using namespace std 를 했음에도 불구하고), 특정 namespace 안에 새로운 클래스/함수를 추가하기 위해서는 위처럼 명시적으로 namespace (이름) 를 써줘야만 하기 때문이다.

 

그리고 마지막으로 == 연산자를 추가해주면 된다.

bool operator==(const Todo& t) const {
  if (priority == t.priority && job_desc == t.job_desc) return true;
  return false;
}

 

 

사용처

• set : 데이터의 존재 유무 파악 (multiset  - 중복 허용)
• map : 데이터에 대응되는 데이터 저장 (multimap - 중복 허용)
• unordered_set, unordered_map : 정렬된 상태가 필요없으며, 최적화가 필요한 경우