侯捷c++STL体系结构与内核分析

About

videos;

课件，密码kr24;

认识headers、版本、重要资源

以STL为目标探讨泛型编程。

使用一个东西，却不明白它的道理，不高明！

• level 0: 使用C++标准库；

• level 1: 认识C++标准库（胸中自有丘壑，体系结构应当建立起来）；

• level 2: 良好使用C++标准库；

• level 3: 扩充C++标准库；

Standard Template Library (6大部件：Container(容器) 各种基本数据结构；Adapter(适配器) 可改变containers、Iterators或Function object接口的一种组件；Algorithm(算法) 各种基本算法如sort、search…等；Iterator(迭代器) 连接containers和algorithms；Function object(函数对象)；Allocator(分配器)) 加上其他一些零碎的东西构成了C++ Standard Library.

STL体系结构基础介绍

STL六大部件（component）：

数据在容器（内存的事情我们不必管，由分配器支持），处理数据在算法，连接之间的桥梁是迭代器（泛化的指针）。仿函数可以处理类之间的一些操作，适配器转换。

int stl_component()
{
  int ia[6] = {27, 210, 12, 47, 109, 83};
  //用到了容器和分配器定义一个vector
  vector <int, allocator<int> > vi(ia, ia+6);
  //用到了算法，迭代器，函数适配器，函数对象
  // vi.begin()和vi.end()迭代指向vi中的元素
  // not1是negator，否定less的作用，变成了大于等于40的数
  // bind2nd绑定了less比较的第二个对象，固定在40
  cout << count_if(vi.begin(), vi.end(),
         not1(bind2nd(less<int>(), 40))) << endl;
 
  return 0;  

}

简单提及时间复杂度。

“前闭后开”曲间，标准库规定容器迭代器的最后一个元素取不到，即[iter.begin(), iter.end() )，此外容器也不一定是连续空间，比如链表。

Container<T> c;
...
Container<T>::iterator ite = c.begin();
// for语句的语法规定，括号里面一定要有两个分号，分开三个句子。
//第一个句子是初始化用的，如果没有初始化的必要，就视为空语句，加上分号；
//第二个句子作为判断条件，如果没有判断条件，也视为空语句，后加一个分号。这种情况，会无限循环，相当于while(1)。如果for的执行部分，就是{}之间有break语句，可以退出；
//第三个句子是执行部分执行完毕再执行的语句；无则视为属空语句；此时不用再加分号
for (; ite != ite.end(); ++ite)
   ...

建议使用range-based for statement (since c++11):

for (decl:coll){
statement
}

for (int i : {2,3,5,7,9,13}) {
  std::cout<<i<<std::endl;
}

容器与分类之各种测试（1）

容器-结构与分类

1.sequence containers 序列式：

array（不可扩充）, vector（分配器动态扩容）, deque（前后快速插入）, list（双向循环链表）, forward-list（单向链表）；

2.associative containers 关联式，便于查找：

set/multiset, map/multimap, 两者编译器所带标准库都用红黑树实现。set只带key，map带有key和value，两者意思与python的set和dict类似。multiset/multimap代表key是可以重复的。

3.unordered containers (since c++11)：

不定序，hash table，其实也可以属于一种associative containers.内部采用链表法解决哈希冲突。

---

使用容器array示例：

array必须指定固定大小，不能是变量大小；

array.data()首地址；

clock()得到的是ms；

snprintf()是c标准库函数，在这里是将数字转成字符串，具体可参考此；

容器与分类之各种测试（2）

侯捷老师给的一些建议：

1.通过给每个测试定义不同的namespace，使得每一部分都是独立的，方便测试。

2.用到变量的时候去定义，然后缩排方便寻找。

---

使用容器vector：

vector.push_back()把元素放到尾巴；

vector 2倍扩容增长空间；

vecotr.size()元素个数；

vector.capacity()容器容量，一般比size的结果大；

try, catch目的是了解当前是否可以抓取到指定的内存大小；

::find中双冒号代表全局的，find()是模板函数（循序查找），返回的是iterator;

容器与分类之各种测试（3）

1.使用容器list:

容器的第二个参数是分配器，一般我们不写，使用默认的分配器分配内容；

