「set」及「map」使用指北

发表于 | 分类于 |  PV

set&map高频出现在笔试题&竞赛中，做总结如下

本文通过 http://www.cplusplus.com/reference 的 set&map API 介绍 set&map
有关红黑树的更多知识，请通过「任意门」跳转到我的另一篇博文（TODO）

引言

set&map 基于红黑树构成，借助其近似平衡树的特性，查询结构中元素的算法复杂度仅为 logN

以 AVL树 为例，其完全平衡树结构使得 $1073741824(2^{30})$ 个数字中查找一个数字最多只需要 30 次。

因此，基于红黑树封装的 set&map 广泛运用于比赛与实际项目中。

set/map 概述

  • 主要特点
    • set/ map 天然具备去重复+排序功能
    • set/ map 查询效率非常高（近似平衡二叉树）
  • 结构区别
    • map 基于红黑树（K-V结构）实现，封装了插入、迭代器等接口
    • set 基于红黑树实现，但可以看作抛弃了 value ，只存储 key
    • 实际源码通过rbtree<key, key>实现set、rbtree<key, pair<key, value>>实现map

此外对于

  • set/multiset 区别
    • multiset在底层红黑树中，key可以有重复值。
    • 在接口方面几乎没有区别

set

set 插入

1. 直接插值

1
2
3
4
5
6
//原型
pair<iterator,bool> insert (const value_type& val);
    
//实例
set<int> s;
s.insert(1);

其中：

  • value_type: The first template parameter (T)（模版参数）
  • 返回值中pair::first指向插入的元素的迭代器
  • 当该元素是新插入的值时（插入前set没有这个值），返回值中pair::second中的布尔值为true

2. 通过迭代器插值

1
2
3
4
5
6
7
8
9
//原型
iterator insert (iterator position, const value_type& val); //with hint (2)
    
//实例
set<int> s;
std::pair<std::set<int>::iterator,bool> ret;
    
ret = s.insert(1);
s.insert(ret,2);

其中：

  • 新的元素将会插入在原来迭代器的位置
  • 插入并不是强制插入（不是一定插入在选择的迭代器的位置），而是遵循给定的排序
    • 意味着插入从指定迭代器的位置开始寻找合适的插入点
    • 在已知一个合适的迭代器时，可以有利于性能提升

3. 插入两个迭代器中所有数据（泛型）

1
2
3
4
5
6
7
8
//原型
template <class InputIterator> 
void insert (InputIterator first, InputIterator last); //range (3)
    
//实例
set<int> s;
int myints[]= {5,10,15};
s.insert (myints,myints+3);

set 其他接口

其他常用接口比较简单，不在赘述。函数原型如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//删除 可选参数：迭代器、原始数据类型、迭代器范围
void erase (iterator position);
size_type erase (const value_type& val);
void erase (iterator first, iterator last);

//查询
iterator find (const value_type& val) const;
size_type count (const value_type& val) const;/*对于set来说与find接口没什么区别
                                                更多是考虑到与multiset保持一致性*/
                                                
//向上查询
iterator upper_bound (const value_type& val) const;//val作为上界，寻找一个最近的迭代器
//向下查询
iterator lower_bound (const value_type& val) const;//val作为上界，寻找一个最近的迭代器

map

map 插入

map的插入总体与set没有太大区别，在此仅强调不同部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
std::map<char,int> mymap;

//直接插值
//原型  
pair<iterator,bool> insert (const value_type& val);
//实例
mymap.insert ( std::pair<char,int>('a',100) );

//通过迭代器插入
//原型  
iterator insert (iterator position, const value_type& val);
//实例
std::pair<std::map<char,int>::iterator,bool> it;
it = mymap.begin();
mymap.insert (it, std::pair<char,int>('b',200));

//通过两个迭代器（泛型），取两者范围插入
//原型
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
//实例
std::map<char,int> anothermap;
anothermap.insert(mymap.begin(),mymap.find('c'));

其中对于map.find()

1
2
3
4
5
//原型
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

//key_type	The first template parameter (Key)（key_type 就是模版参数key）

在这里map的接口相比set有一个较大的区别是：

  • value_type: pair
  • mapped_type : The second template parameter (T)（第二个模版参数 value）

上述可以看作：value_type:pair<key, value>

map 其他接口

对于 count、upper_bound、erase方法，除了参数明确为key_type（模版参数）外，与set没有区别。

map 对方括号的重载

map中有一个十分实用的使用方法：通过重载方括号访问和插入元素

1
2
3
4
5
6
7
//原型
mapped_type& operator[] (const key_type& k);

//实例
//.....
mymap['a'] = "an element";
cout << mymap['a'] << endl; //输出为 an element

见以上代码，我们可以通过重载方括号实现：

  • 直接插入一个元素，格式为 mymap[key] = value;
  • 给定 key 输出对应 value 格式为 mymap[key]

根据 www.cplusplus.com 给出的源码参考，该重载函数的定义为

1
2
3
4
mapped_type& operator[] (const key_type& k)
{
    return (*((this->insert (make_pair(k,mapped_type()) )).first)).second;
}

简单剖析上述代码：
首先调用

1
2
3
//适当增减空格以增加可读性
this->insert ( make_pair(k,mapped_type() ) /*首先使用this指针调用insert函数
                                            其中make_pair<K, V> 定义匿名函数*/

此时map中一定存在希望插入的一对元素的值，插入动作已经完全完成

1
2
( this->insert(make_pair(k,mapped_type())) ).first /*insert返回pair<iterator,bool>
                                                    调用 xxx.first 得到迭代器*/

拿到了该对元素的迭代器

1
*((this->insert (make_pair(k,mapped_type()) )).first)

将上一步拿到的迭代器解引用，得到含有该对元素的pair类型

1
(*((this->insert (make_pair(k,mapped_type()) )).first)).second;

取得pair.second,即该对元素的value值

对于以下用法

1
cout << mymap['a'] << endl;

目的是获取 ‘a’ 对应的 value
实际先做插入操作，尽管插入失败，但仍能得到对应的元素对应的迭代器，继而取得目标 value

以上，重载方括号的实现极大地增强了可读性，同时提升了开发效率

不仅是 C++，读者可以在各类编程语言都能看到这种格式的操作，可见其魅力