《Game Engine Architecture》是一直以来我很有兴趣也很想阅读的书，书的译者是我很敬重的milo叶劲峰前辈（魔方引擎中心的大大）。

但是由于自己基础不牢，再加上这本厚厚的大书所带来的畏难情绪，同时自己过于功利总是把时间抽去做容易提升的事情，

以及n个自己给自己找的理由，让这个阅读计划一直搁置。

但这学期拿到了暑期实习的offer，刚巧也在魔方，对于就业的压力就减小了很多

再加上自己有意往引擎方向发展，阅读这本书就提上了日程。

今天把第五章的东西看完，看的内容不多但是感觉有收获，

书上讲的东西很干货，特别是谈及链表那个地方确实给了人很大的启发

---

第五章

5.3 容器

这个章节讲了一些基本上常用的数据结构，比较详细的分析了他们适用的场景

并且为我们自己亲自编写他们也提供了很不错的方案，是我觉得很有用很精华的内容

---

5.3.2 迭代器

问题c++的迭代器在我第一次学习的时候，我不知道他和直接i++的区别是什么

书中所说，迭代器像是数组索引或指针，可以移至下一个元素（我也知道）

但是！迭代器通常是容器类的友元，因此可以高效迭代访问容器，不向外面暴露容器类的实现细节

其次，迭代器简化了迭代过程，无论数据结构多复杂，我都可以 iterator++

这个又涉及到前置递增++i和后置递增i++的问题

原文：在深度流水线CPU上，前置递增必须完成递增才能使用这个值，会引起流水线停顿

在for循环里面前置和后置没有区别，当用到值的时候建议使用后置递增

在使用类类型的时候，由于前置和后置可能是自定义的运算符重载

而后置递增需要对对象进行拷贝，会造成性能消耗，因此在类类型尽量使用前置递增

---

5.3.3 算法复杂度

这个大家面试的时候应该都刷烂了，但是书里边对于复杂度的常见解释

写的不错所以还是可以记一下的：

若算法的运行时间和容器中的元素数目无关的话，称算法为O（1）；

若算法循环访问容器里面的元素，每个元素当访问一次，则算法为O（n）；

若算法有两层循环，每层循环访问每个元素一次，则算法为O（n2）（自动联想上标）；

若算法使用分治法（二分查找），每次都能消去余下元素的一半，则算法为O（logn）；

若算法执行一个子算法n次，且子算法为O（logn），则整个算法为O（nlogn）

最长预见的数量级O（1），O（logn）,O（n）,O（nlogn）,O（n2）

同时也应该考虑容器的内存布局和使用特性

数组的内存连续，更加缓存友好，且除了元素不需要额外的内存开销（对比链表需要存指向下一元素的指针）

若插入以及移除元素的速度很重要，则应该使用链表

---

5.3.4 自建容器

这里对于是否使用自建的数据结构提供了讨论，使用自建容器有以下好处：

• 可以自己控制如何分配内存，自由的进行优化
• 可自行提供第三方库没有的功能（stl中只能搜索单个最有关元素，而不能搜索n个）
• 不需要第三方库支持则可以消除第三方团队的外部依赖
• 可全权控制多线程或多核系统的保护机制

---

常见第三方：

STL：

优势：功能丰富，多平台的壮健表现，几乎所有c++编译器自带stl

缺点：难学，对于特定问题速度不如自建容器快，对比自建容器会占用更多内存

会进行许多动态分配，要控制stl的内存占用量

STL适合pc游戏引擎，因为对比游戏主机内存受限，缺乏高级CPU和虚拟内存

现代pc拥有高级虚拟内存系统，通常也能忽略物理内存不足的可能性

Boost：

优势：文档写得好，功能比stl更多，能有效处理智能指针

缺点：核心类是模板，可能会生成较大的lib，不适合小项目

不保证向后兼容，Boost团队也不提供保障。

---

数组和动态数组不加赘述，没什么好说的

---

链表这块讲的很不错：

外露式链表：

template<typename ELEMENT>
struct Link
{
   Link<ELEMENT>* Prev;
   Link<ELEMENT>* Next;
   ELEMENT* Elem;
}

节点数据结构和元素数据结构完全分离，每个节点含指针指向元素。

外露式链表的特点在于，一个元素可以置于多个链表中，只需要节点指向该元素

但分配节点时必须进行动态分配，许多时候会使用池分配器。

---

侵入式链表：

template<typename ELEMENT>
struct Link
{
   Link<ELEMENT>* Prev;
   Link<ELEMENT>* Next;
}
class SomeElement:public Link<SomeElement>
{
   //其他成员
}

使用侵入式链表的好处是，分配元素时无须再动态分配节点（已经获得了节点）

但每个元素不能置于多个列表中，（元素只有一个节点数据），因此侵入式链表不如外露式有弹性

---

循环链表的结构一般会包含头尾指针：

template<typename ELEMENT>
struct Link
{
   Link<ELEMENT>* Tail;
   Link<ELEMENT>* Head;
   
   //相关操作成员函数
}

用Link类来管理头尾指针有些好处:

template<typename ELEMENT>
struct Link
{
   Link<ELEMENT> Root; //包含了头尾指针
   
   
   //相关操作成员函数
}

这样一来最后节点的next和第一个节点的pre都是指向root的

这样设计能简化插入和移除的逻辑，我们先看看独立头尾指针移除元素的代码：

void LinkList::remove(Link<ELEMENT>& link)
{
  if(link.next)link.next.pre=link.pre;
  else this.Tail=link.pre  //移除链表末元素
  
  if(link.pre)link.pre.pre=link.next;
  else this.Head=link.next//移除链表首元素
  
  link.pre=link.next=nullptr;

}

在这个设计中首节点的pre和末节点的next必为空指针，若列表只有一个节点，则两个指针都会是空指针

不能单凭一个指针得知他是否属于一个链表

若使用root的设计：

void LinkList::remove(Link<ELEMENT>& link)
{
  ASSERT(link.next);
  ASSERT(link.pre);
  
  link.next.pre=link.pre;
  link.pre.pre=link.next;
  
  link.pre=link.next=nullptr;

}

最后节点的next和第一个节点的pre都是指向root的

因此若首节点的pre和末节点的next为空指针，则他不属于这个链表

---

字典，散列表（哈希表）

笔者不可能去手写哈希函数所以感觉没什么好说的哈哈哈

感觉还是乖乖std::吧

---

5.4 字符串

问了问魔方的引擎前辈

那边好像基本上都是在改ue的，说在游戏引擎里面处理这个不多

而且ue内部的字符串管理也还行

那我就选择性忽略这章吧

---

5.5 引擎配置

5.5这章感觉也没有提供什么对我比较有启发的东西

讲到ini，xml还有注册表什么的感觉算是短期之内比较接触不到的东西

如果具体想做的话应该很快能找到不错的解决方案

---

今天就到这吧 赶紧shadowmapping去了

2022.3.9 17:35

---