map和set-EW帮帮网

1.序列式容器和关联式容器

在认识map和set之前，关于容器，有两个重要的分类

序列式容器
关联式容器

序列式容器：按照元素插入的顺序保存数据，关注元素的顺序和位置，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，元素是按他们在容器中的存储位置来顺序保存和访问的，如string、vector、list、deque、array、forward_list等

关联式容器：通过关键字来存储和访问元素，关注的是元素之间的关系，逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，如果交换顺序，它的存储结构就被破坏了，如map/set系列和unordered_map/unordered_set系列

2.1 set的声明

template < class T,                     // set::key_type/value_type
   class Compare = less<T>,   // set::key_compare/value_compare
   class Alloc = allocator<T> // set::allocator_type
   > class set;

set默认要求T支持小于比较，如果想按自己的需求可以自行实现仿函数传给第⼆个模版参数
set底层存储数据的内存是从空间配置器申请的
⼀般情况下，使用时不需要传后两个模版参数
set底层是⽤红⿊树(特殊的二叉搜索树)实现，增删查效率是O(logN),迭代器走中序遍历，可以保证数据有序

红黑树：

2.2 set的构造和迭代器

//⽆参默认构造
explicit set(const key_compare& comp = key_compare(),
   const allocator_type& alloc = allocator_type());

//迭代器区间构造

template <class InputIterator>
set(InputIterator first, InputIterator last,
   const key_compare& comp = key_compare(),
   const allocator_type & = allocator_type());

//拷⻉构造
set(const set& x);

//列表构造
set(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();

set支持正向迭代器和反向迭代器，遍历默认按升序(set默认小于比较) ，支持迭代器就支持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，因为修改数据会破坏底层的数据结构

2.3 set的增删查（不支持改）

增：

pair insert (const value_type& val); // 单个数据插⼊，如果已经存在则插⼊失败

set<int> se; //单个数据插⼊使用示例
se.insert(5);
se.insert(4);

void insert (initializer_list il); // 列表插⼊，已经在容器中存在的值不会插⼊

set<int> se; //列表插⼊使用示例

se.insert({1,2,5});

template<class InputIterator>

void insert (InputIterator first, InputIterator last); //迭代区间插入

vector<int> arr;
arr.push_back(2);
arr.push_back(4);
arr.push_back(1);

set<int> se;
se.insert(arr.begin(), arr.end()); //迭代区间插入使用示例

查：

iterator find (const value_type& val); //查找 val ，返回 val 所在的迭代器，没有找到返回 end()

set<int> se;
se.insert(5);
se.insert(2);
se.insert(1);
auto it = se.find(2); //查找val使用示例

size_type count (const value_type& val) const; //查找 val ，返回 Val 的个数

//对于set而言，数据会去重，返回值是0或1

set<int> se;
se.insert(5);
se.insert(2);
se.insert(1);
size_t n = se.count(2)；

//对于multiset，支持数据冗余，返回值 >=0

multiset<int> mse;
mse.insert(5);
mse.insert(2);
mse.insert(2);
mse.insert(2);
mse.insert(1);
size_t n = mse.count(2);

iterator lower_bound (const value_type& val) const; //返回小于等于 val 位置的迭代器

    set<int> se;
   se.insert(2);
   se.insert(4);
   se.insert(6);
   se.insert(5);
   auto it = se.lower_bound(3);

iterator upper_bound (const value_type& val) const; //返回⼤于 val 位置的迭代器

    set<int> se;
   se.insert(2);
   se.insert(4);
   se.insert(6);
   se.insert(5);
   auto it = se.upper_bound(4);

删：

size_type erase (const value_type& val); //删除 val ，返回删除成功的个数

对于set来说，不存在数据冗余，只能删除1个或0个，所以erase返回1或0

对于multiset而言，可能存在多个相同数据，所以erase返回值 >=0

set<int> se; //set
se.insert(2);

se.insert(2);
se.insert(4);
se.insert(1);

size_t ret = se.erase(2); //ret = 1

multiset<int> mse; //multiset
mse.insert(2);
mse.insert(2);
mse.insert(2);
mse.insert(4);

size_t ret = mse.erase(2); //ret = 3

iterator erase (const_iterator position); //删除⼀个迭代器位置的值，返回下一个位置的迭代器

当删除set中仅有的一个值之后，返回的迭代器会失效，不可访问

set<int> se;
se.insert(2);
se.insert(4);
se.insert(1);
se.insert(3);
auto it = se.begin();

auto it1 = se.erase(it);

iterator erase (const_iterator first, const_iterator last); //删除⼀段迭代器区间的值

set<int> se;
se.insert(2);
se.insert(4);
se.insert(1);
se.insert(3);

se.erase(se.begin(), se.end()); //删除se中的所有数据

3.1 map

map的声明如下

template < class Key,
   class T,
   class Compare = less<Key>,
   class Alloc = allocator<pair<const Key, T> >
   > class map;

Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的

map底层是⽤红⿊树实现
增删查改效率是 O(logN)
迭代器遍历是⾛的中序，所以是按key有序顺序遍历的

3.2 pair类型

map底层的红⿊树节点中的数据，使⽤pair存储键值对数据

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

3.2 map的构造和迭代器

map⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构

//无参默认构造

explicit map(const key_compare& comp = key_compare(),
   const allocator_type& alloc = allocator_type());

//迭代器区间构造

template <class InputIterator>
map(InputIterator first, InputIterator last,
   const key_compare& comp = key_compare(),
   const allocator_type & = allocator_type());

//拷贝构造

map (const map& x);

//列表构造

map(initializer_list<value_type> il,
   const key_compare& comp = key_compare(),
   const allocator_type& alloc = allocator_type());

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

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

3.3 map的增删查

map增接⼝，插⼊的pair键值对数据，跟set所有不同，但是查和删的接⼝只⽤关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value

Member types
key_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;

3.4 map数据的修改

map⽀持修改mapped_type数据，也就是second的值，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构

map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个⾮常重要的修改接⼝operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接⼝

需要注意从内部实现⻆度，map这⾥把我们传统说的value值，给的是T类型，typedef为 mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。

1.查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type值

iterator find(const key_type& k);

2.insert插⼊⼀个pair<key, T>对象

如果key已经在map中，插⼊失败，则返回⼀个pair<iterator, bool>对象，返回pair对象first是key所在结点的迭代器，second是false

如果key不在在map中，插⼊成功，则返回⼀个pair<iterator, bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true

pair<iterator, bool> insert(const value_type& val);

因此，⽆论insert插⼊成功还是失败，返回 pair 对象的 first 都会指向 key 所在的迭代器，insert 可以⽤来实现 operator[]

mapped_type& operator[] (const key_type& k);

3.5 multimap和map的差异

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改

map和set