目錄
關聯式容器
鍵值對
set
set的概念
set的構造函數
set的使用
map
map的概念
map的構造函數
map的使用
multiset
multimap
關聯式容器
C++標準庫提供了多種容器，用于高效管理和操作數據集合。這些容器可分為以下幾類：
-
順序容器（Sequence Containers）
-
關聯容器（Associative Containers）
-
容器適配器（Container Adapters）
-
其他類容器類型
?順序容器：核心是元素的線性存儲，支持隨機或順序訪問
| 容器分類 | 容器類 | C++標準 | 描述 |
|---|---|---|---|
| 順序容器 | vector | C++98 | 動態數組，支持快速隨機訪問，尾部操作高效。 |
list | C++98 | 雙向鏈表，任意位置插入/刪除高效，不支持隨機訪問。 | |
deque | C++98 | 雙端隊列，頭尾插入/刪除高效，支持隨機訪問。 | |
array | C++11 | 固定大小數組，安全性優于內置數組，編譯時確定大小。 | |
forward_list | C++11 | 單向鏈表，節省內存，僅支持單向遍歷。 |
?關聯容器：基于鍵（Key）組織數據，有序容器（紅黑樹）與無序容器（哈希表）區分明顯。
| 有序關聯容器 | set | C++98 | 唯一鍵集合，基于紅黑樹，自動排序。 |
map | C++98 | 鍵值對集合（鍵唯一），基于紅黑樹，按鍵排序。 | |
multiset | C++98 | 允許重復鍵的集合，基于紅黑樹。 | |
multimap | C++98 | 允許重復鍵的鍵值對集合，基于紅黑樹。 | |
| 無序關聯容器 | unordered_set | C++11 | 唯一鍵哈希集合，基于哈希表，元素無序。 |
unordered_map | C++11 | 鍵值對哈希表（鍵唯一），基于哈希表。 | |
unordered_multiset | C++11 | 允許重復鍵的哈希集合。 | |
unordered_multimap | C++11 | 允許重復鍵的鍵值對哈希表。 |
容器適配器：通過限制接口實現特定數據結構（如棧、隊列、堆），底層依賴其他容器。
| 適配器 | stack | C++98 | 后進先出（LIFO）結構，默認基于std::deque實現。 |
queue | C++98 | 先進先出（FIFO）結構，默認基于std::deque實現。 | |
priority_queue | C++98 | 優先級隊列（最大堆），默認基于std::vector實現。 |
?其他類容器類型：如std::string和std::bitset，雖不是嚴格意義上的通用容器，但提供類似容器的操作。
| 其他類容器類型 | string | C++98 | 字符串類，支持類似vector的操作。 |
bitset | C++98 | 固定大小的位集合，用于位操作。 | |
valarray | C++98 | 數值計算專用數組，支持向量化操作。 | |
span | C++20 | 非擁有視圖，提供對連續內存的輕量訪問（如數組、vector等）。 |
鍵值對
鍵值對（Key-Value Pair）?是一種核心數據結構，用于將唯一的鍵（Key）?與對應的值（Value）?關聯，常用于快速查找、映射或配置管理。
-
鍵（Key）：唯一標識符，用于快速定位值（不可重復，除非使用?
multimap）。 -
值（Value）：與鍵關聯的數據，可以是任意類型（基本類型、對象、容器等）。
鍵值對類型?std::pair
-
定義：
std::pair<KeyType, ValueType>?是標準庫中表示鍵值對的模板類。 -
訪問成員：通過?
first（鍵）和?second（值）訪問。
pair<string, int> p("hello", 1);
cout << p.first << p.second << endl;
// hello1set
set的概念
set?是一個有序關聯容器，存儲唯一鍵（Key），鍵本身即為其值（沒有額外的Value）。
元素按鍵的嚴格弱序規則（默認升序）自動排序，不允許重復鍵。
| 特性 | 說明 |
|---|---|
| 唯一性 | 所有元素唯一，插入重復值會被忽略（通過返回值可判斷是否插入成功）。 |
| 自動排序 | 元素按鍵值自動排序（默認升序，可自定義排序規則）。 |
| 不可修改鍵 | 元素（鍵）在容器中不可直接修改，需先刪除舊值再插入新值。 |
| 高效查找 | 支持?O(log n)?復雜度的查找（find()、count()?等操作）。 |
| 穩定迭代器 | 插入或刪除操作不會使其他元素的迭代器失效（除非指向被刪除元素）。 |
- set在底層是用平衡搜索樹（紅黑樹）實現的，所以在set當中查找某個元素的時間復雜度為 logN
- set中的元素不能被修改，因為set在底層是用平衡搜索樹（紅黑樹）來實現的，若是對平衡搜索樹（紅黑樹）當中某個結點的值進行了修改，那么這棵樹將不再是平衡搜索樹（紅黑樹）
set的構造函數
1、默認構造函數：創建一個空的集合，可以指定自定義的比較器（Comparator）和分配器（Allocator）。
explicit set(const Compare& comp = Compare(), const Allocator& alloc = Allocator());set<int> s1; // 默認升序排序的空集合// 自定義降序排序的比較器
struct CompareDesc
{bool operator()(int a, int b) const { return a > b; }
};
set<int, CompareDesc> s2; // 降序排列的空集合2、范圍構造函數：通過迭代器范圍?[first, last)?初始化集合，元素會被自動去重并排序。
template <class InputIterator>
set(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& alloc = Allocator());vector<int> vec = {5, 2, 2, 3, 5};
// 從 vector 的迭代器范圍構造，自動去重并升序排序
std::set<int> s(vec.begin(), vec.end()); // s = {2, 3, 5}?3、拷貝構造函數：創建一個新集合，復制另一個集合的所有元素。
set(const set& other);set<int> s_original = {1, 2, 3};
set<int> s_copy(s_original); // 深拷貝，s_copy = {1, 2, 3}4、初始化列表構造函數（C++11 起）：通過初始化列表（Initializer List）直接初始化集合。
set(std::initializer_list<value_type> init, const Compare& comp = Compare(), const Allocator& alloc = Allocator());set<int> s = {3, 1, 2, 2}; // 自動去重并排序為 {1, 2, 3}
set的使用
| 成員函數 | 功能 |
|---|---|
| insert | 插入指定元素 |
| erase | 刪除指定元素 |
| find | 查找指定元素 |
| size | 獲取容器中元素的個數 |
| empty | 判斷容器是否為空 |
| clear | 清空容器 |
| swap | 交換兩個容器中的數據 |
| count | 獲取容器中指定元素值的元素個數 |
?示例：
#include <iostream>
#include <set>
#include <vector>
#include <algorithm> // 集合運算所需頭文件
using namespace std;// 自定義比較器（按字符串長度排序）
struct LengthCompare
{bool operator()(const string& a, const string& b) const {return a.size() < b.size();}
};int main()
{// ------------------------ 1. 初始化與插入 ------------------------set<int> s1 = {3, 1, 2, 2}; // 去重排序: {1, 2, 3}s1.insert(5); // 插入5s1.emplace(4); // 原地構造插入4// ------------------------ 2. 刪除與清空 ------------------------s1.erase(3); // 刪除元素3auto it = s1.find(1);if (it != s1.end()) s1.erase(it); // 通過迭代器刪除// s1.clear(); // 清空集合// ------------------------ 3. 遍歷與查找 ------------------------cout << "s1: ";for (int val : s1) { // C++11 范圍for遍歷cout << val << " "; // 輸出: 2 4 5}cout << endl;// 查找示例if (s1.count(4)) {cout << "4 exists in s1" << endl;}// ------------------------ 4. 自定義排序 ------------------------set<string, LengthCompare> s3 = {"apple", "banana", "cat"};// 按長度排序: "cat", "apple", "banana"cout << "s3: ";for (const auto& str : s3) {cout << str << " ";}cout << endl;return 0;
}map
map的概念
-
定義：
map?是一個有序關聯容器，存儲鍵值對（Key-Value Pair），其中鍵（Key）唯一，元素按鍵的嚴格弱序規則（默認升序）自動排序。
每個元素是一個?std::pair<const Key, Value>，鍵不可修改，值可以修改。 -
底層實現：
基于紅黑樹（Red-Black Tree，自平衡二叉搜索樹），保證插入、刪除和查找的時間復雜度為?O(log n)。
| 特性 | 說明 |
|---|---|
| 鍵唯一性 | 所有鍵唯一，插入重復鍵會被忽略（可通過返回值判斷是否成功）。 |
| 自動排序 | 元素按鍵自動排序（默認升序，可自定義排序規則）。 |
| 不可修改鍵 | 鍵在容器中不可直接修改，需先刪除舊鍵值對再插入新鍵。 |
| 高效查找 | 支持?O(log n)?復雜度的查找（find()、count()?等操作）。 |
| 穩定迭代器 | 插入或刪除操作不會使其他元素的迭代器失效（除非指向被刪除元素）。 |
map的構造函數
1、默認構造函數：創建一個空的?map，可指定自定義的比較器（Comparator）和分配器（Allocator）。
explicit map(const Compare& comp = Compare(), const Allocator& alloc = Allocator());map<int, string> m1; // 空map，默認按鍵升序排序// 自定義按字符串長度排序的比較器
struct KeyCompare {bool operator()(const string& a, const string& b) const {return a.size() < b.size();}
};
map<string, int, KeyCompare> m2; // 鍵按長度排序的空map2、范圍構造函數：通過迭代器范圍?[first, last)?初始化?map，鍵值對會被自動去重并排序。
template <class InputIterator>
map(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& alloc = Allocator());vector<pair<int, string>> vec = {{3, "Alice"}, {1, "Bob"}, {3, "Charlie"}};// 從vector的迭代器構造，自動去重并按鍵升序排序
map<int, string> m3(vec.begin(), vec.end()); // {1: "Bob", 3: "Alice"}3、拷貝構造函數：深拷貝另一個?map?的所有鍵值對。
map(const map& other);map<int, string> m_original = {{1, "A"}, {2, "B"}};
map<int, string> m_copy(m_original); // 深拷貝，m_copy = {1: "A", 2: "B"}4、初始化列表構造函數（C++11 起）：通過初始化列表直接初始化?map。
map(initializer_list<value_type> init, const Compare& comp = Compare(), const Allocator& alloc = Allocator());map<int, string> m5 = {{3, "Alice"}, {1, "Bob"}, {3, "Charlie"}}; // 去重后 {1: "Bob", 3: "Alice"}// 自定義降序排序
map<int, string, greater<int>> m6 = {{3, "A"}, {1, "B"}}; // {3: "A", 1: "B"}注意事項
-
鍵的唯一性：插入重復鍵時，
insert?會失敗，operator[]?會覆蓋原有值。 -
自定義比較器：需滿足嚴格弱序規則（例如不能定義?
<=?作為比較邏輯）。 -
性能權衡：若無需有序性，優先使用?
unordered_map（哈希表實現，平均 O(1) 操作）。
map的使用
| 接口分類 | 接口名稱 | 作用 |
|---|---|---|
| 插入操作 | insert | 插入鍵值對，返回插入結果（迭代器 + 是否成功）。 |
emplace | 原地構造鍵值對，避免臨時對象拷貝。 | |
operator[] | 通過鍵訪問值（若鍵不存在，插入默認值并返回引用）。 | |
| 刪除操作 | erase | 刪除指定鍵或迭代器范圍內的鍵值對。 |
clear | 清空所有鍵值對。 | |
| 查找與訪問 | find | 查找鍵，返回迭代器（未找到返回?end()）。 |
count | 返回鍵的數量（0 或 1）。 | |
contains?(C++20) | 檢查鍵是否存在，返回布爾值。 | |
at | 安全訪問值（鍵不存在時拋出異常）。 | |
| 容量查詢 | empty | 檢查容器是否為空。 |
size | 返回鍵值對數量。 | |
| 迭代器 | begin?/?end | 獲取正向迭代器（按鍵升序）。 |
rbegin?/?rend | 獲取反向迭代器（按鍵降序）。 |
?示例：
#include <iostream>
#include <map>
#include <string>
using namespace std;int main()
{map<int, string> m;// 插入操作m.insert({1, "Alice"});m.emplace(2, "Bob"); // 原地構造m[3] = "Charlie"; // operator[] 插入// 刪除操作m.erase(1); // 刪除鍵1// m.clear(); // 清空所有元素// 查找與訪問auto it = m.find(3);if (it != m.end()) {cout << "鍵3的值: " << it->second << endl;}// operator[] 的副作用（自動插入默認值）cout << "m[4]: " << m[4] << endl; // 輸出空字符串（自動插入{4, ""}）// 遍歷（C++17 結構化綁定）cout << "所有鍵值對:" << endl;for (const auto& [key, value] : m) {cout << key << ": " << value << endl;}// 容量查詢cout << "元素數量: " << m.size() << endl;cout << "是否為空: " << (m.empty() ? "是" : "否") << endl;return 0;
}multiset
multiset容器與set容器的底層實現一樣，都是平衡搜索樹（紅黑樹），multiset容器和set容器的唯一區別就是，multiset允許鍵值冗余，即multiset容器當中存儲的元素是可以重復的。
| 特性 | std::set | std::multiset |
|---|---|---|
| 鍵的唯一性 | 鍵唯一，不允許重復 | 允許重復鍵 |
| 插入操作 | 插入重復鍵時失敗（返回?pair<iterator, bool>） | 總是插入成功（返回?iterator） |
| 查找與計數 | count(key)?返回?0?或?1 | count(key)?可返回?>=0?的任意值 |
| 底層實現 | 紅黑樹（自平衡二叉搜索樹） | 紅黑樹（自平衡二叉搜索樹） |
| 時間復雜度 | 插入、刪除、查找均為?O(log n) | 同?set |
| 典型應用場景 | 需要唯一鍵的有序集合（如用戶ID集合） | 允許重復的有序集合（如統計成績分布） |
-
選擇?
set：需要保證鍵唯一性且需要有序遍歷的場景（如字典、配置表）。 -
選擇?
multiset：允許重復鍵且需要統計頻率或保留重復數據的場景（如日志時間戳記錄、投票統計）。
?
multimap
multimap容器與map容器的底層實現一樣，也都是平衡搜索樹（紅黑樹），multimap容器和map容器的區別，multimap允許鍵值冗余，即multimap容器當中存儲的元素是可以重復的
| 特性 | std::map | std::multimap |
|---|---|---|
| 鍵的唯一性 | 鍵唯一，不允許重復 | 允許重復鍵 |
| 插入操作 | 插入重復鍵時覆蓋原有值（operator[]）或失敗（insert） | 總是插入成功，允許多個相同鍵的鍵值對共存 |
| 查找與訪問 | operator[]?直接通過鍵訪問值（鍵不存在時插入） | 沒有?operator[]，必須通過迭代器訪問 |
| 查找結果 | find(key)?返回單個迭代器 | find(key)?返回第一個匹配鍵的迭代器 |
| 鍵值對數量 | 每個鍵對應唯一值 | 一個鍵可對應多個值 |
| 典型應用場景 | 字典、配置表（鍵唯一） | 一對多映射（如學生ID對應多門課程成績） |
-
選擇?
map：需要鍵唯一且直接通過鍵訪問值（如用戶ID到用戶名的映射）。 -
選擇?
multimap：允許鍵重復且需處理一對多關系（如訂單ID對應多個商品）。 -
關鍵區別：
-
map?的鍵唯一，支持?operator[]； -
multimap?允許鍵重復，需用迭代器或?equal_range?處理多個值。
-
?
)