目錄

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

二、鍵值對

三、set

3.1 set 的介紹

3.2 set 的使用

3.3. set 的使用舉例

四、map

4.1?map的介紹

3.2 map 的使用

4.3 map的使用舉例

五、經(jīng)典練習(xí)題

1.set的使用

2.map的使用

思路一(穩(wěn)定排序)：

思路二(priority_queue)：

在之前，我們接觸過 vector、list、deque……，這些容器被稱為序列式容器，因為其底層為線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身。那么什么是關(guān)聯(lián)式容器呢？

關(guān)聯(lián)式容器：關(guān)聯(lián)式容器也是用來存儲數(shù)據(jù)的，與序列式容器不同的是，其中存儲的是結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時比序列式容器效率更高。

用來表示具有一一對應(yīng)關(guān)系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個成員變量 key 、value。

key代表鍵值，value 表示與 key 對應(yīng)的信息。比如：現(xiàn)在要建立一個英漢互譯的字典，那該字典必然有英文單詞與其對應(yīng)的中文含義，而且，英文單詞與其中文含義是一一對應(yīng)的關(guān)系，即通過該英文單詞，在字典中就可以找到其對應(yīng)的中文含義。

SGI-STL中關(guān)于鍵值對的定義：

templatestruct 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)
    {}
};

這里是 set 的文檔介紹：set的介紹_C++reference?以下是幾個重要點。?

1. set 是按照一定次序存儲的容器
2. 在 set 中，元素的 value 也標(biāo)識它(value 就是 Key，類型為 T)，并且每個 value 必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。
3. 在內(nèi)部，set 中的元素總是按照其內(nèi)部比較對象(類型比較)所指示的特定嚴(yán)格弱排序準(zhǔn)則進(jìn)行排序。
4. set 容器通過 key 訪問單個元素的速度通常比 unordered_set 容易慢，但它們允許根據(jù)順序?qū)ψ蛹M(jìn)行直接迭代。
5. set 在底層是用二叉搜索樹(紅黑樹)實現(xiàn)的。

1. set 的模板參數(shù)列表

T：set 中存放元素的類型，實際在底層存儲的鍵值對。

Compare：set 中元素默認(rèn)按照小于來比較。

Alloc：set 中元素空間的管理方式，使用STL提供的空間配置器管理。

2. set 的構(gòu)造函數(shù)

3. set 的迭代器

4. set 的修改操作

map的文檔簡介?以下是幾個重要點：

1. map是關(guān)聯(lián)容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。
2. 在map中，鍵值key通常用于排序和唯一的標(biāo)識元素，而值value中存儲與此key關(guān)聯(lián)的內(nèi)容。簡直key和值value的類型可能不同，并且在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，為其取名別稱為pair
3. 在內(nèi)部，map中的元素總是按照及那只key進(jìn)行排序的。
4. map中通過簡直訪問但各國元素的熟讀通常比unordered_map容器慢，但map允許根據(jù)順序?qū)υ剡M(jìn)行直接迭代(即對map中的元素進(jìn)行迭代時，可以得到一個有序的序列)
5. map支持下標(biāo)訪問操作符，即在[]中放入key，就餓可以找到與key對應(yīng)的value。
6. map通常被實現(xiàn)為二叉搜索樹(準(zhǔn)確的說是紅黑樹)

1.map的模板參數(shù)說明

• key：鍵值對中key的類型
• T：鍵值對中value的類型
• Compare：比較器的類型。默認(rèn)為less，如果存在特殊的比較，需要用戶自己顯示傳入比較規(guī)則(函數(shù)指針或仿函數(shù)進(jìn)行傳遞)

2.map的構(gòu)造函數(shù)

3.map的迭代器

4.insert

首先我們來看看insert的使用，首先要知道m(xù)ap的insert是插入pair類型的數(shù)據(jù)

然后我們舉例進(jìn)行插入一下

void test_map1()
{
	//創(chuàng)建字典
	mapdict1;
	mapdict2;
	mapdict3;
	//插入數(shù)據(jù)——方式1、
	pairkv1("sort", "排序");
	pairkv2("insert", "插入");
	dict1.insert(kv1);
	dict1.insert(kv2);

	//插入數(shù)據(jù)——方式2、匿名對象
	dict2.insert(pair("sort", "排序"));
	dict2.insert(pair("insert", "插入"));

	//插入數(shù)據(jù)——方式3、make_pair()
	dict3.insert(make_pair("sort", "排序"));
	dict3.insert(make_pair("insert", "插入"));
}

插入方式3，make_pair其實是一個模板函數(shù)，就是為了方便我們進(jìn)行pair結(jié)構(gòu)的插入數(shù)據(jù)。

4. 下標(biāo)訪問操作符

這里我們實現(xiàn)一個統(tǒng)計水果次數(shù)功能的map，如下：

但是這樣的插入方式，非常的麻煩，所以map將下標(biāo)訪問操作符進(jìn)行了重載，讓其插入數(shù)據(jù)變得十分輕松。以下是 map中下標(biāo)訪問操作符：

功能解析：

1. map中有這個key，返回value的引用。(查找、修改value)
2. map中沒有這個key，會插入pair(key,V())，并返回value的引用。(插入+修改)

其實下標(biāo)訪問操作符的本質(zhì)是調(diào)用了 insert 函數(shù)，下面的文檔中的實現(xiàn)方式：

這種方式其實不是太好理解，這里我們可以將其分為兩步，就非常好理解了。

