C++ 标准库系列课 - 你所不知道的 set 容 器 by 小彭老师（ @archibate ） 课件 & 代码： https://github.com/parallel101/course 上期回顾： https://www.bilibili.com/video/BV1qF411T7sd 课程安排 1. vector 容器初体验 & 迭代器入门 (BV1qF411T7sd) 2. 你所不知道的 拟出来的 + n 复杂度为 O(n) 。虽然低效，但至少可 以用了。 std::next 等价于 + • 但是这样手写三个 ++ 太麻烦了 ，而且是就地操作，会改变迭代 器本身。 • 因此标准库提供了 std::next 函 数，他的内部实现相当于这样： • 没错，他会自动判断迭代器是否 支持 + 运算，如果不支持，会 改为比较低效的调用 n 次 ++ 。 std::advance 等价于 • 如果找不到，则返回 end() 迭代器。 • 刚刚说过， end() 指向的是 set 的尾部 再之后一格元素，他指向的是一个不存在 的地址，不可能有任何元素在那里！因此 end() 常被标准库用作一个标记，来表示 找不到的情况。 Python 中的 find 找不 到元素时会返回 -1 来表示，也是这个思 想。 • iterator find(int const &val) const;

还为自身的标准库增加了非常多的工具和方法，诸如在语言自身标准的层面上制定了 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

