1. 關聯(lián)式容器

在C++初階階段，我們已經(jīng)接觸過STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，這些容器統(tǒng)稱為序列式容器，因為其底層為線性序列的數(shù)據(jù)結構，里面存儲的是元素本身。那什么是關聯(lián)式容器？它與序列式容器有什么區(qū)別？

關聯(lián)式容器是STL中的一類容器，用于存儲鍵值對（key - value pairs）。主要包括 set、map、multiset 和 multimap。與序列式容器（如 vector、list 等）不同，關聯(lián)式容器的元素是以鍵（key）來索引的，而不是通過元素的順序。

主要區(qū)別：
存儲方式：序列式容器按順序存儲元素，關聯(lián)式容器按鍵值對存儲，允許快速查找。
訪問方式：序列式容器通過索引訪問元素，關聯(lián)式容器通過鍵訪問對應的值。
性能：關聯(lián)式容器通常提供對元素的快速查找、插入和刪除操作，時間復雜度一般為對數(shù)級（O(log n)），而序列式容器的某些操作可能是線性級（O(n)）。
關聯(lián)式容器在處理需要快速查找的場景時非常有用。

2. 鍵值對

用來表示具有一一對應關系的一種結構，該結構中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息。比如：現(xiàn)在要建立一個英漢互譯的字典，那該字典中必然有英文單詞與其對應的中文含義，而且，英文單詞與其中文含義是一一對應的關系，即通過該單詞，在詞典中就可以找到與其對應的中文含義。

SGI-STL中關于鍵值對的定義:

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

3. 樹形結構的關聯(lián)式容器

根據(jù)應用場景的不同，STL總共實現(xiàn)了兩種不同結構的管理式容器：樹型結構與哈希結構。樹型結 構的關聯(lián)式容器主要有四種：map、set、multimap、multiset。這四種容器的共同點是：使用平衡搜索樹(即紅黑樹)作為其底層結果，容器中的元素是一個有序的序列。下面一依次介紹每一 個容器。

3.1 set 

set的介紹

1. set是按照一定次序存儲元素的容器

2. 在set中，元素的value也標識它(value就是key，類型為T)，并且每個value必須是唯一的。 set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。

3. 在內部，set中的元素總是按照其內部比較對象(類型比較)所指示的特定嚴格弱排序準則進行排序。

4. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據(jù)順序對 子集進行直接迭代。

5. set在底層是用二叉搜索樹(紅黑樹)實現(xiàn)的。

注意：

1. 與map/multimap不同，map/multimap中存儲的是真正的鍵值對，set中只放 value，但在底層實際存放的是由<value, value>構成的鍵值對。

2. set中插入元素時，只需要插入value即可，不需要構造鍵值對。

3. set中的元素不可以重復(因此可以使用set進行去重)。

4. 使用set的迭代器遍歷set中的元素，可以得到有序序列

5. set中的元素默認按照小于來比較

6. set中查找某個元素，時間復雜度為：log(N)

7. set中的元素不允許修改(為什么?)

8. set中的底層使用二叉搜索樹(紅黑樹)來實現(xiàn)  

set 中的元素不允許修改是因為 set 是基于鍵的唯一性和排序特性來管理元素的。如果允許修改元素，會導致以下問題：

唯一性破壞：修改后的元素可能會與其他元素重復，從而破壞 set 的唯一性。
排序不一致：set 中的元素是自動排序的，修改元素會影響其在容器中的位置，可能導致內部結構不一致。
因此，為了維護這些特性，set 中的元素必須是不可修改的

 參考:set - C++ Reference

set的使用

1. set的模板參數(shù)列表

T: set中存放元素的類型，實際在底層存儲<value, value>的鍵值對。

Compare：set中元素默認按照小于來比較

Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理  

2. set的構造  

3. set的迭代器  

4. set的容量

 5. set的修改操作

6. set的使用舉例

#include <iostream>
#include <set>
using namespace std;
void TestSet()
{
    // 用數(shù)組array中的元素構造set
    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    set<int> s(array, array + sizeof(array) / sizeof(array[0]));
    cout << s.size() << endl;
    // 正向打印set中的元素，從打印結果中可以看出：set可去重
    for (auto& e : s)
        cout << e << " ";
    cout << endl;
    // 使用迭代器逆向打印set中的元素
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        cout << *it << " ";
    cout << endl;
    // set中值為3的元素出現(xiàn)了幾次
    cout << s.count(3) << endl;
}
int main()
{
    TestSet();
    return 0;
}

 3.2 map

map的介紹

1. map是關聯(lián)容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。

2. 在map中，鍵值key通常用于排序和唯一地標識元素，而值value中存儲與此鍵值key關聯(lián) 的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair:

typedef pair<const key, T> value_type;

3. 在內部，map中的元素總是按照鍵值key進行比較排序的。

4. map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據(jù)順序 對元素進行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。

5. map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。

6. map通常被實現(xiàn)為二叉搜索樹(更準確的說：平衡二叉搜索樹(紅黑樹))。

參考:map - C++ Reference 

map的使用

1. map的模板參數(shù)聲明

key: 鍵值對中key的類型

T： 鍵值對中value的類型

Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內置類型元素)該參數(shù)不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規(guī)則(一般情況下按照函數(shù)指針或者仿函數(shù)來傳遞)

Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的 空間配置器

注意：在使用map時，需要包含頭文件 

2. map的構造

