map和set

? c++98支持的是單參數的隱式類型轉換，而c++11支持多參數的隱式類型轉換；

1.map和set的使用

1.1set

? set實現key值不允許修改，是將iterator轉變成const_iterator；可以對同一個類型typedef成兩個不同的自定義標識符。即set沒有設置普通迭代器；

? set的底層是紅黑樹，使用仿函數比較大小。關聯式容器。

? set可以實現比較記錄重復次數但是需要重載仿函數，實現key_value只需要set內部實現的是一個結構體。

? count和equal_range在set容器里面一樣不大，而在multiset才有意義。

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;
//1.構造
empty (1)	explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
range (2)	template <class InputIterator>set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
copy (3)	set (const set& x);
//2.迭代器
//和一起的容器一樣，迭代器底層走的是一個中序遍歷，還可以去重。
//3.insert
iterator insert (iterator position, const value_type& val);//某個迭代器位置進行插入
//4.erase
void erase (iterator position);//配合find使用，使用find找到迭代器位置。
size_type erase (const value_type& val);//根據值來進行刪除。其實就是find和erase的復用，但是會斷言。
//5.find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);//暴力查找會查找O(N)次
iterator find (const value_type& val) const;//因為樹的左右兩邊是平衡的，會根據大小進行比較，最多訪問高度次lg(N)次，建議優先使用它。
//6.key/value的仿函數
key_compare key_comp() const;
value_compare value_comp() const;
//7.count
size_type count (const value_type& val) const;//返回這個值出現的次數，在set中存在返回的就是1，不存在返回的就是零。
//8.找邊界
//常用在erase使用區間刪除
iterator lower_bound (const value_type& val) const;//返回的迭代器位置是大于等于這個值
iterator upper_bound (const value_type& val) const;//由于區間一般是左閉右開，所以返回的迭代器位置一般是這個值的下一位。即刪除找左閉右閉，查找找左閉右開
//9.找區間
pair<iterator,iterator> equal_range (const value_type& val) const;

1.2multiset(Multiple-key set)

? 支持鍵值冗余的multiset容器，相等的值插入在左邊和右邊都可以。

//1.count
size_type count (const value_type& val) const;//返回val的個數
//2.equal_range
pair<iterator,iterator> equal_range (const value_type& val) const;//由于set容器是一個有序的紅黑樹，所以大小相同的值的是一段連續的區間范圍，可以用pair結構來接收迭代區間的lower和upper。返回大于val數的[val+,val+)
//3.find
//相較于set的find，由于有了數據冗余，所以返回值返回的是中序遍歷的第一個val的iterator

1.3map

? 使用map來完成括號匹配問題，而且初始化用initializer_list更加方便。

? 鍵值唯一，value可重復；map內存放的是pair對象；key必須支持比較大小；如果不支持比較大小可以自己寫一個仿函數來實現，因為仿函數比較使用的就是key；

template < class Key,                                     // map::key_typeclass T,                                       // map::mapped_typeclass Compare = less<Key>,                     // map::key_compare，只有key參與比較class Alloc = allocator<pair<const Key,T> >    // map::allocator_type> class map;//相較于set多了一個模板參數，用來設置value
//1.insert
pair<iterator,bool> insert (const value_type& val);//1.value_type是一個pair<const key_type,mapped_type>,即key只讀不允許寫入，而value可讀寫；2.可以使用make_pair函數模板來實現傳入參數val或者使用隱式類型轉換；3.設置pair的原因是c++不支持返回多個參數，但是可以返回一個結構，如：解引用運算符重載返回的就是一個結構；4.key相同但是value不相同，也不會插入不會覆蓋，值比較key，不關心value；5.返回值插入成功返回true，要插入的key值存在則是false
//2.erase
void erase (iterator position);
size_type erase (const key_type& k);
//3.operator[]
mapped_type& operator[] (const key_type& k);//特點是通過key來返回value；
//對于不存在的key值會創建并用匿名對象來初始化pair，已經存在的key值會修改value值；
//底層實現就是return (*((this->insert(make_pair(k,mapped_type()))).first)).second，即使用的是insert的返回值中的迭代器位置的value。
//1.可以使用[]來實現統計出現的次數；2.可以實現插入加修改；

1.4multimap

? 支持鍵值冗余的multimap容器，value和map一樣。

? 1.相較于map沒有提供[]，因為鍵值不是唯一的。

? 2.insert返回的是迭代器不是pair，因為插入一定成功;

? 3.哈希的效率可以達到O1；

1.5pair

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