연관 컨테이너 사용하기 using associative containers Chapter 7 연관 컨테이너 사용하기 using associative containers

7 장에서는… 지금까지 7장에서는 순차컨테이너 (sequential container): vector, list 순차컨테이너의 요소들은 우리가 선택한 순서대로 유지된다 7장에서는 순차컨테이너를 이용하는 경우 비효율적인 경우가 있다. 예: 컨테이너 요소에 정수 42가 포함되어있는지 확인하는 문제 방법 1) 컨테이너의 시작부터 끝까지 검사 방법 2) 적당한 순서대로 저장하여 원하는 요소를 효과적으로 찾을 수 있는 알고리즘 이용 효과적인 참조방법을 제공하는 연관 컨테이너: map

연관 컨테이너(Associative Containers) 연관 컨테이너의 요소들은 삽입한 순서대로 배열하지 않고, 요소의 값에 따라 삽입 순서를 자동적으로 조정한다. 따라서, 특정 요소들을 더 빨리 검색할 수 있다. Maps: 빠른 검색을 위한 연관 컨테이너 연관 자료구조에는 키-값 쌍(key-value pair)으로 저장 연관 배열(associative array) 값과 키를 연결시켜서, 키(key) 에 의해 빠르게 삽입, 탐색 효과적인 검색을 위해 사용하는 컨테이너의 요소

map map 을 정의하는 형식: map<key_type, value_type> var_name; pair 타입: map의 각 요소은 pair 타입 pair 타입: first와 second를 멤버로 갖는 구조체(struct) 타입 pair 클래스는 여러 타입의 값을 담을 수 있다. 따라서, first와 second 의 데이터 멤버를 명시해야 한다. pair<const key_type, value_type> 키는 항상 const이기 때문에 해당하는 값은 바꿀 수 없다. #include <map> <key> <value> first second pair Austria 43 Korea 82 U.S.A 1

순차 컨테이너와 연관 컨테이너 map과 vector의 기본적인 차이점: 인덱스 연관 컨테이너의 중요한 특징은 vector: 인덱스가 정수이다. v[0], v[1], v[2], … map: 다른 것들과 순서를 비교할 수 있는 것이라면 어떤 타입도 가능하다. string 일 수 있다. 연관 컨테이너의 중요한 특징은 자체 순서 (self-ordering)를 유지시킨다. 입력 순서와 상관없이 키 값의 순서에 따라 저장된다. 따라서, 순서를 변경하는 작업은 할 수 없다.

예 각국의 국제전화 코드번호 <key> <value> 저장할 정보의 키와 값 쌍: <국가이름, 국가코드번호> map<string, int> m; m[“Canada”] = 1; m[“Austria”] = 43; pair<const string, int> e1(“Czech”, 42); m.insert(e1); cout << e1.first << “ ” << e1.second << endl; … <key> <value> first second Austria 43 Canada 1 Czech 42 Egypt 20 Japan 81 Korea 82 Spain 34 U.S.A

Map 반복자 Map iterator: 순차적으로(sequentially) Map에 저장된 내용을 접근하도록 이용 가능 begin() end() map 반복자는 pair를 가리킨다: Map에 저장된 pair의 key 부분과 value 부분을 참조 it->first it->second 삽입된 순서와 상관없이 키 값에 따라 순서를 유지하고 있어서 정렬되어 출력된다. for(map<string, int>:: const_iterator it = m.begin(); it != m.end(); ++it) cout << it-> first << “ ” << it->second << endl;

Map 멤버함수 insert() : 요소 삽입 find() : 키를 이용한 검색 erase() : 요소 삭제 begin() end() size() clear() … 참조사이트: http://msdn.microsoft.com/ko-kr/library/xdayte4c(v=VS.90).aspx

