体系结构与内核分析

OOP VS GP

<big>OOP将datas和methods关联在一起，GP却将datas和methods分开来。
　　GP可以让Containers和Algorithms两个团队各自进行工作，只需要通过Iterator联通，让另一个团队使用。
　　对于list来说，由于其迭代器不能进行加减运算，所以不能采用Algorithem所提供的sort排序算法，所以list是通过OOP自己实现一个sort。
　　对于algorithms来说，无论哪种算法，几乎都是通过元素的比较运算，通过迭代器来对容器进行各种操作。</big>

操作符重载与模板

<big>对于一些特殊的操作符如：　::　.　.　?:　*这四个操作符不能进行重载。
　　模板内容见前几期笔记内容。</big>

分配器allocator

<big>C++的动态内存分配，最终都是通过调用malloc来实现的。malloc在分配内存空间的时候，不仅仅只是分配所需要的内存大小，还会存在其他的内存消耗，比如说内存对齐，记录分配空间大小的区块和debug内存等等。详见上次作业operator new部分。
对于VC++6.0和BC5.0大部分的容器默认都是采用的allocator这个分配器。分配器通过allocate和deallocate来调用operator new和operator delete进行分配和释放内存，而operator new和operator delete又是通过嗲用malloc和free进行的操作。allocate和deallocate可以直接通过对象调用，如下：

不推荐直接调用

alloc的实现模型

容器之间的实现关系与分类

部分容器是通过其他容器作为底层实现的

链表list

<big>list为双向链表，每一个节点除了数据所占用的空间，还需要两个指针对象，指向当前结点的上一个节点和下一个节点，最后一个节点的下一个节点的next指向第一个节点成为一个循环（为了实现前闭后开，所以特意加了一个空节点，尾后迭代器指向该节点）。

节点设计

链表模型

对于链表的迭代器iterator并不是一个指针，因为list并不是一个连续的空间，所以必须自定义操作符重载让它具有类似于指针的作用，即为智能指针。
　　对于++、--操作符重载，由于这两种操作符都只对应一个操作符，但是操作符可以前置也可以后置，对于这种操作符的重载就必须先，区分到底是前置还是后置，就以在重载的时候对后置运算符的参数列表里面加上一个int标记，后置++不能连续两次在同一个语句中。

迭代器示例

对于GCC4.9与2.9的节点设计来说，2.9采用的是void，这种方式需要对指针类型进行转换操作，而到了4.9有一个良好的改善，将指针类型转变为*__list_node_base****；并且在创建迭代器的时候4.9也只需要一个模板参数。</big>

迭代器设计原则和iterator traits的作用与设计

<big>iterator是算法和容器之间的桥梁，算法需要知道迭代器的五个associated types（category; difference_type; value_type; reference_type; pointer_type）中的一个或几个，才能进行运算。所以算法通过提问的方式，得到迭代器的associated types，即iterator必须提供这五种设计。

五种**associated types**

对于iterator不是一个class，而是一种单纯的指针，就不能采用上面这种问答方式。这种情况下就需要单独设计一种traits，traits必须能够分别单纯的指针迭代器和class迭代器。</big>

萃取机

区分过程

Vector

<big>vector可以认为是一种可以自动扩充的数组，每次扩充都是重新分配一块原来大小双倍空间，然后把数据拷贝过去，再删除原有的内存空间，实现容量增大。vector的迭代器为普通的元素指针外覆一个iterator adapter，而不是设计好的智能指针。

vector iterator

到了后期，每一次空间成长和插入都会造成大量调用元素的拷贝构造和析构，所以在经常性在中间插入的情况下尽量不用vector容器。</big>

array

<big>将单纯的数组通过容器来实现，可以是数组能够与算法进行联系，使所有数据结构都有一个统一的运行方式。array实例化的时候最少都要有一个元素空间并且之后空间大小不可改变。array类没有构造与析构函数且其迭代器也是一个普通的指针。</big>

array实现

deque&queue和stack

<big>deque在内存空间并不是一整块连续的空间，是多块连续内存的集合。所以需要对迭代器的操作符进行重载，当迭代器指向当前缓冲区的边界的时候，会自动移动到下一缓冲区的开始位置，其迭代器不是单纯的指针而是一个带有四个指针和操作符重载的class。</big>

deque的内存分布

queue一种先进后出的容器（适配器），默认通过deque来实现，封锁deque的某些功能就能实现一个queue，所有对于queue的操作都是通过底层的deque的相关操作实现的。stack的实现也是这样的，通过deque实现。

queue内存模型

queue的实现

stack和queue都不提供遍历过程，也不提供迭代器，其内部实现不一定要使用deque，也都可以采用list作为类模板的第二模板参数。对于stack可以用vector作为底层结构，但是queue不可以。</big>

红黑树（RB-tree）

<big>红黑树是一种平衡式二分查找树，其排列规则对查找和插入有很大优势，并且保持平衡，即最大深度与最小深度只差最多为1。对红黑树通过迭代器进行遍历之后，一定是排序后的状态。对于红黑树的迭代器，不应用于修改红黑树的节点数值，更改之后会破坏搜索结构。

