41장 연관 컨테이너

41.1 셋

41.1.1 pair

연관 컨테이너(Associative Container)는 키와 값처럼 관련이 있는 데이터를 하나의 쌍으로 저장하는 컨테이너

• 연관 컨테이너 분류

저장 대상	키	키 + 값
중복 불허	셋	맵
중복 허용	멀티셋	멀티맵

연관 컨테이너의 반복자는 모두 양방향 반복자이다. 자료들이 항상 정렬된 상태를 유지하므로 다시 정렬할 필요가 없으며 검색이 워낙 빠르기 대문에 이분 검색을 할 필요도 없다. 언제든지 순서대로 순회하면 정렬된 결과를 얻을 수 있고 검색은 원래부터 초고속이므로 굳이 임의 접근 반복자가 필요하지도 않다.

연관 컨테이너들은 키와 값의 쌍을 표현하기 위해 pair구조체를 사용

• pair 구조체

  연관 컨테이너들이 키와 값의 쌍을 표현하기 위해 사용하는 일종의 유틸리티 클래스, 컴파일에 따라 달라짐

  template<class T1, class T2>

  struct pair {

  typedef T1 first_type;

  typedef T2 second_type;

  T1 first;

  T2 second;

  pair() : first(T1()), second(T2()) {}

  pair(const T1& v1, const T2& v2) : first(v1), second(v2) {}

  };

• 예제 pair

#include <iostream> #include <string> #include <utility> using namespace std;     typedef pair<string, double> sdpair; sdpair getPair() { sdpair temp; temp.first = "문자열"; temp.second = 1.234; return temp; // return make_pair("문자열", 1.234); }     void main() { sdpair sd;     sd = getPair(); cout << sd.first << "," << sd.second << endl; }

임시 변수를 선언하는 것이 귀찮다면 make_pair템플릿 함수로 first와 second에 대입될 값을 전달하여 그 결과를 곧바로 리턴할 수도 있다. getPair는 다음과 같은 모양을 가지는 sdpair구조체를 리턴한다.

41.1.2 셋

셋(Set)은 영어 단어 뜻 그대로 집합을 의미하는데 동일한 타입의 데이터를 모아 놓은 것이다. 저장하는 데이터 자체가 키로 사용되며 값은 저장되지 않는다. 동일 타입의 집합이라는 면에서는 벡터와 같지만 아무 위치에나 삽입되는 것이 아니라 정렬된 위치에 삽입된다는 점이 다르며 그래서 검색 속도가 아주 빠르다.

:: 셋 클래스

STL의 다른 컨테이너들과 마찬가지로 셋도 템플릿으로 정의되어 있다.

template<class Key, class BinPred = less<Key>, class A = allocator<Key>>

class set{ ... }

BinPred는 키를 정렬하기 위한 비교 함수 객체인데 디폴트는 less로 되어 있어 오름차순으로 정렬된다.

set<int>는 정수형의 집합이며 set<Time>은 Time객체의 집합이다. 연관 컨테이너도 시퀀스와 마찬가지로 내부에서 사용하는 타입을 정의하는데 value_type, iterator, const_iterator, reference 등의 같은 이름을 사용한다. 이 외에 다음 세 개의 타입을 추가로 정의한다.

타입	설명
key_type	키의 타입이다. 셋은 키가 곧 값이므로 value_type과 동일하며 맵은 키와 값의 pair 타입으로 정의
key_compare	키를 비교하는 함수 객체 타입이다. 디폴트는 less로 되어 있다.
value_compare	값을 비교하는 함수 객체 타입이다. 셋에서는 key_compare와 동일한 타입으로 정의되며 맵에서는 pair를 비교한다.

생성자는 세 개가 정의되어 있다

explicit set(const BinPred& comp = BinPred());

set(const set& x);

set(InIt first, InIt last, const BinPred& comp = BinPred());

:: 삽입, 삭제

셋에 키를 삽입할 때는 insert 멤버 함수를 사용한다.

pair<iterator, bool> insert(const value_type& val);

iterator insert(iterator it, const value_type& val);

void insert(iterator first, iterator last);

셋은 값이 주어지면 삽입 위치가 정렬 규칙에 의해 자동적으로 결정되므로 별도의 위치를 지정할 필요가 없다. 삽입한 결과로 삽입한 위치의 반복자와 삽입 송공 여부 두 개가 pair로 묶여 리턴된다. 셋은 중복을 허용하지 않으므로 val가 이미 존재할 경우 삽입에 실패할 수도 있다. 키 하나를 삽입하면 삽입된 위치와 성공 여부를 동시에 리턴해야 하며 그래서 pair 구조체가 리턴된다. 반복자에 실패를 뜻하는 특이값이 없기 때문에 반복자와 bool의 짝을 리턴한다. insert를 호출한 후 성공 여부를 알고 싶다면 리턴된 pair의 second 멤버를 읽어 보고 이 값이 true이면 first멤버에서 삽입된 반복자의 위치를 구할 수 있다.

