C++中的-map和set
最新推荐文章于 2022-12-09 19:48:19 发布
Kurumi Tokisaki
最新推荐文章于 2022-12-09 19:48:19 发布
阅读量90
收藏
点赞数
最新推荐文章于 2022-12-09 19:48:19 发布
阅读量90
收藏
点赞数
1.
关联式容器
2.
键值对
3.
树形结构的关联式容器
1.
关联式容器
在初阶阶段，我们已经接触过
STL
中的部分容器，比如：
vector
、
list
、
deque
、
forward_list(C++11)
等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面
存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器
也是用来存储数据的，与序列式容器不同的是，其
里面存储的是
<key, value>
结构的
键值对，在数据检索时比序列式容器效率更高
。
2.
键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量
key
和
value
，
key
代
表键值，
value
表示与
key
对应的信息
。比如：现在要建立一个英汉互译的字典，那该字典中必然
有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
该单词，在词典中就可以找到与其对应的中文含义。
SGI-STL
中关于键值对的定义：
3.
树形结构的关联式容器
根据应用场景的不桶，
STL
总共实现了两种不同结构的管理式容器：树型结构与哈希结构。
树型结
构的关联式容器主要有四种：
map
、
set
、
multimap
、
multiset
。这四种容器的共同点是：使
用平衡搜索树
(
即红黑树
)
作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一
个容器。
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
)
{}
};
3.1 set
3.1.1 set
的介绍
翻译：
1. set
是按照一定次序存储元素的容器
2.
在
set
中，元素的
value
也标识它
(value
就是
key
，类型为
T)
，并且每个
value
必须是唯一的。
set
中的元素不能在容器中修改
(
元素总是
const)
，但是可以从容器中插入或删除它们。
3.
在内部，
set
中的元素总是按照其内部比较对象
(
类型比较
)
所指示的特定严格弱排序准则进行
排序。
4. set
容器通过
key
访问单个元素的速度通常比
unordered_set
容器慢，但它们允许根据顺序对
子集进行直接迭代。
5. set
在底层是用二叉搜索树
(
红黑树
)
实现的。
注意：
1.
与
map/multimap
不同，
map/multimap
中存储的是真正的键值对
<key, value>
，
set
中只放
value
，但在底层实际存放的是由
<value, value>
构成的键值对。
2. set
中插入元素时，只需要插入
value
即可，不需要构造键值对。
3. set
中的元素不可以重复
(
因此可以使用
set
进行去重
)
。
4.
使用
set
的迭代器遍历
set
中的元素，可以得到有序序列
5. set
中的元素默认按照小于来比较
6. set
中查找某个元素，时间复杂度为：
$log_2 n$
7. set
中的元素不允许修改
(
为什么
?)
8. set
中的底层使用二叉搜索树
(
红黑树
)
来实现。
3.1.2 set
的使用
1.
set
的模板参数列表
3.2 map
3.2.1 map
的介绍
翻译：
1. map
是关联容器，它按照特定的次序
(
按照
key
来比较
)
存储由键值
key
和值
value
组合而成的元
素。
2.
在
map
中，键值
key
通常用于排序和惟一地标识元素，而值
value
中存储与此键值
key
关联的
内容。键值
key
和值
value
的类型可能不同，并且在
map
的内部，
key
与
value
通过成员类型
value_type
绑定在一起，为其取别名称为
pair:
typedef pair<const key, T> value_type;
3.
在内部，
map
中的元素总是按照键值
key
进行比较排序的。
4. map
中通过键值访问单个元素的速度通常比
unordered_map
容器慢，但
map
允许根据顺序
对元素进行直接迭代
(
即对
map
中的元素进行迭代时，可以得到一个有序的序列
)
。
5. map
支持下标访问符，即在
[]
中放入
key
，就可以找到与
key
对应的
value
。
6. map
通常被实现为二叉搜索树
(
更准确的说：平衡二叉搜索树
(
红黑树
))
。
3.2.2 map
的使用
1.
map
的模板参数说明
5. map中元素的修改
396
暂无认证
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
