首页 > C++教程 > STL(标准模板库)
阅读:3,044
C++关联容器,STL关联容器
关联容器内部的元素都是排好序的,有以下四种。
不能修改 set 或 multiset 容器中元素的值。因为元素被修改后,容器并不会自动重新调整顺序,于是容器的有序性就会被破坏,再在其上进行查找等操作就会得到错误的结果。因此,如果要修改 set 或 multiset 容器中某个元素的值,正确的做法是先删除该元素,再插入新元素。
同理,也不能修改 map 和 multimap 容器中元素的关键字。
关联容器内部的元素或关键字之间比较大小可以用
使用关联容器的目的也就在于快速查找。当一个元素被插入关联容器时,该元素会和已有的元素进行比较,最终被插入一个合适的位置。
在关联容器中查找元素和插入元素的时间复杂度都是 O(log(n))。从 begin() 到 end() 遍历整个关联容器,就是从小到大遍历整个容器。
在排好序的 vector 和 deque 上进行折半查找,时间复杂度也可以是 O(log(n))。但是,对于插入、删除和查询交替进行的情况,使用 vector 和 deque 的效率不高。因为它们上面的插入和删除操作会引起元素的移动,时间复杂度是 O(n)。
关联容器一般是用平衡二叉树实现的。平衡二叉树的原理属于“数据结构”课程的内容,本教程不做介绍。
除了所有容器共有的成员函数外,关联容器还具有以下成员函数:
- set:排好序的集合,不允许有相同元素。
- multiset:排好序的集合,允许有相同元素。
- map:每个元素都分为关键字和值两部分,容器中的元素是按关键字排序的。不允许有多个元素的关键字相同。
- multimap:和 map 类似,差别在于元素的关键字可以相同。
不能修改 set 或 multiset 容器中元素的值。因为元素被修改后,容器并不会自动重新调整顺序,于是容器的有序性就会被破坏,再在其上进行查找等操作就会得到错误的结果。因此,如果要修改 set 或 multiset 容器中某个元素的值,正确的做法是先删除该元素,再插入新元素。
同理,也不能修改 map 和 multimap 容器中元素的关键字。
关联容器内部的元素或关键字之间比较大小可以用
<
运算符,也可以用自定义的比较器。因为有序,所以在关联容器上进行查找的速度较快。使用关联容器的目的也就在于快速查找。当一个元素被插入关联容器时,该元素会和已有的元素进行比较,最终被插入一个合适的位置。
在关联容器中查找元素和插入元素的时间复杂度都是 O(log(n))。从 begin() 到 end() 遍历整个关联容器,就是从小到大遍历整个容器。
在排好序的 vector 和 deque 上进行折半查找,时间复杂度也可以是 O(log(n))。但是,对于插入、删除和查询交替进行的情况,使用 vector 和 deque 的效率不高。因为它们上面的插入和删除操作会引起元素的移动,时间复杂度是 O(n)。
关联容器一般是用平衡二叉树实现的。平衡二叉树的原理属于“数据结构”课程的内容,本教程不做介绍。
除了所有容器共有的成员函数外,关联容器还具有以下成员函数:
- find:查找某个值。
- lower_bound:查找某个下界。
- upper_bound:查找某个上界。
- equal_range:同时查找上界和下界。
- count:计算等于某个值的元素个数。
- insert:插人一个元素或一个区间。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频