關聯式容器
在前面，我們所學的vector、list、deque，這些都是序列容器，也就是底層為線性序列的數據結構。
而關聯式容器是C++標準庫中的一種類別，用于存儲鍵值對（key-value pair），關聯式容器中的元素中的元素是按照鍵值進行有序存儲的，同時也支持快速查找、插入、修改等操作。而map和set就是主要的類型；
這些關聯式容器在實現上通常采用平衡二叉搜索樹或哈希表等數據結構來保證元素的有序性和高效的查找性能。
鍵值對
鍵值對是關聯式容器中的一種結構，它由一個鍵（key）和一個對應值（value）組成。在關聯式容器中，每個元素都有一個唯一的鍵，用于標識和訪問該元素。鍵值對的特性使得關聯式容器能夠通過鍵快速查找、插入、刪除。
在關聯式容器中，鍵通常用于確定元素的順序和唯一性，而值則是與鍵關聯的數據。鍵和值可以是任何類型，但通常使用類或結構體作為鍵類型，以提供自定義的比較規則。通過比較鍵的值，關聯式容器能夠按照鍵的順序進行有序存儲，并支持快速的查找操作。
鍵值對的定義：
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)
{}
};
set
介紹
set是C++標準庫中的一種關聯式容器，它用于存儲一組有序的、唯一的元素。set中的元素按照鍵值進行自動排序，并且不允許存在重復的元素。
set在底層是由二叉搜索樹（紅黑樹）實現的。
set中只放value，但在底層實際存放的是由<vlaue,value> 構成的鍵值對。
set中查找某個元素時，時間復雜度為：log_2 n .
使用
void test1()
{set<int> s;s.insert(1);s.insert(3);s.insert(3);s.insert(4);s.insert(6);s.insert(9);s.insert(7);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " " ;it++;}cout << endl;// 使用迭代器逆向打印set中的元素for (auto it = s.rbegin(); it != s.rend(); ++it){cout << *it << " ";}cout << endl;set<int>::iterator pos = s.find(7);if (pos != s.end()){cout << "找到了" << endl;s.erase(pos);}}
void test2()
{set<int> s;s.insert(1);s.insert(3);s.insert(3);//s.insert(4);s.insert(6);s.insert(9);s.insert(7);auto start = s.lower_bound(4);cout << *start << endl;auto finish = s.upper_bound(4);cout << *finish << endl;
}
muiltiset
multisetsC++標準庫中的一種關聯式容器，它與set容器類似，但允許存儲重復的元素。
muiltiset容器和set容器的主要區別在于對重復元素的處理。在set容器中，每個鍵值只能出現一次，而在muitiset容器中，同一個鍵值可以出現多次。multisey中的元素會根據鍵值自動進行排序。
void test3()
{multiset<int> s;s.insert(5);s.insert(1);s.insert(6);s.insert(3);s.insert(4);s.insert(5);s.insert(1);s.insert(1);s.insert(5);s.insert(1);s.insert(1);s.insert(2);s.insert(7);s.insert(10);multiset<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;//統計相同元素的個數cout << s.count(1) << endl;cout << s.count(5) << endl;
}
map
介紹
map是C++標準庫中的一種關聯式容器，它用于存儲一組鍵值對。每個元素都由一個唯一的鍵和對應的值組成。map中的元素按照鍵進行自動排序，并且不允許存在重復鍵。
在map內部，key和value通過成員類型value_type綁定在一起，為其取別名為pair；
typedef pair<const key,T> value_type;
map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value值；
map通常被實現為二叉搜索樹（平衡二叉搜索樹）.
使用
void test4()
{map<string, string> dict;dict.insert(pair<string, string>("sort", "排序"));//pair<string, string> kv("string", "字符串");pair<string, string> kv = { "string", "字符串" };dict.insert(kv);// C++11 多參數隱式類型轉換(構造函數)dict.insert({ "apple", "蘋果" });// C++98dict.insert(make_pair("sort", "排序"));for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;
}
void test5()
{string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
"蘋果", "香蕉", "蘋果", "西瓜", "香蕉", "草莓" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;//通過operator[]進行查找value值cout << countMap["蘋果"] << endl;
}
multimap
multimapC++標準庫中的一種關聯式容器，它與map容器類似，但允許存儲重復的鍵。
multimap容器和map容器的主要區別在于對重復鍵的處理方式。在multimap中，可以有很多個元素具有相同的鍵，這些元素會按照鍵進行自動排序，但不保證值的順序。
multimap中沒有重載operator[]操作；
使用時與map包含的頭文件相同。