图像。总共只花了 1 分钟。 图形学爱好者：我看中的是多核，目的是加速比，如果是单核，那多线程对我无用！ 某互联网公司：我看中的是异步，目的是无阻塞，即使是单核，多线程对我也有用。 因特尔开源的并行编程库： TBB https://link.springer.com/chapter/10.1007%2F978-1-4842-4398-5_2 安装 TBB • Ubuntu: • sudo apt-get article/details/111681426 详见 https://www.bilibili.com/video/BV1fa411r7zp 的 1:18:48 上一课的案例代码：基于标准库 基于 TBB 的版本：任务组 • 用一个任务组 tbb::task_group 启动多个 任务，一个负责下载，一个负责和用户交 互。并在主线程中等待该任务组里的任务 全部执行完毕。 • 区别在于，一个任务不一定对应一个线程 区别在于，一个任务不一定对应一个线程 ，如果任务数量超过 CPU 最大的线程数， 会由 TBB 在用户层负责调度任务运行在 多个预先分配好的线程，而不是由操作系 统负责调度线程运行在多个物理核心。 封装好了： parallel_invoke 更好的例子 第 1 章：并行循环 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency ） • 在“小学二

](https://git-scm.com/doc) - [GitHub 官方文档 ](https://docs.github.com/en) 古代： C 语言 近代： C++98 引入 STL 容器库 近现代： C++11 引入了 {} 初始化表达式 近现代： C++11 引入了 range-based for-loop 如果想使用 for_each 这个算法模板呢？ 我知道可以用 accumulate ）和生成器（ generator ） 未来： C++20 标准库加入 format 支持 跑远了！ • 鉴于 C++20 还没有普遍落地（例如 CMake 不支持 C++20 modules ）因此我们的课程 基于 C++17 标准，有时会谈到 C++20 作为扩展阅读。 C++ 有哪些面向对象思想？ C++ 思想：封装 比如要表达一个数组，需要：起始地址指针 v ，数组大小 nv 将多个逻辑上相关的变量包装成一个类 将他俩打包起来，避免程序员犯错 封装：不变性 比如当我要设置数组大小为 4 时，不能只 nv = 4 还要重新分配数组内存，从而修改数组起始地址 v 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 这种情况出现时，就意味着你需要把成员变量的读写封装为成员函数 不变性：请勿滥用封装 • 仅当出现“修改一个成员时，其他也成员要 被修改，否则出错”的现象时，才需要 getter/setter 封装。 •

https://github.com/parallel101/course C++ 标准库五大件：容器（ container ） C++ 标准库五大件：迭代器（ iterator ） C++ 标准库五大件：算法（ algorithm ） C++ 标准库五大件：仿函数（ functor ） C++ 标准库五大件：分配器（ allocator ） 侯捷 STL 侯捷 STL vector capacity() const noexcept; vector 容器： resize 的优化策略 • 注意这里 resize(7) 之后容量实际上扩充到了 10 而不是刚好 7 ，为什么 ？ • 因为标准库的设计者非常聪明，他料想到了你 resize(7) 以后可能还会来 个 resize(8) 甚至 resize(9) 之类的。为了减少重复分配的次数，他有一 个策略：当 resize 后的新尺寸变化较小时，则自动扩容至原尺寸的两倍 组大小（很多同学都号称自己实现过 vector ，都是这种 写法），那么如果要用 push_back 推入 n 个元素，就 需要重新分配内存 n 次，移动元素 n(n+1)/2 次。 • 而像标准库这样允许数组大小和实际容量不同，这样 push_back 在容量不足的时候就可以一次性扩容两倍， 只需重新分配 logn 次，移动元素 2n-1 次。 vector 容器： push_back

这里的解构函数也是多态的，他根据类型的不同 调用不同派生类的解构函数。 多态用于设计模式之“模板模式” • 这样之后如果有一个任务是要基于 eatFood 做文章，比如要重复 eatFood 两遍。 • 就可以封装到一个函数 eatTwice 里，这个函数只需接受他们共同的基类 IObject 作为参数，然后调 用 eatFood 这个虚函数来做事（而不是直接操作具体的猫和狗本身）。 • 这样只需要写一遍 思考：能不能把拷贝构造函数也作为虚函数？ • 现在我们的需求有变，不是去对同一个对象调用两次 eatTwice ，而是先把对象复制一份 拷贝，然后对对象本身和他的拷贝都调用一次 eatFood 虚函数。 • 代码如下，这要怎么个封装法呢？你可能会想，是不是可以把拷贝构造函数也声明为虚函 数，这样就能实现了拷贝的多态？不行，因为 C++ 规定“构造函数不能是虚函数”。 模板函数？未免有些差强人意 • 索性把 eatTwice this 指针所指向的类型，也就是当前所在类的类型 。 • 宏的缺点是他不遵守命名空间的规则，宏的名 字是全局可见的，不符合 C++ 的高大尚封装思 想。 • 宏： IOBJECT_DEFINE_CLONE • 高大尚 C++ 封装： zeno::IObject::clone() 如何批量定义 clone 函数？ • 另一种方法是定义一个 IObjectClone 模板 类。其模板参数是他的派生类

hash().pointer(11).dense(8) 。 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 • 这样就封装好了，通过模板的方式实现了 自定义的稀疏数据结构： • hash().pointer(11).dense(8) 开源的体素处理库： OpenVDB • OpenVDB 的稀疏体积，可以存储符号距 bits |= 1 << n; • 可以设置 bits 的第 n 位为 1 。 • bits |= 0 << n; • 则没有任何改变。 std::vector ：标准库帮你实现好了 • 其实标准库的 vector 是一个特化的版本 ，他会自动像刚刚说的把值看做 1bit ，然后八个 合并成一个 int8_t 。 • 不过效率比我们手写的低很多…… 不推荐使用 对象，而且效率很低。 • 如果配合用 decltype 和 auto 的话，他们不会正确推导出 bool ，影响我们正常使用模板元编 程。 • 一般认为 vector 是 C++ 标准库设计上的一个败笔，是为了向前兼容才保持这样不变的 。 • 他们就不应该直接特化 vector 而是哪怕搞另一个名字，比如 std::bit_vector 之类的都好 。 • 包括他的

就像你和同学随手“拉钩”定下的约定，这是 printf 约定俗成的。 • \ 就像正式合同，有法律效力的，这是 C 语言编译器规定好的。 C++ 字符串类 第 3 章 C 语言字符串操作繁琐 封装的 std::string 应运而生 封装的 std::string 应运而生 • string 可以从 const char * 隐式构造： • string s = “hello”; • string 具有 + 、 类型的，他们没有 + 运算 符。 • C++ 为了向前兼容，没办法改变 C 语言的这项规定，只能退而求其次，他另 外定义了一个 string 类，重载了 + 运算符，并告诉同学们：以后尽量用我这 个封装好的类，不要直接用 C 语言的 const char * 。 • 因此如果需要把两个字符串加在一起，就必须至少有一方是 string 才行。 • 可以用 string(“hello”) 这种形式包裹住每个字符串常量，这样就方便用 正确： C++14 新特性：自定义字面量后缀 • 不少同学就觉得这样好麻烦，其他语言都是直接 “ hello” 就是字符串类 型， C++ 还得套一层壳 string(“hello”) 才能变成安全封装的类型，才能用他 的成员函数。 • 因此， C++14 引入了一项缓解“键盘压力”的新特性： • 写 “ hello”_s 就相当于写 operator“”_s(“hello”, 5) ，就相当于

正是人类的本能，空出更多的脑力心力与精力，追求更新的事物。 但是，作为信息教育体系一员的我，不能不有version control。事实上我亦从来没有忘记初学 MFC 的痛苦：C++ 语言本身的技术问题是其一，MFC 庞大类别库的命名规则是其二，熟知 的Windows 程序基本动作统统不见了是其三，对象导向的观念与application framework 的 包装是其四。初学MFC programming 时，我的脑袋犹如网目过大的筛子，什么东西都留不住； Microsoft Foundation Classes 的缩写，这是一个架构在Windows API 之上的 C++ 类别库（C++ Class Library），意图使Windows 程序设计过程更有效率，更符合物 件导向的精神。MFC 在争取成为「Windows 类别库标准」的路上声势浩大。Symantec C++ 以及WATCOM C/C++ 已向微软取得授权，在它的软件开发平台上供应MFC。Borland 的缩写，这也是一个具备Application Framework 架势 的C++ 类别库，附含在Borland C++ 之中。 Application Framework - 在对象导向领域中，这是一个专有名词。关于它的意义，本书 第５章有不少介绍。基本上它可以说是一个更有凝聚力，关联性更强的类别库。并不是 每一套C++ 类别库都有资格称为Application Framework，不过MFC 和OWL