欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中set/multiset與map/multimap的使用詳解

 更新時(shí)間：2023年02月14日 09:38:05   作者：蔣靈瑜的筆記本  
這篇文章主要為大家詳細(xì)介紹了C++中set/multiset與map/multimap的使用，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下

一、關(guān)聯(lián)式容器

vector、list、deque、forward_list(C++11)等，這些容器統(tǒng)稱為序列式容器，因?yàn)槠涞讓訛榫€性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身。

而關(guān)聯(lián)式容器也是用來存儲數(shù)據(jù)的，與序列式容器不同的是，其里面存儲的是<key, value>結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時(shí)比序列式容器效率更高。 （插入刪除只需挪動(dòng)指針指向，無需挪動(dòng)數(shù)據(jù)，查找時(shí)間logN）

關(guān)聯(lián)式容器有兩種，一種是map、set、multimap、multiset采用樹形結(jié)構(gòu)，他們的底層都是紅黑樹，另一種是哈希結(jié)構(gòu)。

二、set的介紹

1、set是關(guān)聯(lián)式容器，它表面上只存放value，實(shí)際底層中存放的是由<value,value>組成的鍵值對。

2、set調(diào)用find將采用中序遍歷，可以用于排序+去重。

3、為了保證元素的唯一性，set中的元素均為const，所以并不能對元素進(jìn)行修改，但可以進(jìn)行插入刪除。

1、接口count與容器multiset

count和find的作用一樣，都是用于查找set中是否存在某個(gè)元素。

其實(shí)count是為了容器multiset設(shè)計(jì)的，該容器允許插入重復(fù)的元素，此時(shí)count會(huì)返回紅黑樹中被搜索元素的個(gè)數(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)值的迭代器。（比如找到兩個(gè)邊界的迭代器，就可以使用erase對數(shù)據(jù)進(jìn)行刪除）

#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中有一個(gè)鍵值對pair，這個(gè)pair是一個(gè)key/value結(jié)構(gòu)的struct模板類。這個(gè)類將一對鍵值耦合在一起，所以，map的存儲方式是通過在搜索二叉樹中存儲鍵值對pair，而搜索二叉樹的k/v模型是在節(jié)點(diǎn)中存儲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是一個(gè)函數(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)計(jì)每個(gè)字符出現(xiàn)個(gè)數(shù)

寫法2的[]詳解：

Value& operator[] (const Key& k)
{
	pair<iterator,bool> ret=insert(make_pair(k,Value() ) );
	//在結(jié)構(gòu)體pair中找到first(一個(gè)map的迭代器)，->解引用找到該迭代器的pair，再找該pair的second(即value)
	return ret.first->second;
}
//map的insert
pair<iterator,bool> insert (const value_type& pair);
//插入
dict["迭代器"];//在dict中找不到"迭代器"這個(gè)key，將新增一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的key為"迭代器",value為value類型的默認(rèn)構(gòu)造
//修改
dict["迭代器"]="iterator";//將key為"迭代器"的節(jié)點(diǎn)的value修改為"iterator"

不難看出map的operator[]兼具查找、插入、修改三種功能。(注意如果搜尋值不在map中，map可是會(huì)幫你新增一個(gè)節(jié)點(diǎn)的，map底層的紅黑樹將發(fā)生改變)

使用operator[]，編譯器會(huì)去調(diào)用insert(pair<const key,value()>)進(jìn)行插入，如果沒有找到key所對應(yīng)的節(jié)點(diǎn)，則會(huì)新增一個(gè)節(jié)點(diǎn)并將該節(jié)點(diǎn)中pair的value置為value類型的默認(rèn)構(gòu)造；如果找到了，則返回該節(jié)點(diǎn)pair中value的引用。(可讀可寫)

at的功能和[]一樣，區(qū)別在于用at找不到key將不會(huì)發(fā)生插入新節(jié)點(diǎn)，而是拋出異常。

3、容器multimap

multimap多個(gè)鍵值對中的key可以重復(fù)，所以并沒有operator[]。同樣的，使用find將返回中序遍歷找到的第一個(gè)key值所處節(jié)點(diǎn)的迭代器。

四、map和set相關(guān)OJ

1、前K個(gè)高頻單詞

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、兩個(gè)數(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;
    }
};

或者將兩個(gè)數(shù)組排序+去重完畢后，使用雙指針求解。（可用于找交集，差集）

以上就是C++中set/multiset與map/multimap的使用詳解的詳細(xì)內(nèi)容，更多關(guān)于C++ set/multiset map/multimap的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

最新評論