快速上手 STL中 map 和 set 的使用
1.set和map简介
map和set都是树形结构的关联式容器,其底层都以红黑树(一种平衡二叉搜索树)作为底层结构。像vector、list这些容器是序列式容器,其中存储的是一个个的元素本身;关联式容器存储的是一个个的<Key,Value>结构的键值对。
那键值对是什么呢?键值对是一种用来表示具有 一 一 对应关系的结构,该结构中一般只有两个成员变量,一个Key,一个Value,并且一个Key对应一个Value;关联式容器中的Key值是不允许修改的。
2.set和map使用的注意事项
使用set的注意事项:
- 0.使用set时,需要包含<set>头文件
- 1. set与map不同,map中存储的是真正的键值对<key, value>,set中只放value,但在底层实际存放的是由<value, value>构成的键值对。
- 2. set中插入元素时,只需要插入value即可,不需要构造键值对。
- 3. set中的元素不可以重复,因此可以使用set进行去重。
- 4. 使用set的迭代器遍历set中的元素,可以得到有序序列;这是因为set的底层是二叉搜索树,并且迭代器遍历的时候走的是中序遍历,激发了二叉搜索树的 “隐藏技能”。
- 5. set中的元素默认按照小于来比较
- 7. set中的元素不允许修改,否则会破坏set的底层结构。
使用map的注意事项:
- 0.使用map时,要包含<map>头文件。
- 1.map中的元素是键值对,在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:typedef pair<const key, T> value_type;
- 2. map中的key是唯一的,并且不能修改。
- 3. 在内部,map中的元素总是按照键值key进行比较排序的,并且默认按照小于的方式对key进行比较。
- 4. map中的元素如果用迭代器去遍历,可以得到一个有序的序列。
- 5. map支持下标访问符 [ ] ,operator[]中实际进行插入查找,即在[]中放入key,就可以找到与key对应的value。
3.set 的使用
函数声明 | 功能介绍 |
set (const Compare& comp = Compare(), const Allocator&=Allocator() ); | 构造空的set |
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); | 利用迭代器区间构造 |
set ( const set<Key,Compare,Allocator>& x); | set的拷贝构造 |
函数声明 | 功能介绍 |
iterator begin() | 返回set中起始位置元素的迭代器 |
iterator end() | 返回set中最后一个元素后面的迭代器 |
函数声明 | 功能介绍 |
bool empty ( ) const | 检测set是否为空,空返回true,否则返回true |
size_type size() const | 返回set中有效元素的个数 |
函数声明 | 函数功能 |
pair<iterator,bool> insert (const value_type& x ) | 在set中插入元素x,实际插入的是<x, x>构成的键值对,如果插入成功,返回<该元素在set中的位置,true>,如果插入失败,说明x在set中已经存在,返回<x在set中的位置,false> |
void erase ( iterator position ) | 删除set中position位置上的元素 |
size_type erase ( const key_type& x ) | 删除set中值为x的元素,返回删除的元素的个数 |
void erase ( iterator first, iterator last ) | 删除set中[first, last)区间中的元素 |
void swap (set<Key,Compare,Allocator>& st ); | 交换set中的元素 |
void clear ( ) | 将set中的元素清空 |
iterator find ( const key_type& x ) const | 返回set中值为x的元素的位置 |
size_type count ( const key_type& x ) const | 返回set中值为x的元素的个数 |
4.map的使用
函数声明 | 功能介绍 |
map() | 构造一个空的map |
函数声明 | 功能介绍 |
begin()和end() | begin返回首元素的位置,end返回最后一个元素的下一个位置 |
函数声明 | 功能介绍 |
bool empty ( ) const | 检测map中的元素是否为空,是返回 true,否则返回false |
size_type size() const | 返回map中有效元素的个数 |
mapped_type& operator[] (const key_type& k) | 返回key对应的value的引用 |
函数声明 | 功能介绍 |
pair<iterator,bool> insert (const value_type& x ) | 在map中插入键值对x,注意x是一个键值对,返回值也是键值对:iterator代表新插入元素的位置,bool代表释放插入成功 |
void erase ( iterator position ) | 删除position位置上的元素 |
size_type erase ( const key_type& x ) | 删除键值为x的元素 |
void erase ( iterator first, iterator last ) | 删除[first, last)区间中的元素 |
void swap (map<Key,T,Compare,Allocator>& mp ) | 交换两个map中的元素 |
void clear ( ) | 将map中的元素清空 |
iterator find ( const key_type& x) | 在map中插入key为x的元素,找到返回该元 素的位置的迭代器,否则返回end |
const_iterator find ( const key_type& x ) const | 在map中插入key为x的元素,找到返回该元 素的位置的const迭代器,否则返回cend |
size_type count ( const key_type& x ) const | 返回key为x的键值在map中的个数,注意 map中key是唯一的,因此该函数的返回值 要么为0,要么为1,因此也可以用该函数来 检测一个key是否在map中 |
5.map中重载的 operator[ ] 的原理
operator[] 是通过调用insert实现的;insert的返回值是pair<iterator,bool> 类型的键值对;如果插入成功,insert会返回插入成功的那个元素的迭代器,并将bool值设为true;如果插入失败,insert会返回 已经存在的元素的迭代器,并将bool值设为false。pair<iterator,bool> 类型的键值对中的iterator是指向 pair<K,V>类型的键值对的,operator[]返回的是该键值对中的Value值的引用。
map中重载的operator[] 具有 插入,查找,修改的功能。
- 插入:当使用[]时,map中不存在该Key值,如果使用了Value值,就插入该Key和Value,如果没指定Value,就会使用默认构造赋予Value一个初始值。
- 查找:使用Key值,返回对应的Value值。
- 修改:当使用[]时,map中存在Key值相同,Value值不同的键值对;那么该键值对的Value就会被修改成新的Value。