STL剖析全书的总结笔记

 

1          概念理解

仿函数(functor)，就是使一个类的使用看上去象一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

ptrdiff_t是C/C++标准库中定义的一个与机器相关的。ptrdiff_t类型通常用来保存两个减法操作的结果。标准库类型(library type)ptrdiff_t 与 size_t 类型一样, 也是一种与机器相关的类型,在 cstddef 头文件中定义。size_t 是unsigned 类型,而 ptrdiff_t 则是 signed 整型^[1]。

这两种类型的差别体现了它们各自的用途： 类型用于指明数组长度,它必须是一个正数;ptrdiff_t 类型则应保证足以存放同一数组中两个指针之间的差距,它有可能是负数^[1]。

STL容器：即是将最常用被运用的一些数据结构实现出来，其涵盖种类有可能在每五年召开一次的C++标准委员会议中不断增订。

2         容器

2.1 序列式容器

List： 每一次插入或删除元素，都释放空间；而且对于任何位置的元素插入或删除，list运行时间都是常数；list不能运用std：：sort算法，只能自己写了归并排序的sort算法。

Vector：每一次释放或删除元素，不将释放空间，且其运行时间根据实际元素数量确定。

deque:是由一段一段的定量连续空间构成，可以随时增加一段新空间，换句话说并不像vector那样：因空间不足而重新配置更大空间，然后复制元素，释放旧空间 。但是这种定量连续空间换来的代价则是迭代器复杂的架构。此外对于deque的排序，为了提高效率，可将deque先复制到一个vector身上，将vector利用STL sort算法排序，再复制回deque。此外deque允许常数时间内对元素插入及删除。

Stack:是一种先进后出的数据结构，deque是双端开口的数据结构，若以deque为底部结构并封闭其开端开口，就等价于stack。具有“修改某物接口，形成另外一种风貌”称之为adapter（适配器）。因此，STL stack往往不被归类为container，而是container adapter。

注意：stack必须符合“先进后出”条件，只有顶端元素才可访问，所以不提供迭代器。

queue:是一种先进先出的数据结构，但除了最低端可以加入、最顶端可以取出外，没有任何其他方法可以存取queue的其他元素，换言之queue不允许遍历。

注意：queue必须符合“先进先出”条件，只有顶端元素才可访问，所以不提供迭代器。

不属于STL容器组件：

l  heap、priority_heap的实现引用了make_heap() push_heap()  pop_heap()泛型算法。

l  比较快排、堆排、合并排序效率

2.2 关联式容器

标准的STL关联容器分为set（集合）和map（映射）两大类。

Set:set不允许两个元素有相同的键值，也不可以通过set的迭代器改变set的元素值。它的键值就是实值，实值就是键值。

针对find算法;使用STL算法find（）搜寻元素，可以有效运作，但效率不及其本身提供的find函数。因为STL算法find只是循序搜寻。

Map:不允许键值重复；

Multiset：允许键值重复，因为插入操作时底层机制的insert_equal

Multimap:允许键值重复

红黑树和哈希表区别在于有没有自动排序

3         算法

合并排序算法：List的sort();

关于算法sort：对于关联式容器拥有自动排序功能，所以不需要用到sort算法，至于序列式容器中的stack、queue、list，前两者的迭代器属于RandomAccesslterators，适合使用sort。其中就效率来看，List利用其自身携带的sort函数较为快点。

4         比较（这些算法都是针对STL）

快排、堆排、合并排、二叉树、红黑树排序区别

STL的sort算法的优化策略：

?  Insertion sort排序复杂度为O(N²)，quick sort的平均复杂度是O(NlogN)，最坏情况下将达到O(N²)。而introsort可将最坏情况推进到O(NlogN)。

?  Introsort过程如下：

数据量大时采用QuickSort，分段递归排序。

一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来的额外负荷，就改用Insertion Sort。

如果层次过深，还会改用HeapSort

“三点中值”获取好的分割

?  Merge Sort的复杂度为O(NlogN)。虽然这和Quick Sort是一样的，但Merge Sort需要借用额外的内存，而且在内存之间移动、复制耗费不少时间，所以Merge Sort的效率比不上Quick Sort。但实现简单、概念简单，是Merge Sort的两大优点。