C++의 표준 연관 컨테이너(associative container)

연관 컨테이너는 키(key) - 값(value)의 구조를 가짐.
즉, 연관 컨테이너는 키를 바탕으로 이에 대응되는 값을 얻을 수 있는 구조

• set, multiset : 특정 키가 연관 컨테이너에 존재하는지 유무
• map, multimap : 특정 키에 대응되는 값이 무엇인지 질의

셋 (Set)

트리 구조 로 구성되어 있으며, 중복된 원소들이 없음

• 삽입, 삭제 : O(logN)
• 검색 : O(logN)

#include <iostream>
#include <set>

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

  std::cout << "순서대로 정렬되서 나온다" << std::endl;
  print_set(s);

  std::cout << "20 이 s 의 원소인가요? :: ";
  auto itr = s.find(20);
  if (itr != s.end()) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  std::cout << "25 가 s 의 원소인가요? :: ";
  itr = s.find(25);
  if (itr != s.end()) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
}

• BidirectionalIterator 반복자
  - set에 저장되어 있는 원소에 접근하기 위해 제공하는 반복자 BidirectionalIterator. 따라서, 임의 위치의 원소에 접근 불가능하고 순차적으로 하나씩 접근해야 함.

• insert()
  - 내부에 원소를 추가할 때 정렬된 상태를 유지하며 추가됨.
  - 이미 같은 원소가 있다면 insert 수행하지 X

• find()
  - 원소의 존재 유무를 확인하며, 원소 검색 횟수는 트리 높이에 비례.

만든 클래스 객체를 셋에 넣고 싶을 때

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

operater <에 대한 정의로 오버로딩 필요함.
set 내부적으로 정렬 시에 상수반복자 사용하기 때문에 const Todo.

operator< 는 아래 조건을 만족해야 함.

• A < A 는 거짓
• A < B != B < A
• A < B 이고 B < C 이면 A < C
• A == B 이면 A < B 와 B < A 둘 다 거짓
• A == B 이고 B == C 이면 A == C

맵 (map)

set과 거의 같은 자료구조. set은 키만 보관했지만, map은 키에 대응하는 value를 함께 보관

#include <iostream>
#include <map>
#include <string>

template <typename K, typename V>
void print_map(std::map<K, V>& m) {
  // 맵의 모든 원소들을 출력하기
  for (auto itr = m.begin(); itr != m.end(); ++itr) {
    std::cout << itr->first << " " << itr->second << std::endl;
  }
}

int main() {
  std::map<std::string, double> pitcher_list;

  // 참고로 2017년 7월 4일 현재 투수 방어율 순위입니다.

  // 맵의 insert 함수는 pair 객체를 인자로 받습니다.
  pitcher_list.insert(std::pair<std::string, double>("박세웅", 2.23));
  pitcher_list.insert(std::pair<std::string, double>("해커 ", 2.93));

  pitcher_list.insert(std::pair<std::string, double>("피어밴드 ", 2.95));

  // 타입을 지정하지 않아도 간단히 std::make_pair 함수로
  // std::pair 객체를 만들 수 도 있습니다.
  pitcher_list.insert(std::make_pair("차우찬", 3.04));
  pitcher_list.insert(std::make_pair("장원준 ", 3.05));
  pitcher_list.insert(std::make_pair("헥터 ", 3.09));

  // 혹은 insert 를 안쓰더라도 [] 로 바로
  // 원소를 추가할 수 있습니다.
  pitcher_list["니퍼트"] = 3.56;
  pitcher_list["박종훈"] = 3.76;
  pitcher_list["켈리"] = 3.90;

  print_map(pitcher_list);

  std::cout << "박세웅 방어율은? :: " << pitcher_list["박세웅"] << std::endl;
}

• 2개의 템플릿 인자
  - 맵은 템플릿 인자로 2개를 가지는데, 첫번째는 key의 타입이고 두번째는 value의 타입

• std::pair
  -insert()에 필요
  -map에 원소를 넣기 위해서는 반드시 std::pair 필요함 (단순히 2개의 객체를 멤버로 가지는 객체)
  -STL 에서는 std::make_pair 함수를 제공해줌으로써 들어오는 객체를 보고 타입을 추측해서 알아서 std::pair객체를 만들어서 리턴해줌 = 타입을 굳이 명시해줄 필요 없음

// std::pair
template <class T1, class T2>
struct std::pair {
  T1 first;
  T2 second;
};

• operator[]
  -insert()에 필요한 다른 방법
  -만일 해당하는 키가 맵에 이미 있다면 값 대체됨

// 혹은 insert 를 안쓰더라도 [] 로 바로
// 원소를 추가할 수 있습니다.
pitcher_list["니퍼트"] = 3.56;
pitcher_list["박종훈"] = 3.76;
pitcher_list["켈리"] = 3.90;

• 반복자
  -*itr가 map에 저장되어 있는 std::pair 객체를 가리킴.
  -따라서 itr->first는 key를, itr->second는 value를 출력

• 범위 기반 for문

