AcceleratedC++/Chapter6 | AcceleratedC++/Chapter8 |
1. Chapter 7 Using associative containers ¶
κΈ°μ‘΄μ μ΄μ©ν vector, listλ λͺ¨λ push_back, insertλ₯Ό μ΄μ©ν΄μ μμλ₯Ό λ£μ΄μ£Όμμ λ,
μμκ° μμλλ‘ λ€μ΄κ°λ μμ°¨ 컨ν μ΄λμ΄λ€.
μ΄λ¬ν μ차컨ν μ΄λκ° λͺ¨λ νλ‘κ·Έλ¨μ μλ£κ΅¬μ‘°μ λμμ΄ λμ΄ μ€ μλ μλ€.
(μλ₯Ό λ€μλ©΄
Binary_search_tree,
AVL_treeμ κ°μ΄ μ΅μ νλ μκ³ λ¦¬μ¦μ ν΅ν΄μ μ°λ¦¬λ
λ¨μν μμ°¨κ²μλ³΄λ€ λμ± λΉ λ₯Έ μν μκ°μ κ°λ νλ‘κ·Έλ¨μ μμ±μ νκ³ μΆμ μ μλ€.)
μμκ° μμλλ‘ λ€μ΄κ°λ μμ°¨ 컨ν μ΄λμ΄λ€.
μ΄λ¬ν μ차컨ν μ΄λκ° λͺ¨λ νλ‘κ·Έλ¨μ μλ£κ΅¬μ‘°μ λμμ΄ λμ΄ μ€ μλ μλ€.
(μλ₯Ό λ€μλ©΄


λ¨μν μμ°¨κ²μλ³΄λ€ λμ± λΉ λ₯Έ μν μκ°μ κ°λ νλ‘κ·Έλ¨μ μμ±μ νκ³ μΆμ μ μλ€.)
1.1. 7.1 Containers that support efficient look-up ¶
μ°κ΄μ»¨ν μ΄λ(Associative Container) | μμλ€μ μ½μ ν μμλλ‘ λ°°μ΄νμ§ μκ³ , μμμ κ°μ λ°λΌ μ½μ μμλ₯Ό μλμ μΌλ‘ μ‘°μ νλ€. λ°λΌμ κ²μμκ³ λ¦¬μ¦μ μνμ κΈ°μ‘΄μ μ차컨ν μ΄λ μ΄μμ μ±λ₯μ 보μ₯νλ€. |
Key | μμμ κ²μμ μν΄μ μ¬μ©λλ κ²μμ΄. νκ°μ μμλ₯Ό λ€λ₯Έ μμμ ꡬλΆνλ μν μ νλ€. ν€λ μμμ λ³κ²½μμ λ³κ²½λμ§ μλ κ°μ΄λ€. μ΄μ λ°νμ¬ vectorμ μΈλ±μ€λ μμμ μ κ±°μ μΆκ°μ μΈλ±μ€κ° λ³ννλ€. μ°Έμ‘°)DBμ ![]() |
<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μΌλ‘ 컀μ§. νμ μ λ ¬ μνλ₯Ό μ μ§ |
