C++容器的實踐與應用:輕松掌握set、map與multimap的區別與用法
- 一. 序列式容器與關聯式容器
- 1.1 序列式容器 (Sequential Containers)
- 1.2 關聯式容器 (Associative Containers)
- 二. set系列使用
- 2.1 set的構造和迭代器
- 2.2 set的增刪查
- 2.2.1 插入
- 2.2.2 查找
- 2.2.3 刪除
- 2.3 multiset和set的差異
- 三. map系列使用
- 3.1 pair類
- 3.1.1 定義與創建
- 3.1.2 訪問元素
- 3.2 map構造
- 3.3 map增刪查
- 3.3.1 插入
- 2.2.2 查找
- 2.2.3 刪除
- 3.4 map[]功能(重點)
- 3.4.1 基本功能
- 3.4.2 返回值類型
- 3.4.3 自動插入特性
- 3.5 multimap和map的差異
- 四. 最后
在C++中,容器是存儲和操作數據的核心工具。序列式容器(如vector、list)通過線性順序存儲數據,而關聯式容器(如set、map)則通過鍵值對存儲數據,允許更高效的查找、插入和刪除。set是一個存儲唯一元素的容器,內部自動排序,底層通常使用紅黑樹實現。它支持高效的查找和元素去重。map是存儲鍵值對的容器,每個鍵都是唯一的,值可以重復,同樣基于紅黑樹實現,提供快速的鍵值對查找。在需要快速檢索、插入或刪除元素時,set和map是非常實用的選擇。
一. 序列式容器與關聯式容器
1.1 序列式容器 (Sequential Containers)
序列式容器按照元素的插入順序進行存儲,它們提供了對元素的線性訪問。序列式容器的元素是有順序的,可以通過下標或迭代器來訪問。常見的序列式容器包括:
-
vector:動態數組,支持快速的隨機訪問。適用于頻繁訪問元素,但在中間插入或刪除元素時性能較差。
-
deque:雙端隊列,支持在兩端快速插入和刪除元素,但相比 vector,在訪問和修改元素時稍慢。
-
list:雙向鏈表,支持在任意位置快速插入和刪除元素,但不支持隨機訪問。
-
array:固定大小的數組,支持快速隨機訪問,但在大小固定時使用。
-
forward_list:單向鏈表,比 list 更節省內存,但只支持向前遍歷。
1.2 關聯式容器 (Associative Containers)
關聯式容器是基于鍵值對的容器,每個元素由鍵和值組成,并且通過鍵進行訪問。它們通常提供基于鍵的排序和查找功能,能夠高效地查找、插入和刪除元素。常見的關聯式容器包括:
-
set:存儲唯一元素的集合,自動排序。可以高效地判斷元素是否存在。
-
map:存儲鍵值對,其中每個鍵都是唯一的,值可以重復。自動按照鍵排序。
-
multiset:與 set 類似,但允許存儲重復的元素。
-
multimap:與 map 類似,但允許存儲重復的鍵。
聲明:本篇文章重點介紹關聯式容器中的set,map
二. set系列使用
set的底層是用紅黑樹實現的,增刪查效率是 O(logN),迭代器的遍歷是中序,所以是有序的。
2.1 set的構造和迭代器
set的迭代器是雙向迭代器,遍歷默認是升序的,因為底層說到底還是二叉搜索樹,所以迭代器(const和非const版本迭代器)都不支持修改數據,會破壞二叉搜索樹的結構。
構造類型 | 原型 | 功能 |
---|---|---|
無參默認構造 | explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type()); | 構造一個指定類型T的對象 |
迭代器區間構造 | template set(InputIterator first, InputIterator last,const key_compare & comp = key_compare(),const allocator_type & = allocator_type()); | 使用迭代器區間初始化對象 |
初始化列表構造 | set(initializer_list<value_type> il,const key_compare & comp = key_compare(),const allocator_type & alloc = allocator_type()); | 使用初始化列表構造對象 |
拷貝構造 | set (const set& x); | 使用拷貝構造對象 |
迭代器 | 原型 | 功能 |
正向迭代器 | iterator begin();iterator end() | 正向遍歷容器中的數據 |
反向迭代器 | reverse_iterator rbegin();reverse_iterator rend(); | 反向遍歷容器中的數據 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#include<iostream>
#include<set>
using namespace std;int main()
{//無參默認構造set<int> s1;cout << "修改前s1: ";for (auto ch : s1){cout <<"原:s1 " << ch;}cout << endl;//迭代器區間構造set<int> s2({ 1,2,3,4,5,6,7,8,9,10 });//initializer 列表構造//set<int> s1(s2.begin(), s2.end());錯誤寫法,s1重定義//使用賦值,或者直接插入//s1.insert(s2.begin(),s2.end())s1 = set<int>(s2.begin(), s2.end());//創建臨時對象,進行賦值cout << "修改后s1:";for (auto ch : s1){cout << ch << " ";}cout << endl;//拷貝構造set<int> s3(s1);cout << "s3: ";for (auto ch : s3){cout <<ch << " ";}cout << endl;// 正確的反向遍歷cout << "Reverse traversal of s3: ";for (auto rit = s3.rbegin(); rit != s3.rend(); ++rit) {cout << *rit << " ";}cout << endl;return 0;
}
2.2 set的增刪查
2.2.1 插入
類型 | 原型 | 功能 |
---|---|---|
單個插入 | pair<iterator,bool> insert (const value_type& val); | 插入單個數據,插入已經存在插入失敗 |
列表插入 | insert (initializer_list<value_type> il); | 使用初始化列表插入元素 |
迭代器區間插入 | template void insert(InputIterator first, InputIterator last); | 使用迭代器區間插入元素 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#include<iostream>
#include<set>
using namespace std;int main()
{int a = 10;set<int> s;s.insert(a);//插入單個數據for (auto ch : s){cout << ch;}cout << endl;s.insert({ 1,2,3,4,5,6,7,8,9 });//初始化列表插入for (auto ch : s){cout << ch<<" ";}cout << endl;set<int> s3({ 10,20,30,40,50,60,70,80,90,100 });s.insert(s3.begin(), s3.end());//迭代器區間插入數據for (auto ch : s){cout << ch << " ";}cout << endl;return 0;
}
2.2.2 查找
類型 | 原型 | 功能 |
---|---|---|
查找單個元素 | iterator find (const value_type& val); | 查找val,返回val所在的迭代器,沒有找到返回end() |
查找每個元素的總出現個數 | size_type count (const value_type& val) const; | 查找val,返回Val的個數 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#include<iostream>
#include<set>
using namespace std;int main()
{set<int> s;s.insert({ 1,2,3,4,5,6,7,8,9 });//初始化列表插入for (auto ch : s){cout << ch<<" ";}cout << endl;auto it = s.find(6);//存在返回所在迭代器cout << *it << endl;it = s.find(10);//不存在不可進行解引用//cout << *it << endl;error程序會終止int ret = s.count(6);cout << ret << endl;//查找6出現的總個數return 0;
}
2.2.3 刪除
類型 | 原型 | 功能 |
---|---|---|
刪除單個元素 | size_type erase (const value_type& val); | 刪除val,val不存在返回0,存在返回1 |
刪除迭代器位置 | iterator erase (const_iterator position); | 刪除?個迭代器位置的值 |
刪除迭代器區間 | iterator erase (const_iterator first, const_iterator last) | 刪除?段迭代器區間的值 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<set>
using namespace std;int main()
{set<int> s;s.insert({ 1,2,3,4,5,6,7,8,9 });//初始化列表插入cout << "刪除前: ";for (auto ch : s){cout << ch<<" ";}cout << endl;cout << "刪除5后: ";s.erase(5);//刪除單個值for (auto ch : s){cout << ch << " ";}cout << endl;cout << "刪除8后: ";auto it = s.find(8);s.erase(it);//刪除迭代器位置的值for (auto ch : s){cout << ch << " ";}cout << endl;cout << "全部刪除后: ";s.erase(s.begin(), s.end());//刪除迭代器區間區間的值,等效于s.clear()for (auto ch : s){cout << ch << " ";}cout << endl;return 0;
}
補充:
// 返回?于等val位置的迭代器
- iterator lower_bound (const value_type& val) const;
// 返回?于val位置的迭代器
- iterator upper_bound (const value_type& val) const;
2.3 multiset和set的差異
multiset和set的使?基本完全類似,主要區別點在于multiset?持值冗余,說白就是允許插入相同的值。
下面主要來看insert/find/count/erase都圍繞著?持值冗余有所差異,示例代碼:
```cpp
#include<iostream>
#include<set>
using namespace std;
int main()
{// 相?set不同的是,multiset是排序,但是不去重multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;// 相?set不同的是,x可能會存在多個,find查找中序的第?個int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;}cout << endl;// 相?set不同的是,count會返回x的實際個數cout << s.count(x) << endl;// 相?set不同的是,erase給值時會刪除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}
三. map系列使用
map的底層是紅黑樹,key/value結構場景,也是有序的。
3.1 pair類
在C++中,pair 是標準模板庫(STL)提供的一個模板類,用于將兩個可能不同類型的對象組合成一個單一單元。
3.1.1 定義與創建
#include // 包含pair的頭文件
// 創建pair的幾種方式
std::pair<int, double> p1; // 默認構造,兩個元素被值初始化
std::pair<int, double> p2(1, 3.14); // 直接初始化 std::pair<int,
double> p3 = {2, 2.718}; // 列表初始化(C++11起) auto p4 =
std::make_pair(3, 1.618); // 使用make_pair輔助函數
3.1.2 訪問元素
int first_element = p2.first; // 訪問第一個元素(int類型)
double second_element = p2.second; // 訪問第二個元素(double類型)
結論:pair 是C++中處理簡單二元組合的高效工具,在需要臨時組合兩個相關值時非常有用。對于更復雜的數據結構,建議使用 struct 或 class 來提高代碼可讀性。
3.2 map構造
map的迭代器是雙向迭代器,遍歷默認是升序的,因為底層說到底還是二叉搜索樹,所以迭代器(const和非const版本迭代器)都不支持修改數據,會破壞二叉搜索樹的結構。
構造類型 | 原型 | 功能 |
---|---|---|
無參默認構造 | explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type()); | 構造一個指定類型T的對象 |
迭代器區間構造 | template map(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type & = allocator_type()); | 使用迭代器區間初始化對象 |
初始化列表構造 | map(initializer_list<value_type> il,const key_compare & comp = key_compare(),const allocator_type & alloc = allocator_type()); | 使用初始化列表構造對象 |
拷貝構造 | map (const map& x); | 使用拷貝構造對象 |
迭代器 | 原型 | 功能 |
正向迭代器 | iterator begin();iterator end(); | 正向遍歷容器中的數據 |
反向迭代器 | reverse_iterator rbegin();reverse_iterator rend(); | 反向遍歷容器中的數據 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#include<iostream>
#include<map>
using namespace std;int main()
{//無參默認構造map<string, string> t1;for (auto entry : t1){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//初始化列表構造map<string, string> t2({{ "apple", "蘋果" }, { "banana", "香蕉" }, { "orange", "橙子" } });for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//迭代器區間構造map<string, string> t3(t2.begin(), t2.end());for (auto entry : t3){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//拷貝構造map<string, string> t4(t2);for (auto entry : t4){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//正向迭代器遍歷auto it = t4.begin();while (it != t4.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;//反向迭代器遍歷for (auto it = t4.rbegin(); it != t4.rend(); it++){cout << it->first << " " << it->second << endl;}return 0;
}
3.3 map增刪查
3.3.1 插入
類型 | 原型 | 功能 |
---|---|---|
單個插入 | pair<iterator,bool> insert (const value_type& val); | 單個數據插?,如果已經key存在則插?失敗,key存在相等value不相等也會插?失敗 |
列表插入 | void insert (initializer_list<value_type> il); | 列表插?,已經在容器中存在的值不會插? |
迭代器區間插入 | template void insert(InputIterator first, InputIterator last); | 使用迭代器區間插入元素 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#include<iostream>
#include<map>
using namespace std;int main()
{pair<string, string> s("insert", "插入");map<string, string> t1;t1.insert(s);//插入單個元素cout << "t1: ";for (auto entry : t1){cout << entry.first << " -> " << entry.second << endl;}cout << endl;map<string, string> t2;t2.insert({ { "apple", "蘋果" }, { "banana", "香蕉" }, { "orange", "橙子" } });//初始化列表插入cout << "t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;map<string, string> t3;t3.insert(t2.begin(), t2.end());//迭代器區間插入cout << "t3: ";for (auto entry : t3){cout << entry.first << " -> " << entry.second << endl;}cout << endl;return 0;
}
2.2.2 查找
類型 | 原型 | 功能 |
---|---|---|
查找單個元素 | iterator find (const value_type& val); | 查找val,返回val所在的迭代器,沒有找到返回end() |
查找每個元素的總出現個數 | size_type count (const value_type& val) const; | 查找val,返回Val的個數 |
下面將給出一個整合代碼演示上述的功能:
- 示例代碼:
#include<iostream>
#include<map>
using namespace std;int main()
{map<string, string> t2;t2.insert({ { "apple", "蘋果" },{ "apple", "蘋果" },{ "apple", "蘋果" }, { "banana", "香蕉" }, { "orange", "橙子" } });//初始化列表插入cout << "t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}auto it = t2.find("apple");//返回apple位置所在的迭代器cout << it->first << " " << it->second << endl;int ret = t2.count("apple");//查找apple出現的總次數cout << ret << endl;return 0;
}
2.2.3 刪除
類型 | 原型 | 功能 |
---|---|---|
刪除單個元素 | size_type erase (const value_type& val); | 刪除val,val不存在返回0,存在返回1 |
刪除迭代器位置 | iterator erase (const_iterator position); | 刪除?個迭代器位置的值 |
刪除迭代器區間 | iterator erase (const_iterator first, const_iterator last) | 刪除?段迭代器區間的值 |
示例代碼:
#include<iostream>
#include<map>
using namespace std;int main()
{map<string, string> t2;t2.insert({ { "apple", "蘋果" },{ "apple", "蘋果" },{ "apple", "蘋果" }, { "banana", "香蕉" }, { "orange", "橙子" } });//初始化列表插入cout << "刪除前t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;t2.erase("apple");//刪除指定元素值cout << "前t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;auto it = t2.find("orange");t2.erase(it);//刪除迭代器位置的值cout << "中t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;t2.erase(t2.begin(), t2.end());//刪除迭代器區間的值cout << "后t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}return 0;
}
3.4 map[]功能(重點)
3.4.1 基本功能
- 訪問元素:如果鍵存在于map中,operator[]會返回該鍵對應的值的引用。
- 修改元素:通過返回的引用,可以直接修改該鍵對應的值。
- 插入元素:如果鍵不存在于map中,operator[]會插入一個新的鍵值對,其中鍵是給定的鍵,值是值類型的默認構造值(對于內置類型如int、string等,默認構造值通常是0或空字符串;對于自定義類型,則是其默認構造函數創建的對象)。
3.4.2 返回值類型
operator[]返回的是值的引用(value_type&),這允許對值進行直接修改。
3.4.3 自動插入特性
當使用operator[]訪問一個不存在的鍵時,map會自動插入一個新的鍵值對。
新插入的鍵的值部分是其值類型的默認構造值。
- 使用實例:
#include<iostream>
#include<map>
#include<string>
using namespace std;int main() {map<string, int> wordCount;// 訪問并修改現有元素wordCount["apple"] = 10; // 插入或修改鍵為"apple"的元素cout << "apple: " << wordCount["apple"] << endl; // 輸出: apple: 10// 訪問不存在的鍵,自動插入新元素cout << "banana: " << wordCount["banana"] << endl; // 輸出: banana: 0(因為int的默認構造值是0)// 修改自動插入的元素wordCount["banana"] += 5;cout << "banana: " << wordCount["banana"] << endl; // 輸出: banana: 5// 使用at()方法訪問元素(需要確保鍵存在)try {cout << "orange: " << wordCount.at("orange") << endl;} catch (const out_of_range& e) {cout << "orange: " << e.what() << endl; // 輸出: orange: map::at: key not found}return 0;
}
3.5 multimap和map的差異
multimap和map的使?基本完全類似,主要區別點在于multimap?持關鍵值key冗余,那么
insert/find/count/erase都圍繞著?持關鍵值key冗余有所差異,
- 示例代碼:
#include <iostream>
#include <map>
#include <string>using namespace std;int main() {// 創建multimap并插入數據multimap<string, int> scores = {{"Alice", 90},{"Bob", 85},{"Alice", 95}, // 允許重復的key{"Charlie", 88}};// 1. 查找操作(返回第一個匹配項)auto it = scores.find("Alice");if (it != scores.end()) {cout << "找到Alice的第一個分數: " << it->second << endl; // 輸出90}// 2. 計數操作(統計重復key的數量)int count = scores.count("Alice");cout << "Alice出現的次數: " << count << endl; // 輸出2// 3. 范圍查找(獲取所有匹配項)cout << "所有Alice的分數: ";auto range = scores.equal_range("Alice");for (auto itr = range.first; itr != range.second; ++itr) {cout << itr->second << " "; // 輸出90 95}cout << endl;// 4. 刪除操作(刪除所有匹配項)scores.erase("Alice");cout << "刪除Alice后剩余元素數量: " << scores.size() << endl; // 輸出2(Bob和Charlie)// 5. 嘗試使用[]操作符(會編譯失敗)// scores["David"] = 78; // 錯誤:multimap不支持[]操作符return 0;
}
通過這個示例可以看出,multimap在處理需要多個相同key的場景時比map更靈活,但相應地也失去了一些特性(如[]操作符的直接訪問能力)。在實際開發中,應根據是否需要key唯一性來選擇合適的數據結構。
四. 最后
本文詳述了C++中關聯式容器set、multiset、map、multimap的用法,涵蓋構造、迭代器、增刪查等操作。set自動排序去重,multiset允許重復;map存儲鍵值對,multimap支持鍵冗余。重點解析了map的[]操作符自動插入特性及multimap的范圍查找。通過代碼示例展示了各容器的核心功能與應用場景,是學習C++標準庫關聯容器的實用指南。