C++ map和set

C++參考文獻：cplusplus.com - The C++ Resources Network

一、序列式容器和關聯式容器

二、set系列

（1）set類的介紹

（2）set的構造和迭代器

（3）set的接口

??1.insert?編輯

2.find和erase

3.lower_bound和upper_bound

（4）set和multiset的差異

三、map系列

（1）map類的介紹

（2）pair類型介紹

（3）map的接口

1.insert

2.erase

3.operator[]

（4)multimap和map的差別

一、序列式容器和關聯式容器

前面我們已經接觸過STL中的部分容器如:string、vector、list、deque、array、forward_list等，這些容器統稱為序列式容器，因為邏輯結構為線性序列的數據結構，兩個位置存儲的值之間一般沒有緊密的關聯關系，比如交換一下，他依舊是序列式容器。順序容器中的元素是按他們在容器中的存儲位置來順序保存和訪問的。
關聯式容器也是用來存儲數據的，與序列式容器不同的是，關聯式容器邏輯結構通常是非線性結構，兩個位置有緊密的關聯關系，交換一下，他的存儲結構就被破壞了。順序容器中的元素是按關鍵字來保存和訪問的。關聯式容器有map/set系列和unordered map/unordered set系列。本章節講解的map和set底層是紅黑樹，紅黑樹是一顆平衡二叉搜索樹。set是key搜索場景的結構，map是key/value搜索場景的結構。

二、set系列

（1）set類的介紹

set的聲明如下圖，T就是set底層關鍵字的類型set默認要求T支持小于比較，如果不支持或者想按自己的需求走可以自行實現仿函數傳給第二個模版參數set底層存儲數據的內存是從空間配置器申請的，如果需要可以自己實現內存池，傳給第三個參數。
一般情況下，我們都不需要傳后兩個模版參數。set底層是用紅黑樹實現，增刪查效率是O(logN)，迭代器遍歷是走的搜索樹的中序，所以是有序的。因為STL庫實現的接口相似度高，我們就不一一展示，挑選重要的來理解學習。

（2）set的構造和迭代器

迭代器是一個雙向迭代器。

set支持正向和反向迭代遍歷，遍歷默認按升序順序，因為底層是二叉搜索樹，迭代器遍歷走的中序;支持迭代器就意味著支持范圍for，set的iterator和const iterator都不支持迭代器修改數據，修改關鍵字數據，破壞了底層搜索樹的結構。

（3）set的接口

??1.insert

set的insert不支持插入相同的值。當然不管是不是const迭代器都不支持修改。

說明默認的insert作用就是去重和升序。如果我們想要變成降序的話，我們就需要增加仿函數這個參數。

對于列表值的插入，類似下圖。

接著我們也觀看一下構造中的列表初始化。下圖是先構造了個臨時對象，然后再拷貝構造出strset。

2.find和erase

find返回值是迭代器，成功返回要找的迭代器，返回失敗返回end的迭代器。

而erase刪除提供傳迭代器，傳數據，還可以傳迭代器區間。

這時候會有疑問，為什么第二個返回值不是bool而是size_type呢？這是為了兼容multiset，這里是刪除成功返回1刪除失敗返回0，在multiset中，刪除幾個返回多少。

我們通過一些例子去熟悉掌握這些接口。例如我們想把set中的最小值刪除，這里因為默認是升序，我們刪除begin迭代器即可。

例如我們如果要實現輸入一個值然后刪除。例如直接查找在利用迭代器刪除x。

這里erase后迭代器肯定失效。第一種是野指針，第二種是在替換法后當前位置的迭代器意義改變，也稱為迭代器失效。

3.lower_bound和upper_bound

lower_bound返回大于等于val位置的迭代器，upper_bound則是返回大于val位置的迭代器

????????

這個有什么作用呢？假如我們需要刪除一段區間的值，而刪除一段區間需要左閉右開，這個時候我們就可以用上面兩個接口來獲得區間。

int main()
{set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); for (auto e : myset){cout << e << " ";}cout << endl;auto itlow = myset.lower_bound(30);auto itup = myset.upper_bound(60);myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}