list.max_size()

list.size()

list.front()

list.back()

list.sort()对其进行排序

2.使用容器forward_list:

forward_list.push_front只提供单向的放数据

forward_list.max_size()

forward_list.front()

没有forward_list.back()和forward_list.size()

3.使用容器slist:

非C++11标准库；

#include<ext\list>头文件包含。

4.使用容器deque:

双向开口，可进可出。

分段连续的buffer构成的，但是给使用者感觉是连续的，内部其实不是，分段连续，buffer内部连续。每次扩充一个buffer.

vector扩充方便，但是容易浪费，list每次扩充一个节点，但是查找麻烦，deque每次一个buffer,相对折衷。

deque.size()

deque.front()

deque.back()

deque.max_size()

没有自己的sort()函数

5.使用容器stack:

stack.pop()

stack.push()

stack.size()

stack.top()

6.使用容器queue:

queue.push()

queue.pop()

queue.front()

queue.back()

queue.size()

stack和queue用的deque，因此在技术上称容器的adapter, 不提供iterator

容器之分类与各种测试（4）

关联式容器

1.使用容器multiset:

key就是value, 可插入相同元素，内部红黑树组织数据

multiset.insert()

multiset.size()

multiset.max_size()

multiset.find()容器自带find()函数

2.使用容器multimap:

，内部使用红黑树，key可以重复，指定key和value的数据类型，multimap<long, string> c;

multimap.insert(), c.insert(pair<long,string>(i,buff))，利用pair插入和取出

multimap.find()

3.使用容器unordered_multiset:

内部使用hash_table, 链表法解决哈希冲突，一个篮子bucket后续可以挂链表

load_facotr载重因子

4.使用容器unordered_multimap:

5.使用容器set:

内部用红黑树实现，元素不允许相同

6.使用容器map:

内部用红黑树实现，key不允许相同

c[i] = string(buf)，与之前的multimap插入元素不同，可以用这种特殊写法，在内部会合成pair

7.使用容器unordered_set:

内部用hash_table

8.使用容器unordered_map:

内部用hash_table

分配器测试

使用分配器：

不使用标准库自带的std::allocator, 调用GNU c++编译器的allocator

OOP vs. GP

object-oriented programming and generic programming, 面对对象编程与泛型编程

OOP企图将data和methods放在一起，GP却将data和methods分开来

算法通过迭代器操作容器数据

操作符重载和模板（泛化，全特化，偏特化）

再次强调和复习operator overloading，templates（类模板，成员模板，函数模板；模板的泛化，全特化和偏特化）。

1.操作符重载的情况主要是为了满足用户自己定义类的一些操作，可以在相关网站查询，并不是每个操作符都可以重载。

2.模板

Allocator

不建议你单独使用分配器。

operator new()和底层的内存分配函数malloc()

malloc()分配给申请内存大小的空间时会额外给一些空间放必要的东西，有一些额外的开销cookie，free释放内存。但是一般使用时，由于申请的size不大，所以这些额外的空间占所有的比例比较大，所以是个缺陷。

P11总结一下，allocator就是用来分配内存的，最重要的两个函数是allocate和deallocate，就是用来申请内存和回收内存的，外部（一般指容器）调用的时候只需要知道这些就够了。内部实现，目前的所有编译器都是直接调用的::operator new()和::operator delete()，说白了就是和直接使用new运算符的效果是一样的，所以老师说它们都没做任何特殊处理。G2.9里的那个更好的allocator，在老师的另一门课《C++内存管理》里讲得特别细，大概从P23开始讲细节，更早的几P也有使用用例。

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

深度探索list（上）

最具代表性的容器，双向循环列表，优先介绍。

定义自己的迭代器iterator， 其中要有typedef和operator reloading（操作符重载）

深度探索list（下）

迭代器的设计原则和Iterator Traits的作用与设计

容器用域存储数据，算法用以处理数据，而迭代器iterator就是沟通容器和算法的桥梁。上一讲提到，容器需要自己定义iterator，并且写出五个规定的typedef，这个就是为了算法询问iterator，得出这样的特性然后进行定制的数据操作。但是如果iterator不是类，无法写出typedef的时候，就需要traits这样的中间变量来让算法得出迭代器的特性。

