Qliphoth's Blog

前言 heap 并不归属于 STL 容器组件，它是个幕后英雄，扮演 priority queue 的助手。顾名思义，priority queue 允许用户以任何次序将任何元素推人容器内，但取出时一定是从优先权最高 (也就是数值最高) 的元素开始取。binary max heap 正是具有这样的特性，适合作为 priority queue的底层机制。 ———— 《STL源码剖析》侯捷 本节将会分析 heap 的实现。 heap 让我们做一点分析。如果使用 list 作为 priority queue 的底层机制，元素插人操作可享常数时间。但是要找到 list 中的极值，却需要对整个 list 进行线性扫描。我们也可以改变做法，让元素插人前先经过排序这-一关，使得 list 的元素值总是由小到大 (或由大到小)，但这么一来，虽然取得极值以及元素删除操作达到最高效率，可元素的插人却只有线性表现。 虽然以 binary search tree 作为 priority queue 的底层机制，元素的插入和极值的取得就有 O(logN) 的表现。但杀鸡用牛刀，未免小题大做，一来 binary ...

前言 正常来说，我们一般使用的运算符是对基本的数据类型进行操作，但是在C++中有了对象，导致对象无法通过运算符进行运算，故引入了运算符重载即需要重新的定义这些运算符，赋予已有运算符新的功能，使它能够用于特定类型执行特定的操作。运算符重载的实质是函数重载，它提供了C++的可扩展性。 运算符重载有成员函数与全局函数两种方式，本文将简要分析二者的关系。 作为成员函数进行重载 定义一个测试用的类并在类内重载 + 运算符。 123456789101112131415161718192021class addFloat{public: addFloat(float f) : m_f(f) { cout << "---construct addFloat(float f)---" << endl; } addFloat operator+(const addFloat& a) { cout << "---addFloat operator+( ...

前言 STL 中，stack 及 queue 均以底部容器完成其所有工作，而具有这种 “修改某物接口，形成另一种风貌” 之性质者，称为 adapter（配接器），因此，STL stack 与 STL queue 往往不被归类为 container（容器），而被归类为 container adapter。 ———— 《STL源码剖析》侯捷 本节将会分析 STL 中的 stack 及 queue 的实现。 stack stack 是一种先进后出 (First In Last Out，FILO) 的数据结构。它只有一个出口。stack 允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取 stack 的其它元素。换言之，stack不允许有遍历行为，因此 stack 不具有迭代器。将元素推人stack的操作称为push，将元素推出stack 的操作称为pop。 以某种既有容器作为底部结构，将其接口改变，使之符合 “先进后出” 的特性，形成一个stack，是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一 ...

记录一个比较神奇的 bug 在测试 deque 的过程中，发现： 当在 d1 的倒数第二个位置插入两个 7 的操作后，d1 的最后一个数字莫名变成了 9，在一番对照后发现这个数字是前面d1.assign(8, 9) 遗留的产物，为什么会出现这种现象呢？ 首先，之前的 insert 操作没有问题，并且 deque 也能正常工作，且除了这里的异常外别的测试均能顺利通过，说明极大概率是这个 insert 的重载出了问题，我们回到原函数中查看： 可以看到插入 n 个元素的 insert 操作除前后插入的特殊情况外，剩余的操作全权交由 fill_insert 负责，因此我们再跳转到 fill_insert fill_insert 是一个很长的函数，根据要插入的位置的前后元素个数的比较来执行更有效率的插入方式，且每种方式都要根据要插入元素个数与 deque 中对应方向上元素个数的关系来执行不同的操作。这里我们在倒数第二个位置插入，且插入元素个数（2）大于 pos 后方元素个数（1），因此问题一定出在 973 ~ 978 之间的语句中。 根据代码可以看出，函数的执行逻辑为：1. 填充超出原数 ...

前言 STL 中，deque 是一种双向开口连续线性空间（逻辑上），deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作，二在于 deque 没有所谓容量 (capacity) 观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，功能十分强大；但对应的代价则是：deque 的迭代器与数据结构为了维持其 “整体连续” 的假象，被设计得异常复杂。 ———— 《STL源码剖析》侯捷 本节将会分析 deque 的插入与删除操作。 map 及 buffer (node) 的管理 由于 deque 采用分段式存储的方式，将数据存放在分段的缓冲区 ( node ) 中，并使用中控器 ( map ) 进行管理。而 map 与每个 node 本身也是有容量的概念的，在插入操作时必然会引起 map 及 node 的变化，在分析插入操作之前让我们先来分析一下 deque 是如何管理 map 及 node 的。 1234567891011121314151617181920212223242526272829303132 ...

前言 本来想接着把 deque 的部分给总结完的，但在看后面的函数部分时突然发现自己不是很清楚清楚 push_back 与 emplace_back 的区别，在这里总结一下。 emplace_back() 是 C++11 之后，新加入的方法，和 push_back() 一样的是都是在容器末尾添加一个新的元素进去，不同的是 emplace_back() 在效率上相比较于 push_back() 有了一定的提升。 push_back() 首先分析较为简单直观的 push_back() 方法。对于 push_back() 而言，最开始只有 void push_back( const T& value ); 这个函数声明，后来从 C++11 ，新加了void push_back( T&& value ) 函数，以下为 C++ 中的源码实现： 1234567891011121314151617181920212223242526272829/** * 以下程序来自STL源码 bits/stl_vector.h * * @brief Add data to the e ...

前言 STL 中，deque 是一种双向开口连续线性空间（逻辑上），deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作，二在于 deque 没有所谓容量 (capacity) 观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，功能十分强大；但对应的代价则是：deque 的迭代器与数据结构为了维持其 “整体连续” 的假象，被设计得异常复杂。 ———— 《STL源码剖析》侯捷 值得一提的是，在 MYTinySTL 原始仓库中，deque 部分的实现也与原始 STL 的区别也比较大，比如 insert 与 reallocate 部分的逻辑等，这部分内容博主也进行了一些修改。 本节将会分析 deque 设计、迭代器、构造及析构等内容。 deque deque 由一段一段的定量连续空间构成，并使用中控器 ( map ) 与迭代器来维护与访问它们。 deque 的中控器 deque 采用一块所谓的 map (注意，不是 STL 的 map 容器) 作为主控。这里所谓 map 是一小块连续空问，其中每个元素 ...

前言 本篇博客是为了给下一篇博客：UE 中的委托机制，铺路的。起因是在学习 ue 的过程中发现 ue 使用委托这个概念的频率与深度都比 unity 中要高得多，因此在这里总结一下学习 unity 期间对于委托的理解。 C# 中的委托与事件 C# 委托 ( delegate ) C# 中的委托（Delegate）类似于 C 或 C++ 中函数的指针。委托（Delegate） 是存有对某个方法的引用的一种引用类型变量。引用可在运行时被改变。 委托（Delegate）特别用于实现事件和回调方法。所有的委托（Delegate）都派生自 System.Delegate 类。 声明委托 委托声明决定了可由该委托引用的方法。委托可指向一个与其具有相同标签的方法。 例如，假设有一个委托： 1public delegate int MyDelegate (string s); 上面的委托可被用于引用任何一个带有一个单一的 string 参数的方法，并返回一个 int 类型变量。 声明委托的语法如下： 1delegate <return type> <delegate-name> ...

前言 相较于 vector 的连续线性空间，list 就显得复杂许多、它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，1ist 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list 永远是常数时间。 ———— 《STL源码剖析》侯捷 本篇博客将会分析 STL 中 list 的 sort。值得注意的是，在原始的 MyTinySTL 仓库中，作者 list 部分的实现方式是有些怪异的，包括但不限于：使用了本该出现在 SGI-STL 的 slist 中的 base_ptr 与 node_ptr 来代表 list 的指针、没有实现 transfer 函数、sort 的实现也很繁杂；保险起见，下面的解析均以 SGI-STL 中的实现为准。 sort 在分析 list 的 sort 之前，需要弄清楚一件事情：为什么 list 不能使用 STL 算法中的 sort 函数而是需要在内部设计一个自己的 sort 函数？ 很多人以及博客会说：因为 list 维护的并不是一个连续的空间，因此不能使用 STL 的 sort。但实际上，deque 内部 ...

前言 相较于 vector 的连续线性空间，list 就显得复杂许多、它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，1ist 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list 永远是常数时间。 ———— 《STL源码剖析》侯捷 本篇博客将会分析 STL 中 list 的基本函数。值得注意的是，在原始的 MyTinySTL 仓库中，作者 list 部分的实现方式是有些怪异的，包括但不限于：使用了本该出现在 SGI-STL 的 slist 中的 base_ptr 与 node_ptr 来代表 list 的指针、没有实现 transfer 函数、sort 的实现也很繁杂；保险起见，下面的解析均以 SGI-STL 中的实现为准。 list 的构造函数 辅助函数 以下函数为实现构造函数的辅助函数，包括对于空间的分配与释放，节点的构造与析构等。 1234567891011121314151617181920212223242526272829303132template <class T, class Alloc = allo ...

前言 相较于 vector 的连续线性空间，list 就显得复杂许多、它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，1ist 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list 永远是常数时间。 ———— 《STL源码剖析》侯捷 本篇博客将会分析 STL 中 list 的结构定义部分。值得注意的是，在原始的 MyTinySTL 仓库中，作者 list 部分的实现方式是有些怪异的，包括但不限于：使用了本该出现在 SGI-STL 的 slist 中的 base_ptr 与 node_ptr 来代表 list 的指针、没有实现 transfer 函数、sort 的实现也很繁杂；保险起见，下面的解析均以 SGI-STL 中的实现为准。 list SGI-STL 中的 list 是一个 双向环状链表。对删除、插入的时间复杂度为O(1)O(1)O(1)，效率相当高；但是随机访问的时间复杂度为O(n)O(n)O(n)。另外，list在插入和删除操作后迭代器并不会失效。 __list_node 以下是 list 的节点结构。 123456 ...

前言 vector 的数据安排以及操作方式，与 array 非常相似。两者的唯一差别在于空间的运用的灵活性。array 是静态空间，一旦配置了就不能改变；vector 是动态空间，随着元素的加人，它的内部机制会自行扩充空间以容纳新元素。因此，vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助，vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。 ———— 《STL源码剖析》侯捷 本篇博客将会分析 STL 中 vector 的实现。 vector 的型别定义与数据结构 这里摘取部分 TinySTL::vector 的型别及成员变量定义部分代码进行分析。 1234567891011121314151617181920212223242526272829303132333435363738// 模板类 vectortemplate <class T>class vector {// 静态断言，用于在编译期间判断 T 是否为 bool 类型static_assert(!std::is_same<bool, T>::v ...

前言 以STL的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作，默默付出。但若以 STL 的实现角度而言，第一个需要介绍的就是空间配置器，因为整个STL 的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放资料。不先掌握空间配置器的原理，难免在阅读其它STL组件的实现时处处遇到挡路石。 ———— 《STL源码剖析》侯捷 本篇博客将介绍 Allocator 的最后一部分：内存处理工具，之所以要介绍完 Iterator 之后再写这篇是因为理解这部分的实现需要 traits 的前置知识。 内存处理工具 STL 定义有五个全局函数，作用于未初始化空间上。这样的功能对于容器的实现很有帮助，看到它们肩负的重任。前两个函数是用于构造的construct() 和用于析构的 destroy()，另三个函数是 uninitialized_copy()，uninitialized_fill()，uninitialized_fill_n()，下面将依次介绍这些函数。 construct & destro ...

继续被 C++ 折磨

前言 迭代器（iterators）是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。《Designt Patterns》一书提供有 23 个设计模式（design patterns）的完整描述，其中iterator 模式定义如下：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。 不论是泛型思维或 STL 的实际运用，迭代器（iterators）都扮演着重要的角色。STL 的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在-起。容器和算法的泛型化，从技术角度来看并不困难，C++的class templates 和 function templates 可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。 ———— 《STL源码剖析》侯捷 本篇博客将会讲解 STL 中的 type_traits 与 iterator 组件完整的实现。 __type_traits iterator_traits 负责萃取迭代器的特性，__type_t ...