C++ STL - 연관 컨테이너

  저번에 이어서 이번에는 연관 컨테이너에 대해 간단히 살펴봤다.

 

---

연관 컨테이너(Associative Container)

  연관 컨테이너에 대해서 Key-Value의 구조를 갖는다고 언급한 적이 있었다. 그렇기에 연관 컨테이너는 시퀀스 컨테이너와 달리 특정 키 값을 통해 그 키에 해당하는 값을 반환하는 역할을 수행한다. 이러한 Key-Value 구조로 연관 컨테이너가 제공할 수 있는 정보값은 다음과 같다.

 

1. 특정 키가 컨테이너에 존재 하는가?
2. 특정 키에 대응하는 값(value)이 무엇인가?

  위키피디아에 의하면 연관 컨테이너에는 set, multiset, map, multimap 등이 있다고 한다. 이 중에서도 1번 질문에 대답할 수 있는 기능을 가진 컨테이너는 set과 multiset, 2번 질문에 답할 수 있는 기능을 가진 컨테이너는 map과 multimap이다. 일단 2번 질문에 답하기 위해선 자동적으로 1번 질문에 답할 수 있는 능력이 필요하기 때문에, map과 multimap은 set과 multiset의 역할 또한 수행할 수 있다.

 

 

Set

  Set은 지난 번에 알아보았던 vector와 같은 시퀀스 컨테이너에 비교하면 재밌는 특징들을 갖고 있다. 우선, 원소를 어디에 '삽입'할 것인가에 대한 정보가 필요 없다는 점이 있는데, 이는 set이 들어온 원소를 자동적으로 정렬하는 기능을 갖추고 있기 때문이다. 이 때의 정렬 기준은 오름차순이다.

 

#include <iostream>
#include <set>

int main()
{
  std::set<int> s1;

  s1.insert(1);
  s1.insert(100);
  s1.insert(30);
  s1.insert(50);
  s1.insert(75);

  for (std::set<int>::iterator itr = s1.begin(); itr != s1.end(); itr++)
  {
    std::cout << *itr << '\n';
  }

  return 0;
}

/*
출력값 : 
1
30
50
75
100
*/

  역시나 지난 번에 보았던 반복자를 사용하여 set의 각 원소에 접근한다. 데이터를 넣은 순서에 상관 없이 set 내부적으로 정렬이 완료되어 출력되는 것을 확인할 수 있다. 참고로 이때 사용되는 반복자는 시퀀스 컨테이너의 리스트처럼 임의의 위치에 있는 원소에 접근하는 것이 불가능하다.

 

  set의 편리한 점은 특정 원소의 존재 유무를 찾는 작업이 빠르다는 점이다. set 속에 특정 원소가 있는지 없는지를 파악하는 데에는 find가 사용되는데, 해당 원소가 존재하면 그 원소의 반복자를 반환하고 없다면 set::end()의 반복자를 반환한다.

 

#include <iostream>
#include <set>

int main()
{
  std::set<int> s1;

  s1.insert(1);
  s1.insert(100);
  s1.insert(30);
  s1.insert(50);
  s1.insert(75);

  auto itr = s1.find(100);
  if (itr != s1.end()) std::cout << "Found\n";
  else std::cout << "Not Found\n";

  return 0;
}

//출력값 : Found

  다음과 같은 형식으로 찾을 수 있다.

 

  set이 이러한 작업을 빠르게 처리하는 이유는 set이 트리 구조로 구성되어있기 때문이다. 이 때의 트리들은 다음 규칙을 갖는다.

 

1. 왼쪽 자식 노드는 그 부모 노드보다 작은 값을 갖는다.
2. 오른쪽 자식 노드는 그 부모 노드보다 큰 값을 갖는다.

  따라서 특정 값을 찾고자 할 때, 트리의 루트부터 시작하여 자식 노드들과 값을 비교하고, 해당 값이 있을 범위로 이동하면서 찾게 된다. 이러한 탐색 과정 때문에 균형 잡히지 않은 트리, 즉 'Skewed Tree(사향 트리)'의 경우 set의 빠른 탐색 속도를 전혀 살릴 수 없게 된다.

 

  참고로 set의 모든 항목들을 오름차순으로 접근하려면 중위 순회를 이용하면 된다고 한다.

 

  또한, set의 경우 중복된 원소들을 갖지 않는다. 아무리 같은 값을 여러 개 입력하더라도 set 자체적으로 같은 값의 중복 입력을 막아준다. 

 

  추가로 주의할 점. 이전 게시물에서도 이야기했지만 컨테이너는 C++의 템플릿 덕분에 사용자가 새로운 클래스 객체를 사용한다고 해도 대응이 가능하다고 했었다. set 또한 예외는 없지만, 새로이 만든 클래스 객체를 사용하고 싶다면 operator <를 오버로딩하여야만 한다. set 내부적으로 정렬이 일어나기 위해선 원소들간의 비교가 불가결하기 때문이다. operator <를 오버로딩하지 않을 것이라면 어쨌든 set의 내부적인 정렬을 위한 비교 수단을 만들어두어야 한다.

 

 