멀티셋은 중복이 허용되므로 첫번째 insert함수의 원형이 조금 다르다

iterator insert(const value_type& val);

나머지 insert함순느 셋과 멀티셋의 원형이 동일하다.

• 예제 setcon

#include <iostream> #include <set> using namespace std;     template<typename C> void dump(const char *desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }     void main() { int ar[] = { 1,4,8,1,9,6,3 }; int i; set<int> s; for( i = 0 ; i < sizeof(ar)/sizeof(ar[0]) ; i++ ) { s.insert(ar[i]); } dump("원본", s);     set<int> s2 = s; dump("사본", s2);     const char* str = "ASDFASDFGHJKL"; set<char> sc( &str[0], &str[13] ); dump("문자셋", sc); }

셋에서 요소를 삭제할 때는 erase함수를 사용한다.

iterator erase(iterator it);

iterator erase(iterator first, iterator last);

size_type erase(const Key& key);

멀티셋의 경우 같은 키값을 가지는 모든 요소를 한꺼번에 삭제한다.

:: 검색

셋에서 특정 키를 찾을 때는 find멤버 함수를 사용한다.

iterator find(const Key& val);

const_iterator find(const Key& val) const;

val키가 발견되면 그 반복자를 리턴하고 없을 경우 end()가 리턴된다.

• 예제

#include <iostream> #include <set> #include <algorithm> using namespace std;     void main() { set<int> s; s.insert(1); s.insert(2); s.insert(3);     set<int>::iterator it; it = s.find(2);     if( it != s.end() ) { cout << *it << endl ; } else { cout << "찾는 키 값이 없음" << endl; } }

멀티셋의 경우 find 멤버 함수로 찾으면 중간 중간 쿡쿡 찔러가며 검색하므로 중복된 키 중 어떤 것이 검색될지 알 수 없는데 이는 이진 검색의 일반적인 특성이다. 중복된 키 중 첫 번째 또는 마지막 요소를 찾고 싶으면 lower_bound, upper_bound함수를 사용해야 하며 둘을 한꺼번에 조사하고 싶으면 equal_range멤버 함수를 사용한다.

iterator lower_bound(const Key& _Key);

iterator upper_bound(const Key& _Key);

pair<iterator, iterator> equal_range(const Key& _Key);

:: 셋의 활용

어떤 값의 집합을 관리하는데 중복되어서는 안되며 빠른 검색으로 존재 여부를 신속하게 알고 싶을 때 셋을 사용한다.

• 예제 stringset

#include <iostream> #include <string> #include <set> using namespace std;     void main() { set<string> s; string name; char ch; set<string>::iterator it;     for(;;) { cout << "1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => "; cin >> ch; switch(ch) { case '1': cout << "새 이름 입력 : "; cin >> name; s.insert(name); break; case '2': cout << "삭제할 이름 입력 : "; cin >> name; s.erase(name); break; case '3': for( it = s.begin() ; it != s.end() ; it++ ) { cout << *it << endl; } break; case '4': cout << "검색할 이름 입력 : "; cin >> name; cout << name << "이(가)" << (s.find(name) != s.end() ? "있" : "없") << "습니다." << endl; break; case '5': return ; }                 } }

41.1.3 객체의 셋

:: 객체의 집합

셋은 템플릿이므로 정수뿐만 아니라 임의의 타입을 모두 넣을 수 있다. 셋은 키를 삽입할 때 항상 정렬된 위치에 삽입하는데 올바른 삽입 위치를 찾기 위해서는 비교 함수를 제공해야 한다.

• 예제 TimeSet

#include <iostream> #include <set> #include <functional> using namespace std;     class Time { protected: int hour, min, sec; public: Time(int h, int m, int s) { hour = h ; min = m ; sec = s ; } void outTime() { printf("%d:%d:%d\n", hour, min, sec); } bool operator < (const Time &t) const { return (hour*3600+min*60+sec < t.hour*3600+t.min*60+t.sec); } };     void main() { set<Time> times; times.insert(Time(1,1,1)); times.insert(Time(9,3,3)); times.insert(Time(4,4,4));     set<Time>::iterator it; for( it = times.begin() ; it != times.end() ; it++ ) { (*it).outTime(); } }

:: 함수 객체 사용

