Qliphoth's Blog

前言 本节开始，将会分析 STL 中的仿函数（Functor）部分的内容。在进入这一章之前，让我们回顾一下到目前为止我们都实现了哪些内容。 首先，我们实现了 Allocator，这个组件负责空间的分配，是其他组件实现的基石；随后我们实现了 Iterator，它是沟通容器与算法之间的桥梁，有了迭代器，才能使算法完全在一个抽象的层面上工作，对于泛型编程的实现十分重要；紧接着我们实现了各种 Container，包括顺序容器与关联容器等，容器是大多数人对 STL 的第一印象，也是最经常被使用的组件；最后我们实现了一大堆的 Algorithm，可以在容器上实现各种各样的操作，如 sort，rotate 等。 到目前为止，似乎已经比较完美了，既然如此，最后的 Functor 与 Adaptor 又有怎样的重要作用呢？ 可以这么说，如果把目前为止实现的 STL 内容，比作原版的 MC 的话，那 Functor 和 Adaptor 就是 MC 的 Mod 接口。 是的，即使目前为止的功能已经足够解决大部分编程问题，但它们终究是封闭的，algorithm.h 中的算法虽然多，但总是有限。而 Functo ...

前言 本节是算法部分的最后一小节了，将会主要介绍 stl_algo.h 中的 sort()，以排序函数作为压轴倒也十分合理，毕竟无论是面试还是工作或学习中的使用，排序都是最经常被提及的一个话题。稍后将会看到，作为对效率有着很高追求的 STL，对于 sort() 函数的设计，依然十分精彩。 sort STL 所提供的各式各样算法中，sort() 是最复杂最庞大的一个。这个算法接受两个 RandomAccessterators，然后将区间内的所有元素以渐增方式由小到人重新排列.第二个版本则允许用户指定一个仿函数，作为排序标准。STL 中，的所有关系型容器都拥有自动排序功能（底层结构采用 RB-tree，hashtable 不在标准的 STL 范围内），所以不需要用到这个 sort 算法。至于序列式容器中的 stack、queue 和 priority-queue 都有特别的出入口，不允许用户对元素排序。剩下 vector、deque 和 list，前两者的迭代器属于 RandomAccesslterators，适合使用 sort 算法，list 的迭代器则属于 BidirectionelI ...

前言 本节将会分析 merge 与 inplace_merge 的实现，二者的作用都是合并两个有序的区间，不同之处在于 inplace_merge 是原地合并，会更加复杂。 merge merge() 的作用为将 [first1, last1)、[first2, last2) 两个有序区间的元素合并到以 result 为起始的空间中，重载版本接受一个仿函数 comp 来比较元素的大小，原理十分简单，这里就直接附上代码。 123456789101112131415161718192021222324252627/*****************************************************************************************/// merge// 要求两个序列有序// 将两个经过排序的集合 S1 和 S2 合并起来置于另一段空间，返回一个迭代器指向最后一个元素的下一位置/****************************************************************************** ...

前言 本节将会分析 stl_algo.h 中 next_permutation 与 prev_premutation 的实现，之所以分析这两个函数倒不是因为他们的实现有多么精彩（像 copy() 那样），而是“下一个排列”与“上一个排列”这种问题十分经典，解法也很固定。 STL 提供了两个用来计算排列组合关系的算法，分别是 next_permucation 和 prev_permutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列 {a,b,c}。这个序列有六个可能的排列组合: abc，acb，bac，bca，cab，cba。这些排列组合根据 less-than 操作符做字典顺序的排序。也就是说，abc 名列第一，因为每一个元素都小于其后的元素。acb是次一个排列组合，因为它是固定了a（序列内最小元素）之后所做的新组合。同样道理、那些固定b （序列内次小元素）而做的排列组合，在次序上将先于那些固定 c 而做的排列组合。以 bac 和 bca 为例，bac 在 bca之前，因为序列 ac 小于序列 ca。面对bc ...

