| 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λ₯Ό λ΄λλ€.
λ°λΌμ νλ² μ±μ±λ Keyλ λ³κ²½μ΄ λΆκ°νλ€.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μΌλ‘ 컀μ§. νμ μ λ ¬ μνλ₯Ό μ μ§ |