除了iterator traits之外，还有各式的traits, 包括type traits, char traits, pointer traits等等。

Vector深度探索

array, forward_list深度探索

把array包装成容器，然后利用指针当iterator进行操作。

deque, queue和stack深度探索（上）

双向队列deque在上层调用时表现是连续的，但是底层实现是用分段连续的buffer来实现的，通过迭代器和操作符重载来营造连续插入或弹出的假象。

deque, queue和stack深度探索（下）

deque内部通过iterator操作符重载并做一些处理来进行表面上连续空间的模拟。

RB-Tree深度探索

关联式查找容器的底层支撑结构。

Set, Multiset深度探索

set和multiset底层利用Rb_tree实现，所以基本上它们的事内部都是交给红黑树去完成，所以又被叫成container adapter. 其中需要注意的是它们中的key和value是一样的，所以不能被改变，否则key就会变化。

Map, Multimap深度探索

related blog

Hash Table深度探索

另一个关联式容器哈希表，或散列表，是一种常用的存储较多数据的数据结构（减少查找时间），其中难点在于hasd function的选择和对对哈希碰撞的处理（一般是开放式寻址法或者链表法）。

Unordered容器概念

利用hash table实现unordered_set, unordered_multiset, unordered_map, unordered_multimap容器。

算法的形式

算法通过迭代器联通容器，进行数据处理和函数运行。从语言层面上讲，容器是class template, 而算法是function template, 其中有些算法还可传入你定制的准则criterion, 比如sort函数的比较函数。

迭代器的分类

STL容器中总共会用到三种种类，分别是random_access_iterator_tag (array, vector, deque), bidirectional_iterator_tag(list, rb_tree), forward_iterator_tag(forward_list, hashtable可能是) 这三种。多出来的两种input_iterator_tag和output_iterator_tag属于istream和ostream. 五种之间是继承关系，同时用这种tag的方式，非简单的12345.

迭代器类别对算法的影响

STL算法内部会利用迭代器的类别开辟出不同的处理分支，想尽方法达到最快的处理速度。

算法源码剖析（几个例子）

举了几个C++标准库中的例子。表明与迭代器结合很紧密。

仿函数和函数对象

在前面一些的算法的使用中，已经见识到了函数对象/仿函数传入其中进行特殊的操作。在C++的STL中有三大类functors，分别是算术类，逻辑运算类和相对关系类。他们都继承了某个适当者，这样是为了后续利用适配器进行改造，而前提就是像algorithm对iterator一样利用traits询问问题，继承的作用就是为了融入STL，利用被继承者的typedef来回答问题。此外，GNU中也会有一些仿函数供用户使用，比如前面提到的Identity和Select1st

存在多种适配器

适配器可以认为具有一个桥梁作用：把某个底层B包装下做成A交给用户使用，但是内部仍然是调用B来运作。在C++中，适配器采用复合的方式获得某种功能，非继承。

容器适配器方面，典型的是stack和queue，它们内部都是内含了deque作为其底层容器，然后改造成具有自己特性和接口的容器。

Binder2nd/not1/bind

介绍了前面使用过的一个计数语句cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>, 40)))，其中用到了算法，函数适配器和函数对象。

bind2nd和not1都是函数适配器，用以修饰后面的函数并将其包装。bind2nd绑定第二实参，限制less函数调用时保持第二参数为40不变。修饰后的函数继续被not1修饰，将结果取反，也就是不小于40的数计数。

bind2nd内部使用binder2nd函数，目的是为了简化用户使用难度，自动帮你推导operation模板参数。侯老师提到binder1st, binder2nd这些函数后来都被bind函数取代，但是旧的函数依旧可以使用。

在C++2.0版本中，bind函数取代了bind2nd，可以用来绑定函数/函数对象/成员函数和数据成员，同时可以指定绑定哪个参数，哪个参数不用绑定，利用诸如_1这样下划线加数字的形式（palceholder，占位符）代表第几个参数可以被后续调用再指明。bind可以指定一个模板参数，代表返回类型。更多的例子和示意见下面的图片。