Time객체를 셋에 저장하기 위해서는 < 연산자를 제공해야 하는데 이는 셋의 비교 함수 객체인 less가 이 연산자를 요구하기 때문이다. 만약 set의 비교 객체를 greater로 변경하려면 이때는 < 연산자가 아닌 > 연산자를 정의해야 한다. less, greater같은 미리 제공되는 함수 객체 대신 사용자가 직접 만든 함수 객체 타입을 지정할 수도 있다.

• 예제 TimeComp

#include <iostream> #include <set> #include <functional> using namespace std;     class Time { friend struct TimeComp; protected: int hour, min, sec; public: Time(int h, int m, int s) { hour = h ; min = m ; sec = s ; } void outTime() { printf("%d:%d:%d\n", hour, min, sec); } };     struct TimeComp : public binary_function<Time, Time, bool> { bool operator()(const Time &a, const Time &b) const { return (a.hour*3600+a.min*60+a.sec < b.hour*3600+a.min*60+a.sec); } };     void main() { set<Time, TimeComp> Times; Times.insert(Time(1,1,1)); Times.insert(Time(8,8,8)); Times.insert(Time(2,2,2));     set<Time, TimeComp>::iterator it;     for( it = Times.begin() ; it != Times.end() ; it++ ) { (*it).outTime(); } }

셋은 원하는 비교 방법을 마음대로 지정할 수 있도록 두 번째 템플릿 인수로 사용자가 만든 함수 객체를 받아들이며 이 객체의 비교 방식을 그대로 따른다. 템플릿의 인수로 전달되어야 하므로 단순한 함수 포인터는 사용할 수 없으며 반드시 타입으로 정의되는 클래스여야 한다. set은 비교 함수 객첼르 생성해서 가지고 있다가 비교할 때 객체의 ( )연산자 함술르 호출한다.

:: 객체의 포인터 집합

객체의 번지를 기준으로 정렬하는 것은 실용성이 없으며 포인터가 가리키는 곳의 실제 객체를 기준으로 정렬해야 한다. 이때도 사용자가 비교 함수 객체를 직접 제공해야 한다.

• 예제 TimePtrSet

#include <iostream> #include <set> #include <functional> using namespace std;     class Time { protected: int hour, min, sec; public: Time(int h, int m, int s) { hour = h ; min = m ; sec = s ; } void outTime() { printf("%d:%d:%d\n", hour, min, sec); } bool operator <(const Time &t) const { return (hour*3600+min*60+sec < t.hour*3600+t.min*60+t.sec); } };     struct Timeless : public binary_function<const Time*, const Time*, bool> { bool operator()(const Time *a, const Time *b) const { return *a < *b; } };     void main() { set<Time*, Timeless>times; times.insert(new Time(1,1,1)); times.insert(new Time(9,1,1)); times.insert(new Time(3,1,1));     set<Time*, Timeless>::iterator it; for( it = times.begin() ; it != times.end() ; it++ ) { (**it).outTime(); } }

41.1.4 동등성 조건

비교 함수 객체를 직접 만들 때도 크다 또는 작다 둘 중의 하나로 전후 관계를 분명히 판별하는 식으로 작성해야 한다.

• 예제 setlessequal

#include <iostream> #include <set> #include <ctime> using namespace std;     template<typename C> void dump(const char *desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }     void main() { srand(time(NULL)); set<int, less_equal<int>> s;     for( int i = 0 ; i < 20 ; i++ ) { s.insert(rand()%30); } dump("결과",s); }

셋은 < 아니면 > 두 연산자 중 하나로만 비교해야한다.

그런데 이분 검색 중에 범위를 좁혀 나갈 때는 < 미만 비교 연산자만으로도 충분하지만 검색을 할 때는 정확하게 같은 것이 있는지 조사해야 하므로 == 연산이 필요하다. 그러나 셋은 == 연산을 요구하지 않으며 대신 < 연산의 조합으로 검색할 키를 찾는다. 여기서 동일성과 동등성의 개념이 나누어진다.

• 동일성(equality) : 두 값이 완전히 같은지 검사한다. 객체의 경우 모든 멤버가 일치해야 동일하며 주로 == 연산자를 사용한다.
• 동등성(equivalance) : 두 값이 같은 값으로 인정되는지 검사한다. 키에 해당하는 값만 비교하며 < 연산자의 조합으로 정의된다.

동일성은 두 값이 완전히 같다는 뜻이고 동등성은 두 값이 집합의 기준에서 볼 때 같다고 인정된다는 뜻이다. STL에서 두 키 a와 b의 동등성은 다음 조건으로 점검한다.

!(a < b) && !(b < a)

a가 b보다 작지 않고 b가 a보다 작지 않으면 두 키가 동등하고 인정하는 것이다. 비교 객체가 Comp일 때 다음 조건을 만족해야 두 키가 동등하다고 한다.