红黑树的结构

红黑树具有五个模板参数，key作为查找和排序；value用于key所对应的节点的值的结合；keyofvalue为key所对应的打他值；compare为比较运算规则，为仿函数对象；如果key和value的类型设置为相同，则节点没有data部分，key就是data。</big>

image.png

set/multiset

<big>set/multiset都是以红黑树为底层结构的容器，因此具有自动排序的特性，依据key排序，且set的value就是key，key也是value。不能使用迭代器来改变元素的值，其迭代器也是const iterator，禁止用户对元素赋值。set需要三个模板参数：</big>

set实现

map/multimap

<big>map/multimap与set的差别不大，不过是map的value是由key和data通过pair组合而成，pair.first 为key， pair.second 为data，其中key不能改变，通过pair的first的类型前加const实现，而data可以改变，通过key进行排序和查找，对于map来说，key可以作为下标。map需要默认四个模板参数，后两个有默认值。

**map**实现

map有重载操作符[]进行下标运算，[]接受的下标为KEY值，如果** key** 不存在就会创建一个，以下标为** key 的pair节点。但是multi map不支持[]运算符，因为multi map是可以有重复key**值的。</big>

hash table

**hash table**

<big>给定每一个对象设置一个号码，那么至少需要sizeof（T）2^32大的空间才能完全容纳下所有对象。但是并不是每一个号码都有相应的对象，那么我么可以给定一个小于刚刚所需的最大空间，但是要大于对象个数的空间来存放所有对象。而之后的对象在内存空间所在的位置通过号码对空间大小取余之后的位置上。比如说有两个int型整数11和12如果按照编号放的话就需要12个int型对象的空间，但是由于只有两个数值，却占用了更大的空间，所以我们可以只分配两个空间（buckets），让他们对2取余的到两个编号1和2，那么11放在buckets1的位置，12放在buckets2的位置，这样不仅方便查找还省内存空间。这就是hash table的基础。但是如果两个数字是11和13那么对2取余就会造成，两个数值都放在了编号为1的buckets*，但是一个空间不能放两个数据，所以用一个链表把他们串联起来，如下图：

**buckets**比较小时内存分配

在这种情况下，如果链表太长又会影响到查找的速度，那么就可以扩大buckets的范围，使整个空间变大，那么元素取余之后便会变得更分散，链表就会变短，链表越短查找越快。如下图：

**buckets**比较大时内存分配

buckets的大小一般都采用大的素数来实现一个hash table。hash table容器一般都是作为其它容器的底层，不会单独拿出来使用。hash table的实现中hashfcn又称作散列函数，用于算出元素所处bukets位置即hash code，Extractkey 去除对象的编号函数，Equalkey用于对象比较的函数。** hash table**的源代码如下图：</big>

**hash table**

对本周内容的理解

<big>在STL中常用容器有: vector、list、deque、set、map等。根据他们的特性不同有不同的适用范围，比如：
　　set 和map都是无序的保存元素,只能通过它提供的接口对里面的元素进行访问。set:集合, 用来判断某一个元素是不是在一个组里面时比较好用，占用空间少，查找快；map:映射,相当于字典,把一个值映射成另一个值,如果想创建字典的话使用它好了。set和map底层多采用的是树型结构,多数使用平衡二叉树实现,查找某一值是常数时间,遍历起来效果也不错, 只是每次插入值的时候,会重新构成底层的平衡二叉树,效率有一定影响，也有的是通过hash_table来实现，占用空间比通过树来实现要多，但是访问速度更快，特别是空间很大时访问速度最快。
　　vector、list、deque、set、array 是有序容器。
　　vector就是动态数组.它也是在堆中分配内存,元素连续存放,有保留内存,如果减少大小后内存也不会释放.如果添加新值后占用空间大于当前大小时才会再分配内存。它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。对最后元素操作最快(在后面添加删除最快 ), 此时一般不需要移动内存,只有保留内存不够时才需要对中间和开始处进行添加删除元素操作需要移动内存,如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作，所以性能不高 （最好将结构或类的指针放入vector中，而不是结构或类本身，这样可以避免移动时的构造与析构)。 访问方面,对任何元素的访问都是O(1),也就是是常数的,所以vector常用来保存需要经常进行随机访问的内容,并且不需要经常对中间元素进行添加删除操作。
　　list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存。list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构造与析构了,所以常用来做随机操作容器.。但是访问list里面的元素时就开始和最后访问最快，访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好。如果你喜欢经常添加删除大对象的话,那么请使用list。要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替。list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存 。
　　deque是一个双端队列(double-ended queue)，也是在堆中保存内容的。每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.它支持[]操作符，也就是支持随即存取，可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度,和vector的效率相差无几，它支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多。在标准库中vector和deque提供几乎相同的接口,在结构上它们的区别主要在于这两种容器在组织内存上不一样,deque是按页或块来分配存储器的,每页包含固定数目的元素.相反vector分配一段连续的存,vector只是在序列的尾段插入元素时才有效率,而deque的分页组织方式即使在容器的前端也可以提供常数时间的insert和erase操作,而且在体积增长方面也比vector更具有效率。

不同容器的比较