연관 컨테이너

SET

정렬된 연관 컨테이너다.

  set<int> s;
  s.insert(10);
  s.insert(50);
  s.insert(20);
  s.insert(40);
  s.insert(30);

  // 정렬되어 출력
  for (set<int>::iterator itr = s.begin(); itr != s.end(); ++itr) {
    cout << *itr << " ";
  }

  auto itr = s.find(20);
  if (itr == s.end()) { cout << "No" << end; }
  else { cout << "Yes, I found." << end; }

정렬을 하기 때문에,

SET 에 객체를 넣고 싶을 때

우리가 sort() 함수에 구조체 객체를 넣으려면 comparator 를 넣어줘야 하는 것 처럼, 여기서도 comparator 정의가 안 되면 넣을 수 없다.

class Todo {
  int priority;
  string job_desc;

 public:
  Todo(int priority, string job_desc)
      : priority(priority), job_desc(job_desc) {}

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

operator< 를 구현하면 된다. (이게 없으면 컴파일 오류가 난다. 이거 구현해라고..)

중요한 점은, 두 객체의 순서가 ‘같은’ 경우는 원소 추가가 중복으로 안 되기 때문에, 잘 처리해야 한다. 예제에서는 priority 가 높을 때 job_desc 를 비교해서 대소를 구분하는데, 이게 빠지면 priority 가 같은 친구는 중복으로 간주한다는 것.

SET 에 외부 객체를 넣고 싶을 때

즉, operator< 를 구현할 수 없는 경우다.

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;
  }
};

Wrapper class (여기선 struct) 를 하나 더 만든다. 여기서는 단순 함수만 존재한다.

그리고 set 을 만들 때, 템플릿 인자가 2개인 걸 골라 선언한다.

set<Todo, TodoCmp> todos;

set 의 정의가 다음과 같기 때문이다. (세 번째는 default value 가 붙어있다)

template <class Key, class Compare = std::less<Key>,
          class Allocator = std::allocator<Key>  // ← 후에 설명하겠습니다
          >
class set;

MAP

SET 과 똑같다. 키에 대응되는 값도 보관한다는 것만 빼면.

#include <map>
  map<string, double> pitcher_list;

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

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

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

  // key 의 순서대로 출력됩니다. '니퍼트가 ㄴ 이니 가장 빨리 출력되겠네요'
  print_map(pitcher_list);

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

Multiset / Multimap

중복 키를 허용한다. 나머지는 똑같다.

#include <set>
  multiset<string> s;

  s.insert("a");
  s.insert("b");
  s.insert("a");
  s.insert("c");
  s.insert("d");
  s.insert("c");
a
a
b
c
c
d

그래서 여기서는 전혀 다른 조회 함수를 써야 한다.

multiset 에서 조회

    auto range = s.equal_range("a");
    for (auto itr = range.first; itr != range.second; ++itr) {
        cout << *itr << endl;
    }

first / second 는 lower - upper bound 라고 이해하면 된다. 어차피 세 번째 increment 파트는 loop 가 한번 돌아야 작동되므로 그런 부분에 헷갈릴 필요는 없다. **itr++ 로 해도 똑같다. **(어차피 increment -> condition 임)

multimap 에서 조회

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

range 에 붙은 first / second 는 동일하게 boundary 를 나타내지만, 이렇게 받아온 element 가 pair 임을 명심하자. 그래서 다시 first / second 를 참조해서 key - value 를 출력하는 것이다.

unordered_set/map

C++11 에 추가되었다. (언급이 안되면 C++98)

어째서 이게 가능할까? 별거 없고 그냥 hashtable (…) collision 나면 최악은 O(n) 인데 어쩔래.. 암튼, 당연히 입력 원소에 따라 bucket 이 재할당된다고 한다.

나머지는 기존 set/map 과 동일하다.

내가 만든 클래스를 unorderd_set/map 에

우선 hash class 를 만들어서 재정의해야 한다. std::hash 가 되도록 그리고 이번에는 `operator==` 를 구현하면 된다. collision 때문에 동일 비교를 해야 함.

class Todo {
  int priority;  // 중요도. 높을 수록 급한것!
  string job_desc;

 public:
  Todo(int priority, string job_desc)
      : priority(priority), job_desc(job_desc) {}

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

  friend ostream& operator<<(ostream& o, const Todo& t);
  friend struct hash<Todo>;
};

// Todo 해시 함수를 위한 함수객체(Functor) 를 만들어줍니다!
// 템플릿 특수화를 하는 것이니, 눈여겨 봐야 합니다 
// (std namespace 안에서 특수화 시켜버림. 이후에 참조되는 영역이 없는 이유)
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));
  }
};

  unordered_set<Todo> todos;

다시 말하는데, 템플릿 인자로 class Ttypename T 가 와도 되고 int 같이 고정된 타입이 와도 되고 Todo 처럼 고정된 클래스가 와도 된다. 2 같은 상수가 와도 된다. 하지만 sTodo 같은 클래스 객체는 못 온다.

그래서 뭘 써야 함?