41-2.맵

41-2-가.맵

셋이 키의 집합만을 관리하는데 비해 맵은 키와 값의 쌍을 관리한다. 연관이 있는 두 개의 값을 쌍으로 관리한다는 점에서 진정한 연관 컨테이너라고 할 수 있다. 셋과 마찬가지로 정렬된 상태로 요소를 저장하므로 키값으로 빠르게 검색할 수 있다. 셋에 비해 값을 추가로 가진다는 차이점이 있는데 반대로 표현하면 셋은 값을 가지지 않는 맵이라고도 할 수 있다.

두 컨테이너 모두 키를 정렬 및 검색의 기준으로 사용한다. 그러나 값은 단순히 키와 함께 같이 저장되기만 할 뿐이지 맵의 내부적인 구성이나 관리 방법에는 전혀 영향을 미치지 않는다. 단순 맵은 키의 중복을 허락하지 않으므로 한 키에 대해 하나만 저장할 수 있는데 비해 멀티 맵은 키의 중복을 허용하므로 여러 개의 키를 저장할 수 있다. 맵은 연관있는 데이터의 관계를 표현하는데 주로 사용된다.

예를 들어 주민등록번호와 사람 이름과의 관계를 들 수 있는데 이 둘은 일대일로 대응되므로 하나의 쌍으로 볼 수 있다. 번호를 키로, 이름을 값으로 하여 하나의 짝으로 묶어서 맵에 정렬된 상태로 저장하면 번호로부터 이름을 빠르게 검색할 수 있다. 주민등록번호는 중복되어서는 안되므로 중복을 허락하지 않는 맵으로 이 관계를 표현한다.

만약 번호와 이름의 역할을 바꾸어 이름이 키가 되고 번호가 값이 된다면 이때는 멀티맵을 사용해야 한다. 왜냐하면 사람은 동명이인이 존재할 수 있으므로 이름이 같더라도 삽입 가능해야 하기 때문이다. 이 경우는 이름을 키로 하여 주민등록번호를 빠르게 검색할 수 있되 여러 개의 결과가 나올 수 있다.

맵은 연관이 있는 두 데이터의 쌍을 관리하므로 셋보다는 훨씬 더 실용적이다. STL 컨테이너 중에 벡터 다음으로 자주 사용되는 컨테이너가 맵이며 잘 활용하면 아주 복잡한 작업을 짧은 코드로 빠른 시간안에 끝낼 수 있다.

맵 클래스

맵도 여타의 STL 컨테이너와 마찬가지로 다음과 같은 클래스 템플릿으로 정의되어 있다. 멀티 맵도 이름만 다를 뿐 클래스 정의는 맵과 동일하다.

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

class map { ... }

셋보다 하나의 인수를 더 취하는데 키 외에 데이터에 해당하는 값의 타입을 두 번째 인수로 요구한다. 나머지 비교 함수 객체나 할당기는 셋과 동일하며 디폴트가 무난하게 지정되어 있으므로 생략 가능하다. 비교 함수의 디폴트는 less이므로 맵의 요소들은 키의 값을 기준으로 오름차순으로 정렬되어 저장된다. 키와 값의 타입은 디폴트가 없으므로 반드시 지정해야 한다. 임의의 모든 타입을 조합하여 지정할 수 있는데 정수와 문자열, 문자열과 정수, 정수와 실수 등등이 가능하며 조건만 맞다면 사용자 정의 타입도 지정할 수 있다. 두 타입이 꼭 다를 필요는 없으며 같아도 상관없다.

맵이 정의하는 타입은 셋과 동일하되 key_type과 value_type이 다르게 정의되어 있으며 key_compare와 value_compare도 다른 함수 객체이다. 셋은 키만 있고 키가 값을 겸하는 것으로 취급하므로 value_type이 key_type과 같지만 맵은 이 둘이 각각 따로이므로 다른 타입이다. 맵의 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<iterator, 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));

키는 "문자열"이고 값은 1234인 요소 하나가 맵에 삽입될 것이다. 삽입된 위치를 가리키는 반복자와 성공 여부를 표시하는 bool값이 pair로 묶여서 리턴되며 키가 이미 존재하면 삽입은 거부된다. 단, 멀티 맵은 키의 중복이 가능하므로 insert 함수가 bool을 리턴할 필요없이 반복자만 리턴한다.

두 번째 원형의 insert 함수는 삽입 위치에 대한 힌트를 제공하며 세 번째 insert 함수는 반복자 구간을 삽입한다. 삽입되는 요소가 pair라는 것만 빼고 사용 방법은 셋의 insert 함수와 완전히 동일하다. 맵은 insert 함수외에 좀 더 편리한 삽입 방법을 제공하는데 [ ] 연산자와 대입 연산자로도 요소를 삽입할 수 있다. 맵의 [ ] 연산자는 다음과 같이 정의되어 있다.

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

