U E D R , A S I H C RSS

AcceleratedC++/Chapter7

1. Chapter 7 Using associative containers

기쑴에 μ΄μš©ν•œ vector, listλŠ” λͺ¨λ‘ push_back, insertλΌ μ΄μš©ν•΄μ„œ μš”μ†ŒλΌ λ„£μ–΄μ£Όμ—ˆμ„ λ•Œ,
μš”μ†Œκ°€ μˆœμ„œλŒ€λ‘œ λ“€μ–΄κ°€λŠ” 순차 μ»¨ν…Œμ΄λ„ˆμ΄λ‹€.
μ΄λŸ¬ν•œ μˆœμ°¨μ»¨ν…Œμ΄λ„ˆκ°€ λͺ¨λ“  ν”„λ‘œκ·Έλž¨μ˜ 자료ꡬ쑰의 λŒ€μ•ˆμ΄ λ˜μ–΄ μ„ μˆ˜λŠ” μ—†λ‹€.
(μ˜ˆλΌ λ“€μžλ©΄ WikiPedia:Binary_search_tree, WikiPedia:AVL_tree와 같이 μ΅œμ ν™”λœ μ•Œκ³ λ¦¬μ¦˜μ„ ν†΅ν•΄μ„œ μš°λ¦¬λŠ”
λ‹¨μˆœν•œ μˆœμ°¨κ²€μƒ‰λ³΄λ‹€ λ”μš± λΉ λ₯Έ μˆ˜ν–‰ μ‹œκ°„μ„ κ°–λŠ” ν”„λ‘œκ·Έλž¨μ˜ μž‘μ„±μ„ ν•˜κ³  싢을 수 μžˆλ‹€.)

1.1. 7.1 Containers that support efficient look-up

μ—°κ΄€μ»¨ν…Œμ΄λ„ˆ(Associative Container) μš”μ†Œλ“€μ„ μ‚½μž…ν•œ μˆœμ„œλŒ€λ‘œ λ°°μ—΄ν•˜μ§€ μ•Šκ³ , μš”μ†Œμ˜ 값에 따라 μ‚½μž… μˆœμ„œλΌ μžλ™μ μœΌλ‘œ μ‘°μ •ν•œλ‹€. λ”°λΌμ„œ κ²€μƒ‰μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰μ‹œ 기쑴의 μˆœμ°¨μ»¨ν…Œμ΄λ„ˆ μ΄μƒμ˜ μ„±λŠ₯을 보μž₯ν•œλ‹€.
Key μš”μ†Œμ˜ 검색을 μœ„ν•΄μ„œ μ‚¬μš©λ˜λŠ” 검색어. ν•œκ°œμ˜ μš”μ†ŒλΌ λ‹€λ₯Έ μš”μ†Œμ™€ κ΅¬λΆ„ν•˜λŠ” 역할을 ν•œλ‹€. ν‚€λŠ” μš”μ†Œμ˜ λ³€κ²½μ‹œμ— λ³€κ²½λ˜μ§€ μ•ŠλŠ” 값이닀. 이에 λ°˜ν•˜μ—¬ vector의 μΈλ±μŠ€λŠ” μš”μ†Œμ˜ μ œκ±°μ™€ μΆ”κ°€μ‹œ μΈλ±μŠ€κ°€ λ³€ν™”ν•œλ‹€. μ°Έμ‘°)DB의 WikiPedia: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
    λ”°λΌμ„œ ν•œλ²ˆ μ„±μ„±λœ KeyλŠ” 변경이 λΆˆκ°€ν•˜λ‹€.

  • 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

문법과 주어진 λ‹¨μ–΄λΌ μ΄μš©ν•˜μ—¬μ„œ κ°„λ‹¨ν•œ λ¬Έμž₯μ‘°ν•© ν”„λ‘œκ·Έλž¨μ„ λ§Œλ“€μ–΄ λ³Έλ‹€. μ œμ‹œλœ κ·œμΉ™μ€ λ‹€μŒκ³Ό κ°™λ‹€.
<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 이 λ„ˆλ¬΄ 큰 κ²½μš°μ—λ„ νŠΉμ •ν•œ μˆ˜κ°€ 반볡적으둜 λ‚˜νƒ€λ‚˜κ²Œ λœλ‹€.
λ”°λΌμ„œ μš°λ¦¬λŠ” RAND_MAXλΌ n으둜 λ‚˜λˆ„μ–΄μ„œ 전체 RAND_MAXλΌ bucketμ΄λΌλŠ” λ‹¨μœ„λ‘œ λ‚˜λˆˆλ’€μ— 이 bucket으둜 rand()κ°€ λ°œμƒμ‹œν‚€λŠ” λ‚œμˆ˜λΌ λ‚˜λˆ„μ–΄ 쀌으둜써 μš°λ¦¬κ°€ μ›ν•˜λŠ” [0, 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으둜 컀짐. 항상 μ •λ ¬ μƒνƒœλ₯Ό μœ μ§€
STL의 Associative ContainerλŠ” balanced self-adjusting tree(μ°Έκ³  WikiPedia:AVL_tree )κ΅¬μ‘°λΌ μ΄μš©ν•˜μ—¬μ„œ μ—°κ΄€ μ»¨ν…Œμ΄λ„ˆλΌ κ΅¬ν˜„ν–ˆμŒ.

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:25
Processing time 0.0664 sec