【C++ 笔记四】STL 标准模板库 —— 容器基础

news/2024/11/28 5:36:15/

【C++ 笔记四】STL 标准模板库 —— 容器基础

文章目录

  • 【C++ 笔记四】STL 标准模板库 —— 容器基础
    • I - 概述 STL
      • 1.1 - 范围与定义
      • 1.2 - 组成与关系
      • 1.3 - 实用举例
    • II - 概述容器
      • 2.1 - 迭代器
      • 2.2 - 容器的结构与分类
      • 2.3 - 序列式容器
      • 2.4 - 关联式容器
      • 2.5 - 不定序容器
      • 2.6 - 总述
    • III - 参考书目

I - 概述 STL

1.1 - 范围与定义


Standard Template Library (标准模板库) 包含于 Standard Library (标准库) 中,都封装于命名空间 std 中。

属于泛型编程 (Generic Programming) ,使用模板 (template) 为主要工具来编写的程序。

1.2 - 组成与关系


STL 包含六大组件 :

  1. 容器 (Containers)
  2. 分配器 (Allocators)
  3. 算法 (Algorithms)
  4. 迭代器 (Iterators)
  5. 适配器 (Adapters)
  6. 仿函数 (Functors)

这六大组件之间的关系图如下:

在这里插入图片描述

容器 用来存储数据,数据占用内存,容器背后有一个部件负责内存的分配与释放,这个组件就是分配器 ,此操作对用户透明,所以在使用容器时,基本不需要去管内存的分配与释放。

算法 ,如常用的 sort 排序和查找等,算法通过 迭代器 去访问容器的内容,有时我们排序需要自定义排序方式,这些自定义的方法就是 仿函数 ,其他的一些细节的操作就是通过 适配器 来完成的。

1.3 - 实用举例


如下,使用了六个组件的一段代码:

int arr[6] = { 19, 23, 52, 18, 50, 9 };std::vector<int, allocator<int>> vec(arr, arr+6);std::cout << count_if(vec.begin(), vec.end(), 
not1(bind2nd(less<int>(), 50)));

首先来识别一下代码中的各个元素:

在这里插入图片描述
代码中首先创建一个 6 个元素的整型数组,然后基于数组构建一个 整型容器 vector<int> vec ,容器使用整型的默认分配器,count_if 为算法,通过 vec 的首尾迭代器访问容器中的全部元素,此算法为条件计数,仿函数 less<int>() 比较任意两个元素的小于是否满足。

bind2nd 为仿函数适配器,将仿函数的第二个元素绑定为 50 ,即所有小于 50 的元素,not1 同样为仿函数适配器,将原来的结果取反,即 vec 中所有大于等于 50 的元素个数,所以输出结果为 2。

II - 概述容器

2.1 - 迭代器


迭代器是一种泛化的指针,可以使用 ++-- 去访问容器中的元素,需要注意它的访问区间是一个 前闭后开 的区间。

在这里插入图片描述
c.begin() 解引用是容器的第一个元素,
c.end() 指向的是容器最后一个元素的下一个元素,所以不能解引用,即 *(c.end()); 可能导致程序异常,程序崩溃异常退出。

基于范围的 for 循环 (range-based for loop),使用迭代器遍历元素语法:

for (decl : coll) {statement;
}
// 遍历
for (auto elem : container)  {// ...
}
// 修改
for (auto& elem : container) {//...
} 
// 查找,建议使用 算法
auto iter = std::find(c.begin(), c.end(), target);

示例

std::vector<double> vec = {/* ... */}; 
// 遍历
for (double elem : vec) {std::cout << elem << std::endl;
}
// 修改
for (double& elem : vec) {elem *= 3;
}
// 查找
std::vector<double>::iterator iter = std::find(vec.begin(), vec.end(), 1.0);

2.2 - 容器的结构与分类


  • 序列式容器

在这里插入图片描述

  • 关联式容器 (associative containers) ,基于红黑树的实现

在这里插入图片描述

  • 不定序容器 (unordered containers), 或者叫无序容器,基于哈希表实现

在这里插入图片描述

2.3 - 序列式容器


  • array,数组:固定大小,初始时需指定长度,不可更改。元素数量不能动态增长,支持随机访问。