3. map的迭代器

4. map的容量與元素訪問

注意：在元素訪問時，有一個與operator[]類似的操作at()(該函數(shù)不常用)函數(shù)，都是通過key找到與key對應的value然后返回其引用，不同的是：當key不存在時，operator[]用默認 value與key構造鍵值對然后插入，返回該默認value，at()函數(shù)直接拋異常。 

5. map中元素的修改

6. map的使用舉例

#include <iostream>
#include <string>
#include <map>
using namespace std;
void TestMap()
{
    map<string, string> m;
    // 向map中插入元素的方式：
    // 將鍵值對<"peach","桃子">插入map中，用pair直接來構造鍵值對
    m.insert(pair<string, string>("peach", "桃子"));
    // 將鍵值對<"peach","桃子">插入map中，用make_pair函數(shù)來構造鍵值對
    m.insert(make_pair("banan", "香蕉"));
    // 借用operator[]向map中插入元素
       /*
    operator[]的原理是：
     用<key, T()>構造一個鍵值對，然后調用insert()函數(shù)將該鍵值對插入到map中
     如果key已經(jīng)存在，插入失敗，insert函數(shù)返回該key所在位置的迭代器
     如果key不存在，插入成功，insert函數(shù)返回新插入元素所在位置的迭代器
     operator[]函數(shù)最后將insert返回值鍵值對中的value返回
    */
    // 將<"apple", "">插入map中，插入成功，返回value的引用，將“蘋果”賦值給該引用結果，
    m["apple"] = "蘋果";
    // key不存在時拋異常
    //m.at("waterme") = "水蜜桃";
    cout << m.size() << endl;
    // 用迭代器去遍歷map中的元素，可以得到一個按照key排序的序列
    for (auto& e : m)
        cout << e.first << "--->" << e.second << endl;
    cout << endl;
    // map中的鍵值對key一定是唯一的，如果key存在將插入失敗
    auto ret = m.insert(make_pair("peach", "桃色"));
    if (ret.second)
        cout << "<peach, 桃色>不在map中, 已經(jīng)插入" << endl;
    else
        cout << "鍵值為peach的元素已經(jīng)存在：" << ret.first->first << "--->"
        << ret.first->second << " 插入失敗" << endl;
    // 刪除key為"apple"的元素
    m.erase("apple");
    if (1 == m.count("apple"))
        cout << "apple還在" << endl;
    else
        cout << "apple被吃了" << endl;
}
int main()
{
    TestMap();
    return 0;
}

3.3 multiset 

multiset的介紹

1. multiset是按照特定順序存儲元素的容器，其中元素是可以重復的。

2. 在multiset中，元素的value也會識別它(因為multiset中本身存儲的就是組成的鍵值對，因此value本身就是key，key就是value，類型為T). multiset元素的值不能在容器中進行修改(因為元素總是const的)，但可以從容器中插入或刪除。

3. 在內部，multiset中的元素總是按照其內部比較規(guī)則(類型比較)所指示的特定嚴格弱排序準則進行排序。

4. multiset容器通過key訪問單個元素的速度通常比unordered_multiset容器慢，但當使用迭 代器遍歷時會得到一個有序序列。

5. multiset底層結構為二叉搜索樹(紅黑樹)。

注意：

1. multiset中在底層中存儲的是<key, value>的鍵值對

2. multiset的插入接口中只需要插入即可

3. 與set的區(qū)別是，multiset中的元素可以重復，set中value是唯一的

4. 使用迭代器對multiset中的元素進行遍歷，可以得到有序的序列

5. multiset中的元素不能修改

6. 在multiset中找某個元素，時間復雜度為: logN

7. multiset的作用：可以對元素進行排序 

參考:multiset - C++ Reference 

multiset的使用

此處只簡單演示set與multiset的不同，其他接口接口與set相同

#include <iostream>
#include <set>
using namespace std;
void TestSet()
{
	int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7, 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
	// 注意：multiset在底層實際存儲的是<int, int>的鍵值對
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
}
int main()
{
	TestSet();
	return 0;
}

3.4 multimap

multimap的介紹

1. Multimaps是關聯(lián)式容器，它按照特定的順序，存儲由key和value映射成的鍵值對，其中多個鍵值對之間的key是可以重復的。

2. 在multimap中，通常按照key排序和惟一地標識元素，而映射的value存儲與key關聯(lián)的內 容。key和value的類型可能不同，通過multimap內部的成員類型value_type組合在一起， value_type是組合key和value的鍵值對:

typedef pair <const key, T>value_type;

3. 在內部，multimap中的元素總是通過其內部比較對象，按照指定的特定嚴格弱排序標準對 key進行排序的。

4. multimap通過key訪問單個元素的速度通常比unordered_multimap容器慢，但是使用迭代 器直接遍歷multimap中的元素可以得到關于key有序的序列。

5. multimap在底層用二叉搜索樹(紅黑樹)來實現(xiàn)。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重復的。

參考: multimap - C++ Reference 

multimap的使用

multimap中的接口可以參考map，功能都是類似的。

注意：

1. multimap中的key是可以重復的。

2. multimap中的元素默認將key按照小于來比較

3. multimap中沒有重載operator[]操作

4. 使用時與map包含的頭文件相同：

到此這篇關于C++map,set,multiset,multimap詳細解析的文章就介紹到這了,更多相關C++map,set,multiset,multimap內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論