說明：以下筆記大部分參考文末的Reference,，并結(jié)合自己的理解進(jìn)行整理

1. 簡介

map 是 STL 的一個關(guān)聯(lián)容器，它提供一對一的hash

• 第一個稱為關(guān)鍵字(key),，每個關(guān)鍵字只能在map中出現(xiàn)一次,；
• 第二個稱為該關(guān)鍵字的值(value)；

map以模板(泛型)方式實(shí)現(xiàn),，可以存儲任意類型的數(shù)據(jù),，包括使用者自定義的數(shù)據(jù)類型。Map主要用于資料一對一映射(one-to-one)的情況,，map內(nèi)部的實(shí)現(xiàn)自建一顆紅黑樹,，這顆樹具有對數(shù)據(jù)自動排序的功能。在map內(nèi)部所有的數(shù)據(jù)都是有序的,，后邊我們會見識到有序的好處,。比如一個班級中，每個學(xué)生的學(xué)號跟他的姓名就存在著一對一映射的關(guān)系,。

標(biāo)準(zhǔn)卡提供8個關(guān)聯(lián)容器

2. pair類型

在介紹關(guān)聯(lián)容器操作之前,，先了解一下 pair 的標(biāo)準(zhǔn)庫類型。pair類型是在有文件 utility 中定義的,，pair是將2個數(shù)據(jù)組合成一組數(shù)據(jù),，當(dāng)需要這樣的需求時就可以使用pair，如STL中的map就是將key和value放在一起來保存,。另一個應(yīng)用是,，當(dāng)一個函數(shù)需要返回2個數(shù)據(jù)的時候，可以選擇pair,。 pair的實(shí)現(xiàn)是一個結(jié)構(gòu)體,，主要的兩個成員變量是first ，second 因?yàn)槭鞘褂胹truct不是class,，所以可以直接使用pair的成員變量,。

2.1 pair類型的定義和初始化

pair類型包含了兩個數(shù)據(jù)值，通常有以下的一些定義和初始化的一些方法：

• pair<T1, T2> p; ： 定義了一個空的pair對象p,，T1和T2的成員都進(jìn)行了值初始化
• pair<T1, T2> p(v1, v2); ： p是一個成員類型為T1和T2的pair; first和second成員分別用v1和v2進(jìn)行初始化,。
• pair<T1, T2> p = {v1, v2} ：等價于p(v1, v2)
• make_pair(v1, v2) ： 以v1和v2值創(chuàng)建的一個新的pair對象

2.2 pair對象的一些操作

除此之外，pair對象還有一些方法,，如取出pair對象中的每一個成員的值：

例如：

#include <stdio.h>
#include <string.h>
#include <string>
#include <utility>
using namespace std;

int main(){
    pair<int, string> p1(0, "Hello");
    printf("%d, %s\n", p1.first, p1.second.c_str());
    pair<int, string> p2 = make_pair(1, "World");
    printf("%d, %s\n", p2.first, p2.second.c_str());
    return 0;
}

3. map基本操作

3.1 頭文件

#include <map>

3.2 創(chuàng)建map對象

map是鍵-值對的組合,，即map的元素是pair,，其有以下的一些定義的方法：

• map<k, v> m; ： 定義了一個名為m的空的map對象
• map<k, v> m2(m); ： 創(chuàng)建了m的副本m2
• map<k, v> m3(b, e); ： 創(chuàng)建了map對象m3，并且存儲迭代器b和e范圍內(nèi)的所有元素的副本

map的 value_type 是存儲元素的鍵以及值的pair類型,，鍵為const,。

map<int, char> m; 						// 定義了一個名為m的空的map
map<int, char> m2(m); 					// 創(chuàng)建了m的副本m2
map<int, char> m3(m.begin(), m.end()); 	// 創(chuàng)建了map對象m3，并且存儲迭代器范圍內(nèi)的所有元素的副本

3.3 map元素訪問

注意：下標(biāo)[] 和 at() 操作,，只使用與非 const 的 map 和 unordered_map

3.3.1 使用下標(biāo) [ ] 訪問

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<char, std::string> mymap;

    mymap['a'] = "an element";
    mymap['b'] = "another element";
    mymap['c'] = mymap['b'];

    std::cout << "mymap['a'] is " << mymap['a'] << '\n';
    std::cout << "mymap['b'] is " << mymap['b'] << '\n';
    std::cout << "mymap['c'] is " << mymap['c'] << '\n';
    std::cout << "mymap['d'] is " << mymap['d'] << '\n';

    std::cout << "mymap now contains " << mymap.size() << " elements.\n";
    return 0;
}
/*
mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is 					// 下標(biāo)訪問不會進(jìn)行下標(biāo)檢查
mymap now contains 4 elements.
*/

