Code：[ZachxPKU/AcceleratedCPlusPlus]

Chapter 7 Using associative containers

7.1 Containers that support efficient look-up

• associative array 关联数组

In many ways, maps behave like vectors. One fundamental difference is that the index of a map need not be an integer; it can be a string, or any other type with values that we can compare so as to keep them ordered.

map 的键值可以是任何可比较的类型。

7.2 Counting words

• pair

A pair is a simple data structure that holds two elements, which are named first and second. Each element in a map is really a pair, with a first member that contains the key and a second member that contains the associated value. When we dereference a map iterator, we obtain a value that is of the pair type associated with the map.

//  
// Created by Zach on 2022/9/5.  
//  
  
#include <iostream>  
#include <string>  
#include <map>  
  
using namespace std;  
  
int main()  
{  
    string s;  
    map<string, int> counters;  
  
    while (cin >> s)  
        ++counters[s];  
  
    for (map<string, int>::const_iterator iter = counters.begin();  
         iter != counters.end(); ++iter) {  
        cout << iter->first << "\t" << iter->second << endl;  
    }  
  
    return 0;  
}

7.3 Generating a cross-reference table

• default argument

If you look at thedeclaration of our return type and the local variable ret, you will see that we carefully wrote > > instead of >>. The compiler needs that space, because if it sees >> without intervening spaces, it will assume that it is looking at an >> operator, rather than at two separate > symbols.

在我的编译环境下不存在">>“和”> >"的问题，不过不排除一些其他的编译环境存在这样的问题，这是需要注意的！

//  
// Created by Zach on 2022/9/6.  
//  
  
#include <iostream>  
#include <string>  
#include <map>  
#include <vector>  
#include "../chapter05/split.h"  
  
using namespace std;  
  
map<string, vector<int>> crossRef(istream& in, vector<string> find_words(const string&) = split){  
    string line;  
    int line_num = 0;  
    map<string, vector<int>> ret;  
  
    while(getline(in, line)){  
        ++line_num;  
  
        vector<string> words = find_words(line);  
  
        for(vector<string>::const_iterator iter = words.begin(); iter != words.end(); ++iter){  
            ret[*iter].push_back(line_num);  
        }  
    }  
    return ret;  
}  
  
int main(){  
    map<string, vector<int>> ret = crossRef(cin);  
  
    for(map<string, vector<int>>::const_iterator iter = ret.begin(); iter != ret.end(); iter++){  
        cout << iter->first << " occurs on line(s): ";  
        vector<int>::const_iterator line_iter = iter->second.begin();  
        while(line_iter != iter->second.end()){  
            cout << *(line_iter++) << " ";  
        }  
        cout << endl;  
    }  
  
    return 0;  
}

7.4 Generating sentences

7.4.1 Representing the rules

7.4.2 Reading the grammar

7.4.3 Generating the sentence

Now comes the interesting part: finding in g the rule that corresponds to our word. You might think that we could simply refer to g[word], but doing so would give us the wrong result. Recall from §7.2/125 that when you try to index a map with a nonexistent key, it automatically creates an element with that key. That will never do in this case, because we don’t want to litter our grammar with spurious rules. Moreover, g is a const map, so even if we wanted to create new entries, we couldn’t do so. Indeed, [] isn’t even defined on a const map. Evidently, we must use a different facility: The find member of the map class looks for the element, if any, with the given key, and returns an iterator that refers to that element if it can find one. If no such element exists in g, the find algorithm returns g.end(). The comparison between it and g.end(), therefore, serves to ensure that the rule exists. If it doesn’t exist, that means the input was inconsistent—it used a bracketed word without a corresponding rule—so we throw an exception

对于map数据类型查找元素，不要以上来就使用[]，这可能会往里面容器里增加pair。

7.4.4 Selecting a random element

一个相对来说更随机的随机数生成例子。

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;  
}

7.5 A note on performance

简单讲了一下hash table，但是，hash table 不是标准C++的一部分。

7.6 Details