9.1 map 데이터 추상(data abstraction)
Map 대신 사용되는 다른 명칭들
vector나 deque와 마찬가지로 map도 인덱싱이 가능하다. 그러나, map은 두가지점에서 이들과 차이가 난다. 첫째로, map에서는 인덱스 값(키값)이 반드시 정수일 필요는 없고, ordered 데이터 타입이면 가능하다. 예를 들어, 실수나 string으로 인덱싱이 가능하다. 비교연산자를 가지고 있는 데이터 타입이면 키로서 사용이 가능하다. vector나 deque에서처럼, 첨자 연산자로 원소들을 접근할 수 있고, 물론 다른 방법도 있다. 두번째 차이점은 map은 ordered 데이터 구조란 점이다. 이는 원소들이 키값에 따라 순서가 정해져서 관리된다는 말이다. 값들을 순서를 매겨 관리하기 때문에, 주어진 키에 해당하는 원소를 아주 빨리 찾아낼 수 있다(검색 시간은 log 시간). list와 마찬가지로, map도 사이즈에 제한이 없지만, 새 원소들이 추가되거나 삭제될 때, 확장하거나 축소한다. 대부분의 경우, map은 pair를 관리하는 set으로 봐도 무방하다.
표준 라이브러리가 제공하는 map에는 두가지 종류가 있다. map은 키가 반드시 유일해야 한다. 즉, 키와 그에 대응되는 값이 서로 일대일대응이 되어야 한다는 것이다. map에서는 이미 존재하는 키값을 가지는 원소를 삽입할 때 이는 무시된다. 한편으로 multimap은 같은 키로 인덱싱되는 여러개의 서로 다른 원소들을 허용한다. 이 두가지는 모두 삽입, 삭제, 접근 연산이 상대적으로 빠르다.(log 시간)
Pairs
Pairs
9.1.1 Include 화일
map이나 multimap을 사용할 때는 map 헤더화일을 포함해야 한다.
#include <map>
9.2 map과 multimap 연산
map과 multimap 데이터 타입이 제공하는 멤버 함수에 관해 자세히 살펴본다. 멤버 함수들이 기초적인 연산들을 제공하는 반면에, 13절과 14절에 설명하고 있는 generic 알고리듬을 사용함으로써 데이터 구조를 보다 유용하게 사용할 수 있게 된다.
9.2.1 map의 선언과 초기화
map의 선언은 표준 라이브러리에서 자주 보아왔던 방식을 따른다. map은 템플릿 데이터 구조이며, 템플릿의 인자로 키의 타입, 키에 대응되는 값의 타입, 키를 비교하는데 사용될 비교 연산자를 지정해야 한다. 만약에 컴파일러가 디폴트 템플릿 인자(아직은 많은 회사에서 지원하지 않는 C++의 새특징)를 지원하면, 방금 언급한 템플릿 인자 중 세번째 것은 생략이 가능하고, 생략되는 경우에는 키의 타입에 정의되어 있는 less-than 연산자로 지정된다. map은 초기값없이 선언될 수 있고, 한쌍의 반복자를 사용하여 다른 컨테이너에 담긴 값들로 초기화 될 수도 있다. 후자의 경우에, 반복자는 pair 타입의 값을 가리키고 있어야 하며, 이때 첫번째 필드는 키(key)로 간주되고, 두번째 필드는 값(value)으로 간주되는 것이다. 복사 생성자를 사용하여 다른 map의 복사본을 만들어 낸다.
// map indexed by doubles containing strings map<double, string, less<double> > map_one; // map indexed by integers, containing integers map<int, int> map_two(aContainer.begin(), aContainer.end()); // create a new map, initializing it from map two map<int, int> map_three(map_two); // copy constructor
map을 다른 map에 대입할 수 있으며, swap() 연산을 사용하여 두 map간에 값을 서로 교환할 수 있다.
9.2.2 타입 정의
map과 multimap은 많은 타입 정의들을 포함하고 있으며, 이들은 주로 선언문에서 많이 사용된다. 예를 들어, string을 정수로 매핑하는 map에 사용되는 반복자는 다음과 같이 선언된다.
map<string, int>::iterator location;
'iterator' 뿐만 아니라, 다음과 같은 타입들이 정의되어 있다.
| key_type | map을 인덱싱할 때 사용하는 키의 타입 |
| value_type | 맵이 담고 있는 데이터 즉 key/value pair 타입 |
| const_iterator | 자신이 가리키는 원소를 변경할 수 없는 상수 반복자 |
| reverse_iterator | 역방향으로 이동하는 역반복자 |
| const_reverse_iterator | 상수 반복자와 역 반복자의 성질을 모두 가지는 반복자 |
| reference | A reference to an underlying value. |
| const_reference | A reference to an underlying value that will not permit the element to be modified. |
| size_type | An unsigned integer type, used to refer to the size of containers. |
| key_compare | A function object that can be used to compare two keys. |
| value_compare | A function object that can be used to compare two elements. |
| difference_type | A signed integer type, used to describe the distances between iterators. |
| allocator_type | An allocator used by the container for all storage management. |
9.2.3 삽입과 접근
insert() 연산을 사용하여 map이나 multimap에 값들을 삽입한다. 이때 인자는 반드시 키와 값의 pair이어야 한다. 이때 사용되는 pair는 map에 정의되어 있는 value_type이라는 데이터 타입을 사용하여 만든다.
map_three.insert(map<int>::value_type(5, 7));
한쌍의 반복자를 사용하여 삽입을 수행할 수도 있는데, 다음과 같이 다른 컨테이너로부터 값을 가져올 수 있다.
map_two.insert(map_three.begin(), map_three.end());
map(multimap은 제외)에서는 첨자 연산을 통해 값을 접근하거나 삽입할 수 있다. 단순히 키를 첨자로 사용하면 해당 값을 접근할 수 있고, 첨자 연산의 결과에 대입을 함으로써 키에 대응되는 값을 변화시킬 수 있다.
cout << "Index value 7 is " << map_three[7] << endl; // now change the associated value map_three[7] = 5; cout << "Index value 7 is " << map_three[7] << endl;
9.2.4 삭제
키값을 가지고 map과 multimap으로부터 값들을 삭제할 수 있다. multimap에서는 키와 연관된 모든 원소를 삭제한다. 삭제될 원소를 반복자로 지정할 수도 있다. 예를 들면, find() 연산의 결과로 얻은 반복자를 사용할 수도 있다. 한쌍의 반복자를 사용하여 지정한 range내의 원소들을 모두 지우는 것도 가능하다.
// erase the 4th element 4 map_three.erase(4); // erase the 5th element mtesttype::iterator five = map_three.find(5); map_three.erase(five); // erase all values between the 7th and 11th elements mtesttype::iterator seven = map_three.find(7); mtesttype::iterator eleven = map_three.find(11); map_three.erase(seven, eleven);
원소타입이 소멸자를 정의하고 있다면, 콜렉션으로부터 키와 값을 제거하기 전에 이 소멸자가 호출될 것이다.
9.2.5 반복자
begin()과 end() 멤버 함수는 map과 multimap의 경우 양방향 반복자를 생성한다. 이렇듯, map과 multimap에서 사용되는 반복자들은 양방향 반복자이므로 대소 비교(<, >, <=, >=)가 허용되지 않는다는 점에 유의하자(2.2절의 표를 참고). map이나 multimap에 사용되는 반복자를 참조하면 키(key)와 값(value)의 pair를 얻게 된다. 따라서, 필드명으로 first를 사용하면 키를, second를 사용하면 값(value)을 얻을 수 있다. 첫번째 필드는 상수라서 변경할 수 없지만, 두번째 필드는 주어진 키(key)와 연결된 값(value)을 변화시키는데 사용된다. 원소들은 키 필드의 순서에 따라 접근된다(?).
rbegin()과 rend() 멤버 함수는 역방향으로 원소들을 생성하는 반복자들을 반환한다.
9.2.6 검색과 카운팅
size() 멤버 함수는 컨테이너가 가지고 있는 원소의 갯수를 리턴한다. empty() 멤버 함수는 컨테이너가 비었을 때, true를 리턴하고, size()를 zero와 비교하는 것보다 대체로 빠르다.
find() 멤버함수는 키를 인자로 취해서, 키/값 pair를 가리키는 반복자를 리턴한다. multimap의 경우에는, 가장 먼저 일치하는 값을 리턴한다. 두경우 모두, 원하는 값을 찾지 못할 때는, past-the-end 반복자를 리턴한다.
if (map_one.find(4) != map_one.end()) cout << "contains a 4th element" << endl;
lower_bound() 멤버 함수는 인자로 주어진 키와 일치하는 첫번째 원소를 리턴하고, upper_bound() 멤버 함수는 인자로 주어진 키와 일치하는 마지막 원소 바로 직후의 원소를 리턴한다. 마지막으로, equal_range() 함수는 lower bound와 upper bound를 담고 있는 반복자의 pair를 리턴한다. 이들 연산을 사용하는 예는 이 절의 마지막에 주어진다.
count() 멤버 함수는 인자로 주어진 키값과 일치하는 원소의 갯수를 리턴한다. map의 경우에는 결과값이 항상 0 또는 1인 반면에, multimap의 경우에는 음수가 아닌 값이면 결과값이 될 수 있다. 단순히 콜렉션이 주어진 키로 인덱싱되는 원소를 포함하는지의 여부만을 확인하고 싶을 때는 find()의 결과값을 end-of-sequence 반복자와 비교하는 것보다는 count()를 사용하는 것이 쉬울 때가 더 많다.
if (map_one.count(4)) cout << "contains a 4th element" << endl;
9.2.7 원소 비교
인자가 필요없는 key_comp()와 value_comp() 멤버함수는 각각 key 타입 또는 value 타입의 원소를 비교할 때 사용되는 함수 객체를 반환한다. 비교할때 사용되는 값들이 콜렉션이 포함되어 있을 필요는 없으며, 이 함수들은 컨테이너에 아무런 영향을 미치지 않는다.
if (map_two.key_comp (i, j)) // map_two.key_comp()(i, j) ? cout << "element i is less than j" << endl;
9.2.8 기타 map 연산
map과 multimap은 ordered 콜렉션이고, map에 대한 반복자는 pair를 반환하기 때문에, 13절과 14절에서 설명하는 함수들이 사용하기에 무의하거나 곤란한 것들이 많다. 그러나, for_each(), adjacent_find(), accumulate()들 각각은 나름대로 쓸모가 있다. 하지만, 인자로 제공되는 함수들은 키/값 pair를 인자로 취하는 것이라야 한다는 것을 반드시 기억해야 한다.
9.3 예제 프로그램
We present three example programs that illustrate the use of maps and multimaps. These are a telephone database, graphs, and a concordance.
9.3.1 전화 데이터베이스
A maintenance program for a simple telephone database is a good application for a map. The database is simply an indexed structure, where the name of the person or business (a string) is the key value, and the telephone number (a long) is the associated entry. We might write such a class as follows:
typedef map<string, long, less<string> > friendMap;
typedef friendMap::value_type entry_type;
class telephoneDirectory {
public:
void addEntry (string name, long number) // add new entry to
// database
{ database[name] = number; }
void remove (string name) // remove entry from database
{ database.erase(name); }
void update (string name, long number) // update entry
{ remove(name); addEntry(name, number); }
void displayDatabase() // display entire database
{ for_each(database.begin(), database.end(), printEntry); }
void displayPrefix(int); // display entries that match prefix
void displayByPrefix(); // display database sorted by prefix
private:
friendMap database;
};
Simple operations on our database are directly implemented by map commands. Adding an element to the database is simply an insert, removing an element is an erase, and updating is a combination of the two. To print all the entries in the database we can use the for_each() algorithm, and apply the following simple utility routine to each entry:
void printEntry(const entry_type & entry)
{ cout << entry.first << ":" << entry.second << endl; }
We will use a pair of slightly more complex operations to illustrate how a few of the algorithms described in Section 13 can be used with maps. Suppose we wanted to display all the phone numbers with a certain three digit initial prefix[1] . We will use the find_if() function (which is different from the find() member function in class map) to locate the first entry. Starting from this location, subsequent calls on find_if() will uncover each successive entry.
void telephoneDirectory::displayPrefix(int prefix)
{
cout << "Listing for prefix " << prefix << endl;
friendMap::iterator where;
where =
find_if (database.begin(), database.end(),
checkPrefix(prefix));
while (where != database.end()) {
printEntry(*where);
where = find_if (++where, database.end(),
checkPrefix(prefix));
}
cout << "end of prefix listing" << endl;
}
For the predicate to this operation, we require a boolean function that takes only a single argument (the pair representing a database entry), and tells us whether or not it is in the given prefix. There is no obvious candidate function, and in any case the test prefix is not being passed as an argument to the comparison function. The solution to this problem is to employ a technique that is commonly used with the standard library, defining the predicate function as an instance of a class, and storing the test predicate as an instance variable in the class, initialized when the class is constructed. The desired function is then defined as the function call operator for the class:
int prefix(const entry_type & entry)
{ return entry.second / 10000; }
class checkPrefix {
public:
checkPrefix (int p) : testPrefix(p) { }
int testPrefix;
bool operator () (const entry_type & entry)
{ return prefix(entry) == testPrefix; }
};
Our final example will be to display the directory sorted by prefix. It is not possible to alter the order of the maps themselves. So instead, we create a new map with the element types reversed, then copy the values into the new map, which will order the values by prefix. Once the new map is created, it is then printed.
typedef map<long, string, less<long> > sortedMap;
typedef sortedMap::value_type sorted_entry_type;
void telephoneDirectory::displayByPrefix()
{
cout << "Display by prefix" << endl;
sortedMap sortedData;
friendMap::iterator itr;
for (itr = database.begin(); itr != database.end(); itr++)
sortedData.insert(sortedMap::value_type((*itr).second,
(*itr).first));
for_each(sortedData.begin(), sortedData.end(),
printSortedEntry);
}
The function used to print the sorted entries is the following:
void printSortedEntry (const sorted_entry_type & entry)
{ cout << entry.first << ":" << entry.second << endl; }
9.3.2 그래프
A map whose elements are themselves maps are a natural representation for a directed graph. For example, suppose we use strings to encode the names of cities, and we wish to construct a map where the value associated with an edge is the distance between two connected cities. We could create such a graph as follows:
typedef map<string, int> stringVector;
typedef map<string, stringVector> graph;
const string pendleton("Pendleton"); // define strings for
// city names
const string pensacola("Pensacola");
const string peoria("Peoria");
const string phoenix("Phoenix");
const string pierre("Pierre");
const string pittsburgh("Pittsburgh");
const string princeton("Princeton");
const string pueblo("Pueblo");
graph cityMap; // declare the graph that holds the map
cityMap[pendleton][phoenix] = 4; // add edges to the graph
cityMap[pendleton][pueblo] = 8;
cityMap[pensacola][phoenix] = 5;
cityMap[peoria][pittsburgh] = 5;
cityMap[peoria][pueblo] = 3;
cityMap[phoenix][peoria] = 4;
cityMap[phoenix][pittsburgh] = 10;
cityMap[phoenix][pueblo] = 3;
cityMap[pierre][pendleton] = 2;
cityMap[pittsburgh][pensacola] = 4;
cityMap[princeton][pittsburgh] = 2;
cityMap[pueblo][pierre] = 3;
The type stringVector is a map of integers indexed by strings. The type graph is, in effect, a two-dimensional sparse array, indexed by strings and holding integer values. A sequence of assignment statements initializes the graph.
A number of classic algorithms can be used to manipulate graphs represented in this form. One example is Dijkstra's shortest-path algorithm. Dijkstra's algorithm begins from a specific city given as an initial location. A priority_queue of distance/city pairs is then constructed, and initialized with the distance from the starting city to itself (namely, zero). The definition for the distance pair data type is as follows:
struct DistancePair {
unsigned int first;
string second;
DistancePair() : first(0) { }
DistancePair(unsigned int f, const string & s)
: first(f), second(s) { }
};
bool operator < (const DistancePair & lhs, const DistancePair & rhs)
{ return lhs.first < rhs.first; }
In the algorithm that follows, note how the conditional test is reversed on the priority queue, because at each step we wish to pull the smallest, and not the largest, value from the collection. On each iteration around the loop we pull a city from the queue. If we have not yet found a shorter path to the city, the current distance is recorded, and by examining the graph we can compute the distance from this city to each of its adjacent cities. This process continues until the priority queue becomes exhausted.
void shortestDistance(graph & cityMap,
const string & start, stringVector & distances)
{
// process a priority queue of distances to cities
priority_queue<DistancePair, vector<DistancePair>,
greater<DistancePair> > que;
que.push(DistancePair(0, start));
while (! que.empty()) {
// pull nearest city from queue
int distance = que.top().first;
string city = que.top().second;
que.pop();
// if we haven't seen it already, process it
if (0 == distances.count(city)) {
// then add it to shortest distance map
distances[city] = distance;
// and put values into queue
const stringVector & cities = cityMap[city];
stringVector::const_iterator start = cities.begin();
stringVector::const_iterator stop = cities.end();
for (; start != stop; ++start)
que.push(DistancePair(distance + (*start).second,
(*start).first));
}
}
}
Notice that this relatively simple algorithm makes use of vectors, maps, strings and priority_queues. priority_queues are described in greater detail in Section 11.
9.3.3 A Concordance
A concordance is an alphabetical listing of words in a text, that shows the line numbers on which each word occurs. We develop a concordance to illustrate the use of the map and multimap container classes. The data values will be maintained in the concordance by a multimap, indexed by strings (the words) and will hold integers (the line numbers). A multimap is employed because the same word will often appear on multiple different lines; indeed, discovering such connections is one of the primary purposes of a concordance. Another possibility would have been to use a map and use a set of integer elements as the associated values.
class concordance {
typedef multimap<string, int less <string> > wordDictType;
public:
void addWord (string, int);
void readText (istream &);
void printConcordance (ostream &);
private:
wordDictType wordMap;
};
The creation of the concordance is divided into two steps: first the program generates the concordance (by reading lines from an input stream), and then the program prints the result on the output stream. This is reflected in the two member functions readText() and printConcordance(). The first of these, readText(), is written as follows:
void concordance::readText (istream & in)
{
string line;
for (int i = 1; getline(in, line, 'n'); i++) {
allLower(line);
list<string> words;
split (line, " ,.;:", words);
list<string>::iterator wptr;
for (wptr = words.begin(); wptr != words.end(); ++wptr)
addWord(*wptr, i);
}
}
Lines are read from the input stream one by one. The text of the line is first converted into lower case, then the line is split into words, using the function split() described in Section 12.3. Each word is then entered into the concordance. The method used to enter a value into the concordance is as follows:
void concordance::addWord (string word, int line)
{
// see if word occurs in list
// first get range of entries with same key
wordDictType::iterator low = wordMap.lower_bound(word);
wordDictType::iterator high = wordMap.upper_bound(word);
// loop over entries, see if any match current line
for ( ; low != high; ++low)
if ((*low).second == line)
return;
// didn't occur, add now
wordMap.insert(wordDictType::value_type(word, line));
}
The major portion of addWord() is concerned with ensuring values are not duplicated in the word map if the same word occurs twice on the same line. To assure this, the range of values matching the key is examined, each value is tested, and if any match the line number then no insertion is performed. It is only if the loop terminates without discovering the line number that the new word/line number pair is inserted.
The final step is to print the concordance. This is performed in the following fashion:
void concordance::printConcordance (ostream & out)
{
string lastword("");
wordDictType::iterator pairPtr;
wordDictType::iterator stop = wordMap.end();
for (pairPtr = wordMap.begin(); pairPtr != stop; ++pairPtr)
// if word is same as previous, just print line number
if (lastword == (*pairPtr).first)
out << " " << (*pairPtr).second;
else { // first entry of word
lastword = (*pairPtr).first;
cout << endl << lastword << ": " << (*pairPtr).second;
}
cout << endl; // terminate last line
}
An iterator loop is used to cycle over the elements being maintained by the word list. Each new word generates a new line of output - thereafter line numbers appear separated by spaces. If, for example, the input was the text:
- It was the best of times,
it was the worst of times.
The output, from best to worst, would be:
- best: 1
it: 1 2
of: 1 2
the: 1 2
times: 1 2
was: 1 2
worst: 1