因為返回的是其value的引用，所以我們可以對其進(jìn)行賦值，這也是一種插入方式，也是最簡單的一種插入方式。

所以，在上面實現(xiàn)統(tǒng)計水果次數(shù)的map中，我們可以將其插入方式改為 [] 插入：

題目鏈接：349. 兩個數(shù)組的交集

題目介紹：

算法思路1：

1. 因為是求交集，所以我們可以使用set對nums1、nums2進(jìn)行排序+去重。
2. 遍歷set1，判斷set1中的值是否存在于set2中，如果存在，則放到結(jié)果數(shù)組中，不存在則跳過(時間復(fù)雜度：O(N*N))。

算法思路2：

1. 因為是求交集，所以我們可以使用set對nums1、nums2進(jìn)行排序+去重。
2. 同時處理兩個區(qū)間，讓it1指向的值與it2指向的值進(jìn)行比較，如果相等則為交集，兩個迭代器同時向后移動，如果不相等，結(jié)果小的迭代器進(jìn)行向后移動(時間復(fù)雜度:O(N))

兩種算法就是找交集的代碼不同，這里一并給出源代碼：

class Solution {
public:
    vectorintersection(vector& nums1, vector& nums2) {
        sets1;
        sets2;
        //去重  
        for(auto& e: nums1)
            s1.insert(e);
            
        for(auto& e: nums2)
            s2.insert(e);
        //找交集
        vectorresult;
        //方法1：
        for(auto& e: s1)
        {
            if (s2.find(e)!=s2.end())
                result.push_back(e);
        }
        //============================================
        //方法2：
        set::iterator it1=s1.begin();
        set::iterator it2=s2.begin();
        while(it1!=s1.end()&&it2!=s2.end())
        {
            if (*it1==*it2)
            {
                result.push_back(*it1);
                it1++,it2++;
            }
            else if (*it1>*it2) it2++;
            else it1++;
        }
        return result;
    }
};

題目鏈接：692. 前K個高頻單詞

題目介紹：

這題的難點就在于出現(xiàn)頻率相等的情況下，要按照字典序排序，這就意味著不能簡單的使用一次排序解決。

算法思路：

1. 使用map根據(jù)其字典序進(jìn)行排序，并統(tǒng)計單詞的出現(xiàn)次數(shù)。
2. 通過sort根據(jù)單詞的出現(xiàn)次數(shù)進(jìn)行排序。

使用了map存儲后，單詞在map中都按出現(xiàn)次數(shù)進(jìn)行排序，但是此時，如果我們使用一種穩(wěn)定排序，讓其在符合次數(shù)相同時，并進(jìn)行字典序的排序，就可以完成最終的排序。

首先 sort 是一個的迭代器是隨機迭代器(RandomAccess Iterator)，而map雙向迭代器(bidirectional iterator)，所以我們要先將map中的數(shù)據(jù)放入到一個數(shù)組中。

因為sort是快速排序，不穩(wěn)定的排序，所以我們要編寫仿函數(shù)控制其排序的結(jié)果。

仿函數(shù)的比較規(guī)則：

1. 如果出現(xiàn)次數(shù)多，則排在前面，返回true。
2. 出現(xiàn)次數(shù)相同時再比較字典序，如果kv1的字典序小于kv2，即kv1在kv2前，則返回true，編寫這條規(guī)則可以間接控制穩(wěn)定性。
3. 其他情況直接返回false。

class Solution {
public:
    struct Greater{
        bool operator()(const pair& kv1,const pair& kv2)
        {
            //按次數(shù)比較
            if (kv1.second >kv2.second)
                return true;
            //次數(shù)相同，按字典序比較。
            if (kv1.second==kv2.second&&kv1.first< kv2.first)
                return true;
            return false;
        }
    };
    vectortopKFrequent(vector& words, int k) {
        mapcountMap;
        for(auto& str:words)
        {
            countMap[str]++;
        }
        //導(dǎo)數(shù)據(jù)，因為迭代器類型不同
        vector>sortV(countMap.begin(),countMap.end());
        sort(sortV.begin(),sortV.end(),Greater());

        vectorresult;
        for(int i=0;i

因為map中已經(jīng)按照字典序進(jìn)行了排序，所以我們只需要使用一種穩(wěn)定的排序，將出現(xiàn)次數(shù)多的調(diào)整到前面，出現(xiàn)次數(shù)相同則不進(jìn)行調(diào)整。

庫中的穩(wěn)定排序(stable_sort)：

進(jìn)行以下修改即可：

struct Less {
	bool operator()(const pair& kv1, const pair& kv2)
	{
		//按次數(shù)比較
		if (kv1.second< kv2.second)
			return true;
		//次數(shù)相同，按字典序比較。
		if (kv1.second == kv2.second && kv1.first >kv2.first)
			return true;
		return false;
	}
};

class Solution {
public:
    struct Less{
        bool operator()(const pair& kv1,const pair& kv2)
        {
            //按次數(shù)比較
            if (kv1.secondkv2.first)
                return true;
            return false;
        }
    };
    vectortopKFrequent(vector& words, int k) {
        mapcountMap;
        for(auto& str:words)
        {
            countMap[str]++;
        }
        //迭代器區(qū)間初始化
        priority_queue,vector>,Less>maxHeap(countMap.begin(),countMap.end());
        vectorresult;
        while(k--)
        {
            result.push_back(maxHeap.top().first);
            maxHeap.pop();
        }
        return result;
    }
};