Map

  map은 set과 거의 비슷하나, key만 저장했던 set과는 달리 key에 해당하는 value까지 저장한다. 사용 예시는 다음과 같다.

 

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

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

  //1. Pair 객체로 추가
  m1.insert(std::pair<int, std::string>(1, "아이스 아메리카노"));
  m1.insert(std::pair<int, std::string>(2, "카페 라떼"));

  //2. make_pair를 통해 추가
  m1.insert(std::make_pair(3, "바닐라 라떼"));

  //3. 배열처럼 추가
  m1[4] = "허브 티";

  for (std::map<int, std::string>::iterator itr = m1.begin(); itr != m1.end(); itr++)
  {
    std::cout << itr->first << "번 메뉴 : " << itr->second << '\n';
  }

  return 0;
}

/*
출력 결과 :
1번 메뉴 : 아이스 아메리카노
2번 메뉴 : 카페 라떼
3번 메뉴 : 바닐라 라떼
4번 메뉴 : 허브 티
*/

  먼저, map은 무조건 그 원소를 std::pair로 받는다. std::pair는 두 개의 객체를 갖는 객체로, pair에 map의 key값과 value값을 넣어 insert함수로 추가해주면 된다. 이 외에도 map을 배열처럼 취급하여 원소를 추가하는 방법, std::make_pair함수를 사용하여 추가하는 방법 등이 있다. std::make_pair함수를 사용하게 되면 여기에 입력한 값들의 타입은 추측된 타입으로 들어가게 된다. map에 대한 접근 또한 반복자를 통해 가능하다. 이 때 itr->first로 map의 key 값을, itr->second로 map의 value 값을 접근할 수 있다.

 

  해당 key에 해당되는 값이 있는지 [] 연산자로 찾는 방법도 있지만, 이 경우 map에 해당 key를 갖는 value가 없는데도 마음대로 값을 추가해버리게 되기에, 가능한 한 find함수로 해당 key가 있는지 판별하는 것이 좋다. map의 find 함수 또한, 찾는 값이 없다면 해당 map의 end()의 반복자를 반환한다.

 

  map 또한 앞서 본 set처럼 중복 원소를 허용하지 않으므로, 같은 값이 여러 번 들어온다면 이를 무시한다.

 

 

Multiset & Multimap

  얘네들은 위에서 본 set과 map과 거의 같다. 다만 큰 차이점이 있다면, 이 둘은 set과 map이 허락하지 않았던 중복 원소를 허용한다는 것이다.

 

  이러한 특징 때문에 생기는 부가적인 문제와 특징은 아래와 같다.

 

1. [] 연산자의 사용이 불가능하다. : 중복 원소를 허용하기 때문에 무슨 값을 반환해야 하는지 확실치 않기 때문이다.
2. find 함수로 중복 원소들 중 하나를 반환하게 될 경우 아무거나 반환된다.
3. 중복되는 값들을 전부 가져오기 위해 equal_range라는 함수를 제공한다. 해당 함수의 인자로 key값을 넣으면, 그 key값을 갖는 반복자들의 시작과 끝을 찾아 std::pair 형태로 반환한다. 따라서 이 함수를 사용해 특정 key 값을 갖는 모든 원소들에 접근할 수 있다.

 

---

  이 외에도 Unordered_set과 Unordered_map이 남았는데 일단 여기까지... 이 둘은 천천히 보고 추가해보는 걸로.

 

참고

• https://www.cplusplus.com/reference/map/map/

map - C++ Reference

• https://ko.wikipedia.org/wiki/%ED%91%9C%EC%A4%80_%ED%85%9C%ED%94%8C%EB%A6%BF_%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC#%EC%BB%A8%ED%85%8C%EC%9D%B4%EB%84%88

표준 템플릿 라이브러리 - 위키백과, 우리 모두의 백과사전

• https://modoocode.com/224

씹어먹는 C++ - <10 - 2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map>