【STL】map和set的原理及其使用

简介: 【STL】map和set的原理及其使用

关联容器

关联容器是c++中的一种数据结构,提供了一种通过键来访问值的方式。根据使用场景的不同,STL的关联容器有两种结构,树型结构和哈希结构。常见树形结构的关联容器有:map和set。map是一种键值对容器,里面存储的结构是<key,value>.set是一种集合容器,有序且唯一。常见的哈希结构的关联容器有unordered_map和unordered_set。

键值对

键值对用来表示具有一一对应关系的一种结构,该结构中包含两个成员变量keyvalue,key表示键值,value表示与key对应的值。我们常用的pair<key,value> 就是键值对。

下面观察STL源码中是如何定义pair的:

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

所以pair其实就是一个类模板,根据<>里的两个参数来实例化类,第一个参数表示key,第二个表示value。

pair的两个成员变量first表示key,second表示value。

set

set的介绍

在c++文档中是这么定义set的:

  1. set是按照一定次序存储元素的容器,其中class Compare控制比较逻辑,默认是小于。可以是一个仿函数,也可以是一个函数指针。
  2. set中的key必须是唯一的。不能修改key但是可以删除或者插入一个key。
  3. 在内部,set中的元素总是按照其内部比较对象(类型比较)所指定的特定严格强弱排序准则进行排序。
  4. set访问元素的平均时间复杂度为O(logn).
  5. set的底层是通过二叉搜索树(红黑树)来实现的

与map等容器不同,set存储的元素其实只有value,在底层是<value,value>.所以在插入元素时,只需要提供value即可,不需要构造键值对。使用set的迭代器进行遍历set时,会得到一个有序的序列。这是因为遍历的方式其实是二叉搜索树的中序遍历。

set的使用

set的模板参数列表有三个:

  • T:元素类型
  • Compare:用于控制set的比较逻辑,默认是小于
  • Alloc:控制set的空间管理方式,使用STL提供的空间管理配置器.

set的构造

函数声明1:

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

构造一个空的set,里面没有元素

函数声明2:

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

根据提供的范围[InputIterator,InputIerator last)里的值来一一构造。

函数声明3:

set (const set& x);
• 1

拷贝构造,根据提供的一个set对象去构造一个一模一样的另一个set对象。

set的迭代器

begin和end

分别指向set第一个元素和最后一个元素的下一个位置。

rbegin和rend表示const修饰的begin和end。

rbegin和rend

方向迭代器,分别指向set最后一个元素的下一个位置和第一个元素的位置。

crbegin和crend表示被const修饰的 rbegin和rend。

注意,const迭代器并不是指迭代器本身不能被修改,而是指向的元素不能被修改。

set的容量

empty()

检测set中的元素是否为空,空返回true,否则false.

size()

返回set中有效元素的个数

set的修改操作

下面讲一些比较常用的修改操作

insert

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

在set中插入元素x,实际上插入的是<x,x>构成的键值对,如果插入成功,返回一个迭代器和true构成的键值对。该迭代器指向插入set后的x。如果插入失败,说明x已经存在,返回一个迭代器和false构成的键值对。

erase

void erase ( iterator position )
void erase ( iterator first, iterator last )
  1. 删除set中position位置上的元素。
  2. 删除[first,last)这个区间的所有元素

clear

void clear ( ) 

清空set中的所有元素

find

iterator find ( const key_type& x ) const

返回指向元素x的迭代器

count

size_type count ( const key_type& x ) const

返回set中值为x的元素的个数.

map

map的介绍

map的文档介绍:

  1. 键值对映射 :map中的元素是一对键值对,每一个key都有一个value对应。
  2. 自动排序:与set类似,mao中的元素在插入的同时会进行排序,默认情况下是key小的排在前面。
  3. 唯一键:每个键在map中都是唯一的。
  4. map查找的时间复杂度是O(logn).
  5. 迭代器支持:支持使用迭代器来遍历map中的元素。本质上是搜索二叉树的中序遍历。
  6. 底层是用二叉搜索树(红黑树)实现的。
  7. 可以使用[key]访问对应的value

map和set的特性其实很像,只不过map中的元素更像是一个键值对。

map的构造

函数声明1

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

构造一个空的map对象,没有元素。

函数声明2

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

迭代器范围构造map,根据[first,last)范围内的元素一一构造出与其对应的map元素。

函数声明3

map (const map& x);

拷贝构造

map的迭代器

begin和end

begin:首元素的位置,end最后一个元素的下一个位置

cbegin和cend:与begin和end意义相同,但cbegin和cend所指向的元素不能修改

rbegin和rend

反向迭代器,rbegin在end位置,rend在begin位置,其++和–操作与begin和end操作移动相反

crbegin和crend:与rbegin和rend意义相同,但crbegin和crend所指向的元素不能修改

map的[]访问

当访问的key不存在,[key]操作会先将key插入到map中,返回默认的value.否则直接返回其value值。

map的修改操作

multiset

multiset的文档介绍:

multiset和set的区别就在于multiset可以存相同的元素。因此我们可以使用multiset对数组进行排序。

其内部结构和set都是一样的,都是用二叉搜索树(红黑树)实现的。

multimap

multimap的文档介绍:

multimap和map的区别就在于multimap可以存重复的key。此外,multimap不支持[key]操作

其内部结构和map都是一样的,都是用二叉搜索树(红黑树)实现的。

相关文章
|
4天前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
11 2
|
4天前
|
存储 C++ 容器
【C++】map和set深度讲解(下)
【C++】map和set深度讲解(下)
13 2
|
4天前
|
存储 自然语言处理 Java
【C++】map和set深度讲解(上)
【C++】map和set深度讲解(上)
15 2
|
14天前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
17 1
|
4天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
11 0
|
11天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
17 0
|
13天前
|
存储 C++ 索引
C++基础知识(八:STL标准库 Map和multimap )
C++ 标准模板库(STL)中的 map 容器是一种非常有用的关联容器,用于存储键值对(key-value pairs)。在 map 中,每个元素都由一个键和一个值组成,其中键是唯一的,而值则可以重复。
|
21天前
|
Dart
Dart之集合详解(List、Set、Map)
Dart之集合详解(List、Set、Map)
20 1
|
26天前
|
存储 JavaScript 前端开发
JavaScript进阶-Map与Set集合
【6月更文挑战第20天】JavaScript的ES6引入了`Map`和`Set`,它们是高效处理集合数据的工具。`Map`允许任何类型的键,提供唯一键值对;`Set`存储唯一值。使用`Map`时,注意键可以非字符串,用`has`检查键存在。`Set`常用于数组去重,如`[...new Set(array)]`。了解它们的高级应用,如结构转换和高效查询,能提升代码质量。别忘了`WeakMap`用于弱引用键,防止内存泄漏。实践使用以加深理解。
|
6天前
|
存储 安全 Java
Java基础之集合Map
【7月更文挑战第8天】Java中的Map集合以键值对方式存储数据,如`Map&lt;&quot;name&quot;, &quot;张三&quot;&gt;`。Map接口定义了存取、判断、移除等操作,包括`put`、`get`、`containsKey`等方法。HashMap是最常用的实现,基于哈希表,允许null键值,但不保证顺序。其他实现包括同步的Hashtable、处理属性文件的Properties、保持插入顺序的LinkedHashMap、基于红黑树的TreeMap、弱引用的WeakHashMap、并发安全的ConcurrentHashMap和针对枚举优化的EnumMap。
12 4