在这里插入图片描述

  • vector,向量,可变长度数组:可单向动态增长,两倍扩容或会造成内存空置。支持下标,随机访问,尾部以外的位置插入/删除可能会比较慢。
    插入使用 insert ,尾部添加元素 push_backemplace_back,不提供 push_frontemplace_front 接口,由于首部添加需要移动所有元素,耗时操作。

在这里插入图片描述

  • deque,双向增长,实质上伪双边增长,实现为映射管理多个分段连续内存。
    两端操作都比较快,支持 push_backemplace_backpush_frontemplace_front

在这里插入图片描述

  • list,双向链表,每个元素包含两个指针,支持双向顺序访问。在链表任何位置插入/删除都很快。动态单个增长, “一个萝卜,一个坑” ,没有空置内存,但相同元素情况下,占用内存大于 vector 。
    非连续内存,不支持随机访问,但遍历缓慢

在这里插入图片描述

  • forward_list,单链表,与 list 相同,在任何位置插入删除都很快。相较 list,一个指针更节约内存,但迭代器不支持递减运算符 ( -- ),不提供 push_backemplace_back 尾端插入函数,由于过于耗时。

在这里插入图片描述

  • stackqueue 栈与队列 ,为容器适配器,表示两种数据结构 队列 ,栈先进后出 (FILO first in last out),队列先进先出 (FIFO first in first out) 。插入方式 push ,删除方式 pop 。不属于容器,不对外提供迭代器访问,不提供随机访问,会破坏结构设计。

2.4 - 关联式容器


关联式容器底层实现为红黑树,查询快,但插入耗时较久,由于每次插入都需要排序。

  • set,集合,元素只存在一份,不重复。
  • multiset,相同的元素可存在多份。

在这里插入图片描述

  • map,键值对 (key value pair),键存在时,insert , emplace 都会插入失败,[] 赋值会覆盖。使用 [] 访问时,键不存在会创建。C++ 17 为提高性能,增加 try_emplace 接口,在键存在时,不会构造参数,在值复杂时可较多节省内存,提升性能。
  • multimap,相同的键可存在多份,不支持 [] 访问。

在这里插入图片描述

2.5 - 不定序容器


不定序容器底层实现为哈希表,插入元素,对其计算哈希值,分配到对应的 bucket (桶)上,哈希值计算可能会产生哈希冲突,即不同的值计算的哈希值相同。哈希表的查找时间复杂度为 O(1),虽然元素哈希值相同时,还是会进行顺序查找,但不改变不定序容器查找基本为 O(1) 的情况。

为了避免较多的顺序查找,当 bucket 数量与元素个数相同时,bucket 会进行两倍扩容,之前的元素会被打散,重新计算哈希值,分布到新的 bucket 后。也会产生较多的内存空置,如 bucket 后无任何的元素。

  • unordered_map
  • unordered_set
  • unordered_multimap
  • unordered_multiset

在这里插入图片描述

先哈希查找,后循序查找。

2.6 - 总述


  • 查询

序列式容器查找为顺序查找时间复杂度为 O(n),关联式容器为红黑树时间复杂度 O(log n),不定序容器为哈希表基本上为 O(1)。
查询效率:不定序容器 > 关联式容器 > 序列式容器

关联式容器和不定序容器都提供自身的 find 函数, STL 算法也提供 std::find 查找,但使用容器自身的查找会更快捷

  • 排序

list 容器自身也提供 sort 接口,STL 算法提供的 std::sort 查找无法对 list 进行查找,因为 std::sort 接收的迭代器需要为随机访问迭代器类型,而 list 的迭代器为双向顺序访问迭代器。编码时若使用则会产生编译错误。

std::list<int> container = { 5, 6, 10, 1, 4, 8 };
std::sort(container.begin(), container.end(), greater<int>());

编译报错:

C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2676: binary '-': 'const std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<_Ty>>>' does not define this operator or a conversion to a type acceptable to the predefined operator
1>        with
1>        [
1>            _Ty=int
1>        ]
1>D:\GZC\Work\Train\TrainDemo\TrainDemo\TrainDemo\TrainDemo.cpp(17): note: see reference to function template instantiation 'void std::sort<std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>,std::greater<_Ty>>(const _RanIt,const _RanIt,_Pr)' being compiled
1>        with
1>        [
1>            _Ty=int,
1>            _RanIt=std::_List_iterator<std::_List_val<std::_List_simple_types<int>>>,
1>            _Pr=std::greater<int>
1>        ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2672: '_Sort_unchecked': no matching overloaded function found
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2780: 'void std::_Sort_unchecked(_RanIt,_RanIt,iterator_traits<_Iter>::difference_type,_Pr)': expects 4 arguments - 3 provided
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3328): note: see declaration of 'std::_Sort_unchecked'

需要修改为

std::list<int> container = { 5, 6, 10, 1, 4, 8 };
container.sort(greater<int>());

III - 参考书目


《STL源码剖析》 — 侯捷
《C++ Primer》— 中文版 第 5 版


http://www.ppmy.cn/news/338468.html

相关文章

webpack的一些常用打包配置

1.webpack 是什么&#xff1f; webpack 是一个模块化打包工具 2.模块是什么&#xff1f; 模块我理解就是 import xx 后面导入的文件就是一个模块 它可以是js css 图片 等等 3&#xff0c;webpack的配置文件的作用&#xff1f; 就是根据需求自定义配置webpack webpack默认只能打…

PhotoShop .psd文件格式读取分析(结合unity)

用了photoshop那么久&#xff0c;从来没仔细想过它到底用了哪些算法。想一想就觉得倒抽一口凉气。 传闻photoshop的创始人&#xff0c;和wps创始人一样&#xff0c;就一个程序员写好了这第一版的成品。同样是做人&#xff0c;咋就差距这么大呢&#xff1f; 千古疑问 所以这个…

史上最简单的 Nginx 教程,没有之一!

作者&#xff1a;哆啦A梦的猜想 链接&#xff1a;https://juejin.im/post/5d81906c518825300a3ec7ca 安装 安装依赖 安装 nginx 之前&#xff0c;确保系统已经安装 gcc、openssl-devel、pcre-devel 和 zlib-devel 软件库 gcc 可以通过光盘直接选择安装openssl-devel、zlib-dev…

一个合格的中级前端工程师需要掌握的技能笔记(下)

Github来源&#xff1a;一个合格的中级前端工程师需要掌握的技能 | 求星星 ✨ | 给个❤️关注&#xff0c;❤️点赞&#xff0c;❤️鼓励一下作者 大家好&#xff0c;我是魔王哪吒&#xff0c;很高兴认识你~~ 哪吒人生信条&#xff1a;如果你所学的东西 处于喜欢 才会有强大的动…

miranda- core src tree

1、小子&#xff0c;敢泡我马子&#xff01;你说吧&#xff0c;是单挑还是群殴&#xff1f;群殴&#xff0c;我们一帮殴你一个&#xff1b;单挑&#xff0c;你挑我们一帮&#xff01;       2、常函数和指数函数e的x次方走在街上&#xff0c;远远看到微分算子&#xff0c; …

python 怎么得到图像深度图 软件_如何用 Python 和 fast.ai 做图像深度迁移学习?...

本文带你认识一个优秀的新深度学习框架&#xff0c;了解深度学习中最重要的3件事。 框架 看到这个题目&#xff0c;你可能会疑惑&#xff1a;老师&#xff0c;你不是讲过如何用深度学习做图像分类了吗&#xff1f;迁移学习好像也讲过了啊&#xff01; 说得对&#xff01;我要感…

python深度神经网络文本二分类代码_如何用Python和深度神经网络识别图像?

只需要10几行Python代码&#xff0c;你就能自己构建机器视觉模型&#xff0c;对图片做出准确辨识和分类。快来试试吧&#xff01; 视觉 进化的作用&#xff0c;让人类对图像的处理非常高效。 这里&#xff0c;我给你展示一张照片。 如果我这样问你&#xff1a; 你能否分辨出图片…

使用graphhopper(map-matching)进行地图匹配

因为在做国创项目的时候需要进行地图匹配&#xff0c;在地图匹配的过程中也遇见了很多问题&#xff0c;在此记录&#xff0c;希望我的经历可以帮助大家规避一些问题&#xff0c;节约时间 在github上面有关地图匹配的开源项目有很多&#xff0c;我在此分享一下&#xff1a; bm…