前言 本节就来分析一下 rotate 的实现。为什么前言就一句话！ rotate rotate 的作用为将 [first,middle) 内的元素和 [middle,last) 内的元素互换。middle 所指的元素会成为容器的第个元素。如果有个数字序列 { 1,2,3,4,5,6,7}，对元素 3 做旋转操作，会形成 {3,4,5,6,7,1,2}。rotate() 可以交换两个长度不同的区间，如下所示。 做过力扣189. 轮转数组 的人都知道，实现这种效果最简单的方法就是分别在前半段，后半段以及整个区间上各翻转一次，这里的前后段以 middle 分界，这样就可以达到 rotate 的效果，并且代码也最好理解。 当然，STL 中的 rotate 函数仍然不是简单地这样实现的，按照《STL 源码剖析》，rotate 函数的全貌如下： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 ...

前言 从本节开始，将会分析 algo.h 中的算法，这部分的算法有很多，也不可能逐一分析，因此这里就挑几个典型且重要的进行分析，即使这样依然有很多啊喂，主要会分析 equal_range、rotate、next_permutation、merge、sort、nth_element，其他的函数如果读者感兴趣的话可以自行查看 STL 的实现。 equal_range 算法 equal_range 是二分查找法的一个版本，试图在已排序的 (first, last) 中寻找 value。它返回一对迭代器 i 和 j，其中 i 是在不破坏次序的前提下，value 可插入的第一个位置（亦即lower_bound）,j 则是在不破坏次序的前提下, value 可插入的最后一个位置（亦即upper_bound）。 当 (first, last) 并未含有与 vaiue 相同的任何元素时，返回的区间将是一个空区间，即返回的 i 和 j 指向同一个位置。 这个函数的效果有点类似于 python 中的 bisect_left 和 bisect_right 综合后的结果，STL 中与此对应的二分查找算法为 l ...

前言 本节将会分析 algobase.h 中的算法，algobase.h 中存放的都是一些比较基础的算法，如 max()、min()、copy() 等，这里就挑其中最具有代表性的 copy() 函数来分析，除了 copy() 外还有许多如 copy_backward()、move()、move_backward() 等函数，STL 对这些函数效率上的优化方式与 copy() 的处理基本是一致的，就不再分析。 copy 不论是对客端程序或对 STL 内部而言，copy() 都是一个常常被调用的函数。由于 copy 进行的是复制操作，而复制操作不外乎运用 assignment operator 或 copy constructor （copy算法用的是前者），但是某些元素型别拥有的是 trivialassignment operator，因此，如果能够使用内存直接复制行为（例如标准函数 memmove 或 memcpy），便能够节省大量时间。为此，SGI STL的copy 算法用尽各种办法，包括函数重载（function overloading）、型别特性（type traits）、偏特化 ...

前言 上一节介绍了 STL 中算法的分类以及泛化过程，这一节将介绍数值算法以及集合相关的算法，这部分算法包含在 STL 的 stl_numeric.h 以及 algo.h 中，在 TinySTL 中被放在 numeric.h 以及 set_algo.h 中。 numeric 算法 数值算法中主要包括四个算法：accumulate、adjacent_difference、inner_product、partial_sum，这些算法都不会改变处理区间的值，即都是非质变算法。 accumulate accumulate(first, last, init) 的作用为对 [first, last) 内的元素进行以 init 为初值的累加，并返回求和的结果。 重载版本可以接收一个二元仿函数，以初值 init 对每个元素进行二元操作。 1234567891011121314151617181920212223/*****************************************************************************************/// ac ...

前言 从本节开始，将会持续介绍 STL 中的算法（Algorithm）部分的内容，算法也是很庞大的一个组件，光是《STL 源码剖析》中列出的算法就有接近 80 个，大部分算法还有许多重载，十分繁杂，因此算法部分这里就只挑一部分具有代表性的算法进行分析，如：copy、sort、merge 等。 STL 中的大部分文件都放在这三个文件中：stl_numeric.h、stl_algobase.h、stl_algo.h，分别代表了数值算法、基础算法以及其他的大部分算法，其中关于集合（set）的一些算法如交集（intersection）、并集（union）等也放在了 stl_algo 中，而在 TinySTL 里，这部分内容被单独放进了 set_algo 里。 本节将主要介绍 STL 中的算法分类以及算法的泛化思想，算是一个开胃菜。 质变算法与非质变算法 所有的STL算法都作用在由迭代器 (first, last) 所标示出来的区间上。 所谓“质变算法（mutating algorithms）”，是指运算过程中会更改区间内（迭代器所指）的元素内容。诸如 copy、swap、replace、fil ...