注意：下標(biāo)訪問不會做下標(biāo)檢查,，如上第4行打印的語句不會報(bào)錯，但打印結(jié)果為空,，因?yàn)?strong>下標(biāo)訪問會插入不存在的key,，對應(yīng)的value為默認(rèn)值
而使用 at() 訪問則會做下標(biāo)檢查，若不存在該key會報(bào)錯

3.3.2 使用 at() 方法訪問

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> mymap = {
        {"alpha", 0}, {"beta", 0}, {"gamma", 0}};

    mymap.at("alpha") = 10;
    mymap.at("beta") = 20;
    mymap.at("gamma") = 30;

    for (auto& x : mymap) {
        std::cout << x.first << ": " << x.second << '\n';
    }

    return 0;
}
/*
alpha: 10
beta: 20
gamma: 30
*/

3.4 map中元素的插入

在map中元素有兩種插入方法：1. 使用下標(biāo) [] 2. 使用 insert() 函數(shù)

3.4.1 使用下標(biāo)[]插入

使用下標(biāo)訪問不存在的元素,，將會在map容器中添加一個新的元素,；
使用下標(biāo)訪問存在的元素，將會覆蓋map容器中的該元素

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, char> mymap;
    mymap[0] = 'a';
    mymap[1] = 'b';
    mymap[2] = 'c';
    mymap[0] = 'x';
    for (map<int, char>::iterator iter = mymap.begin(); iter != mymap.end(); iter++)
        cout << iter->first << " ==> " << iter->second << endl;
    return 0;
}

3.4.2 使用insert()插入元素

insert函數(shù)的插入方法主要有如下：

• pair<iterator,bool> insert (const value_type& val);
  • 插入單個鍵值對,，并返回插入位置和成功標(biāo)志,，插入位置已經(jīng)存在值時，插入失敗
• iterator insert (const_iterator position, const value_type& val);
  • 在指定位置插入,，在不同位置插入效率是不一樣的,，因?yàn)樯婕暗街嘏?/li>
• void insert (InputIterator first, InputIterator last);
  • 插入迭代器范圍內(nèi)鍵值對

幾種插入方法如下面的例子所示：

#include <iostream>
#include <map>

int main()
{
    std::map<char, int> mymap;

    // （1）插入單個值
    mymap.insert(std::pair<char, int>('a', 100));
    mymap.insert(std::pair<char, int>('z', 200));
    mymap.insert(std::make_pair('f', 300));	// pair方式和make_pair功能是一樣的

    // 返回插入位置以及是否插入成功
    std::pair<std::map<char, int>::iterator, bool> ret;
    ret = mymap.insert(std::pair<char, int>('z', 500));
    if (ret.second == false) {
        std::cout << "element 'z' already existed";
        std::cout << " with a value of " << ret.first->second << '\n';
    }

    // （2）指定位置插入
    std::map<char, int>::iterator it = mymap.begin();
    mymap.insert(it, std::pair<char, int>('b', 300));  //效率更高
    mymap.insert(it, std::pair<char, int>('c', 400));  //效率非最高

    // （3）范圍多值插入
    std::map<char, int> anothermap;
    anothermap.insert(mymap.begin(), mymap.find('c'));

    // （4）列表形式插入
    anothermap.insert({ { 'd', 100 }, {'e', 200} });

    return 0;
}

3.4 erase() 刪除元素

從map中刪除元素的函數(shù)是erase()，該函數(shù)有如下的三種形式：

• size_t erase( const key_type& key );
  • 根據(jù)key來進(jìn)行刪除,， 返回刪除的元素?cái)?shù)量,，在map里結(jié)果非0即1
• iterator erase( iterator pos )
  • 刪除迭代器指向位置的鍵值對，并返回一個指向下一元素的迭代器
• iterator erase( const_iterator first, const_iterator last );
  • 刪除一定范圍內(nèi)的元素,，并返回一個指向下一元素的迭代器

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> mymap;
    for (int i = 0; i < 20; i++) {
        mymap.insert(make_pair(i, i));
    }
    mymap.erase(0);          	 // （1）刪除key為0的元素
    mymap.erase(mymap.begin());  // （2）刪除迭代器指向的位置元素
    map<int, int>::iterator it;
    for (it = mymap.begin(); it != mymap.end(); it++) {
        cout << it->first << "==>" << it->second << endl;
    }
    return 0;
}

3.5 count(k) 查找關(guān)鍵字k出現(xiàn)的次數(shù)

• size_type count (const key_type& k) const;

mymap.count(1);		// 查找關(guān)鍵字1在容器map中出現(xiàn)的次數(shù),，如果不存在則為0

