stl 容器

stl 容器 – map

1. map 和 multimap的使用文档

参考文档参考文档点这里哟 🌈 😘

2. map 类的介绍

map的声明如下

template < class Key, 		// map::key_type
class T, 				  // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > //map::allocator_type> class map;

key就是 map的底层关键字的类型， T,是 map 底层的value的类型,set默认支持 key的小于比较，如果不支持就需要自行实现小于比较，实现仿函数来支持，需要穿第二个模板参数， map底层的存储数据的内训是与空间适配器申请的，想要自己实现内存是就需要自己传入第三个参数。在一般情况下，我们不需要去管着后面两个参数。map的底层是 红黑树，增删查改的效率的 O(logN),迭代器的遍历还是中序，所以在遍历时，是按照 key有序遍历的。

3. pair类型的介绍

map底层的红黑树节点中的数据，使用 pair<key, T>存储的键值对数据

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){}};
template <class T1,class T2>inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

4. map的构造

map的构造我们关注下面的几个接口就可以了。

map支持正向和反向迭代器遍历，遍历默认按照 key的升序遍历
底层为 二叉搜索树，迭代器遍历按照中序遍历
支持迭代器，就意味着支持 范围 for
map支持修改 value数据，不支持修改 key数据 ，修改关键字会破坏搜索二叉树的底层结构。

// empty (1) ⽆参默认构造 
explicit map (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造 
template <class InputIterator>map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());
// copy (3) 拷⻉构造 
map (const map& x);
// initializer list (5) initializer 列表构造 
map (initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// 迭代器是⼀个双向迭代器 
iterator -> a bidirectional iterator to const value_type// 正向迭代器 iterator begin();
iterator end();
// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

5.map的增删查

map的增删查我们就只需要关注下面的几个接口就可以了： 😚🌈

map的增接口，插入 pair键值对数据，和set不同的。
其他的接口和 set类似，但是 find接口返回的 iterator不仅可以确定 key是否存在同时还可以通过 key来访问和修改 vaule

Member typeskey_type -> The first template parameter (Key)mapped_type -> The second template parameter (T)value_type -> pair<const key_type,mapped_type>// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>void insert (InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，没有找到返回end() 
iterator find (const key_type& k);
// 查找k，返回k的个数 
size_type count (const key_type& k) const;
// 删除⼀个迭代器位置的值 
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1 
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值 
iterator erase (const_iterator first, const_iterator last);
/ 返回⼤于等k位置的迭代器 iterator lower_bound (const key_type& k);
// 返回⼤于k位置的迭代器 
const_iterator lower_bound (const key_type& k) const;

5. map的数据修改

第一个支持修改的方式是使用迭代器，迭代器遍历时或者是 find返回的 key所在的 iterator进行修改。
operator[] 是一个十分重要的接口，它不仅仅支持访问修改，还支持插如和查找数据，是一个符合接口！
注意： map这里我们传统说的是 value值，给的是 T类型的数据， typedef 为 mapped_type 而 value_type 是红黑树节点中存储的 pair键值。日常我们还是习惯将 T的映射值叫做 value;

Member typeskey_type -> The first template parameter (Key)mapped_type -> The second template parameter (T)value_type -> pair<const key_type,mapped_type>// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type值 iterator find (const key_type& k);
// ⽂档中对insert返回值的说明 
// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pairis set to true if a new element was inserted or false if an equivalent key already existed.// insert插⼊⼀个pair<key, T>对象 // 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false // 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true // 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器 // 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[]// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另⼀个是insert返回值pair<iterator,bool> pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);
// operator的内部实现 
mapped_type& operator[] (const key_type& k)
{// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能 // 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能 pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

7. 构造遍历和增删查的使用样例

#include<iostream>
#include<map>
using namespace std;
int main()
{// initializer_list构造及迭代遍历 map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << (*it).first <<":"<<(*it).second << endl;// map的迭代基本都使⽤operator->,这⾥省略了⼀个-> // 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取 pair数据 //cout << it.operator->()->first << ":" << it.operator->()->second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;
// insert插⼊pair对象的4种⽅式，对⽐之下，最后⼀种最⽅便 pair<string, string> kv1("first", "第⼀个");dict.insert(kv1);dict.insert(pair<string, string>("second", "第⼆个"));dict.insert(make_pair("sort", "排序"));dict.insert({ "auto", "⾃动的" });// "left"已经存在，插⼊失败 dict.insert({ "left", "左边，剩余" });// 范围for遍历 for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;}else{cout << "⽆此单词，请重新输⼊" << endl;}}// erase等接⼝跟set完全类似，这⾥就不演⽰讲解了 return 0;
}

8. map的迭代器和 []功能的样例

样例1

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{// 利⽤find和iterator修改功能，统计⽔果出现的次数 string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠", "苹果", "⾹蕉", "苹果", "⾹蕉" };map<string, int> countMap;for (const auto& str : arr){// 先查找⽔果在不在map中 // 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1} // 2、在，则查找到的节点中⽔果对应的次数++ auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({ str, 1 });}else{ret->second++;}}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数 string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠", "苹果", "⾹蕉", "苹果", "⾹蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找⽔果在不在map中 // 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤,++⼀下就变成1次了 // 2、在，则返回⽔果对应的次数++ countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

样例2

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插⼊ {"insert", string()} dict["insert"];// 插⼊+修改 dict["left"] = "左边";// 修改 dict["left"] = "左边、剩余";// key存在->查找 cout << dict["left"] << endl;return 0;
}
1