迭代器适配器reverse_iterator/inserter

Adapter在容器，仿函数和迭代器上都有使用。侯老师在这里举了两个例子，一个是前面用到过的reverse_iterator，逆序迭代器遍历方向，另一个是inserter，用来插入数据。在这里侯老师再次强调，adapter是把所有需要的东西系起来，打包好，然后供日后再用，起到一种修饰改造作用。

copy函数内部已经把流程写死了，就是按照指定的result迭代器，一步步搬移前面两个迭代器指定范围内的数据，后续的一些adapter改造操作，通过利用操作符重载各自解读，来实现自己定制的特性。

X适配器ostream_iterator/istream_iterator

ostream和istream是两个特殊的迭代器，他们不属于一般的迭代器适配器，容器适配器和仿函数适配器中的任何一个，因此侯老师称之为X适配器，X代表一种未知。

一个万用的Hash Function

hash function的制定可以没有任何规律，但是效果是一定要够乱，尽量减少碰撞。这里侯老师先以一个比较简单的customerhash函数开场，说明这样虽然简单，但是hash code比较容易重复。之后引出了C++标准库中的一个“万用的hash function”, 其中的重点是variadic templates, 这个是C++ 2.0中比较重要的新特性，大意就是可变的模板参数，常用…表示，比如下图中的序号1表示的函数，其中的template<typename...Types>就表示可以接受任意数量的模板参数。

Tuple用例

Tuple是可以将几个不同的数据结构的变量绑在一起的类型，使用上利用直接声明tuple<>创建，也可以利用make_tuple()实现，或者tie函数快速对变量进行赋值，如下图所示。其中可以对<和=这样的操作符进行重载实现特性上的适配。

type traits

type traits主要是为了给用户自己写的类提供一些特征信息，用户自己不需要对其进行偏特化处理就可以自动获取，节省代码工作量，广泛用于C++泛型编程。这些特征信息通过询问的方式进行获取，指导该类后续的相应操作。

上图出现的Plain Old Data (POD)是一个类型（比如class或者struct），但是没有构造函数，析构函数，虚函数等成分。维基百科的解释是：

POD类类型就是指class、struct、union，且不具有用户定义的构造函数、析构函数、拷贝算子、赋值算子；不具有继承关系，因此没有基类；不具有虚函数，所以就没有虚表；非静态数据成员没有私有或保护属性的、没有引用类型的、没有非POD类类型的（即嵌套类都必须是POD）、没有指针到成员类型的（因为这个类型内含了this指针）。

stackoverflow有也相关问题：

In short, it is all built-in data types (e.g. int, char, float, long, unsigned char, double, etc.) and all aggregation of POD data. Yes, it’s a recursive definition. ;)

To be more clear, a POD is what we call “a struct”: a unit or a group of units that just store data.

一个类如果没有没有涉及到指针，就可以不必写析构函数，使用编译器分配的默认的即可。像string内部带了指针，就必须写析构函数。此外，如果不是父类base，没有覆写的虚函数，也不必写virtual destructor.

type traits通过模板实现，对类型进行操作，比如下面的例子，利用泛化，偏特化，传回真假值。

此外有些type traits实现的特性未曾出现于C++源码标准库。侯老师说这种情况可能就是编译器编译的时候来回答支持，不以源代码的方式呈现。

traits的理解

type traits 理解

cout的操作符重载

cout为何可以接收各式各样的object？因为其内部对各类型都做了操作符重载。注意其返回类型为ostream&，为了可以继续接收，非void返回类型。

movable的使用

move是C++2.0一个比较重要的特性，其内部就是拷贝指针，属于浅拷贝，在type traits中见到的&&符号就代表move功能，而拷贝构造则是深拷贝。move的速度很快，侯捷老师也在课程中比较了加不加move功能对容器元素拷贝速度的影响，同时也给出了一些测试例子，但是在使用move时需要自己对元素的使用有清晰的认识，因为move是拷贝指针，等于是两个指针指向同一个位置，这个是危险的，C++内部会在move时做一些处理去规避这个行为带来的危险情况，所以move完之后的原始对象就最好不要再用了。

C++的左值和右值