!Comp(a,b) && !Comp(b,a)

• 예제 President

#include <iostream> #include <set> #include <string> #include <algorithm> using namespace std;     class president { private: int id; string name; string addr; public:         president(int aid, char *aName, char *aAddr) : id(aid), name(aName), addr(aAddr) {} void outPresident() { printf("id : %d, 이름 : %s, 주소 : %s\n", id, name.c_str(), addr.c_str()); }     bool operator<(const president &other) const { return id < other.id; }     bool operator==(const president &other)const { return (id==other.id && name==other.name && addr==other.addr); } };     void main() { set<president> king; king.insert(president(516,"박정희","동작동")); king.insert(president(1212,"전두환","연희동")); king.insert(president(629,"노태우","강북")); king.insert(president(3030,"김영삼","상도동")); king.insert(president(1234,"김대중","강남"));     set<president>::iterator it;     for( it = king.begin() ; it != king.end() ; it++ ) { (*it).outPresident(); }     president zero(3030,"aaa","bbb"); it = king.find(zero); if( it != king.end() ) { cout << "검색됨" << endl; (*it).outPresident(); }     it = find(king.begin(), king.end(), zero); if( it != king.end() ) { cout << "검색됨" << endl; (*it).outPresident(); } }

<연산자와 == 연산자를 제공하는데 < 연산자는 id만으로 우선 순위를 판별하는 동등성 점검을 하고 == 연산자는 모든 멤버를 다 비교하는 동일성 검사를 하고 있다.

별다른 비교 함수 객체를 지정하지 않았으므로 디폴트 비교 함수 객체인 less가 사용되며 따라서 실제 비교에는 객체의 <연산자가 사용된다. < 연산자가 id로 비교를 수행하므로 id의 오름차순으로 정렬되며 같은 id를 가지는 요소는 삽입이 거부된다.

find멤버 함수로 3030 id를 검색해 보았다. 이런 정보를 가지는 객체는 셋에 포함되어 있지 않지만 결과는 검색되었다고 나온다. 왜 이런 결과가 나오는가 하면 find 멤버 함수가 이분 검색을 하면서 < 연산자만을 사용하여 동등성을 비교하기 때문이다.

<연산자는 id만을 비교하므로 3030과 크지도 않고 작지도 않으면 같은 것으로 취급한다. 이름이나 주소는 아무런 교러 대상이 되지 못한다. set이 삽입이나 검색을 위해 동일성이 아닌 동등성의 개념을 사용한다는 것을 분명히 확인할 수 있다.

반면 전역 find 함수는 구현 코드를 보면 알겠지만 == 연산자로 동일한 요소를 검색한다.

동등성은 동일성 조건의 일부만을 칭하는 개념인데 셋에 포함되는 객체가 멤버 전체를 키로 사용하지 않을 수 있으므로 동일성이 아닌 동등성을 정렬을 하는 것이 논리적으로 합당하다. 사실 find 멤버 함수나 이분 검색의 최종 일치 점검을 위해 동등성보다는 동일성이 더 편리하다. 그러나 이렇게 할 경우 <연산자와 == 연산자가 비교 대상을 다른 것으로 정의하면 혼란스럽기 때문에 하나의 조건만으로 모든 처리를 할 수 있는 정책을 취하는 것이 옳다.

:: 키 변경 불가 원칙

셋은 요소를 정렬할 때 항상 키값을 기준으로 하며 검색할 때도 키값의 대소를 판별하여 이분 검색한다. 키는 셋이 요소의 순서를 정하기 위해 사용하는 중요한 값이므로 셋에 들어가 있는 키를 변경해서는 안된다.

• 예제 KeyChange

#include <iostream> #include <set> using namespace std;     template<typename C> void dump(const char *desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }     void main() { int ar[] = {1,3,2,6,4,5}; int i; set<int> s; for( i = 0 ; i < sizeof(ar)/sizeof(ar[0]) ; i++ ) { s.insert(ar[i]); } dump("최초",s);     set<int>::iterator it; it = s.begin(); it++; it++; it++; *it = 99;     dump("수정 후", s); it = s.find(5); if( it != s.end() ) { cout << *it << endl; } else { cout << "찾는 키가 없습니다." << endl; } }

