STL-map/multimap关联式容器

一、基本概念

1.1 简介

1.2 本质

1.3 库原型

二、使用

2.0 迭代器

2.1 构造函数

2.2 插入删除

2.3 查找统计

2.4 数据修改

三、multimap

一、基本概念

1.1 简介

map中所有元素都是pair
pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
所有元素都会根据元素的键值自动排序
map⽀持修改value数据，不⽀持修改key数据

1.2 本质

map/multimap属于关联式容器，底层结构是用红黑树实现。

1.3 库原型

Key就是map底层关键字的类型，T是map底层value的类型，map默认要求Key⽀持小于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。

map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。

二、使用

迭代器、构造函数、增删查都与set类设计使用相似，唯一不同的是，map类支持修改。

2.0 迭代器

// 迭代器是⼀个双向迭代器
//iterator -> a bidirectional iterator to const value_type

// 正向迭代器
iterator begin();
iterator end();

// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

int main()
{map<string, string> dict = { {"left", " 左边"}, {"right", " 右边"},
{"insert", " 插入 "},{ "string", " 字符串" } };//范围forfor (const auto& e: dict){cout << e.first << ":" << e.second << endl;}//迭代器+重载->操作符auto it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << " ";cout << endl;++it;}return 0;
}

2.1 构造函数

// 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());//赋值操作符重载
map& operator=(const map &mp)

2.2 插入删除

insert(elem); //在容器中插入元素。
clear(); //清除所有元素
erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end); //删除区间[beg,end)的所有元素，返回下一个元素的迭代器。
erase(key); //删除容器中值为key的元素。

//插入的四种办法
int main()
{map<string, string> dict;//1. 有名对象pair<string, string> kv1("apple", "苹果");dict.insert(kv1);//2. 匿名对象dict.insert(pair<string, string>("banana", "香蕉"));//3. 函数dict.insert(make_pair("pear", "梨"));//4. C++11支持多参数隐式类型转换dict.insert({ "strawb","草莓" });return 0;
}

2.3 查找统计

查找k ，返回k 所在的迭代器，没有找到返回end()
iterator find (const key_type& k);
查找k ，返回k 的个数
size_type count (const key_type& k) const;

2.4 数据修改

第一种也是最容易想的方式就是直接使用迭代器的重载->操作符修改second值

int main()
{map<string, string> dict = { {"left", " 左边"}, {"right", " 右边"},
{"insert", " 插入 "},{ "string", " 字符串" } };//范围forfor (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;auto it = dict.find("left");it->second = "不知道";for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}return 0;
}

第二种介绍官方库中支持的[]接口

mapped_type实际上就是value，返回其引用，支持修改
实际上分为两种情况：
1. 如果key存在，返回对应value的引用
2. 如果key不存在，插入此key值，对应的value值走默认构造
底层分析

底层调用的是insert

insert返回值是 pair<iterator,bool>：如果存在就返回已经有的节点的迭代器，bool值为false；如果不存在就返回新建节点的迭代器，bool值为true
由以上分析可见：[]操作符既可以查找、修改也可以插入。

int main()
{map<int, char> mp;mp[1] = 'a';mp[2] = 'b';mp[3] = 'c';mp[4] = 'd';for (const auto& e : mp){cout << e.first << ":" << e.second << endl;}mp[3] = 'x';for (const auto& e : mp){cout << e.first << ":" << e.second << endl;}
}