C++中map和set的使用示例詳解
1. 序列式容器和關(guān)聯(lián)式容器
1.1 序列式容器
核心特征
- 按插入順序存儲:元素的物理存儲順序與插入順序一致。
- 允許重復元素:可以存儲多個相同的值。
- 通過位置訪問:通過索引(如數(shù)組)或迭代器直接訪問元素。
常見容器
vector
:動態(tài)數(shù)組,支持快速隨機訪問,尾部插入高效。list
:雙向鏈表,支持快速插入/刪除,但隨機訪問效率低。deque
:雙端隊列,支持頭尾高效插入/刪除。array
:固定大小數(shù)組,編譯時確定大小。forward_list
:單向鏈表,內(nèi)存占用更小。
適應場景
- 需要保持插入順序(如日志記錄,操作歷史)。
- 頻繁通過索引隨機訪問(如vector的[ ]操作)。
- 需要高效頭尾操作(如deque)。
1.2 關(guān)聯(lián)式容器
- 核心特征
- 按鍵存儲:元素基于鍵值對(key-value)鍵本身存儲。
- 自動排序:元素按鍵的排序規(guī)則(默認升序)組織。
- 唯一性:
set
和map
要求鍵唯一;multiset
和multimap
允許重復鍵。
- 常見容器
set
:存儲唯一鍵的有序集合。map
:存儲鍵值對的有序映射。multiset
:允許重復鍵的有序集合。multimap
:允許重復鍵的有序映射。
- 適用場景
- 需要快速查找(如字典,數(shù)據(jù)庫索引)。
- 需自動排序(如排行榜,有序事件調(diào)度)。
- 需要唯一性約束(如用戶ID管理)。
2. set系列的使用
2.1 set和multiset的參考文檔
2.2 set類的介紹
set
的聲明如下,T就是set
底層關(guān)鍵字的類型。set
默認要求T支持小于比較,如果不支持,可以手動實現(xiàn)一個仿函數(shù)傳給第二個模板參數(shù)。set
底層存儲數(shù)據(jù)的內(nèi)存是從空間配置器上申請的,如果需要可以自己手動實現(xiàn)一個內(nèi)存池,傳給第三個參數(shù)。一般情況下我們都不需要傳后面的兩個模板參數(shù)。set
的底層是用紅黑樹實現(xiàn)的,增刪查的效率是O(logn),迭代器遍歷走的是搜索樹的中序遍歷,所以遍歷后的元素是有序的。
template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;
2.3 set的構(gòu)造函數(shù)和迭代器
set
的構(gòu)造我們只需關(guān)注一下幾個即可
//empty (1) 無參默認構(gòu)造 explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器區(qū)間構(gòu)造 template <class InputIterator> set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type & = allocator_type()); // copy (3) 拷?構(gòu)造 set (const set& x); // initializer list (5) initializer 列表構(gòu)造 set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
迭代器
// 迭代器是?個雙向迭代器 iterator -> a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();
2.4 set的增刪查
#include <iostream> #include <set> using namespace std; int main() { //去重+升序排序 set<int> s; //去重+降序排序,給一個大于的仿函數(shù) //set<int, greater<int>> s; //set<int, greater<int>> s = {1,2,7,4,9,6,}; initializer_list初始化 s.insert(2); s.insert(1); s.insert(5); s.insert(6); //set<int> iterator it = s.begin(); auto it = s.begin(); while (it != s.end()) { //*it = 1;不能修改里面的值 cout << *it << " "; it++; } cout << endl; //插入一段initilizer_list的值,已經(jīng)存在則插入失敗 s.insert({1,5,3,2,7,9}); for (auto e : s) { cout << e << " "; } cout << endl; //插入string類對象,string類對象比較是按照ascll碼來比較大小的 set<string> strset = {"sort","add","insert"}; for (auto &e : strset) { cout << e << " "; } cout << endl; return 0; }
2.5 find和erase的使用樣例
erase
,find
的使用案例:
int main() { set<int> s = {2,7,4,3,1,9,5,0}; for (auto& e : s) { cout << e << " "; } cout << endl; //刪除最小值 s.erase(s.begin()); for (auto& e : s) { cout << e << " "; } cout << endl; //刪除輸入的值,這個值有可能在,也有可能不在 int x; cin >> x; int num = s.erase(x); if (num == 0) { cout << x << "不存在!" << endl; } for (auto& e : s) { cout << e << " "; } cout << endl; //直接查找,再利用迭代器刪除 cin >> x; auto pos = s.find(x); if (pos != s.end()) { s.erase(pos); } else { cout << x << "不存在" << endl; } for (auto& e : s) { cout << e << " "; } cout << endl; //算法庫中的查找O(n) 不會這樣使用 auto pos1 = find(s.begin(), s.end(), x); //set自己實現(xiàn)的查找O(logn) auto pos2 = s.find(x); //利用cout快速實現(xiàn)間接查找 cin >> x; if (s.count(x)) { cout << x << "在!" << endl; } else { cout << x << "不存在!" << endl; } return 0; }
刪除一段區(qū)間的值
int main() { set<int> myset; for (int i = 1; i < 10; i++) { myset.insert(i * 10);//10 20 30 40 50 60 70 80 90 } for (auto e : myset) { cout << e << " "; } cout << endl; //實現(xiàn)查找到的[itlow,itup]包含[30,60]區(qū)間 //返回>=30 auto itlow = myset.lower_bound(30); //返回>60 auto itup = myset.upper_bound(60); //刪除這段區(qū)間的值 myset.erase(itlow,itup); for (auto e : myset) { cout << e << " "; } cout << endl; return 0; }
2.6 multiset和set的差異
multiset
和set
基本完全相似,主要的區(qū)別點在于multiset
支持鍵值冗余,那么insert
/find
/count
/erase
都圍繞著支持鍵值冗余有所差異。
int main() { multiset<int> s = {4,6,4,3,6,7,8,9,2,5,3,7,8,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的實際個數(shù) cout << s.count(x) << endl; //相比set不同的是erase會刪掉里面的所有的x s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }
2.7 兩個數(shù)組的交集 - 力扣(LeetCode)
題目連接: 349. 兩個數(shù)組的交集
解題思路:
兩個數(shù)組依次比較,小的++,相等的就是交集,同時++,其中一個結(jié)束就結(jié)束了
代碼實現(xiàn):
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { //這里用set實現(xiàn)了對數(shù)組的排序+去重 set<int> s1(nums1.begin(),nums1.end());//用一段迭代器區(qū)間初始化 set<int> s2(nums2.begin(),nums2.end()); //小的++,相等就是交集 vector<int> ret; auto it1 = s1.begin(); auto it2 = s2.begin(); while(it1 != s1.end() && it2 != s2.end()) { if(*it1 < *it2) it1++; else if (*it1 > *it2) it2++; else { ret.push_back(*it1); it1++; it2++; } } return ret; } };
2.8 環(huán)形鏈表 II - 力扣(LeetCode)
題目鏈接: 142. 環(huán)形鏈表 II
解題思路:
遍歷這個環(huán)形鏈表,如果count
為0,就把此節(jié)點插入進set
,如果不為0,則此節(jié)點為入口點。
代碼實現(xiàn):
class Solution { public: ListNode *detectCycle(ListNode *head) { set<ListNode*> s; ListNode* cur = head; while(cur) { if(s.count(cur)) return cur;//等于1即為入口點 else s.insert(cur); cur = cur -> next; } return nullptr; } };
3. map系列的使用
3.1 map和multimap的參考文檔
3.2 map類的介紹
map
的聲明如下,Key就是map底層關(guān)鍵字的類型,T是map底層Value的類型,map默認要求Key支持小于比較,如果不支持或者需要的話可以自行實現(xiàn)仿函數(shù)傳給第二個模板參數(shù)。map
底層存儲數(shù)據(jù)的內(nèi)存是從空間配置器申請的。一般情況下我們都不需要傳后面兩個模板參數(shù)。map
的底層使用紅黑樹實現(xiàn)的,增刪查改的效率是O(logn),迭代器遍歷走的是中序遍歷,所以Key的值是有序的。
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key,T> > // map::allocator_type > class map
3.3 pair類型介紹
map
底層紅黑樹節(jié)點中的數(shù)據(jù),使用pair<Key,T>存儲鍵值對數(shù)據(jù)。pair
是一個類模板,里面有兩個成員變量,一個是first
,一個是second
。
typedef pair<const Key, T> value_type; 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) {} template<class U, class V> pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {} }; template <class T1, class T2> inline pair<T1, T2> make_pair(T1 x, T2 y) { return (pair<T1, T2>(x, y)); }
3.4 map的構(gòu)造
map
的構(gòu)造我們只需關(guān)注以下接口即可map
支持正向迭代器遍歷和反向迭代器遍歷,遍歷默認按Key的升序,因為底層是二叉搜索樹,走的是中序遍歷。支持迭代器也就支持范圍for。map
支持value
數(shù)據(jù)的修改,但不支持Key
的修改。修改關(guān)鍵字的數(shù)據(jù)破壞了底層搜索樹的結(jié)構(gòu)。
// empty (1) ?參默認構(gòu)造 explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器區(qū)間構(gòu)造 template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type()); // copy (3) 拷?構(gòu)造 map (const map& x); // initializer list (5) initializer 列表構(gòu)造 map (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // 迭代器是?個雙向迭代器 iterator -> a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();
3.5 map的增刪查
map
的增刪查關(guān)注以下接口即可map
的增接口,插入的是pair的鍵值對數(shù)據(jù),跟set
有所不同,但是查和刪的接口只用關(guān)鍵字Key,跟set
完全相似。不過fin返回的是iterator
,不僅僅可以找到Key在不在,還能找到映射的Value,同時通過迭代還能修改Value。
Member types key_type->The first template parameter(Key) mapped_type->The second template parameter(T) value_type->pair<const key_type, mapped_type> // 單個數(shù)據(jù)插?,如果已經(jīng)key存在則插?失敗,key存在相等value不相等也會插?失敗 pair<iterator, bool> insert(const value_type& val); // 列表插?,已經(jīng)在容器中存在的值不會插? void insert(initializer_list<value_type> il); // 迭代器區(qū)間插?,已經(jīng)在容器中存在的值不會插? template <class InputIterator> void insert(InputIterator first, InputIterator last); // 查找k,返回k所在的迭代器,沒有找到返回end() iterator find(const key_type& k); // 查找k,返回k的個數(shù) size_type count(const key_type& k) const; // 刪除?個迭代器位置的值 iterator erase(const_iterator position); // 刪除k,k存在返回0,存在返回1 size_type erase(const key_type& k); // 刪除?段迭代器區(qū)間的值 iterator erase(const_iterator first, const_iterator last); // 返回?于等k位置的迭代器 iterator lower_bound(const key_type& k); // 返回?于k位置的迭代器 const_iterator lower_bound(const key_type& k) const;
3.6 map的數(shù)據(jù)修改
map第一個支持修改的方式是通過迭代器,迭代器遍歷時或者find返回Key所在的iterator修改。map還有一個非常重要的修改接口operator[]
,但是operator[]
不僅僅支持數(shù)據(jù)的修改,還支持插入數(shù)據(jù)和查找數(shù)據(jù),所以它是一個多功能復合接口。
Member types key_type->The first template parameter(Key) mapped_type->The second template parameter(T) value_type->pair<const key_type, mapped_type> // 查找k,返回k所在的迭代器,沒有找到返回end(),如果找到了通過iterator可以修改key對應的mapped_type值 iterator find(const key_type& k); // ?檔中對insert返回值的說明 // The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to theelement with an equivalent key in the map.The pair::second element in the pairis set to true if a new element was inserted or false if an equivalent keyalready existed. // insert插??個pair<key, T>對象 // 1、如果key已經(jīng)在map中,插?失敗,則返回?個pair<iterator,bool>對象,返回pair對象first是key所在結(jié)點的迭代器,second是false // 2、如果key不在map中,插?成功,則返回?個pair<iterator,bool>對象,返回pair對象first是新插?key所在結(jié)點的迭代器,second是true // 也就是說?論插?成功還是失敗,返回pair<iterator,bool>對象的first都會指向key所在的迭代器 // 那么也就意味著insert插?失敗時充當了查找的功能,正是因為這?點,insert可以?來實現(xiàn) operator[] // 需要注意的是這?有兩個pair,不要混淆了,?個是map底層紅?樹節(jié)點中存的pair<key, T>,另?個是insert返回值pair<iterator, bool> pair<iterator, bool> insert(const value_type & val); mapped_type& operator[] (const key_type& k); // operator的內(nèi)部實現(xiàn) mapped_type& operator[] (const key_type& k) { // 1、如果k不在map中,insert會插?k和mapped_type默認值(默認值是用默認構(gòu)造構(gòu)造的),同時[]返回結(jié)點中存儲mapped_type值的引?,那么我們可以通過引?修改返映射值。所以[]具備了插? + 修改功能 // 2、如果k在map中,insert會插?失敗,但是insert返回pair對象的first是指向key結(jié)點的迭代器,返回值同時[]返回結(jié)點中存儲mapped_type值的引?,所以[]具備了查找 + 修改的功能 pair<iterator, bool> ret = insert({ k, mapped_type() }); iterator it = ret.first; return it->second; }
3.7 構(gòu)造遍歷以及增刪查改樣例
#include <map> int main() { pair<string, string> kv1 = {"left","左邊"}; //initializer_list構(gòu)造以及迭代遍歷 map<string, string> dict = { {"left","左邊"},{"right","右邊"},{"insert","插入"},{"erase","刪除"}}; map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { //cout << *it << " "; //pair不支持流提取和流插入,是一個結(jié)構(gòu)體 //cout << (*it).first << ":" << (*it).second << endl;; cout << it->first << ":" << it->second << endl; //cout << it.operator->()->first << ":" << it.operator->()->second << endl;//原生寫法 ++it; } //map的插入 //insert插入pair的四種方式,對比之下最后一種最方便 pair<string, string> kv2("first","第一個"); dict.insert(kv2); //匿名對象 dict.insert(pair<string, string>("second", "第二個")); //make_pair dict.insert(make_pair("sort","排序"));//make_pair是一個函數(shù)模板,不用聲明模板參數(shù),自己推導,在底層構(gòu)造一個pair對象再返回 //最后一種最好用 dict.insert({"auto","自動的"});//支持隱式類型轉(zhuǎn)換 //支持范圍for遍歷 for (auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; //結(jié)構(gòu)化綁定 C++17 //for (const auto& [k,v] : dict) //{ // cout << k << ":" << v << endl; //} string str; while (cin >> str) { auto ret = dict.find(str); if (ret != dict.end()) { cout << "->" << ret->second << endl; } else { cout << "無此單詞,請重新輸入" << endl; } } //first是不能被修改的,但是second可以被修改 return 0; }
3.8 map的迭代器功能和[]功能樣例
統(tǒng)計水果出現(xiàn)的次數(shù)
#include <iostream> #include <string> #include <map> using namespace std; int main() { //統(tǒng)計水果出現(xiàn)的次數(shù) string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜","蘋果", "香蕉", "蘋果", "香蕉" }; map<string, int> countMap; //先查找水果在不在map中 //1.不在,說明水果第一次出現(xiàn),則插入水果{水果,1} //2.在,則查找到的水果對應的次數(shù)+1 for (const auto& str : arr) { auto ret = countMap.find(str); if (ret == countMap.end())//則證明在 { countMap.insert({str,1}); } //否則,在 else { ret->second++; } } //countMap[str]++; 第二種寫法 for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0; }
3.9 multimap和map的差異
multimap和map的使用基本完全類似,主要區(qū)別是multimap支持關(guān)鍵字Key冗余,那么insert
/find
/count
/erase
都圍繞著支持鍵值冗余有所差異。這里和set
和multiset
基本一樣,比如find時有多個key返回中序中的第一個。其次是multimap不支持[],因為支持key冗余,[]就只能支持插入了,不支持修改。
3.10 隨機鏈表的復制 - 力扣(LeetCode)
題目連接: 138. 隨機鏈表的復制
解題思路: 讓原鏈表與拷貝鏈表通過map
建立映射關(guān)系
代碼實現(xiàn):
class Solution { public: Node* copyRandomList(Node* head) { map<Node*,Node*> nodeMap; Node* copyhead = nullptr,*copytail = nullptr;//定義一個頭一個尾 Node* cur = head; while(cur) { //如果為空 if(copytail == nullptr) { copyhead = copytail = new Node(cur->val); } //如果不為空 else { copytail->next = new Node(cur->val); copytail = copytail->next; } //讓原節(jié)點和拷貝節(jié)點建立map nodeMap[cur] = copytail; cur = cur->next; } //處理random cur = head; Node* copy = copyhead; while(cur) { //原鏈表的random為空,則拷貝鏈表的random也為空 if(cur->random == nullptr) { copy->random = nullptr; } else { copy->random = nodeMap[cur->random]; } cur = cur->next; copy = copy->next; } return copyhead; } };
3.11 前K個高頻單詞 - 力扣(LeetCode)
題目鏈接: 692. 前K個高頻單詞
解題思路1:
用排序找前k個單詞,因為map中已經(jīng)對Key單詞排序過,也就意味著遍歷map時次序相同的單詞,字典序小的在前面,字典序大的在后面,那么我們將數(shù)據(jù)放到vector中用一個穩(wěn)定的排序就可以實現(xiàn)上面特殊的要求,但sort底層是快排,是不穩(wěn)定的,所以我們要用table_sort
,是穩(wěn)定的。
代碼實現(xiàn):
class Solution { public: struct Compare { bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) { return kv1.second > kv2.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { //統(tǒng)計次數(shù) map<string,int> countMap; for(auto &str : words) { countMap[str]++; } vector<pair<string,int>> v(countMap.begin(),countMap.end());//迭代器區(qū)間初始化 stable_sort(v.begin(),v.end(),Compare()); vector<string> retv; for(size_t i = 0; i < k ; ++i) { retv.push_back(v[i].first);//取的是每個pair對象中的單詞 } return retv; } };
解題思路2:
將map統(tǒng)計出來的次序,放到vector中排序,或者放到priority_queue中選出前k個,利用仿函數(shù)強制控制次數(shù)相等的,字典序小的在前面。
代碼實現(xiàn):
class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) { return x.second > y.second || (x.second == y.second && x.first < y.first);; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for (auto& e : words) { countMap[e]++; } vector<pair<string, int>> v(countMap.begin(), countMap.end()); // 仿函數(shù)控制降序,仿函數(shù)控制次數(shù)相等,字典序?的在前? sort(v.begin(), v.end(), Compare()); // 取前k個 vector<string> strV; for (int i = 0; i < k; ++i) { strV.push_back(v[i].first); } return strV; } };
class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { // 要注意優(yōu)先級隊列底層是反的,?堆要實現(xiàn)?于?較,所以這?次數(shù)相等,想要字典序?的在前?要?較字典序?的為真 return x.second < y.second || (x.second == y.second && x.first > y.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for (auto& e : words) { countMap[e]++; } // 將map中的<單詞,次數(shù)>放到priority_queue中,仿函數(shù)控制?堆,次數(shù)相同按照字典序規(guī)則排序 priority_queue<pair<string, int>, vector<pair<string, int>>, Compare>p(countMap.begin(), countMap.end()); vector<string> strV; for (int i = 0; i < k; ++i) { strV.push_back(p.top().first); p.pop(); } return strV; }
到此這篇關(guān)于C++ map和set的使用的文章就介紹到這了,更多相關(guān)C++ map和set使用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c++中struct和class的區(qū)別小結(jié)
在C++中,class和struct都是用于定義自定義數(shù)據(jù)類型的關(guān)鍵字,本文主要介紹了c++中struct和class的區(qū)別小結(jié),具有一定的參考價值,感興趣的可以了解一下2023-08-08