삽입 직후에는 제대로 정렬되어 있지만 반복자로 키의 값을 강제로 바꾼 후에는 정렬 상태가 깨져 버렸다. 셋은 요소들이 항상 정렬되어 있다고 동작하며 삽입할 때 스스로 정렬된 위치에 삽입한다. 그러나 이 예제처럼 키를 강제로 바꿔 버리면 셋은 무결성이 깨져 버려 이후의 어떤 동작도 보장하지 못한다. 5가 분명히 있음에도 불구하고 없다고 오판하는 이유는 이분 검색 중에 5앞에 99를 먼저 보게 되고 99 뒤쪽에는 절대로 5가 있을 수 없다고 판단해 버리기 대문이다. 검색 뿐만 아니라 이후의 삽입도 완전 엉망이 되고 만다. 한 번 무결성이 깨져 버리면 셋은 그야말로 쓰레기통이 되어 버리는 것이다.

begin이나 find등 반복자를 리턴하는 멤버 함수들이 const_iterator를 리턴한다면 컴파일 중에 키 값을 변경하는 것을 막을 수 있을 것이다. 그러나 이 함수들이 상수 반복자를 리턴하지 못하는 이유는 객체의 모든 값이 키가 아니기 때문이다.

따라서 셋의 반복자를 사용할 때는 가급적 const_iterator 타입을 사용하는 것이 바람직하며 불가피하게 iterator 타입을 써야 한다면 키의 값을 바꾸지 않도록 조심하는 수밖에 없다.

41.1.5 집합 연산

집합 연산 알고리즘은 합집합, 교집합, 차집합, 포함 여부 등의 집합 관련 연산 기능을 제공한다.

OutIt set_union(InIt1 first, InIt1 last1, InIt2 first2, InIt2 last2, OutIt result);

OutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt result);

OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt result);

OutIt set_sysmmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt result);

bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);

set_union함수는 두 개의 반복자 구간 first1~last1, first2~last를 인수로 전달받아 두 구간에 속하는 요소들을 중복없이 합쳐서 result 반복자 위치에 대입한다. 나머지 함수들은 교집합, 차집합, 대칭적 차집합을 작성한다. 대칭적 차집합이란 한쪽 구간에만 있는 요소로 구성된 집합을 의미한다. includes 함수는 두 반복자 구간이 포함관계에 있는지를 조사하여 한 집합이 다른 집합의 부분집합인지를 점검한다.

• 예제 setfunction

#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; template<typename C> void dump(const char *desc, C c) { cout.width(12); cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }     void main() { int i; int ar1[] = { 7,0,0,6,2,9,1,9,1,4,9,2,0 }; int ar2[] = { 9,1,7,6,0,0,4,0,5,1,8 };     set<int> s1; for( i = 0 ; i < sizeof(ar1)/sizeof(ar1[0]) ; i++ ) { s1.insert(ar1[i]); }     set<int> s2; for( i = 0 ; i < sizeof(ar2)/sizeof(ar2[0]) ; i++ ) { s2.insert(ar2[i]); }     vector<int> vu; set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(vu)); dump("합집합", vu);     vector<int> vi; set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(vi)); dump("교집합", vi);     vector<int> vd; set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(vd)); dump("차집합", vd);     vector<int> vd2; set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(vd2)); dump("대칭자", vd2); }

41.2 맵

41.2.1 맵

맵은 키와 값의 쌍을 관리

연관이 있는 두 개의 값을 쌍으로 관리한다는 점에서 진정한 연관 컨테이너라고 할 수 있음

정렬된 상태로 요소를 저장하므로 키값으로 빠르게 검색 가능

맵은 연관있는 데이터의 관계를 표현하는데 주로 사용됨 (일대일 대응)

주민번호를 키로, 이름을 값으로 하여 하나의 짝으로 묶어서 맵에 정렬된 상태로 저장하면 주민번호로부터 이름을 빠르게 검색할 수 있다. 주민번호는 중복되어서는 안되므로 중복을 허락하지 않는 맵으로 이 관계를 표현한다.

:: 맵 클래스

다음과 같은 클래스 템플릿으로 정의되어 있다.

template<class Key, class T, class BinPred = less<Key>, class A = allocator<T>>

class map{ ... }

키 외에 데이터에 해당하는 값의 타입을 두 번째 인수로 요구한다. 키와 값의 타입은 디폴트가 없으므로 반드시 지정해야 한다.

맵이 정의하는 타입은 셋과 동일하되 key_type과 value_type이 다르게 정의되어 있으며 key_compare와 value_compare도 다른 함수 객체이다. 맵의 value_type은 키와 값의 pair 타입으로 정의되며 value_compare는 키값만으로 비교를 수행하는 함수 객체 타입이다. 맵의 생성자는 셋의 생성자와 동일하다.

explicit map(const BinPred& comp = BinPred());

map(const map& x);

map(InIt first, InIt last, const BinPred& comp = BinPred());

