C++ 标准库系列课 - 你所不知道的 set 容 器 by 小彭老师（ @archibate ） 课件 & 代码： https://github.com/parallel101/course 上期回顾： https://www.bilibili.com/video/BV1qF411T7sd 课程安排 1. vector 容器初体验 & 迭代器入门 (BV1qF411T7sd) 2. 你所不知道的 7. C++ 标准输入输出流 & 字符串格式化 8. traits 技术，用户自定义迭代器与算法 9. allocator ，内存管理与对象生命周期 set 和 vector 的区别 • 都是能存储一连串数据的容器 。 • 区别 1 ： set 会自动给其中的 元素从小到大排序，而 vector 会保持插入时的顺序。 • 区别 2 ： set 会把重复的元素 去除，只保留一个，即去重。 拟出来的 + n 复杂度为 O(n) 。虽然低效，但至少可 以用了。 std::next 等价于 + • 但是这样手写三个 ++ 太麻烦了 ，而且是就地操作，会改变迭代 器本身。 • 因此标准库提供了 std::next 函 数，他的内部实现相当于这样： • 没错，他会自动判断迭代器是否 支持 + 运算，如果不支持，会 改为比较低效的调用 n 次 ++ 。 std::advance 等价于

计算机如何表达字符 • 众所周知，计算机只能处理二进制 整数，字符要怎么办呢？ • 于是就有了 ASCII 码表，他规定， 每个英文字符（包括大小写字母、 数字、特殊符号）都对应着一个整 数。在计算机里只要存储这个的整 数，就能代表这个字符了。 • 例如 32 代表空格， 48 代表 ‘ 0’ ， 65 代表 ‘ A’ ， 97 代表 ‘ a’…… • 32~126 这些整数就用于是表示这些 可显示字符 ，因为 cpp 字符串没要求一定是 ‘ \0’ 结尾，字符串里是可以包含 ‘ \0’ 的。 C++14 新特性：自定义字面量后缀 • 如果你 using namespace std; 其实标准库已经自动帮你定义好了 “” s 后缀。 • 这里 “ hello”s 就等价于原本繁琐的 string(“hello”) 了。 C++14 新特性：自定义字面量后缀 • 如果你觉得 using namespace 233_i32 ， cpp 做得到吗？ • cpp 标准委员会：谢邀，人在 cpp14 ，已经在 operator“”_i32 了。 • 其实 cpp 这种自定义挺好的，把自由度给到用户。 • 例如标准库说 “ hello”s 是 std::string ，“ hello”s 是 std::string_view 。 • 我也可以定义一个 “ hello”ms 是 mylib::String ，而且还是受

第 0 章：稀疏矩阵 稠密数组存储矩阵 用 foreach 包装一下枚举的过程 改用 map 来存储 分离 read/write/create 三种访问模式 foreach 直接给出当前坐标指向的值 改用 unordered_map 来存储 unordered_map 手动 read(i, j) 也一样速度 索性把坐标和值打包成 tuple ，存储在 vector 按行压缩（ Compressed e91.html 第 1 章：稀疏网格 稠密网格计算粒子经过的格点数量 改用更小的 char 存储 只用一个 bit 存储，一个 char 可以存储 8 个 bit 用 map 来存储 读取：如果不存在，则读到 0 写入：如果不存在，则创建该表项 用 unordered_map 来存储 map 基于红黑树，会按照键值排序，需要键值具有 operator< 重载，复杂度 O(logn) 16x16 分块存储 分块能减少 unordered_map 中存储的表项数量，从而减轻哈 希的压力。但意味着键值在空间上需要具有一定的局域性，否 则 会浪费分块中一 部分空间。 然而我们这里是 要用他记录粒子 经过的点，因此 具有一定空间局 域性，能够被分 块优化。 实际上空间局域 性正是稀疏网格 能够实现的一大 前提，稍后详细 讨论。 在 16x16 分块的基础上，只用一个 bit 存储 图片解释稀疏的好处

如果你没看出来（哪怕是其中一个），那就要好好上小彭老师的课哦！ 字节（ byte ） 和位（ bit ）有什么区别 • 众所周知，计算机是二进制的，存储的实际上是一个个 0 和 1 。 • 每个存储 0 或 1 的空间称为一个位（ bit ），一位可以存储 0 或 1 两个可能的值。 • 现在的计算机都会把 8 个位打包成一个字节（ byte ），也就是说： 1 字节 = 8 位。 • 一字节可以表示 = 1024 KB • 1 GB = 1024 MB • 1 TB = 1024 GB • 也有人说 1 KiB 才是 1024 B 的，但是很少有人采用这种写法…… • 在买硬盘和 u 盘等存储设备的时候，往往会出现容量减少的情况，这是因为生产厂家按照 的是 1000 倍的换算的，而我们的系统中一般都是按照 1024 倍去计算的。 字还被用于表示内存地址 • 字的长度除了决定一次处理 大小（也就是字的大 小）决定了他能读写的内存大小，例如： • 由于 16 位计算机的寄存器只能存储 16 位，他只能访问 65536 字节（ 64 KB ）的内存 。 • 由于 32 位计算机的寄存器只能存储 32 位，他只能访问 4 GB 的内存。 • 由于 64 位计算机的寄存器能存储 64 位，他理论上能访问 16777216 TB 的内存！ • 因此，如果你的电脑内存超过了 4

