AcceleratedC++/Chapter6 | AcceleratedC++/Chapter8 |
1. Chapter 7 Using associative containers ¶
기존에 이용한 vector, list는 모두 push_back, insert를 이용해서 요소를 넣어주었을 때,
요소가 순서대로 들어가는 순차 컨테이너이다.
이러한 순차컨테이너가 모든 프로그램의 자료구조의 대안이 되어 줄 수는 없다.
(예를 들자면 Binary_search_tree, AVL_tree와 같이 최적화된 알고리즘을 통해서 우리는
단순한 순차검색보다 더욱 빠른 수행 시간을 갖는 프로그램의 작성을 하고 싶을 수 있다.)
요소가 순서대로 들어가는 순차 컨테이너이다.
이러한 순차컨테이너가 모든 프로그램의 자료구조의 대안이 되어 줄 수는 없다.
(예를 들자면 Binary_search_tree, AVL_tree와 같이 최적화된 알고리즘을 통해서 우리는
단순한 순차검색보다 더욱 빠른 수행 시간을 갖는 프로그램의 작성을 하고 싶을 수 있다.)
1.1. 7.1 Containers that support efficient look-up ¶
연관컨테이너(Associative Container) | 요소들을 삽입한 순서대로 배열하지 않고, 요소의 값에 따라 삽입 순서를 자동적으로 조정한다. 따라서 검색알고리즘의 수행시 기존의 순차컨테이너 이상의 성능을 보장한다. |
Key | 요소의 검색을 위해서 사용되는 검색어. 한개의 요소를 다른 요소와 구분하는 역할을 한다. 키는 요소의 변경시에 변경되지 않는 값이다. 이에 반하여 vector의 인덱스는 요소의 제거와 추가시 인덱스가 변화한다. 참조)DB의 Primary_key를 알아보자. |
<map> | C++에서 제공되는 연관 배열(Associative Array). 인덱스는 순서를 비교할 수 있는 것이면 무엇이든 가능하다. 단점으로는 자체적 순서를 갖기 때문에 순서를 변경하는 일반 알고리즘을 적용할 수 없다. |
1.2. 7.2 Counting words ¶
~cpp //word_cout.cpp #include <iostream> #include <map> #include <string> using std::cin; using std::cout; using std::endl; using std::map; using std::string; 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 (std::map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it) { cout << it->first << "\t" << it->second << endl; } return 0; }
- 상기에서 지정된 map<string, int>는 "string에서 int로의 map"라는 용어로 부름. string type key, int type value
- 최초로 등장한 string key에 대해서 map<k, v>은 새로운 요소를 생성. value-initialized.
- map은 []연산자를 통해 키값을 통해서 접근이 가능하나, 이 경우 string type key이기 때문에 모든 배열의 요소를 돌기위해서 일반적인 방식을 선택하였다. map의 각각의 요소는 pair라는 자료의 타입으로 구성. map은 pair의 first 요소에는 key, second 요소에는 value를 담는다.
map<class T>::iterator K V pair const K V
- Visual C++ 6.0 에서 소스를 컴파일 할때 책에 나온대로 (using namespace std를 사용하지 않고 위와 같이 사용하는 것들의 이름공간만 지정할 경우) map<string, int>::const_iterator 이렇게 치면 using std::map; 이렇게 미리 이름공간을 선언 했음에도 불구하고 에러가 뜬다. 6.0에서 제대로 인식을 못하는것 같다. 위와 같이 std::map<string, int>::const_iterator 이런식으로 이름 공간을 명시하거나 using namespace std; 라고 선언 하던지 해야 한다.
- Visual C++에서 map을 사용할때 warning이 많이 뜬다면 http://zeropage.org/wiki/STL_2fmap 이 페이지를 참고.
1.3. 7.3 Generating a cross-reference table ¶
~cpp //cross_reference_table.cpp #include <map> #include <iostream> #include <string> #include <vector> #include "split.h" // 6.1.1. 절에서 만들어 놓은 함수 using std::cin; using std::cout; using std::endl; using std::getline; using std::istream; using std::string; using std::vector; using std::map; // find all the lines that refer to each word in the input // 기본적으로 split 함수를 이용하여서 단어를 tokenize 한다. 만약 인자로 find_url을 주게되면 url이 나타난 위치를 기록한다. 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); // ret[*it] == (it->second) = vector<int> 같은 표현이다. // 따라서 백터에는 각 요소가 나타난 곳의 라인이 순서대로 저장된다. } return ret; } 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): "; // key 값인 string을 출력한다. // followed by one or more line numbers vector<int>::const_iterator line_it = it->second.begin(); // it->second == vector<int> 동일 표현 cout << *line_it; // write the first line number ++line_it; // write the rest of the line numbers, if any // second 값인 vector<int> 를 이용하여서 string이 나타난 각 줄의 번호를 출력한다. while (line_it != it->second.end()) { cout << ", " << *line_it; ++line_it; } // write a new line to separate each word from the next cout << endl; } return 0; }
- map
> xref(istream& in, vector<string> find_words(const string&) = split)
주의) STL을 이용하면서 많이 범하는 실수: > > (0) >>(X) 컴파일러는 >>에 대해서 operator>>()를 기대한다.
기본인자(default argument)설정. 함수의 선언식에 매개변수로 = 를 할당하면 기본 인자로 등록된다.
- int main()
기본 변수 split 을 이용해서 입력받은 값을 이용해서 ret를 초기화한다.
map >::const_iterator K V pair first = string second = vector<int>
1.4. 7.4 Generating sentences ¶
문법과 주어진 단어를 이용하여서 간단한 문장조합 프로그램을 만들어 본다. 제시된 규칙은 다음과 같다.
상기의 규칙을 통해서 우리는 간단하게
참고) Google Talks KLDP google talks perl clone
<noun> | cat |
<noun> | dog |
<noun> | table |
<noun-phrase> | <noun> |
<noun-phrase> | <adjective> <noun-phrase> |
<adjective> | large |
<adjective> | brown |
<adjective> | absurd |
<verb> | sits |
<verb> | jumps |
<location> | on the stairs |
<location> | under the sky |
<location> | wherever it wants |
<sentence> | the <noun-phrase> <verb> <location> |
~cpp the table[noun-phrase, noun] jumps[verb] wherever it wants[location]
같은 프로그램을 만들어 볼 수 있다.참고) Google Talks KLDP google talks perl clone
1.4.1. 7.4.1 규칙 표현하기 ¶
상기에서는 map >의 형태로 구현해야한다. 그러나 <adjective>, <location>, <noun>과 같이 동일한 키 값에 대해서 규칙이 여러개가 존재하는 경우를 다루기 위해서 map > > 의 타입을 이용한다.
~cpp // typedef 를 이용해서 좀더 읽기에 수월하도록 형을 지정하는 것이 가능하다. typedef vector<string> Rule; typedef vector<Rule> Rule_collection; typedef map<string, Rule_collection> Grammar;
1.4.2. 7.4.2 문법 읽어들이기 ¶
~cpp Grammar read_grammar(istream& in) { Grammar ret; string line; while (getline(in, line)) { vector<string> entry = split(line); // split 함수를 이용해서 입력된 문자열을 ' '를 기존으로 tokenize 한다. if (!entry.empty()) ret[entry[0]].push_back( Rule(entry.begin() + 1, entry.end())); //vector<string>의 첫번째 요소를 entry의 키값으로 이용한다. 2번째 요소부터 마지막 요소까지는 entry의 값으로 저장한다. } return ret; }
1.4.3. 7.4.3 문장 생성하기 ¶
~cpp vector<string> gen_sentence(const Grammar& g) { vector<string> ret; gen_aux(g, "<sentence>", ret); return ret; }g:Grammar map에서 <sentence> 키값으로 실제의 문장에 관한 문법을 읽어들인다.
~cpp bool bracketed(const string& s) { return s.size() > 1 && s[0] == '<' && s[s.size()-1] == '>'; } //Recursive function call 재귀 함수의 이용 void gen_aux(const Grammar& g, const string& word, vector<string>& ret) { if (!bracketed(word)) { ret.push_back(word); // 실제로 ret:vector<string> 에 값이 저장되고 재귀 함수가 끝이 나는 조건식이 된다. } else { Grammar::const_iterator it = g.find(word); // g[word]로 참조를 할경우 map 컨테이너의 특성상 새로운 map이 생성된다. if (it == g.end()) throw logic_error("empty rule"); // 규직이 존재하지 않는 다면 word로 전달된 규칙이 존재하지 않는 다는 말이된다. // 즉 입력이 잘못된 경우가 된다. const Rule_collection& c = it->second; const Rule& r = c[nrand(c.size())]; // <noun-phrase> 와 같이 연결된 문법이 <noun> 인경우에는 재귀적 함수 호출을 통해서 마지막 단어까지 내려간다. // 마지막 단어까지 내려갓을 경우 재귀 함수를 호출하고 bracketed = false 의 조건이 되기 때문에 재귀 함수가 종료된다. for(Rule::const_iterator i = r.begin(); i != r.end(); ++i) gen_aux(g, *i, ret); } }map<class T>.find(K) : 주어진 키를 갖는 요소를 찾고, 있다면 그 요소를 가리키는 반복자를 리턴한다. 없다면 map<class T>.end()를 리턴한다.
nrand(c.size()) : 7.4.4 절에서 설명함. pseudo rand 함수를 통해서 [0, c.size()) 의 범위를 갖는 가상적 임의의 수를 리턴한다.
재귀함수의 호출은 반드시 함수의 내부에 재귀호출을 탈출 할 수 잇는 코드가 존재해야한다. 그렇지 않을 경우 stack_overflow가 발생한다.
~cpp int main() { // generate the sentence vector<string> sentence = gen_sentence(read_grammar(cin)); // write the first word, if any vector<string>::const_iterator it = sentence.begin(); if (!sentence.empty()) { cout << *it; ++it; } // write the rest of the words, each preceded by a space while (it != sentence.end()) { cout << " " << *it; ++it; } cout << endl; return 0; }
1.4.4. 7.4.4 무작위 요소를 선택하기 ¶
~cpp int nrand(int n) { if (n <= 0 || n > RAND_MAX) throw domain_error("Argument to nrand is out of range"); const int bucket_size = RAND_MAX / n; int r; do r = rand() / bucket_size; while (r >= n) return r; }rand() 는 C Standard Library <cstdlib> 라이브러리에 존재한다. 일반적으로 cstdlib 에 정의된 RAND_MAX보다 작은 값을 임의적으로 리턴한다.
RAND_MAX % n를 이용해서 임의의 수를 구할 경우 Pseudo 임의 값의 한계로 인해서 문제점이 발생한다.
- n 이 작은 경우: rand()함수는 홀수 짝수를 번갈아 출력하는 성질이 있기 때문에 n이 2일경우 0과 1이 반복적으로 출력된다.
- n 이 너무 큰 경우에도 특정한 수가 반복적으로 나타나게 된다.
1.4.5. Addition. Entire Source Filie ¶
~cpp //grammar.cpp #include <algorithm> #include <cstdlib> #include <iostream> #include <map> #include <stdexcept> #include <string> #include <vector> #include "split.h" #include <time.h> using std::istream; using std::cin; using std::copy; using std::cout; using std::endl; using std::find; using std::getline; using std::logic_error; using std::map; using std::string; using std::vector; using std::domain_error; using std::rand; typedef vector<string> Rule; typedef vector<Rule> Rule_collection; typedef map<string, Rule_collection> Grammar; // read a grammar from a given input stream Grammar read_grammar(istream& in) { Grammar ret; string line; // read the input while (getline(in, line)) { // `split' the input into words vector<string> entry = split(line); if (!entry.empty()) // use the category to store the associated rule ret[entry[0]].push_back( Rule(entry.begin() + 1, entry.end())); } return ret; } void gen_aux(const Grammar&, const string&, vector<string>&); int nrand(int); vector<string> gen_sentence(const Grammar& g) { vector<string> ret; gen_aux(g, "<sentence>", ret); return ret; } bool bracketed(const string& s) { return s.size() > 1 && s[0] == '<' && s[s.size() - 1] == '>'; } void gen_aux(const Grammar& g, const string& word, vector<string>& ret) { if (!bracketed(word)) { ret.push_back(word); } else { // locate the rule that corresponds to `word' Grammar::const_iterator it = g.find(word); if (it == g.end()) throw logic_error("empty rule"); // fetch the set of possible rules const Rule_collection& c = it->second; // from which we select one at random const Rule& r = c[nrand(c.size())]; // recursively expand the selected rule for (Rule::const_iterator i = r.begin(); i != r.end(); ++i) gen_aux(g, *i, ret); } } int main() { // generate the sentence vector<string> sentence = gen_sentence(read_grammar(cin)); // write the first word, if any vector<string>::const_iterator it = sentence.begin(); if (!sentence.empty()) { cout << *it; ++it; } // write the rest of the words, each preceded by a space while (it != sentence.end()) { cout << " " << *it; ++it; } cout << endl; return 0; } // return a random integer in the range `[0,' `n)' int nrand(int n) { if (n <= 0 || n > RAND_MAX) throw domain_error("Argument to nrand is out of range"); const int bucket_size = RAND_MAX / n; int r; do r = rand() / bucket_size; while (r >= n); return r; }
1.5. 7.5 A note on performance ¶
Hash Table | 각 키값에 대하여 해쉬 값을 제공해야함. 성능이 해쉬 함수에 크게 영향을 받음. 요소들을 원하는 순서대로 얻기 쉽지 않음 |
Associative Container in STL | 키 값이 <. == 연산으로 비교만 된다면 무엇이든 무관, 요소로의 접근 시간이 logn으로 커짐. 항상 정렬 상태를 유지 |