세 번째 생성자는 반복자 구간으로부터 맵을 생성하는데 다른 컨테이너의 구간으로부터 생성가능하다. 그러나 타입이 키와 값을 쌍으로 가지는 pair여야 하므로 실제로는 같은 타입의 멤버끼리만 구간 복사가 가능하다고 할 수 있다. 구간 복사시 정렬되어 들어가며 멀티 맵이 아니면 중복된 키는 한 번만 삽입된다.

:: 삽입, 삭제

맵에 요소를 추가할 때는 insert 함수를 사용하는데 셋과 원형이 일치한다.

pair<iteraotr, bool> insert(const value_type& val);

iterator insert(iterator it, const value_type& val);

void insert(iterator first, iterator last);

맵에 삽입되는 요소의 타입인 value_type은 키와 값을 쌍으로 가지는 pair 객체여야 한다. 미리 pair객체를 준비해 놓고 삽입할 수도 있겠지만 보통은 pair의 생성자를 호출하여 임시 pair 객체를 만들어 곧바로 맵에 전달한다.

m.insert(pair<string, int>("문자열", 1234));

삽입된 위치를 가리키는 반복자와 성공 여부를 표시하는 bool값이 pair로 묶여서 리턴되며 키가 이미 존재하면 삽입이 거부된다.

두 번째 원형의 insert함수는 삽입 위치에 대한 힌트를 제공하며 세 번째insert 함수는 반복자 구간을 삽입한다. 맵은 insert함수 외에 좀 더 편리한 삽입 방법을 제공하는데 [ ]연산자와 대입 연산자로도 요소를 삽입할 수 있다.

T& operator[](const Key& k);

[ ]연산자는 인수로 전달된 k를 키로 가지는 pair객체를 생성하여 맵에 삽입하고 이 pair의 값(pair.second)에 대한 레퍼런스를 리턴한다. 레퍼런스에 값을 곧바로 대입하기만 하면 방금 삽입한 요소의 값을 지정할 수 있다.

다음 insert문과 대입문은 동일하다.

m.insert(pair<string, int>("문자열", 1234));

m["문자열"] = 1234;

단, [ ]연산자는 맵에서만 정의되어 있으며 멀티 맵에는 정의되어 있지 않다. [ ]연산자가 값의 수정에도 사용되는데 키가 중복되어 있을 경우 어떤 키에 대한 값을 리턴해야 할지가 애매하기 때문이다.

요소를 삭제할 때는 erase 함수를 사용하는데 이 함수도 셋과 동일하다. 멀티 맵의 경우 키를 가진 요소가 여러 개 발견되면 전부 삭제된다.

iterator erase(iterator it);

iterator erase(iterator first, iterator last);

size_type erase(const Key& key);

• 예제 citypopu

#include <iostream> #include <string> #include <map> using namespace std;     void main() { map<string, int> m; m.insert(pair<string, int>(string("서울"), 1000)); m.insert(pair<string, int>("부산", 500)); m["대전"] = 400; m["대구"] = 300; m["광주"] = 200; m["인천"] = 100; m["독도"] = 1;     m.erase(m.begin()); m.erase("인천");     map<string, int>::iterator it; for( it = m.begin() ; it != m.end() ; it++ ) { cout << it->first << ":" << it->second << "만명" << endl; } }

m.begin()으로 맵의 첫 번째 요소를 구해 삭제했는데 서울을 가장 먼저 삽입했지만 정렬되어 들어가므로 begin이 리턴하는 반복자는 가나다순으로 광주를 가리킬 것이다.

it 반복자는 맵의 요소를 가리키고 이 요소는 문자열과 정수의 pair이므로 문자열을 읽을 때는 it가 가리키는 곳의 first를 읽어야 하며 정수를 읽을 때는 second를 읽어야 한다. pair 구조체의 두 멤버 이름이 first, second로 고정되어 있는데 맵의 요소는 first가 키이고 second가 값이다.

:: 검색

검색할때는 find멤버 함수를 사용한다.

iterator find(const Key& val);

const_iterator find(const Key& val) const;

인수로 키를 전달하고 키값을 가진 요소를 찾아 그 반복자를 리턴한다. 발견되지 않으면 end가 리턴된다.

• 예제 mapfind

#include <iostream> #include <string> #include <map> #include <algorithm> using namespace std;     void main() { map<string, int> m; m["서울"] = 1000; m["부산"] = 500; m["대전"] = 400; m["대구"] = 300; m["광주"] = 200; m["인천"] = 100; m["독도"] = 1;     map<string,int>::iterator it; it = m.find("부산"); if ( it == m.end() ) { cout << "없음" << endl; } else { cout << it->first << "의 인구는 " << it->second << "만 명이다" << endl; } }