CPU 的厂商早就意识到了内存延迟高，读写效率低 下的问题。因此他们在 CPU 内部引入了一片极小的存储 器——虽然小，但是读写速度却特别快。这片小而快的 存储器称为缓存（ cache ）。 • 当 CPU 访问某个地址时，会先查找缓存中是否有对应的 数据。如果没有，则从内存中读取，并存储到缓存中； 如果有，则直接使用缓存中的数据。 • 这样一来，访问的数据量比较小时，就可以自动预先加 宽。三级缓存也装不下，那就取决于主内存 的带宽了。 • 结论：要避免 mem-bound ，数据量尽量足 够小，如果能装的进缓存就高效了。 L2: 256 KB L3: 12 MB 缓存的工作机制：读 • 缓存中存储的数据结构： • struct CacheEntry { • bool valid; • uint64_t address; • char data[64]; • }; 架构中每个条目的存储 64 字节的数据，这个条目 又称之为缓存行（ cacheline ）。 • 当访问 0x0048~0x0050 这 4 个字节时，实际会导致 0x0040~0x0080 的 64 字节数据整个被读取到缓存中。 • 这就是为什么我们喜欢把数据结构的起始地址和大小对齐到 64 字节，为的是不要浪费缓存行的存储空间。 缓存的工作机制：写 • 缓存中存储的数据结构：

项目的文件后缀名全部改成 .cu ，都能编 译出来。 • 这是 CUDA 的一大好处， CUDA 和 C++ 的关 系就像 C++ 和 C 的关系一样，大部分都兼容 ，因此能很方便地重用 C++ 现有的任何代码库 ，引用 C++ 头文件等。 • host 代码和 device 代码写在同一个文件内，这 是 OpenCL 做不到的。 编写一段在 GPU 上运行的代码 • 定义函数 kernel ，前面加上 ，类型为 T 的数组 抽象的 std::allocator 接口 • vector 会调用 std::allocator 的 allocate/deallocate 成员 函数，他又会去调用标准库的 malloc/free 分配和释放内存空间 （即他分配是的 CPU 内存）。 • 我们可以自己定义一个和 std::allocator 一样具有 allocate/deallocate 的统一内存 (managed) 上分配。 • 实际上这种“骗”来魔改类内部行为的操作，正是现代 C++ 的 concept 思想所在。因此替换 allocator 实际上是标准库允许的 ，因为他提升了标准库的泛用性。 进一步：避免初始化为 0 • vector 在初始化的时候（或是之后 resize 的时候）会调用所 有元素的无参构造函数，对 int 类型来说就是零初始化。然而 这个初始化会是在

https://github.com/parallel101/course C++ 标准库五大件：容器（ container ） C++ 标准库五大件：迭代器（ iterator ） C++ 标准库五大件：算法（ algorithm ） C++ 标准库五大件：仿函数（ functor ） C++ 标准库五大件：分配器（ allocator ） 侯捷 STL 侯捷 STL vector vector 容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 是一个模板类，第一个模板参数是数组里 元素的类型。 • 例如，声明一个元素是 int 类型的动态数组 a ： • vector a; vector 容器：构造函数和 size • vector 可以在构造时指定初始长度。 • explicit vector(size_t const noexcept; vector 容器： data() 获取首地址指针 • data() 会返回指向数组中首个元素的指针， 也就是等价于 &a[0] 。由于 vector 是连续 存储的数组，因此只要得到了首地址，下一 个元素的地址只需指针 +1 即可。 • 因为指针的 p[i] 相当于 *(p + i) ，因此可以 把 data() 返回的首地址指针当一个数组来 访问。

1 章：添加源文件 一个 .cpp 源文件用于测试 CMake 中添加一个可执行文件作为构建目标 另一种方式：先创建目标，稍后再添加源文件 如果有多个源文件呢？ 逐个添加即可 使用变量来存储 建议把头文件也加上，这样在 VS 里可以出现在“ Header Files” 一栏 使用 GLOB 自动查找当前目录下指定扩展名的文件，实现批量添加源文件 启用 CONFIGURE_DEPENDS gmake 。 对于 VS 7 ， 它被设置为 devenv. 对于 Nmake 构建文件，它的值为 nmake 。 • CMAKE_DL_LIBS: 包含 dlopen 和 dlclose 的库的名称。 • CMAKE_COMMAND: 指向 cmake 可执行程序的全路径。 • CMAKE_CTEST_COMMAND: 指向 ctest 可执行程序的全路径。 • CMAKE_EDIT_COMMAND: 第 3 章：链接库文件 main.cpp 调用 mylib.cpp 里的 say_hello 函数 改进： mylib 作为一个静态库 改进： mylib 作为一个动态库 改进： mylib 作为一个对象库 https://www.scivision.dev/cmake-object-libraries/ 对象库类似于静态库，但不生成 .a 文件，只由 CMake 记住该库生成了哪些对象文件

还为自身的标准库增加了非常多的工具和方法，诸如在语言自身标准的层面上制定了 std::thread，从而支持了并发编程，在不同平台上不再依赖于系统底层的 API，实现了语言层面的跨 平台支持；std::regex 提供了完整的正则表达式支持等等。C++98 已经被实践证明了是一种非常成功 的『范型』，而现代 C++ 的出现，则进一步推动这种范型，让 C++ 成为系统程序设计和库开发更好的 语言。Concept 在学习现代 C++ 之前，我们先了解一下从 C++11 开始，被弃用的主要特性： 注意：弃用并非彻底不能用，只是用于暗示程序员这些特性将从未来的标准中消失，应该尽 量避免使用。但是，已弃用的特性依然是标准库的一部分，并且出于兼容性的考虑，大部分 特性其实会『永久』保留。 • 不再允许字符串字面值常量赋值给一个 char *。如果需要用字符串字面值常量赋值和初始化一个 char *，应该使用 const (convert_type)），应该使用 static_cast、 reinterpret_cast、const_cast 来进行类型转换。 • 特别地，在最新的 C++17 标准中弃用了一些可以使用的 C 标准库，例如 、 、 与 等 • . . . . . . 等等 还有一些其他诸如参数绑定（C++11 提供了 std::bind