關聯容器 Associative Containers
關聯容器包括：
l map
l set
l multimap
l multiset
10.1 初步知識：pair類型
創建和初始化pairs
Examples:
|
pair<string, string> anon; // holds two strings
pair<string, int> word_count; // holds a string and an int
pair<string, vector<int> > line; // holds string and vector<int>
|
使用typedef簡化定義：
|
typedef pair<string, string> Author;
Author proust("Marcel", "Proust");
Author joyce("James", "Joyce");
|
pair操作
可以直接訪問pair的數據成員。這些數據成員都是public。（the pair class gives us direct access to its data members: Its members are public.）
|
string firstBook;
// access and test the data members of the pair
if (author.first == "James" && author.second == "Joyce")
firstBook = "Stephen Hero";
|
10.2 關聯容器
關聯容器共享了很多順序容器的操作。但是關聯容器還定義了自己特有的操作。
關聯容器的元素是按key進行排序的。當我們迭代訪問一個關聯容器時，保證是按照key的順序來訪問，而不是按照元素在容器中的順序來訪問的。When we iterate across an associative container, we are guaranteed that the elements are accessed in key order, irrespective of the order in which the elements were placed in the container.
10.3 map
定義map
|
map<k, v> m;
|
創建一個名字是m的空的map。
|
|
map<k, v> m(m2);
|
創建一個名字是m的map，m是m2的拷貝。m和m2必須具有相同的key和value類型。
|
|
map<k, v> m(b, e);
|
創建一個名字是m的map，它是迭代器b和e指定的元素的拷貝。元素的類型必須可以轉換成<const k, v>
|
key類型的約束條件
key不僅僅有類型，而且還包括對比方法。缺省條件下，使用>操作符比較key。這就是說，作為key的類型必須定義<操作。
map定義的類型
map定義的類型包括：
|
map<K, V>::key_type
|
用于索引map的key的類型
|
|
map<K, V>::mapped_type
|
map中與key關聯的 值的類型
|
|
map<K, V>::value_type
|
pair
它的第一個元素的類型必須是const的map<K, V>::key_type；第二個元素的類型必須是map<K, V>::mapped_type。
|
value_type是一個pair，只能修改pair的值，而不能修改key。
map迭代器解引用生成pair
當我們解引用一個map迭代器，得到的是一個容器值的引用, 這個值的類型是value_type類型。
Example:
|
// get an iterator to an element in word_count
map<string, int>::iterator map_it = word_count.begin();
// *map_it is a reference to a pair<const string, int> object
cout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element
map_it->first = "new key"; // error: key is const
++map_it->second; // ok: we can change value through an iterator
|
向map添加元素
有2種方法：
l 使用insert
l 先用下標操作符索引元素，然后對此元素進行賦值。
通過下標索引map
在map中下標就是key。如果使用的下標值不存在，就會在map里追加一個元素，它的key就是這個下標值。
|
map <string, int> word_count; // empty map
…
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;
|
map下標操作的返回值類型是mapped_value。
使用map::insert
一個簡單的例子可以看出insert和下標操作的區別：
|
int main() {
map <string, int> word_count ;
word_count["first"] =1;
word_count["first"] =9;
cout << word_count["first"] << endl;
word_count.clear();
word_count.insert( map<string, int>::value_type("first", 1) );
word_count.insert( map<string, int>::value_type("first", 9) );
cout << word_count["first"] << endl;
return 0;
}
|
輸出：
insert返回的是一個pair。first是指向元素的map迭代器，second是bool值，表示元素是否插入成功。如果key存在時，直接返回map中的元素迭代器；如果key不存在，創建一個新的pair，然后插入map，返回這個新元素對應的迭代器。
map查找
下標操作提供了最簡單的訪問獲得鍵值的方法：
|
map<string,int> word_count;
int occurs = word_count["foobar"];
|
int occurs = word_count["foobar"];但是這樣的取值方法其實還有可能隱含著一個插入操作。如果word_count不包含"foobar"，則先插入以"foobar"作為key的元素。值則是按默認值處理，等于0，這樣occurs就被賦值為0.
另一類方法：
|
m.count(k)
|
返回k在m中出現的次數
|
|
m.find(k)
|
如果k存在，返回指向該元素的迭代器。如果不存在，返回off-the-end迭代器。
|
先用這類方法進行判斷，然后再用下班取值，就可以避免如果key不存在，直接取值導致向map插入元素帶來的副作用。
Example（使用count檢查某個key是否存在）:
|
int occurs = 0;
if (word_count.count("foobar"))
occurs = word_count["foobar"];
|
Example（讀取元素而不插入元素）:
|
int occurs = 0;
map<string,int>::iterator it = word_count.find("foobar");
if (it != word_count.end())
occurs = it->second;
|
刪除map元素
有三類刪除元素的操作：
|
m.erase(k)
|
刪除key值是k的元素。返回值的類型是size_type，表示刪除元素的個數。
|
|
m.erase(p)
|
刪除由迭代器p指向的元素。p!=m.end()。返回值是void。
|
|
m.erase(b,e)
|
刪除由迭代器b,e指定訪問內的所有元素。返回值是void。
|
10.4 set
其實就是只有key的map。
10.5 multimap 和 multiset 類型
multimap追加元素，還是按照pair來追加的。
|
// adds first element with key Barth
authors.insert(make_pair(
string("Barth, John"),
string("Sot-Weed Factor")));
// ok: adds second element with key Barth
authors.insert(make_pair(
string("Barth, John"),
string("Lost in the Funhouse")));
|
multimap的find操作
find的返回值是迭代器：
|
// author we'll look for
string search_item("Alain de Botton");
// how many entries are there for this author
typedef multimap<string, string>::size_type sz_type;
sz_type entries = authors.count(search_item);
// get iterator to the first entry for this author
multimap<string,string>::iterator iter =
authors.find(search_item);
// loop through the number of entries there are for this author
for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) cout <<
iter->second << endl; // print each title
|
對比map的find操作：
|
//int occurs = 0;
map<string,int>::iterator it = word_count.find("foobar");
if (it != word_count.end())
occurs = it->second;
|
另一種面向迭代器的解決方案
這種方案包含了3種操作，這3種操作返回值都是指針。它們提供了另一種訪問集合元素的方法，雖然這些方法對于map和set也適用，但是更多情況還是用在multimap和multiset。
|
m.lower_bound(k)
|
返回指向key值不小于k的第一個元素的迭代器。
|
|
m.upper_bound(k)
|
返回指向key值大于k的第一個元素的迭代器
|
|
m.equal_range(k)
|
返回一個迭代器的pair。
first相當于m.lower_bound(k)；
second相當于m. upper_bound(k)。
|
例如，key數據如下：
If key=3, lower_bound=第一個3; upper_bound=5
if key=4; lower_bound=第一個5; upper_bound=5。這表明此key不存在（判斷條件lower_bound= upper_bound），同時也表示出這個key在容器中的插入位置。
使用容器：文本查詢程序
這部分其實最好先自己寫寫看。
需求：
讀入指定文件，然后統計指定單詞出現的次數，按規定的格式來顯示。
規定格式包括：
l 出現的總的次數
l 行號 內容
按照這個要求我先寫了一個，然后再回去讀大師的說法，比對不足。