반복자의 second를 읽으면 도시명과 연관된 인구수를 알 수 있다. 문자열로 된 키를 제공하고 정수값을 검색해 낸 것이다. 그래서 맵을 배열의 일반화라고도 한다. 배열은 키가 정수로 고정되어 있는 맵이며 맵은 임의의 타입을 첨자로 사용하는 배열이라고 할 수 있다.

멀티 맵의 find는 여러 개의 요소 중 어떤 것을 검색할지 알 수 없다. 키에 해당하는 요소가 여러 개 있을 수 있는데 그 중에 하나를 검색할 뿐이다. 여러 개의 키 중 처음이나 마지막에 일치하는 요소를 찾고 싶다면 lower_bound, upper_bound 멤버 함술르 사용해야 한다.

맵을 검색할 때 전역 find 알고리즘은 사용할 수 없다. 위 예제에 맵의 요소 타입은 문자열과 정수의 쌍인 pair 객체이다. pair클래스는 == 연산자를 제공하지 않고, find 알고리즘은 키로부터 동등성 비교를 하는 것이 아니라 요소 전체에 대한 동일성 비교를 하므로 쓸모가 없다.

:: 수정

[ ] 연산자는 키가 없으면 삽입하지만 이미 존재할 경우는 해당 요소의 값에 대한 레퍼런스를 리턴한다. 따라서 존재하는 키에 대해서는 값을 수정하는 용도로 사용할 수 있다. mapfind 예제의 삽입문 다음에 아래의 코드를 추가해 보자.

m["부산"] = 600;

부산을 키로 가지는 요소가 이미 삽입되어 있으므로 [ ]연산자는 부산 요소의 값에 대한 레ㅔ퍼런스를 리턴한다. 이 레퍼런스에 원하는 값을 대입하면 요소의 값이 변경된다. 부산이 존재하지 않는다면 이 문장은 새로운 요소를 삽입하는 명령이 될 것이다. 똑같은 작업을 find멤버 함수와 반복자로도 할 수 있다.

it = m.find("부산");

it->second = 600;

그러나 어떤 방법을 쓰더라도 키는 변경할 수 없다.

it->first = "평양"; // 에러

만약 위 문장이 동작한다면 맵의 무경성이 박살나고 이후부터 이 맵이 어떻게 동작할지 보장할 수 없다. 그렇지만 다행이 맵의 키를 수정하는 코드는 컴파일 에러로 처리된다. 맵의 요소 타입이 pair(const Key, T)로 되어 있어 키는 무조건 수정 불가능하다. 키는 오로지 정렬 기준으로만 사용되므로 일단 삽입되면 절대로 수정할 수 없다. 만약 맵의 키를 꼭 수정하고 싶다면 삭제하고 다시 삽입하는 수밖에 없다.

41.2.2 맵의 활용

맵의 가장 큰 장점은 빠른 검색 속도이다. 이분 검색을 사용하므로 10억개 중에 하나를 찾는다 해도 최악의 경우 30번 정도만 비교하면 검색 가능하다.

• 예제 DnsServer

#include <iostream> #include <string> #include <map> #include <algorithm> using namespace std;     struct { const char *first; unsigned second; } sites[] = { {"www.winapi.co.kr", 0x10203040}, {"www.lpacampus.com", 0x20304050}, {"www.microsoft.com", 0x99999999}, {"www.borland.com", 0xbbbbbbbb}, {"kangcom.com", 0xccaabbdd}, {"www.maxplusone.com", 0x12345678}, };     void main() { map<string, unsigned> dns; int i;     for( i = 0 ; i < 4 ; i++ ) { dns[sites[i].first] = sites[i].second ; }     map<string, unsigned>::iterator it; it = dns.find("www.winapi.co.kr"); if( it == dns.end() ) { cout << "등록되지 않은 사이트" << endl; } else { cout << it->first << "의 주소" << it->second << "입니다" << endl; } }

맵의 또 다른 활용예는 희소 자료를 관리할 때이다. 희소(Sparse) 자료란 대부분의 경우 기본값이고 극히 일부만 특정한 값을 가지는 자료를 의미한다.

수학에는 희소 행렬이라는 것이 있다. 가로 세로로 아주 큰 행렬이되 대부분이 값은 0이며 아주 드물게 한 두 요소만 의미있는 값을 가지는 행렬이다. 이런 행렬도 거대한 이차원 배열로 표현하는 것보다는 맵으로 표현하는 것이 정석이다.

41.3 컨테이너 어댑터

41.3.1 스택

컨테이너 어댑터는 기존 컨테이너의 기능 중 일부만을 공개하여 기능이 제한되거나 변형된 컨테이너를 만든다. 기존 컨테이너의 구현 중 일부는 그대로 사용하되 외부에서 사용하는 인터페이스만 변경하는 것이다.