[ ] 연산자는 인수로 전달된 k를 키로 가지는 pair 객체를 생성하여 맵에 삽입하고 이 pair의 값(pair.second)에 대한 레퍼런스를 리턴한다. 레퍼런스에 값을 곧바로 대입하기만 하면 방금 삽입한 요소의 값을 지정할 수 있다. [ ] 연산자와 대입 연산자를 사용하면 [ ] 연산자안에 키를 지정하고 대입문의 오른쪽에 값을 적으면 쉽게 삽입할 수 있다. 앞에서 보인 insert문은 다음 대입문과 동일하다.

m["문자열"]=1234;

pair 객체를 만들 필요없이 키와 값을 곧바로 지정할 수 있어 훨씬 더 편리하고 보기에도 좋다. 또한 이 연산자는 이미 삽입되어 있는 요소의 값을 수정할 때도 사용할 수 있는데 수정하는 방법은 잠시 후에 따로 연구해 보자. 이 연산자는 맵에 의해 오버로딩되어 있으므로 배열의 첨자 연산자인 [ ]와는 의미가 완전히 다르다. 배열의 요소를 읽는 [ ] 연산자는 피연산자로 정수만 취할 수 있지만 맵의 [ ] 연산자는 키의 타입으로 지정된 타입을 취하므로 정수가 아닌 문자열이나 실수를 피연산자로 받을 수도 있다.

단, [ ] 연산자는 맵에만 정의되어 있으며 멀티 맵에는 정의되어 있지 않다. [ ] 연산자가 값의 수정에도 사용되는데 키가 중복되어 있을 경우 어떤 키에 대한 값을 리턴해야 할 지가 애매하기 때문이다. 키에 해당하는 요소가 여러 개 있다고 해서 복수 개의 값에 대한 레퍼런스를 리턴할 수는 없다. 그래서 멀티 맵에서는 값을 삽입할 때 insert 함수만 사용할 수 있으며 수정할 때도 검색 함수를 사용해야 한다.

요소를 삭제할 때는 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;

}

}

도시명을 키로 사용하므로 키의 타입은 string이며 인구수인 값은 정수형으로 표현되므로 타입은 int이다. 이런 데이터의 쌍을 관리하는 맵의 타입은 map<string, int>가 된다. 이 타입의 맵 m을 디폴트 생성자로 선언하여 빈 맵을 준비했다. 맵은 삽입 방법이 조금 복잡하기 때문에 보통 빈 상태로 생성한다.

생성한 빈 맵에 도시명과 인구수의 짝을 삽입하는데 insert 함수와 [ ] 연산자를 둘 다 사용해 보았다. 서울과 부산은 insert 함수로 삽입했는데 이 함수의 인수로 pair 임시 객체를 생성하여 전달하면 된다. 키는 string 타입이지만 string이 문자열 상수에 대한 변환 생성자를 제공하므로 문자열 상수를 바로 지정할 수도 있다.

나머지 도시들은 [ ] 연산자를 사용했는데 insert보다 훨씬 더 보기 좋고 간편하다. [ ] 괄호안에 도시명을 적고 대입문의 우변에 이 도시의 인구수를 지정하면 이 둘이 pair로 묶여 맵에 삽입된다. 7개의 도시를 삽입했는데 도시명을 키로 하여 오름차순으로 정렬되어 들어갈 것이다.

erase 함수를 테스트하기 위해 일부러 두 개의 도시를 삭제해 보기도 했다. m.begin()으로 맵의 첫 번째 요소를 구해 삭제했는데 서울을 제일 먼저 삽입했지만 정렬되어 들어가므로 begin이 리턴하는 반복자는 가나다순으로 가장 빠른 광주를 가리킬 것이다. 인천은 키값을 직접 지정하여 삭제했다. 7개 삽입하고 두 개를 삭제했으므로 맵에는 다섯 개만 남는다. 반복자로 맵을 순회하면서 키와 값을 출력해 보았다.

대구:300만명

대전:400만명

독도:1만명

부산:500만명

서울:1000만명

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

검색

맵을 검색할 때는 find 멤버 함수를 사용한다. 상수 버전과 비상수 버전이 중복 정의되어 있다.

iterator find(const Key& val);

const_iterator find(const Key& val) const;

인수로는 검색하고자 하는 키를 전달한다. find 멤버 함수는 맵의 정렬 상태를 십분 활용하여 빠른 속도로 키값을 가진 요소를 찾아 그 반복자를 리턴한다. 만약 키가 발견되지 않으면 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;

}

}

도시명과 인구수의 맵에서 부산의 인구수를 검색해 보았다. find 함수의 인수로 "부산" 문자열을 전달하면 이 키를 가진 요소가 맵의 어디쯤에 있는지 이분 검색으로 찾아내어 그 반복자를 리턴한다. 반복자의 second를 읽으면 도시명과 연관된 인구수를 알 수 있다. 문자열로 된 키를 제공하고 정수값을 검색해낸 것이다. 그래서 맵을 배열의 일반화라고도 한다. 배열은 키가 정수로 고정되어 있는 맵이며 맵은 임의의 타입을 첨자로 사용하는 배열이라고 할 수 있다.