template <typename K, typename V>
void print_map(std::map<K, V>& m) {
  // 맵의 모든 원소들을 출력하기
  for (auto itr = m.begin(); itr != m.end(); ++itr) {
    std::cout << itr->first << " " << itr->second << std::endl;
  }
}

template <typename K, typename V>
void print_map(std::map<K, V>& m) {
  // kv 에는 맵의 key 와 value 가 std::pair 로 들어갑니다.
  for (const auto& kv : m) {
    std::cout << kv.first << " " << kv.second << std::endl;
  }
}

• 원소 탐색 [] 연산자
  -[] 연산자 이용
  -[]연산자는 인자로 키를 받아서 이를 맵에서 찾아서 대응되는 값을 돌려줌
  -주의할 점은, []연산자가 맵에 없는 키를 참조하게 되면, 자동으로 값의 디폴트 생성자를 호출해서 원소를 추가함.
  -따라서 되도록이면 find()로 키 존재하는지 먼저 확인 후에, 값을 참조하는 것이 좋음

std::cout << "박세웅 방어율은? :: " << pitcher_list["박세웅"] << std::endl;

• 원소 탐색 find()
  -find 함수는 맵에서 해당하는 키를 찾아서 이를 가리키는 반복자를 리턴
  -키가 존재하지 않는다면 end() 를 리턴
  
• insert()
  -중복된 원소 insert 허락하지 않음
  -같은 키가 원소로 들어 있다면 나중에 오는 insert 는 무시됨
  -만약에, 원소에 대응되는 값을 바꾸고 싶다면 insert 를 하지 말고, [] 연산자로 대응되는 값을 바꿔주면 됨

멀티셋(multiset)과 멀티맵(multimap)

멀티셋과 멀티맵은 중복된 원소를 허락

• 중복된 연산을 허용하기 때문에 m[1]과 같은 []연산자 지원하지 X
• find() 사용 시 아무거나 리턴될 수 있음.

#include <iostream>
#include <map>
#include <string>

template <typename K, typename V>
void print_map(const std::multimap<K, V>& m) {
  // 맵의 모든 원소들을 출력하기
  for (const auto& kv : m) {
    std::cout << kv.first << " " << kv.second << std::endl;
  }
}

int main() {
  std::multimap<int, std::string> m;
  m.insert(std::make_pair(1, "hello"));
  m.insert(std::make_pair(1, "hi"));
  m.insert(std::make_pair(1, "ahihi"));
  m.insert(std::make_pair(2, "bye"));
  m.insert(std::make_pair(2, "baba"));

  print_map(m);

  std::cout << "--------------------" << std::endl;

  // 1 을 키로 가지는 반복자들의 시작과 끝을
  // std::pair 로 만들어서 리턴한다.
  auto range = m.equal_range(1);
  for (auto itr = range.first; itr != range.second; ++itr) {
    std::cout << itr->first << " : " << itr->second << " " << std::endl;
  }
}

key로 중복 value 호출

auto range = m.equal_range(1);

begin() 과 end() 를 std::pair 로 만들어서 세트로 리턴

정렬되지 않은 셋과 맵 (unordered_set, unordered_map)

셋이나 맵의 경우 원소들이 순서대로 정렬되어서 내부에 저장되지만, unordered_set 과 unordered_map 의 경우 원소들이 순서대로 정렬되서 들어가지 않음.
따라서 반복자로 원소들을 하나씩 출력해보면 거의 랜덤한 순서로 출력됨.

#include <iostream>
#include <string>
#include <unordered_set>

template <typename K>
void print_unordered_set(const std::unordered_set<K>& m) {
  // 셋의 모든 원소들을 출력하기
  for (const auto& elem : m) {
    std::cout << elem << std::endl;
  }
}

int main() {
  std::unordered_set<std::string> s;

  s.insert("hi");
  s.insert("my");
  s.insert("name");
  s.insert("is");
  s.insert("psi");
  s.insert("welcome");
  s.insert("to");
  s.insert("c++");

  print_unordered_set(s);
}

• insert, erase, find : O(1)

해시 함수(Hash function)

unordered_set 과 unordered_map 은 해시 함수를 사용

해시함수란?

• 임의의 크기의 데이터를 고정된 크기의 데이터로 대응시켜주는 함수
• 보통 고정된 크기의 데이터라고 하면 일정 범위의 정수값을 의미
• 만일 같은 원소를 해시 함수에 전달하면 같은 해시값 리턴
• 해시 충돌 발생할 수 있음 (다른 원소 - 같은 해시값)

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

• operator< 불필요 : 셋이나 맵 과는 다르게 순서대로 정렬하지 않기 때문
• operator== 필요 : 해시 충돌 발생 시에 상자안에 있는 원소들과 비교를 해야하기 때문

그래서 어떤 컨테이너 사용?

• 데이터의 존재 유무 만 궁금할 경우 → set
• 중복 데이터를 허락할 경우 → multiset
• 데이터에 대응되는 데이터를 저장하고 싶은 경우 → map
• 중복 키를 허락할 경우 → multimap
• 속도가 매우매우 중요해서 최적화를 해야하는 경우 → unordered_set, unordered_map