스택이라는 자료 구조는 선형적인 기억 공간에 자료를 저장하되 반드시 넣은 역순으로 빼기(LIFO)를 할 수 있다. 그래서 기억 공간을 관리하는 능력과 넣기와 빼기 정도의 동작만 제공하면 쉽게 만들 수 있다.

스택의 템플릿 정의는 다음과 같다

template<class T, class Cont = deque<T>>

class stack { ... }

두 개의 인수를 받아들이는데 스택에 들어갈 데이터 타입 T와 스택이 자료 저장을 위해 사용할 컨테이너 Cont이다. 이때 Cont는 스택의 요소 타입과 같은 타입을 저장하는 컨테이너여야 한다. Cont의 디폴트는 데크로 되어 있는데 원한다면 벡터나 리스트로 변경할 수도 있다.

스택이 제공하는 타입은 size_type, value_type, container_type세 가지 밖에 없다. 이중 container_type은 스택이 자료 관리를 위해 사용하는 기본 컨테이너의 타입이며 템플릿 인수 Cont와 같은 타입이다. 생성자는 하나밖에 없다.

explicit stack(const allocator_type& al = allocator_type());

스택의 고유한 동작은 push, pop, top 세가지 뿐이다.

void push(const T& x);

void pop( );

value_type& top( );

const value_type& top( ) const;

push는 스택의 상단에 값을 추가하는데 인수로 추가할 값을 전달하면 된다. 기억 장소가 무한해서 추가는 항상 성공하므로 리턴값은 없다.

pop은 상단의 값을 제거하여 버리는데 이 값은 가장 최근에 추가된 값이다. 빈스택에 대해 pop을 호출하면 컴파일러에서 assert가 호출되도록 되어 있다.

top은 스택의 상단의 값을 읽어 레퍼런스로 리턴한다.

이 외에 스택의 크기를 조사하는 size와 스택이 비어있는지 조사하는 empty 멤버 함수가 제공된다.

• 예제 stack

#include <iostream> #include <stack> using namespace std;     void main() { stack<int> s;     s.push(4); s.push(7); s.push(2);     while( !s.empty() ) { cout << s.top() << endl; s.pop(); } }

• 예제 stlcalc

#include <iostream> #include <math.h> #include <stack> using namespace std;     ...     void MakePostfix(char *post, const char *mid) { stack<char> cS; ... while( !cS.empty() && GetPriority(cS.top()) >= GetPriority(*m)) { *p++=cS.top(); cS.pop(); } ... }

41.3.2 큐

큐는 스택에 비해 먼저 들어간 값이 나오는(FIFO) 자료 구조이다. 자료를 관리하는 기본적인 기능은 시퀀스의 것을 그대로 재사용할 수 있으며 FIFO 원리대로 동작하기 위해 꼭 필요한 인터페이스는 4가지밖에 없다.

push, pop : 앞뒤에서 값을 추가하거나 제거한다.

front, back : 앞 뒤의 값을 읽는다.

4개의 주요 함수와 size, empty그리고 생성자가 큐의 함수 전부이다. 큐의 템플릿 선언은 다음과 같다.

template<class T, class Cont=deque<T>>

class queue{ ... }

• 예제 queue

#include <iostream> #include <queue> using namespace std;     void main() { queue<int> q;     q.push(1); q.push(2); q.push(3);     while( !q.empty() ) { cout << q.front() << endl; q.pop(); } }

41.3.3 우선 순위 큐

우선 순위 큐는 벡터와 유사하되 값을 빼 낼 때 가장 큰 값을 리턴한다는 점이 다르다. 필요한 동작은 push, pop, top 세 가지밖에 없다. 템플릿 선언은 다음과 같다.

template<class T, class Cont = vector<T>, class BinPred = less<Cont::value_type>>

class priority_queue { ... }

T는 우선 순위 큐에 저장될 타입이고 Cont는 기본 컨테이너이되 디폴트는 벡터로 되어 있다. 원할 경우 데크로 변경할 수 있지만 임의 접근이 안되는 리스트는 쓸 수 없다. 생서자는 다음과 같다.

explicit priority_queue(const BinPred& pr = BinPred());

priority_queue(const value_type *first, const value_type *last, const BinPred& pr = BinPred());

• 예제 priority_queue

#include <iostream> #include <queue> using namespace std;     void main() { priority_queue<int> q;     q.push(1); q.push(3); q.push(2);     while( !q.empty() ) { cout << q.top() << endl; q.pop(); } }

1, 3, 2를 넣고 빼냈는데 3, 2, 1이 크기 순으로 차례대로 읽혀진다. 이런 특성을 이용하여 우선 순위가 있는 자료를 다룰 때 편리하다.