STL - MAP

  STL 맵들은 기본 컨테이너들 중에서 아마 가장 복잡하고도(상대적으로 말해서) 가장 다목적인 컨테이너들일 것이다. 이 글에서는 가장 기본적인 맵인 map에 대해서만 이야기하고, 다른 트리 기반 구조체(set, multise, mulitimap) 들에 대해서는 생략하겠다. 한 종류의 맵에 대해서는 확실히 알게 되면 다른 것들도 쉽게 이해할 수 있다.

  map은 본질적으로 키-값 쌍들을 담는 컨테이너이다. map에는 임의의 두 종류의 데이터들이 키/값 상의 형태로 저장된다. 키를 통해서 값을 조회하는 데 걸리는 시간은 O(log n)인데, 해시 테이블보다는 비효율적이지만 속도의 차이는 무시할 수 있는 정도이며 삽입과 함께 정렬이 수행된다는 추가적인 장점이 존재한다. 다시 말해서는 map의 항상 정렬된 상태로 존재하는 것이다. 이는 map의 저장 방식 자체(균형 이진 트리(balanced binary, tree), 또는 적흑 트리(red-black tree)라고도 한다)가 가지고 있는 장점이다.

#pragma warning(disable:4786)
#include <map>
#include <iostream>
#include <string>
#include <algorithm>

 

using namespace std;

 

//. 맵 컨테이너들을 비교하는데 쓰이는 템플릿
template <class F, class S>
class value_equals
{
private:
   S second;
public:
   value_equals(const S& s) : second(s) {}
  

   bool operator() (pair <const F, S> elem)
   {
    return elem.second == second;
    }
};

 

//. 코드의 입력과 가독성을 돕기 위한 typedef들
typedef map<int, string> isMap;
typedef isMap::value_type isValType;
typedef isMap::iterator isMapItor;

 