這樣我們就能夠刪除30到60之間的值。

（4）set和multiset的差異

multiset和set的使用基本完全類似，:要區別點在于multiset支持值冗余，insert/find/count/erase都圍繞著支持值冗余有所差異，具體參看下面的樣例代碼理解。相比set不同的是，multiset是排序，但是不去重。

而find相比set也不同，不同的是，x可能會存在多個，find查找中序的第一個。

count則會返回multiset中x的個數。

erase則會刪除所有的x。

三、map系列

（1）map類的介紹

map的聲明如下，Key就是map底層關鍵字的類型，T是map底層value的類型，set默認要求Key支持小于比較，如果不支持或者需要的話可以自行實現仿函數傳給第二個模版參數，map底層存儲數據的內存是從空間配置器申請的。一般情況下，我們都不需要傳后兩個模版參數。map底層是用紅黑樹實現，增刪查改效率是O(logN)，迭代器遍歷是走的中序，所以是按key有序順序遍歷的。

（2）pair類型介紹

我們先來了解一下map的插入，在了解插入之前我們需要去了解pair，因為插入的參數涉及到這個類型。

底層大概就是這樣，對比我們能夠知曉，first就是Key而second就是value。

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

所以我們在map中使用insert需要使用到pair。

（3）map的接口

1.insert

我們先前提到的pair就是我們在insert的時候所要使用到的，對于insert我們有多種形式insert。

第一種就是我們定義一個有名的pair對象，然后插入pair對象。

第二種我們可以插入一個匿名的pair對象。

第三種我們可以借用函數模板make_pair來插入，make_pair它會自己推導出后面的類型，返回一個pair對象。

C++11后提支持多參數隱式類型轉換后，我們就有了第四種方法insert。

在遍歷map的時候，與其他容器也有所不同，map沒有重載流插入和流提取，我們了解了pair的結構后我們需要去解引用后再調用first或者second。

在之前的學習中，我們能夠知曉迭代器不止重載了operator*還重載了operator->。剛好我們存儲的對象是結構，這樣我們就可以采用箭頭。

所以在map中我們常用箭頭來取對應的數據。我們要注意map中可以修改value，但不可以修改key。

2.erase

erase還是只跟key有關，即使你map中沒有key也不會報錯。

3.operator[]

我們先來實現一個統計水果出現的次數。思路就是利用find和iterator修改功能，統計水果出現的次數。

但是實際上在map中不使用這種方式來實現，直接通過一行代碼就可以搞定。

這是怎么做到的呢？那我們需要來學習了解一下operator[]。這個接口提供了插入，查找和修改的功能。我們再回去觀看一下insert。

我們能夠發現這里其實有兩個pair。

我們重點要理解insert的返回值中的迭代器是什么意思呢？

所以返回的迭代器要么是新插入節點的迭代器，要么是插入失敗map里面和插入key相等的迭代器。bool則是根據插入成功失敗返回的。總結來說，insert如果插入成功返回的是pair<新插入值所在的迭代器，true>，插入失敗則是pair<已經存在的跟key相同值的迭代器，false>，所以insert不僅有插入的功能，還有查找的功能。insert插入失敗時充當了查找的功能，因為這一點，insert可以用來實現operator[]。

mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

我們把operator[]內部實現大概的代碼拿出來研究一下。能夠得出：1、如果k不在map中，insert會插入k和mapped_type默認值，同時[]返回結點中存儲mapped_type值的引用，那么我們可以通過引用修改返映射值。所以[]具備了插入+修改功能。2、如果k在map中，insert會插入失敗，但是insert返回pair對象的first是指向key結點的迭代器，返回值同時[]返回結點中存儲mapped_type值的引用，所以[]具備了查找+修改的功能。

（4)multimap和map的差別

multimap和map的使用基本完全類似，主要區別點在于multimap支持關鍵值key冗余，那么insert/find/count/erase都圍繞著支持關鍵值key冗余有所差異，這里跟set和multiset完全一樣，比如find時，有多個key，返回中序第一個。其次就是multimap不支持[]，因為支持key冗余，[]就只能支持插入了，不能支持修改。