C++中set/multiset與map/multimap的使用詳解
一、關(guān)聯(lián)式容器
vector、list、deque、forward_list(C++11)等，這些容器統(tǒng)稱為序列式容器，因為其底層為線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身。
而關(guān)聯(lián)式容器也是用來存儲數(shù)據(jù)的，與序列式容器不同的是，其里面存儲的是<key, value>結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時比序列式容器效率更高。 （插入刪除只需挪動指針指向，無需挪動數(shù)據(jù)，查找時間logN）
關(guān)聯(lián)式容器有兩種，一種是map、set、multimap、multiset采用樹形結(jié)構(gòu)，他們的底層都是紅黑樹，另一種是哈希結(jié)構(gòu)。
二、set的介紹
1、set是關(guān)聯(lián)式容器，它表面上只存放value，實際底層中存放的是由<value,value>組成的鍵值對。
2、set調(diào)用find將采用中序遍歷，可以用于排序+去重。
3、為了保證元素的唯一性，set中的元素均為const，所以并不能對元素進行修改，但可以進行插入刪除。
1、接口count與容器multiset
count和find的作用一樣，都是用于查找set中是否存在某個元素。
其實count是為了容器multiset設(shè)計的，該容器允許插入重復(fù)的元素，此時count會返回紅黑樹中被搜索元素的個數(shù)。
#include <iostream>
#include <set>
int main ()
{
std::set<int> myset;
// set some initial values:
for (int i=1; i<5; ++i) myset.insert(i*3); // set: 3 6 9 12
for (int i=0; i<10; ++i)
{
std::cout << i;
if (myset.count(i)!=0)
std::cout << " is an element of myset.\n";
else
std::cout << " is not an element of myset.\n";
}
return 0;
}2、接口lower_bound和upper_bound
lower_bound返回大于等于目標值的迭代器，upper_bound返回大于目標值的迭代器，在set中用于返回目標值的迭代器。（比如找到兩個邊界的迭代器，就可以使用erase對數(shù)據(jù)進行刪除）
#include <iostream>
#include <map>
int main ()
{
std::map<char,int> mymap;
std::map<char,int>::iterator itlow,itup;
mymap['a']=20;
mymap['b']=40;
mymap['c']=60;
mymap['d']=80;
mymap['e']=100;
itlow=mymap.lower_bound ('b'); // itlow points to b
itup=mymap.upper_bound ('d'); // itup points to e (not d!)
mymap.erase(itlow,itup); // a => 20 e => 100
// print content:
for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
return 0;
}三、map的介紹
map是關(guān)聯(lián)式容器，根據(jù)特定的存儲順序，用于存儲由鍵值及其映射值組合的元素。
可以看到Alloc中有一個鍵值對pair，這個pair是一個key/value結(jié)構(gòu)的struct模板類。這個類將一對鍵值耦合在一起，所以，map的存儲方式是通過在搜索二叉樹中存儲鍵值對pair，而搜索二叉樹的k/v模型是在節(jié)點中存儲key和value，并不相同。pair的結(jié)構(gòu)：
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)
{}
};
1、接口insert
make_pair是一個函數(shù)模板:
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}2、接口insert和operator[]和at
使用map統(tǒng)計每個字符出現(xiàn)個數(shù)
寫法2的[]詳解：
Value& operator[] (const Key& k)
{
pair<iterator,bool> ret=insert(make_pair(k,Value() ) );
//在結(jié)構(gòu)體pair中找到first(一個map的迭代器)，->解引用找到該迭代器的pair，再找該pair的second(即value)
return ret.first->second;
}
//map的insert
pair<iterator,bool> insert (const value_type& pair);
//插入
dict["迭代器"];//在dict中找不到"迭代器"這個key，將新增一個節(jié)點，該節(jié)點的key為"迭代器",value為value類型的默認構(gòu)造
//修改
dict["迭代器"]="iterator";//將key為"迭代器"的節(jié)點的value修改為"iterator"不難看出map的operator[]兼具查找、插入、修改三種功能。(注意如果搜尋值不在map中，map可是會幫你新增一個節(jié)點的，map底層的紅黑樹將發(fā)生改變)
使用operator[]，編譯器會去調(diào)用insert(pair<const key,value()>)進行插入，如果沒有找到key所對應(yīng)的節(jié)點，則會新增一個節(jié)點并將該節(jié)點中pair的value置為value類型的默認構(gòu)造；如果找到了，則返回該節(jié)點pair中value的引用。(可讀可寫)
at的功能和[]一樣，區(qū)別在于用at找不到key將不會發(fā)生插入新節(jié)點，而是拋出異常。
3、容器multimap
multimap多個鍵值對中的key可以重復(fù)，所以并沒有operator[]。同樣的，使用find將返回中序遍歷找到的第一個key值所處節(jié)點的迭代器。
四、map和set相關(guān)OJ
1、前K個高頻單詞
struct Compare
{
bool operator()(const pair<int,string>& a,const pair<int,string>& b)
{
return a.first>b.first || (a.first==b.first&&a.second<b.second);
}
};
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
vector<string> ret;
map<string,int> dataMap;
for(const auto& str : words)
{
dataMap[str]++;
}
vector<pair<int,string>> v;
for(auto& kv : dataMap)
{
v.push_back(make_pair(kv.second,kv.first));//dataMap的first是string，second是int
}
sort(v.begin(),v.end(),Compare());
for(int i=0;i<k;++i)
{
ret.push_back(v[i].second);
}
return ret;
}
};2、兩個數(shù)組的交集
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s1(nums1.begin(),nums1.end());//nums1排序+去重
set<int> s2(nums2.begin(),nums2.end());//nums2排序+去重
vector<int> ret;
for(auto& e : s1)
{
if(s2.find(e)!=s2.end())
{
ret.push_back(e);
}
}
return ret;
}
};或者將兩個數(shù)組排序+去重完畢后，使用雙指針求解。（可用于找交集，差集）
以上就是C++中set/multiset與map/multimap的使用詳解的詳細內(nèi)容，更多關(guān)于C++ set/multiset map/multimap的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
每種語言都對正則表達式有著不同程度的支持，在C語言中，有輸入功能的這三個函數(shù)對正則表達式的支持并不強大，但是我們還是有必要了解一下2021-10-10
下面小編就為大家?guī)硪黄狢基礎(chǔ) 尋找隨機函數(shù)的G點詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
這篇文章主要為大家詳細介紹了C++中動態(tài)內(nèi)存分配的相關(guān)知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-03-03
最接地氣的C函數(shù)基礎(chǔ)介紹，此處對于函數(shù)的相關(guān)知識點做一些簡要的介紹，作者實屬初學，寫博客也是作者學習的一個過程，難免文章中有內(nèi)容理解不到位或者有不當之處，還請朋友們不吝指正2021-11-11
本章將會詳細講解二叉樹遍歷的四種方式，分別為前序遍歷、中序遍歷、后續(xù)遍歷和層序遍歷。在學習遍歷之前，會先帶大家回顧一下二叉樹的基本概念2022-05-05
以下是對函數(shù)指針與返回函數(shù)的指針進行了詳細的分析介紹，需要的朋友可以過來參考下2013-07-07
C語言從strcpy到自定義字符串處理函數(shù)的原理解析
這篇文章主要介紹了C語言從strcpy到自定義字符串處理函數(shù)的相關(guān)資料,本文將從常見的字符串函數(shù)（如strcpy、strcat）入手,逐步深入探討字符串操作的核心原理,并引導(dǎo)你實現(xiàn)自定義字符串處理函數(shù),感興趣的朋友一起看看吧2025-05-05
這篇文章主要介紹了C++中的封裝、繼承、多態(tài)介紹,需要的朋友可以參考下2020-01-01
這篇文章主要介紹了C++11 并發(fā)指南之Lock 詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-02-02
C語言完美實現(xiàn)動態(tài)數(shù)組代碼分享
本文給大家分享的是一則使用C語言實現(xiàn)動態(tài)數(shù)組的代碼，完美解決內(nèi)存溢出以及內(nèi)存回收問題，有需要的小伙伴可以參考下。2016-02-02