3.6 find(k) 查找元素

• iterator find (const key_type& k);
• const_iterator find (const key_type& k) const;

若存在，返回指向該key的迭代器
若不存在,，則返回迭代器的尾指針，即 mymap.end(),，即 -1

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> mp;
    for (int i = 0; i < 20; i++) {
        mp.insert(make_pair(i, i));
    }

    if (mp.count(0)) {
        cout << "yes!" << endl;
    } else {
        cout << "no!" << endl;
    }

    map<int, int>::iterator it_find;
    it_find = mp.find(0);
    if (it_find != mp.end()) {
        it_find->second = 20;
    } else {
        cout << "no!" << endl;
    }

    map<int, int>::iterator it;
    for (it = mp.begin(); it != mp.end(); it++) {
        cout << it->first << " ==> " << it->second;
    }
    return 0;
}

3.7 lower_bound(k) 返回關(guān)鍵字>=k的元素的第一個位置(是一個迭代器)

• iterator lower_bound (const key_type& k);
• const_iterator lower_bound (const key_type& k) const;

c.lower_bound(k)

3.8 upper_bound(k) 返回關(guān)鍵字>k的元素的第一個位置(是一個迭代器)

• iterator upper_bound (const key_type& k);
• const_iterator upper_bound (const key_type& k) const;

c.upper_bound(k)

注意：lower_bound 和 upper_bound 不適用與無序容器

3.9 equal_range() 返回一個迭代器pair,，表示關(guān)鍵字 == k的元素的范圍,。若k不存在，pair的兩個成員均等于c.end()

• pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
• pair<iterator,iterator> equal_range (const key_type& k);

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<char, int> mymap;
    mymap['a'] = 3;
    mymap['b'] = 4;
    mymap['c'] = 5;
    mymap['d'] = 6;
    
    cout << mymap.lower_bound('c')->first << endl;  // 返回key >= 'c'第一個元素的迭代器
    cout << mymap.upper_bound('c')->first << endl;  // 返回key >  'c'第一個元素的迭代器
    
    pair<map<char, int>::iterator, map<char, int>::iterator> ret;
    ret = mymap.equal_range('c');
    cout << "lower bound points to: ";
    cout << ret.first->first << " => " << ret.first->second << '\n';

    cout << "upper bound points to: ";
    cout << ret.second->first << " => " << ret.second->second << '\n';
    return 0;
}
/*
c
d
lower bound points to: c => 5
upper bound points to: d => 6
*/

3.10 empty() 容器是否為空

mymap.enpty();

3.11 clear() 清空容器

mymap.clear();

3.12 size() 容器的大小

mymap.size();

3.13 max_size() 容器可以容納的最大元素個數(shù)

mymap.max_size();

3.14 swap() 交換兩個map

A.swap(B);

3.15 begin() 返回指向map頭部的迭代器

3.16 end() 返回指向map末尾的迭代器

3.17 rbegin() 返回一個指向map尾部的逆向迭代器

3.18 rend() 返回一個指向map頭部的逆向迭代器

3.19 關(guān)聯(lián)容器額外的類型別名

3.20 key_comp() 比較key_type值大小

// 比較兩個關(guān)鍵字在map中位置的先后
key_compare key_comp() const;

map<char,int> mymap;
map<char,int>::key_compare mycomp = mymap.key_comp();

mymap['a']=100;
mymap['b']=200;
mycomp('a', 'b');  // a排在b前面,，因此返回結(jié)果為true

3.21 value_comp() 比較value_type值大小

#include <iostream>
#include <map>

int main() {
    std::map<char, int> mymap;

    mymap['x'] = 1001;
    mymap['y'] = 2002;
    mymap['z'] = 3003;

    std::cout << "mymap contains:\n";
    std::pair<char, int> highest = *mymap.rbegin();  // last element
    std::map<char, int>::iterator it = mymap.begin();
    do {
        std::cout << it->first << " => " << it->second << '\n';
    } while (mymap.value_comp()(*it++, highest));	// 注意這里只會比較value_type中的key

    return 0;
}

4. map遍歷

4.1 使用迭代器遍歷

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    map<string, int> word_count;
    string word;
    while (cin >> word && word != "-1")		// 統(tǒng)計(jì)每個單詞出現(xiàn)的次數(shù)
        word_count[word]++;
    
    // 使用迭代器遍歷
    map<string, size_t>::iterator iter;
    for (iter = word_count.begin(); iter != word_count.end(); iter++) {
        cout << iter->first << " occurs " << iter->second
             << ((iter->second) > 1 ? " times" : " time") << endl;
    }
    
    // 當(dāng)key是int類型的話,，還可以使用下標(biāo)迭代訪問
    return 0;