맵의 find 멤버 함수는 있으면 어디쯤 있다, 없으면 없다는 확정적인 결과를 리턴하는데 비해 멀티 맵의 find는 여러 개의 요소 중 어떤 것을 검색할지 알 수 없다. 키에 해당하는 요소가 여러 개 있을 수 있는데 그 중의 하나를 검색할 뿐이다. 여러 개의 키 중 처음이나 마지막 일치하는 요소를 찾고 싶다면 lower_bound, upper_bound 멤버 함수를 사용해야 한다. 이런 특성은 셋, 멀티 셋과 같다.

맵을 검색할 때 전역 find 알고리즘은 사용할 수 없다. 위 예제의 검색 코드를 다음과 같이 수정한 후 컴파일하면 컴파일되지 않는다.

it=find(m.begin(),m.end(),"부산");

it=find(m.begin(),m.end(),pair<string,int>("부산",500));

"부산"이라는 문자열은 맵의 요소 타입과 틀리므로 컴파일되지 않는다. 맵의 요소 타입은 문자열과 정수의 쌍인 pair 객체이다. 그렇다고 해서 아래줄처럼 pair 객체를 만들어 검색해도 역시 안된다. 왜냐하면 pair 클래스가 == 연산자를 제공하지 않기 때문이다. 설사 == 연산자를 제공한다 하더라도 find 알고리즘은 키로부터 동등성 비교를 하는 것이 아니라 요소 전체에 대한 동일성 비교를 하므로 쓸모가 없다.

위 두 번째 줄이 문법적으로 가능하다고 해 보자. 이 검색을 하려면 부산의 인구가 500이라는 것을 이미 알고 있어야 한다는 얘기인데 이미 알고 있는 정보를 검색할 필요가 뭐가 있겠는가? 맵은 키로부터 값을 검색하는 컨테이너이므로 키만으로 검색을 수행할 수 있어야 하며 그래서 반드시 find 멤버 함수로 검색을 해야 한다. 이번에는 다음과 같이 검색 코드를 수정해 보자.

cout << "부산의 인구는 " << m["부산"] << "만 명이다." << endl;

컴파일도 잘 되고 결과도 제대로 나온다. 그러나 이 코드는 정확한 검색 코드가 아닐 뿐더러 아주 위험한데 다음과 같이 수정해 보자.

cout << "춘천의 인구는 " << m["춘천"] << "만 명이다." << endl;

[ ] 연산자의 정의에 의해 m["춘천"] 연산식은 맵에 춘천이 있는지 보고 없으면 일단 춘천을 먼저 삽입한다. 이때 키만 삽입할 수는 없으므로 값 타입의 디폴트 생성자로 값까지 만들어서 넣게 되는데 m의 값 타입은 정수이므로 int()의 결과인 0이 값으로 대입될 것이다. 그리고 값에 대한 레퍼런스가 리턴되는데 이 값이 그대로 출력되므로 춘천에 아무도 안산다는 거짓말을 하게 된다.

평가만 해도 삽입이 되어 버려 다소 비상식적인데 이는 [ ] 연산자가 검색용으로 오버로딩되어 있지 않고 편리한 삽입을 위해 오버로딩되어 있기 때문이다. 이 연산자로 검색도 할 수 있다면 좋겠으나 한 연산자로 두 가지 일을 할 수는 없으니 STL 설계자는 삽입을 하는 것으로 선택을 한 것이다. 따라서 이 연산자의 특성을 잘 이해하고 주의하여 사용하는 수밖에 없다.

수정

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

m["부산"]=600;

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

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

it->second=600;

부산을 가리키는 반복자를 구한 후 이 요소의 second, 즉 값에 600을 대입했으므로 부산의 인구가 수정될 것이다. 맵에 저장되는 값은 정렬이나 검색의 기준으로 사용되는 것이 아니라 단순한 정보일 뿐이므로 필요할 경우 얼마든지 수정할 수 있다. 그러나 어떤 방법을 쓰더라도 키는 변경할 수 없다. 예를 들어 it가 부산을 가리킬 때 다음 코드를 실행할 수 있다고 해 보자.

it->first="평양";

부산은 정렬 기준에 의해 독도와 서울 사이에 있는데 평양으로 키가 변경되면 정렬 상태를 유지하기 위해 요소의 순서도 조정되어야 한다. 하지만 반복자는 오로지 위치만 가리킬 뿐이지 컨테이너의 내부 구조까지는 모르기 때문에 이런 조정을 할 권한도 능력도 없다. 부산이 그냥 평양으로 바뀔 뿐이며 맵의 무결성이 박살나고 이후부터 이 맵이 어떻게 동작할 지는 보장할 수 없을 것이다.

그러나 다행히 맵의 키를 수정하는 코드는 컴파일 에러로 처리된다. 맵의 요소 타입이 pair(Key, T)가 아니라 pair(const Key, T)로 되어 있어 키는 무조건 수정 불가능하다. 키는 오로지 정렬 기준으로만 사용되므로 일단 삽입되면 절대로 수정할 수 없다. 반면 셋은 이런 안전 장치가 없는데 왜냐하면 키 자체가 값이라 객체의 다른 멤버를 수정하는 것을 허락해야 하기 때문이다. 만약 맵의 키를 꼭 수정하고 싶다면 삭제했다가 다시 삽입하는 수밖에 없다.