void main()
{
 

isMap c;

 

 //. 키-값 쌍들을 삽입
 c.insert(isValType(100, "One Hundered"));
 c.insert(isValType(3, "Three"));
 c.insert(isValType(150, "One Hundred Fifty"));
 c.insert(isValType(99, "Ninety Nine"));

 

 //. 모든 키들과 값들을 출력
 for(isMapItor itor = c.begin(); itor != c.end(); ++itor)
   cout << "Key = " << (*itor).first << ", Value = " << (*itor).second << endl;

 //. 맵을 연관 배열처럼 다룰 수 있다.
 cout << "Key 3 Displays value " << c[3].c_str() << endl;

 

 //. 다음과 같은 방식으로 키 - 값 쌍을 삽입하는 것도 가능하다.
 isMapItor pos = c.find(123);

 if(pos != c.end())
 {
  //. 요소를 삭제하면 그것을 가리키는 반복자는 무효화 된다.
  //. 그 상태에서 그냥 pos++ 를 호출하면 정의되지 않은
  //. 행동이 발생할 것이다.
  c.erase(pos);
 }

 //. 값에 기반해서 특정한 요소를 찾고 제거한다.
 pos = find_if(c.begin(), c.end(), value_equals<int, string>("Ninety Nine"));
 

if(pos != c.end())
   c.erase(pos);

 

 //. 루프 도중에 요소를 제거하는 경우에는 이런식으로..
 for(isMapItor itr = c.begin(); itr != c.end();)
 {
   if(itr->second == "Three")
     c.erase(itr++);
   else
     ++itr;
  }

}

  value_type이라는 새로운 중간 데이터형은 컨테이너 안에 키 - 값 쌍의 형태로 저장되는 요소들은 나타내기 위한 것이다. 편의를 위해서, typedef를 이용해서 이 데이터형과 다른 데이터형들을 좀더 쓰기 쉬운 형태로 정의했다.

 

  요소(키-값 쌍)를 컨테이너에 삽입할 때에는 insert() 함수를 이용한다. 다른 컨테이너들과 유일한 차이는 map::value_type 형의 값을 넣는다는 점이다. map은 요소가 삽입될 때 자동적으로 그것을 정렬하므로 컨테이터는 항상 키에 의해 정렬된 상태를 유지한다. map을 루프로 돌려서 키들과 그에 연관된 값들을 출력하므로 이 점을 확일 할 수 있다.

 

  map은 두 개의 항목(키와 데이터)을 쌍으로 저장하는 컨테이너이므로 하나의 반복자로 두 개의 항목들에 각각 접근하는 것이 가능하려면 또다른 구조체가 존재해야 한다. 그것이 바로 value_type 구조체이다. 반복자를 역참조하면 value_type 구조체를 얻게 된다. value_type에는 first와 second라는 두 개의 데이터 멤버들이 있는데, first 키 값을 담고 있으며 second는 데이터 값을 담고 있다.

 

  map은 키 값을 통한 임의 접근도 허용한다. 이 경우 map은 연관 배열(또는 희소 배열)과 동일한 방식으로 작동하게 된다. 요소들에 접근하거나 요소들을 추가할 때에는 index() 연산사를 사용한다. 이 연산자를 사용할 때에는 주의할 점이 있다. 이 연산자로 아직 존재하지 않은 요소에 접근하려 하면 에러가 발생하는 대신 기본 생성자에 의해 새 요소가 생성되고 그것이 map에 삽입된다. 에러를 발생시키지 않고 새 요소를 추가한다는 것은 논리적인 버그의 원인 될 수 있으므로 주의하기 바란다.

 

  코드 후반부에는 find() 함수로 특정 키에 해당하는 요소를 찾는 부분이 나온다. 키들을 정렬되어 있으므로, find()의 수행 시간은 O(log n) 이다.

 

  값에 기반해서 요소를 찾는 것은 조금 더 복잡하다. 요소들은 키에 기반해서 정렬되어 있으므로 값에 기반해서 요소를 찾는데 필요한 시간은 O(n)가 된다. 이번 예제에서는 루프 구조 대신 find()_if()라는 범용적인 STL 알고리즘을 이용해서 검색을 수행한다. 이 알고리즘에는 세 개의 인자들을 통해서 검색의 시작 위치를 뜻하는 반복자와 종료 위치를 뜻하는 반복자, 그리고 알고리즘이 검색 성공 여부를 판단하는 데 사용할 함수 객체를 지정해야 한다. 두 반복자는 자명하므로 설명할 필요가 없겠지만 함수 객체(functior)에 대해서는 족므 설명이 필요할 것 같다.

 

  STL에서는 함수들 대신 중복된 함수 연산자들을 가진 클래스들이 쓰인다.(함수 연산자를 중복하는 것이 가능하다는 것을 처음 알게 된 독자도 있을 것이다) 이러한 방식은 일반적인 프로그래밍 문제에 캡슐화된, 그리고 형에 안전한 해결책의 제공을 가능하게 한다. 이번 예제에서 지정한 함수 객체는 단순 value_pair의 second 값을 비교하고 그 결과를 돌려 준다. STL에는 대부분의 문제들에서 코드에 즉시 써먹을 수 있는 함수 객체들이 준비되어 있다. 여러 알고리즘들과 그에 사용할 수 있는 함수 객체들에 대해서는 STL 관련 서적을 참고하길 바란다.

 

  find_if() 기법은 컨테이너에서 어떠한 값을 찾을 때 권장되는 방식이나, map을 직접 루프로 돌려서 요소들을 제거해야 하는 경우도 생길 수 이 있다. 코드 마지막 for 루프가 그에 대한 것이다. 그런데 STL 설계자들은 다른 컨테이너들에서와 달리 map에 대해서는 erase() 함수가 다음의 유효한 위치를 돌려주도록 구현하지 않았다.(아마 속도상의 문제 때문일 것이다.) 이 때문에 다른 컨테이너들에서와는 조금 다른 방식으로 요소들을 제거해야 한다. 요소의 제거에 따른 반복자의 무효화 피하기 위해서는 약간의 우회책이 필요하다.

 

  이번 예제에서는 for 루프문 안에서 반복자를 증가시키는 대신 루프의 본문 안에서 조건에 따라 바복자를 증가시킨다. 요소를 제거해야 하는 경우에는 후행 증가(반복자를 참조한 후 증가시킨다.)를 사용했고, 요소를 제거하지 않는 경우에는 선행 증가(먼저 증가시킨 후 참조)를 사용했다. 이런 방식을 이용하면 임시적인 반복자에 유효한 위치를 보존하는 등의 번거로움을 피할 수 있다. 그러나 선행 증가와 후행 증가의 차이에 의존하는 것은 코드를 이해하기 힘들게 만들며 디버깅이나 유지보수에도 좋지 않다. STL 설계자들이 map의 erase()를 다른 컨테이너들의 erase()와 동일한 방식으로 만들더라면(속도를 희생하더라도) 도 좋지 않았을까 싶다. 표준 위원회가 이러한 문제를 이해해서 다음 버전의 STL에서는 보다 낭느 방향으로 개선이 이루어지길 바란다.

 

  여기에서는 교과서적인 이야기를 하나 하고 넘어가야 할 것 같다. 루프 안에서는 항상 선행 증가를 사용하는 것ㅇ이 좋은 이유는 무엇일까?

 

  효율성 때문이라는 것이 정답이다. 후행증가 연산자는 변수의 이전 값을 돌려주므로 이전 값을 담을 임시적인 변수를 만들고 파괴하는 과정이 일어나게 된다. 후행 증가로도 선행증가와 동일한 방식의 루프를 만드는 것이 가능하지만, 후행 증가를 사용할 특별한 이유(위의 예제 나온 것 등)가 없다면 항상 선행 증가 또는 선행 감소 연산자를 사용하는 것이 바람직하다.

 

- 출저 : Game Programming Gems 1  중에서-

출처 : Tong - duragon님의 VC++통