本篇文章，主要通過了map和set的對比，介紹了STL中的map/set兩種容器的用法以及區(qū)別；并介紹了map/set的底層實現(xiàn)原理；簡單提及了一下關聯(lián)式容器和順序式容器的區(qū)別

pair

說明：

是一個結構體類型，里面的兩個成員變量的類型可以通過模板給定；介紹pair的原因是，在map的insert方法中，需要插入pair類型的元素

定義：

template<class T1,class T2> struct pair;
模擬實現(xiàn)：
template<typename T1,typename T2>struct Pair{	typedef T1 first_type;	typedef T2 second_type;	T1 first;	T2 second;	Pair()		:first_type(T1())		, second_type(T2())	{}	Pair(const T1 &x, const T2 &y)		:first_type(x)		, second_type(y)	{}	//拷貝構造函數(shù)	template<typename U,typename V>	Pair(const Pair<U, V> &p)		: first(p.first)		, second(p.second)	{}};
set
簡介：
set是STL中的一個容器，和vector不同的是，set是一種關聯(lián)式容器；
關聯(lián)式容器的底層是用紅黑樹實現(xiàn)的；
紅黑樹是一顆近似平衡的搜索二叉樹，在對元素的查找中有很高的效率；
其查詢一個元素的時間復雜度為O(lg(N))
定義：
接口的使用：
<1>構造一個set類型的變量
set<int> s;
<2>insert() --- 插入一個元素
- 1 第一個insert返回的是一個pair類型的變量，其包含兩個成員，第一個成員的類型是該map迭代器的類型，另一個成員的類型是bool
若map沒有新插入的元素，那么插入成功，返回的是插入節(jié)點的迭代器以及TRUE；
若該元素在map中已經(jīng)存在，那么插入會失敗，返回的是該元素已經(jīng)存在節(jié)點的迭代器，以及FALSE；
	//構造一個int類型的set	set<int> s;	//插入幾個元素	s.insert(1);	s.insert(2);	s.insert(6);	//測試insert()的返回值	pair<set<int>::iterator, bool> ret;	ret = s.insert(4);//set中還沒有4這個元素，插入成功，返回插入節(jié)點的迭代器和TRUE	ret = s.insert(4);//set中已經(jīng)存在了4，插入失敗，返回的是元素4的迭代器和FALSE
- 2 該insert插入的是一段迭代器區(qū)間 
	//定義一段vector，類型也是int	vector<int> v;	v.push_back(10);	v.push_back(50);	v.push_back(5);	//用insert向set s中插入該vector的全部	s.insert(v.begin(), v.end());<3>利用迭代器訪問元素
	//定義一個對應類型的迭代器，指向s的起始	set<int>::iterator it = s.begin();	//當it沒有指向s的最后一個元素的后一個元素時，訪問	while (it != s.end())	{		cout << *it << " ";		it++;//迭代器自增，指向下一個元素	}	cout << endl;反向迭代器也是類似的用法，這里就不多說了
<4>erase() ---刪除一個元素或一段區(qū)間
- 1 用erase() 刪除一個元素，傳入刪除元素的迭代器
- 2 用erase()刪除一個元素，穿入一個key值，返回的是刪除該key值節(jié)點的個數(shù)
- 3 刪除一段迭代器區(qū)間
        //1.用find查找1這個元素，并用迭代器it獲取返回值,然后進行刪除	set<int>::iterator it = s.find(500);	if (it != s.end())                  //查詢成功，則表示元素存在，刪除該元素		s.erase(it);	else		              //若查詢失敗，表示不存在，對it解引用會是NULL		cout << "沒有找到" << endl;	//2.直接刪除一個key值	s.erase(2);	//3.刪除一段迭代器區(qū)間	s.erase(s.begin(), s.end());
<5>find() --- 用來查找一個元素，若查找到，則返回該元素對應的迭代器，否則返回最后一個元素的下一個元素
在刪除的時候已經(jīng)用過
<6>count() 
 統(tǒng)計一個元素的個數(shù)，在set中用于判斷一個元素是否存在；因為無法插入相同的值，所以在set/map中與find的作用一樣
<7>emplace()
emplace和insert都是向set中插入一個元素，但效率上看，emplace的效率要高一點
insert是先構造好，然后又經(jīng)過一次拷貝構造放入set中；
而emplace是直接在set中進行構造
map
簡介：
map也是一種關聯(lián)式容器，與set不同的是，它是一種 Key/Value 結構的容器；
map的幾種用途：
做英語詞典、統(tǒng)計水果出現(xiàn)的個數(shù)
定義：
接口的使用：
<1> 定義一個map
map<string,int> countMap;
<2>insert() 
- 1 插入一個pair
map<string, int> m;m.insert(pair<string, int>("hello", 0));m.insert(pair<string, int>("world", 1));- 2 插入一個value_type
m.insert(map<string, int>::value_type("change", 1));- 3 利用數(shù)組下標進行插入，這里的K值需要是int
map<int, string> m;m[0] = "first";m[1] = "second";m[2] = "third";
<3>erase() 元素的刪除
- 1 迭代器刪除
map<string, int>::iterator it = m.find("hello");if (it != m.end())m.erase(it);- 2 key值刪除
m.erase("hello");
<4> find() 查找元素
和set相同，查找成功返回對應的迭代器，否則返回最后一個元素的下一個位置
<5>count()
統(tǒng)計個數(shù)，但是由于不允許出現(xiàn)重復的Key值，所以和find()作用類似