맵의 가장 큰 장점은 빠른 검색 속도이다. 키를 삽입할 때마다 정렬된 위치를 찾아서 삽입해야 하므로 검색을 위한 대용량의 맵을 작성하는 데는 사실 꽤 오랜 시간이 걸린다. 그러나 일단 한 번 만들어지고 나면 검색 속도는 한마디로 끝내준다. 이분 검색법을 사용하므로 10억개중에 하나를 찾는다 해도 최악의 경우 30번 정도만 비교하면 되는 정도라 그야 말로 엄청난 속도다.
그것도 최악의 경우가 그렇고 대개의 경우 10번 안팎의 비교만으로 원하는 요소를 신속하게 찾을 수 있다. 그래서 맵은 대용량의 자료를 관리하면서 검색 속도는 빨라야 하고 또 검색을 아주 자주할 때 최적의 컨테이너라고 할 수 있다. 맵을 실용적으로 사용하는 예를 보자. 다음 예제는 DNS 서버를 흉내낸다.
|
예 제 : 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;
}
}
DNS 서버란 인터넷 사이트의 URL과 IP의 쌍을 찾아 주는 서비스를 하는 서버인데 사용자들이 사이트의 실제 주소를 일일이 외울 수 없으므로 기억하기 쉬운 도메인 이름을 사용하도록 하고 DNS 서버가 도메인 이름을 실제 IP 주소로 변경해 준다. 예제에서는 고작 여섯 개의 도메인을 구조체 배열로 등록하고 있는데 실제 서버라면 이 정보를 데이터 베이스에서 읽어와 맵으로 작성하거나 아니면 데이터 베이스 자체가 맵 형태로 되어 있을 것이다.
인터넷에서 통용되는 도메인 주소의 개수는 그야말로 엄청나고 지금 이 순간에도 계속 늘어나고 있는 중이다. 아마 족히 백만개는 더 될텐데 이 정도의 대용량 맵을 작성하려면 꽤 오랜 시간이 걸린다. 그러나 DNS 서버는 한 번 셋팅되면 최소 몇 년, 고장나서 폐기될 때까지 버티므로 이 작업은 딱 한 번만 하면 된다. 도메인 주소 정보는 보통 하루에 한두번씩 갱신되는데 몇 개 첨삭하는 정도야 그리 어려운 일도 아니다.
DNS 서버가 받는 검색 요청은 1초에도 수백건이 훨씬 넘으며 하루종일 죽치고 앉아서 도메인 주소 변환만 하고 있다. 하지만 검색을 위해 컨테이너가 만반의 준비를 하고 있으므로 도메인 하나의 주소를 조사하는데 걸리는 시간은 그야말로 눈깜짝할 사이도 안된다. 컨테이너를 생성하는 속도보다는 검색 속도가 엄청나게 중요하므로 DNS 서버에게는 맵 컨테이너가 제격인 것이다.
이런 자료의 예는 일상 생활에서도 아주 많이 찾아 볼 수 있는데 사전 데이터는 전부 맵으로 작성한다. 영한 사전의 데이터는 영어 단어를 키로 하고 해설 문자열을 값을 하는 맵으로 구성된다. 그래서 영어 단어만 쳐 넣으면 즉각 검색 가능하다. 맵이 주로 이런 용도로 사용되기 때문에 딕셔너리라고도 부른다.
맵의 또 다른 활용예는 희소 자료를 관리할 때이다. 희소(Sparse) 자료란 대부분의 경우 기본값이고 극히 일부만 특정한 값을 가지는 자료를 의미한다. 예를 들어 국민들이 국가에 내는 기부금을 관리한다고 해 보자. 왜 가끔 김밥 팔아서 평생 모은 돈을 좋은 일에 써 달라며 국가에 헌납하는 착한 사람들이 있지 않은가? 이런 분들이 낸 기부금의 목록을 관리할 목적으로 다음과 같은 컨테이너를 작성했다.
vector<int> don(50000000);
don[1248576]=100000;
대한민국 국민은 대략 5천만명이고 누구나 기부금을 낼 가능성이 있으므로 국민 한 명당 하나씩의 기억 장소를 할당하여 5천만 크기의 정수 벡터를 작성했다. 그리고 1248576번 할머니가 10억을 기부했으면 벡터의 이 요소에 10억이라고 써 넣는 것이다. 이렇게 하면 누가 얼마를 냈는지 저장할 수 있고 임의 접근이 가능하므로 검색도 빠르다.
하지만 기억 장소의 낭비가 너무 심하다는 것이 문제다. 나같이 밥만 겨우 먹고 사는 사람은 평생을 살아도 기부금을 낼 확률이 거의 없으며 돈이 많아도 기부금을 내지 않는 사람들도 많다. 아마 대부분의 국민들은 기부금이 0일 것이다. 일부 부자이면서 착한 사람들만 국가에 헌납을 할 뿐이다. 게다가 기억 장소가 너무 거대해 알고리즘을 적용하기도 쉽지 않은데 예를 들어 전 국민의 기부금 총합을 구하려면 어쨌거나 5천만회짜리 루프를 한바퀴 돌릴 수밖에 없다. 이럴 때 맵을 사용하면 아주 기가 막힌다.
map<unsigned, int> don;
don[1248576]=100000;
국민 번호를 키로 하고 기부금을 값으로 하는 빈 맵을 만들고 기부금을 낸 사람에 대해서만 요소를 삽입한다. 기부금을 내지 않는 대부분의 사람은 맵에 들어가지도 않으므로 기억 장소가 절약되며 합산을 하려면 반복자로 기부금을 낸 사람들만 순회하면 그만이다. 누가 기부금을 냈는지 조사해 보고 싶으면 find 멤버 함수로 찾아보고 end가 리턴되면 기부금을 내지 않은 것으로 판단할 수 있다.
수학에는 희소 행렬이라는 것이 있다. 가로 세로로 아주 큰 행렬이되 대부분이 값은 0이며 아주 드물게 한 두 요소만 의미있는 값을 가지는 행렬이다. 이런 행렬도 거대한 이차원 배열로 표현하는 것보다는 맵으로 표현하는 것이 정석이다.