연관컨테이너에 삽입 방법 연산자 []를 이용하는 방법 insert() 멤버함수를 이용하는 방법 map <int, int> m1; 연산자 []를 이용하는 방법 m1[1] = 10; m1[5]; // 디폴트 값 0으로 초기화 됨; m1[5]=0; m1[1] = 11; // 이미 있는 요소일 때: m[1]의 값을 변경함 insert() 멤버함수를 이용하는 방법 pair 타입을 이용 1) pair<const int, int> e1(4, 40); m1.insert(e1); 2) m1.insert(pair<const int, int> (8, 80) );

출력결과: 1: 10 2: 20 3: 30 1: 10 2: 40 3: 30 5: 0 int main( ) { #include <map> … int main( ) { map <int, int> m1; map <int, int> :: iterator pIter; // Insert a data value of 10 with a key of 1 into a map // using the operator[] member function m1[ 1 ] = 10; // Compare other ways to insert objects into a map m1.insert ( pair <const int, int> ( 3, 30 ) ); m1.insert ( pair <const int, int> ( 2, 20 ) ); for ( pIter = m1.begin( ) ; pIter != m1.end( ) ; pIter++ ) cout << pIter -> first << ": " << pIter -> second << endl; // If the key already exists, operator[] // changes the value of the datum in the element m1[ 2 ] = 40; // operator[] will also insert the value of the data // type's default constructor if the value is unspecified m1[5]; // m1[5]=0; cout << pIter -> first <<“: " << pIter -> second << endl; } 출력결과: 1: 10 2: 20 3: 30 1: 10 2: 40 3: 30 5: 0

operator[]와 insert() 함수 비교 삽입 후 이미 존재하는 요소(element)가 변경되었는지, 새로운 요소를 삽입했는지를 알 수 없다. insert() 멤버함수를 이용해서 삽입을 시도한 경우, 삽입하기 전에, key가 이미 존재하는를 알려준다. return_type은 map 반복자와 bool로 된 pair 타입이다. pair< map<int,int>::iterator, bool > pr; 이미 존재할 때: map에서 해당요소의 pair를 참조하는 반복자와 false를 리턴한다. 존재하지 않을 때: map에 pair를 새로 추가하고, 추가된 pair를 참조하는 반복자와 true를 리턴한다. pr = m1.insert( make_pair(1, 11) ); if( pr.second == true ) // 존재하지 않을 때 … else

insert() 함수 사용 예 #include <map> #include <iostream> using namespace std; int main( ) { map <int, int> m; m.insert ( make_pair ( 1, 100 ) ); pair< map<int,int>::iterator, bool > pr; pr = m.insert ( make_pair ( 1, 10 ) ); if( pr.second == true ) { cout << "The element was inserted in m successfully." << endl; } else { cout << "Key number already exists in m\n" << "with an associated value = " << ( pr.first ) -> second // 저장된 값 << "." << endl;

operator [] m[Key] = DataValue ; m[s]; cout << m[1]; // 10 출력 cout << m[5]; // 0 출력 m[Key] = DataValue ; 연관컨테이너에서 Key를 탐색한다. 있으면, DataValue로 Key와 연관된 값을 변경한다. 없으면, Key와 DataValue 로 된 새로운 pair를 삽입한다. m[s]; key에 s 를 포함한 pair 를 연관컨테이너에서 탐색한다. 컨테이너에 있으면, pair에 있는 s와 연관된 값에 대한 참조(reference)를 리턴한다. 연관 컨테이너에 없으면, 1) key를 s로 하고, s와 연관된 값을 디폴트 초기값(int, double 은 0으로 초기화)으로 하는 pair를 생성한다. 2) 컨테이너의 적절한 위치에 pair를 삽입한다. 3) 저장된 새로운 pair의 값에 대한 참조를 리턴한다.

find() 멤버 함수 find 함수: Map에 Key 값이 존재하는지를 탐색한다 m.find( key ); 탐색할 Key가 map에 저장되어 있으면, 해당 pair를 참조하는 반복자를 리턴한다. 없으면, m.end()를 리턴한다. map <int, int> m; map <int, int> :: const_iterator m_iter; m.insert ( make_pair ( 1, 10 ) ); m.insert ( make_pair ( 2, 20 ) ); m.insert ( make_pair ( 3, 30 ) ); m_iter = m.find( 2 ); if ( m_iter != m.end( ) ) cout << "The element of map m with a key of 2 is: " << m_iter -> second << endl; // If no match is found for the key, end( ) is returned m_iter = m.find( 4 ); if ( m_iter == m.end( ) ) // NOT FOUND cout << "The map m doesn't have an element with a key of 4." << endl; else // FOUND cout << "The element of map m with a key of 4 is: " << m_iter -> second << endl; 출력 결과: The element of map m with a key of 2 is: 20 The map m doesn't have an element with a key of 4.

erase() 멤버함수 erase()함수: Map에서 요소를 삭제하는 함수 void erase(iterator); // iterator가 참조하는 요소를 삭제 void erase(iterator first, iterator last); // first부터 last 앞까지 삭제 size_type erase(Key); // 해당 Key값의 요소를 삭제; 삭제된 개수를 리턴 map<int, int> m; map<int, int>::iterator pIter, Iter1, Iter2; int i; map<int, int>::size_type n; for (i = 1; i < 10; i++) m.insert(make_pair(i, i)); Iter1 = ++m.begin(); m.erase(Iter1); n = m.erase ( 3 ); for (pIter = m.begin(); pIter != m.end(); pIter++) cout << " " << pIter->second; cout << endl; 출력 결과: 1 4 5 6 7 8 9 Iter1 = ++m.begin(); Iter2 = --m.end(); m.erase(Iter1, Iter2); for (pIter = m.begin(); pIter != m.end(); pIter++) cout << " " << pIter->second; cout << endl; 1 9

7.2 단어개수 세기 입력에 각 단어가 몇 번씩 나오는지를 세는 프로그램 벡터를 이용했을 때.. 꽤 복잡하네. struct word_frequency { string word; int freq; }; vector<word_frequency> words; int main() { string s; while(cin>>s) { s가 vector 속에 있는지 찾아보고, 있다면 그것에 해당하는 freq를 하나 증가시키고 없다면 새로 요소를 추가하고 … } 결과를 출력한다.

단어개수 세기 – map 이용 map을 사용하면… 신기할 정도로 간단하네 #include <iostream> #include <map> #include <string> using namespace std; int main() { string s; map<string, int> counters; // store each word and an associated counter // read the input, keeping track of each word and how often we see it while (cin >> s) ++counters[s]; // write the words and associated counts for (map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it) { cout << it->first << "\t" << it->second << endl; } return 0;

단어 개수 세기: 분석 map<string, int> counters; ++counters[s]; 단어 개수 세기: 분석 map<string, int> counters; counters 를 map으로 정의. “string에서 int로의 map” 키: string 타입, 연관된 값: int 타입 ++counters[s]; 키로 읽어들인 단어 s를 counters에서 찾는다 counters[s]는 s에 저장된 string에 연관된 정수를 리턴한다. ++ 를 사용하여, 저장된 정수 값을 증가시킨다. 값지정-초기화 (value-initialzed) int와 같은 단순한 타입의 경우에는 0으로 초기화 된다. 처음 나타난 단어는 0으로 초기화 된 상태에서, 증가시키므로, 1 cout << it->first << "\t" << it->second << endl; it->first : 현재 요소의 키 it->second : 키와 연관된 값

7.3 교차-참조 테이블 생성 string에서 vector<int>로의 map 을 이용: 단어가 입력의 어느 라인에서 나타나는지를 저장하는 교차-참조 테이블 (cross-reference table)을 생성하는 프로그램 한번에 한 라인을 읽어 들여서, 라인번호와 연관 짓는다. 단어 대신 라인을 읽으므로, 단어별로 분리하는 작업이 필요 5.6절의 split() 함수 이용 교차-참조함수 xref()에 대한 매개변수로 split함수를 이용 라인 상에서 단어 찾는 방식을 다른 함수로 바꿀 수 있도록. string에서 vector<int>로의 map 을 이용: 키: 개별 단어 연관된 값: 단어가 나타난 라인 번호들을 저장 map<string, vector<int> > ret;

// find all the lines that refer to each word in the input map<string, vector<int> > xref(istream& in, vector<string> find_words(const string&) = split) { string line; int line_number = 0; map<string, vector<int> > ret; // read the next line while (getline(in, line)) { ++line_number; // break the input line into words vector<string> words = find_words(line); // remember that each word occurs on the current line for (vector<string>::const_iterator it = words.begin(); it != words.end(); ++it) ret[*it].push_back(line_number); } return ret; 입력 예: aaa bbb ccc ddd aaa ccc eee aaa 저장 예: aaa 1 2 3 bbb 1 ccc 1 2 ddd 2 eee 3

xref() 함수 분석 map<string, vector<int> > ret; 리턴 타입과 지역변수 선언에서 > > 를 사용. (>> 아님) 컴파일러가 이해하기 위해 공백(space)가 필요하다. >>연산자와 구분할 수 있도록 !! xref(istream& in, vector<string> find_words(const string&) = split) 인자 목록에서 find_word() 함수를 매개변수로 정의하고 있다. 기본인자(default argument)를 지정: = split 호출하는 곳에서 매개변수를 생략하면, 기본인자를 이용 매개변수를 명시한다면, 그 인자를 사용 xref(cin); // 입력스트림에서 단어들을 찾기 위해 split함수를 이용 xref(cin, find_urls); // ” find_urls함수를 이용

xref() 함수 분석 find_words() 함수 split 함수일 수 도 있고, string 인자를 받고 vector<string>을 리턴하는 다른 함수도 가능하다. split함수: line을 각 단어별로 쪼개는 함수 (책 p152 이용) ret[*it].push_back(line_number); words의 각 요소를 순차적으로 순회하면서, 단어에 해당하는 라인번호를 벡터에 추가. it: 벡터 words의 한 요소. *it: 단어 for (vector<string>::const_iterator it = words.begin(); it != words.end(); ++it) ret[*it].push_back(line_number); // string s=*it; // ret[s].push_bak(line_number); 이 처음 나오는 단어라면, vector<int>는 값지정 초기화 된다. 즉, 빈 벡터가 생성된다.

main() 함수: 간단한 출력형식으로 입력 예: aaa bbb ccc ddd aaa ccc eee aaa 저장 예: int main() { // call `xref' using `split' by default map<string, vector<int> > ret = xref(cin); // write the results for (map<string, vector<int> >::const_iterator it = ret.begin(); it != ret.end(); ++it) { // write the word cout << it->first << “: "; // followed by one or more line numbers for(vector<int>::const_iterator line_it = it->second.begin(); line_it != it->second.end(); ++line_it) { cout << *line_it << “ ”; // write a new line to separate each word from the next cout << endl; } return 0; 저장 예: aaa 1 2 3 bbb 1 ccc 1 2 ddd 2 eee 3 출력 예: aaa: 1 2 3 bbb: 1 ccc: 1 2 ddd: 2 eee: 3

main() 함수: int main() { // call `xref' using `split' by default map<string, vector<int> > ret = xref(cin); // write the results for (map<string, vector<int> >::const_iterator it = ret.begin(); it != ret.end(); ++it) { // write the word cout << it->first << " occurs on line(s): "; // followed by one or more line numbers vector<int>::const_iterator line_it = it->second.begin(); cout << *line_it; // write the first line number ++line_it; // write the rest of the line numbers, if any while (line_it != it->second.end()) { cout << ", " << *line_it; } // write a new line to separate each word from the next cout << endl; return 0; 출력 예: aaa occurs on line(s): 1, 2, 3 bbb occurs on line(s): 1 ccc occurs on line(s): 1, 2 ddd occurs on line(s): 2 eee occurs on line(s): 3