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返回大于等于目標(biāo)值的迭代器，upper_bound返回大于目標(biāo)值的迭代器，在set中用于返回目標(biāo)值的迭代器。（比如找到兩個邊界的迭代器，就可以使用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類型的默認(rèn)構(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類型的默認(rèn)構(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的使用詳解的詳細(xì)內(nèi)容，更多關(guān)于C++ set/multiset map/multimap的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++踩坑實戰(zhàn)之構(gòu)造和析構(gòu)函數(shù)
不論是構(gòu)造函數(shù),還是析構(gòu)函數(shù),都是C++、C#語言相對于其他語言而言特殊的地方,它是為了方便類中對象的初始化,這篇文章主要給大家介紹了關(guān)于C++踩坑實戰(zhàn)之構(gòu)造和析構(gòu)函數(shù)的相關(guān)資料,需要的朋友可以參考下2021-07-07
C語言中的宏和函數(shù)是非常相似的，它們都可以完成類似的功能。本文為大家整理了C語言中宏和函數(shù)的9個區(qū)別，感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04
VC++?2019?"const?char*"類型的實參與"LPCTSTR"
這篇文章主要給大家介紹了關(guān)于VC++?2019?"const?char*"類型的實參與"LPCTSTR"類型的形參不兼容的解決方法,文中通過圖文介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2023-03-03
這篇文章主要介紹了引用numpy出錯 解決方法的相關(guān)資料,需要的朋友可以參考下2017-02-02
Qt使用SqlLite實現(xiàn)權(quán)限管理的示例代碼
本文主要介紹了Qt使用SqlLite實現(xiàn)權(quán)限管理的示例代碼,管理員針對不同人員進行權(quán)限設(shè)定,具有一定的參考價值,感興趣的可以了解一下2023-09-09
所謂高斯噪聲是指它的概率密度函數(shù)服從高斯分布(即正態(tài)分布)的一類噪聲,這篇文章主要給大家介紹了關(guān)于C++實現(xiàn)點云添加高斯噪聲功能的相關(guān)資料,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C++中vector可以作為map的鍵值實例代碼,需要的朋友可以參考下2017-07-07
C語言中回調(diào)函數(shù)和qsort函數(shù)的用法詳解
這篇文章主要為大家詳細(xì)介紹一下C語言中回調(diào)函數(shù)和qsort函數(shù)的用法教程，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C語言有一定幫助，需要的可以參考一下2022-07-07
C++使用標(biāo)準(zhǔn)庫實現(xiàn)事件和委托以及信號和槽機制
這篇文章主要為大家詳細(xì)介紹了C++如何使用標(biāo)準(zhǔn)庫實現(xiàn)事件和委托以及信號和槽機制，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，需要的可以參考一下2022-11-11
C/C++使用socket實現(xiàn)判斷ip是否能連通
這篇文章主要為大家詳細(xì)介紹了C/C++如何使用socket實現(xiàn)判斷ip是否能連通，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價值，感興趣的小伙伴可以了解一下2023-07-07