C++set&map
1. 序列式容器和關聯式容器
1.1 序列式容器
序列式容器按照線性順序存儲元素,元素的位置取決于插入的時間和位置,與元素的值無關。
主要特點:
-
元素按插入順序存儲
-
可以通過位置(索引)直接訪問元素
-
不自動排序
-
允許重復元素
常見的序列式容器:
-
array(C++11)
-
固定大小的數組
-
內存連續分配
-
大小在編譯時確定
-
快速隨機訪問
-
-
vector
-
動態數組
-
內存連續分配
-
可動態擴展
-
在尾部插入/刪除高效
-
支持快速隨機訪問
-
-
deque(雙端隊列)
-
雙端可擴展
-
內存分段連續
-
在頭尾插入/刪除高效
-
支持快速隨機訪問(比vector稍慢)
-
-
list
-
雙向鏈表
-
內存非連續分配
-
在任何位置插入/刪除高效
-
不支持隨機訪問
-
-
forward_list(C++11)
-
單向鏈表
-
內存非連續分配
-
更節省空間
-
只支持單向遍歷
-
1.2 關聯式容器
關聯式容器按照特定順序存儲元素,元素的順序取決于元素的鍵(key),而不是插入的順序。
主要特點:
-
元素按特定順序(平衡二叉搜索樹或哈希)存儲
-
通過鍵(key)快速查找元素
-
通常實現為平衡二叉搜索樹或哈希表
-
有些版本不允許重復元素
常見的關聯式容器:
-
有序關聯容器(基于紅黑樹實現)
-
set:唯一鍵的集合,按鍵排序
-
map:鍵值對集合,按鍵排序,鍵唯一
-
multiset:鍵可重復的set
-
multimap:鍵可重復的map
-
-
無序關聯容器(C++11引入,基于哈希表實現)
-
unordered_set:唯一鍵的集合,基于哈希
-
unordered_map:鍵值對集合,基于哈希,鍵唯一
-
unordered_multiset:鍵可重復的unordered_set
-
unordered_multimap:鍵可重復的unordered_map
-
2. 認識pair類型
2.1 概念
pair
是C++標準模板庫(STL)中的一個實用模板類,用于將兩個值組合成一個單一對象,可以存儲兩個不同類型的元素,稱為first
和second
。這兩個值可以是相同類型,也可以是不同類型。它定義在<utility>
頭文件中,是許多STL容器(如map
)的基礎構建塊。
2.2 pair實現
template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;first_type first;second_type second;pair(): first(T1()), second(T2()) {} // 默認構造pair(const T1& a, const T2& b): first(a), second(b) {}template<class U, class V>pair (const pair<U,V>& pr): first(pr.first), second(pr.second) {} // 拷貝構造
};
為什么拷貝構造需要使用類中內嵌模板?
template <typename U1, typename U2> pair(const pair<U1, U2>& p);
?這個構造函數的存在是為了支持跨類型的拷貝構造,而不僅僅是同類型的拷貝構造。這是 C++ 模板類設計中的一個重要特性,稱為轉換構造函數。
-
類型轉換支持:
-
允許從?
pair<U1, U2>
?構造?pair<T1, T2>
-
只要?
U1
?可以轉換為?T1
,U2
?可以轉換為?T2
-
-
場景:
std::pair<int, double> p1(42, 3.14); std::pair<long, float> p2(p1); // 需要這個模板構造函數
-
與普通拷貝構造的區別:
-
普通拷貝構造:
pair(const pair<T1, T2>& p)
-
模板拷貝構造:
template <typename U1, typename U2> pair(const pair<U1, U2>& p)
-
-
如果沒有這個模板拷貝構造函數會怎么樣?
std::pair<int, std::string> p1(1, "hello"); std::pair<double, const char*> p2(p1); // 編譯錯誤 // 因為沒有從 pair<int,string> 到 pair<double,const char*> 的轉換路徑
2.3 創建和初始化pair
2.3.1 構造函數
std::pair<int, std::string> p1(1, "apple");
2.3.2 使用make_pair函數(自動推導類型)
make_pair函數模板原型:
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}
auto p2 = std::make_pair(2, "banana");
2.3.3 C++11-initializer_list初始化
std::pair<int, std::string> p3 = {3, "cherry"};
2.4 訪問pair成員
通過 first
和 second
訪問成員。
2.4.1 普通訪問
std::pair<int, std::string> p(1, "apple");std::cout << "First: " << p.first << std::endl; // 輸出: First: 1
std::cout << "Second: " << p.second << std::endl; // 輸出: Second: apple
2.4.2 結構化綁定(C++17)
auto p = std::make_pair(3.14, "pi");
auto [value, name] = p; // value=3.14, name="pi"
3. set
set
是C++ STL中的關聯式容器,它存儲唯一元素(key)并自動排序去重。
set原型
template < class T, class Compare = less<T>, class Alloc = allocator<T>> class set;
-
T就是set底層關鍵字(key)的類型
-
set默認要求T?持?于?較(仿函數less支持搜索樹大于往右走,小于往左走,greater則相反),若比較的類型和方式比較復雜,可以自己實現仿函數
-
set底層是?紅?樹實現,增刪查效率是O(logN) ,迭代器遍歷是?的搜索樹的中序,根據搜索樹的性質,遍歷是有序的
3.1 成員函數
3.1.1 成員類型
成員類型 | 解釋 |
---|---|
key_type | 第一個模板參數T |
value_type | 第一個模板參數T |
key_compare | 第二個模板參數(less仿函數) |
allocator_type | 第三個模板參數,STL空間配置器(內存池) |
3.1.2 構造函數
序號 | 函數原型 | 說明 |
---|---|---|
1?? | explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) | 默認構造 |
2?? | set (const set& x) | 拷貝構造 |
3?? | set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) | 使用 initializer_list 初始化 |
4?? | template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type()) | 使用一段迭代器區間初始化 |
3.1.3 賦值重載
序號 | 函數原型 | 說明 |
---|---|---|
1?? | set& operator= (const set& x) | 兩個已存在的 set 對象的賦值 |
2?? | set& operator= (initializer_list<value_type> il) | 使用 initializer_list 賦值 |
3.1.4 迭代器
序號 | 函數原型 | 說明 |
---|---|---|
1?? | iterator begin() | 返回指向 set 對象中第一個元素的迭代器 |
2?? | const_iterator begin() const | 返回指向 set 對象中第一個元素的 const 迭代器 |
3?? | iterator end() | 返回指向 set 對象末尾元素之后位置的迭代器 |
4?? | const_iterator end() const | 返回指向 set 對象末尾元素之后位置的 const 迭代器 |
5?? | reverse_iterator rbegin() | 返回指向 set 對象末尾元素的反向迭代器 |
6?? | const_reverse_iterator rbegin() const | 返回指向 set 對象末尾元素的 const 反向迭代器 |
7?? | reverse_iterator() rend() | 返回指向 set 對象起始元素之前位置的反向迭代器 |
8?? | const_reverse_iterator() rend() const | 返回指向 set 對象起始元素之前位置的 const 反向迭代器 |
注意:set迭代器是按中序的方式遍歷的。
3.1.5 容量相關的接口
序號 | 函數原型 | 說明 |
---|---|---|
1?? | bool empty() const | 判斷 set 對象是否為空 |
2?? | size_type size() const | 返回 set 對象中元素的數量 |
3.1.6 修改相關的接口
序號 | 函數原型 | 說明 |
---|---|---|
1?? | pair<iterator,bool> insert (const value_type& val) | 向 set 對象中插入 val 元素 |
2?? | iterator erase (const_iterator position) | 刪除 set 對象中 position 迭代器位置元素,返回刪除元素的下一個有效迭代器 |
3?? | size_type erase (const value_type& val) | 刪除 set 對象中 val 元素,返回值返回為刪除的 val 元素(0或1) |
4?? | void clear() | 清空 set 對象 |
pair<iterator,bool> insert (const value_type& val)
返回值解析返回值是一個
std::pair
,包含兩個部分:
iterator:指向插入元素的迭代器
如果插入成功:指向新插入的元素
如果插入失敗(元素已存在):指向已存在的元素
bool:表示插入是否成功
true
:元素被成功插入
false
:元素已存在,未插入新元素
3.1.7 其他
序號 | 函數原型 | 說明 |
---|---|---|
1?? | iterator find (const value_type& val) | 在 set 對象中查找 val 元素,成功返回該位置迭代器,失敗返回迭代器end() |
2?? | size_type count (const value_type& val) const | 返回 set 對象中 val 元素的數量(0或1) |
3.2 set與multiset的區別
set和multiset都是C++ STL中的關聯容器,它們的主要區別在于元素的唯一性。
主要區別
-
元素唯一性
-
set
:存儲唯一元素,不允許重復 -
multiset
:允許存儲重復元素
-
-
插入操作
-
向
set
插入已存在元素時,插入操作會失敗 -
向
multiset
可以重復插入相同元素
-
set與multiset接口一致。
對于包含重復元素的multiset,find接口會返回按照容器排序順序(默認是中序遍歷順序)出現的第一個與
key
相等的元素的迭代器。
4. map
map
是C++標準模板庫(STL)中的一個關聯容器,它存儲的元素是pair類型,并且根據鍵(key)自動排序去重。
map原型
template < class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key,T>> > class map;
map中存儲的pair類型
typedef pair<const Key, T> value_type;
-
Key就是map底層關鍵字的類型,T是map底層value的類型
-
map默認要求Key?持?于?較(仿函數less支持搜索樹大于往右走,小于往左走,greater則相反),若比較的類型和方式比較復雜,可以自己實現仿函數
-
map底層是?紅?樹實現,增刪查效率是O(logN) ,迭代器遍歷是?的搜索樹的中序,根據搜索樹的性質,遍歷是有序的
4.1 成員函數
4.1.1 成員類型
成員類型 | 解釋 |
---|---|
key_type | 第一個模板參數Key |
mapped_type | 第二個模板參數T |
value_type | map 中實際存儲的元素 pair<const key_type,mapped_type> |
key_compare | 第三個模板參數(less仿函數) |
allocator_type | 第死個模板參數,STL空間配置器(內存池) |
4.1.2 構造函數
序號 | 函數原型 | 說明 |
---|---|---|
1?? | explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) | 默認構造 |
2?? | map(const map& x) | 拷貝構造 |
3?? | map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) | 使用 initializer_list 初始化 |
4?? | template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type()) | 使用一段迭代器區間初始化 |
4.1.3 賦值重載
序號 | 函數原型 | 說明 |
---|---|---|
1?? | map& operator= (const map& x) | 兩個已存在的 map 對象的賦值 |
2?? | map& operator= (initializer_list<value_type> il) | 使用 initializer_list 賦值 |
4.1.4 迭代器
序號 | 函數原型 | 說明 |
---|---|---|
1?? | iterator begin() | 返回指向 map 對象中第一個元素的迭代器 |
2?? | const_iterator begin() const | 返回指向 map 對象中第一個元素的 const 迭代器 |
3?? | iterator end() | 返回指向 map 對象末尾元素之后位置的迭代器 |
4?? | const_iterator end() const | 返回指向 map 對象末尾元素之后位置的 const 迭代器 |
5?? | reverse_iterator rbegin() | 返回指向 map 對象末尾元素的反向迭代器 |
6?? | const_reverse_iterator rbegin() const | 返回指向 map 對象末尾元素的 const 反向迭代器 |
7?? | reverse_iterator() rend() | 返回指向 map 對象起始元素之前位置的反向迭代器 |
8?? | const_reverse_iterator() rend() const | 返回指向 map 對象起始元素之前位置的 const 反向迭代器 |
注意:map迭代器是按中序的方式遍歷的。
4.1.5 容量相關的接口
序號 | 函數原型 | 說明 |
---|---|---|
1?? | bool empty() const | 判斷 map 對象是否為空 |
2?? | size_type size() const | 返回 map 對象中元素的數量 |
4.1.6 元素的訪問
序號 | 函數原型 |
---|---|
1?? | mapped_type& operator[] (const key_type& k) |
map
?的?operator[]
?是一個非常有用的成員函數,它提供了對映射值的快速訪問和修改能力。
功能說明
-
查找與修改:如果鍵?
k
?存在于 map 中,返回對應的映射值(value)的引用 -
插入與修改:如果鍵?
k
?不存在,會自動插入一個新的鍵值對,鍵為?k
,值為?mapped_type
?的默認構造值,然后返回這個新值(value)的引用
operator[]實現
(*( (insert(make_pair(k,mapped_type()))).first).second)
解析
mapped_type& operator[] (const key_type& k) {pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}
4.1.7 修改相關的接口
序號 | 函數原型 | 說明 |
---|---|---|
1?? | pair<iterator,bool> insert (const value_type& val) | 向 map 對象中插入 val 元素 |
2?? | iterator erase (const_iterator position) | 刪除 map 對象中 position 迭代器位置元素,返回刪除元素的下一個有效迭代器 |
3?? | size_type erase (const key_type& val) | 刪除 map 對象中 val 元素,返回值返回為刪除的 val 元素(0或1) |
4?? | void clear() | 清空 map 對象 |
pair<iterator,bool> insert (const value_type& val)
返回值解析返回值是一個
std::pair
,包含兩個部分:
iterator:指向插入元素的迭代器
如果插入成功:指向新插入的元素
如果插入失敗(元素已存在):指向已存在的元素
bool:表示插入是否成功
true
:元素被成功插入
false
:元素已存在,未插入新元素
4.1.8 其他
序號 | 函數原型 | 說明 |
---|---|---|
1?? | iterator find (const value_type& val) | 在 map 對象中查找 val 元素,成功返回該位置迭代器,失敗返回迭代器end() |
2?? | size_type count (const value_type& val) const | 返回 map 對象中 val 元素的數量(0或1) |
4.2 map與multimap的區別
map和multimap都是C++ STL中的關聯容器,它們的主要區別在于元素的唯一性。
主要區別
-
元素唯一性
-
map
:存儲唯一元素,不允許重復 -
multimap
:允許存儲重復元素
-
-
插入操作
-
向
map
插入已存在元素時,插入操作會失敗 -
向
multimap
可以重復插入相同元素
-
-
operator[]
-
map
:支持operator[]
訪問 -
multimap
:不支持operator[]
,因為鍵不唯一
-
map與multimap接口一致。
對于包含重復元素的multimap,find接口會返回按照容器排序順序(默認是中序遍歷順序)出現的第一個與
key
相等的元素的迭代器。
5. set與map迭代器失效問題
- 只有指向被刪除元素的迭代器會失效
循環中刪除元素
std::set<int> s = {1, 2, 3, 4, 5};
for (auto it = s.begin(); it != s.end(); ) {if (*it % 2 == 0) {it = s.erase(it); // erase返回下一個有效迭代器} else {++it;}
}
今天的看不懂,會成為明天的太簡單。