前言 前面用四节的内容分析了 STL-hashtable，本节将会分析基于 hashtable 的四种容器：unordered_set、unordered_map、unordered_multiset、unordered_multimap。这四种容器并未在 STL 的标准规格内，是 SGI-STL 额外提供的。 这四种容器以 hashtable 为底层机制，使用方法与 set、map 等完全相同。不同之处在于，使用红黑树实现的容器都会自动排序而使用 hashtable 的容器不会自动排序。 这四种容器所做的事情也几乎都只是转调用了 hashtable 的接口而已，没有什么复杂的地方。 unordered_set 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991 ...

前言 上一节介绍了 hashtable 的构造等功能的实现，本节将会介绍 hashtable 最重要的增删查改功能（与基于红黑树的 set 和 map 相同，hashtable 实现的 unordered_set 与 unordered_map 也不允许修改键值，仅允许修改 pair 类型元素的实值）。 增删元素 与 RB-tree 相同，由于需要同时支持 multiset 与 set 等容器，因此 hashtable 内部要提供两套不同的插入与删除元素的逻辑。 1234567891011121314151617181920212223242526272829303132333435363738394041424344public: // 修改容器相关操作 template <class ...Args> iterator emplace_multi(Args&&... args); template <class ...Args> tinystl::pair<iterator, bool> emplace_ ...

前言 上一节简要分析了 hashtable 的数据结构，包括节点的结构、迭代器的结构以及 hashtable 自身的结构，还是需要说明一下，本文实现的 hashtable 与 STL 中的原生 hashtable 有一定的差别，但逻辑几乎相同，读者如果想完整地实现原生 STL-hashtable 还请阅读源码。 本节将会介绍 hashtable 的构造与析构函数等的实现。 hashtable 的构造与析构 123456789101112131415161718192021222324252627282930313233343536373839public: // 构造、复制、移动、析构函数 // 这里使将构造函数声明为 explicit，因为后两个参数都缺省了，可以通过 size_type // 直接进行隐式转换，会产生一些不必要的 bug explicit hashtable(size_type bucket_count, const Hash& hash = Hash(), ...

记录一个 MPTPS 项目的完成过程

前言 上一节介绍了 hashtable 的相关概念，本节开始将会介绍 STL 中的 hashtable。与 RB-tree 相同，MyTinySTL 的哈希表实现也与 STL 中有所差别，并且 《STL 源码剖析》中对于 STL-hashtable 的具体介绍也不太详细，因此这里还是主要分析 MyTinySTL 中的实现。虽然说有些差别，但是总体的代码逻辑还是一致的。 按照惯例，首先将介绍 hashtable 的数据结构。 关于 std::hashtable 的分析 由于我们实现的 hashtable 与 STL 中的有所差别，因此在讨论数据结构之前还是先看一下 STL 中 hashtable 的一些特点，打开 hashtable.h 可以看到关于 hashtable 的很长一段注释，以下截取部分分析： 1234567891011121314/* * Each _Hashtable data structure has:** - _Bucket[] _M_buckets* - _Hash_node_base _M_before_begin* - size_type ...

前言 本文将会持续总结 ue 的 GamePlay 框架相关内容。 GameModes ue 中有两个主要类负责处理进行中游戏的相关信息：Game Mode 和 Game State。 即使最开放的游戏也拥有基础规则，而这些规则构成了 Game Mode。在最基础的层面上，这些规则包括： 出现的玩家和观众数量，以及允许的玩家和观众最大数量。 玩家进入游戏的方式，可包含选择生成地点和其他 生成/重生 行为的规则。 游戏是否可以暂停，以及如何处理游戏暂停。 关卡之间的过渡，包括游戏是否以动画模式开场。 基于规则的事件在游戏中发生，需要进行追踪并和所有玩家共享时，信息将通过 Game State 进行存储和同步。这些信息包括： 游戏已运行的时间（包括本地玩家加入前的运行时间）。 每个个体玩家加入游戏的时间和玩家的当前状态。 当前 Game Mode 的基类。 游戏是否已开始。 Game Modes 的任务是定义和实现规则。Game Modes 常用的基类有两个：AGameModeBase 与 AGameMode。 AGameModeBase 所有 Ga ...