======STL与泛型编程 第一周======
本页内容是作为 //Boolan// C++ 开发工程师培训系列的笔记。\\
因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！
----
====标准模板库STL====
C++ 标准库提供了强大的类库和相关的函数。在标准库中，C++ 标准模板库STL（//Standard Template Library//）作为标准库的子集，占据了标准库 85% 以上的内容。STL 是一个使用模板建立的类库，其核心思想是**泛型编程**（//Generic Programming//）。
===STL的提供方式===
STL通过 ''header'' 提供给用户使用。''header'' 分为新版本和旧版本。有两点需要注意的是：
* 新版本的 ''header'' 均不带 ''.h'' 扩展名，且都存储在命名空间 ''std'' 中。
* 旧版本的 ''header'' 均带 ''.h'' 扩展名，且都不在命名空间 ''std'' 中。旧版的 ''header'' 可以被新版本的编译器沿用。
===STL相关资源===
相关网站：
* [[http://Cplusplus.com|Cplusplus.com]]
* [[http://cppreference.com|Cppreference.com]]
* [[http://gcc.gnu.org|Gcc.gnu.org]]
相关书籍：
* The C++ standard Library 2nd
* STL 源码剖析
====STL体系简介====
STL 主要分为六的大部分：
* 容器（//Containers//）：扮演了数据结构的角色，解决在STL中的数据存储问题。
* 分配器（//Allocators//）：用于帮助容器将内存分配和对象的构造进行分离。
* 算法（//Algorithms//）：一系列对容器操作的模板函数。
* 迭代器（//Iterators//）：泛化的指针，作为算法和容器沟通的渠道。
* 适配器（//Adapters//）：适配器分为容器 / 迭代器 / 仿函数 适配器，对指定的部分进行转换。
* 仿函数（//Functors//）：一些功能类似于函数的类。
\\
具体的关系图如下图：
\\
\\
\\
\\
===相关代码示例===
侯老师在课程中给出了一个典型的例子：
int ia[6] = { 27, 210, 12,47, 109, 83 }；
vector> vi(ia, ia + 6);
cout << count_if(vi.begin(), vi.end(), not1(bind2nd（less(), 40)));
return 0;
* ''vector'' 代表了容器的一种应用
* ''vector'' 中的 ''allocator'' 是作为容器的参数出现的，作用是手动申请内存。该分配器需要类型与 ''vector'' 一致，否则会导致 //undefined//。
* ''count_if'' 作为算法的一员，接收两个迭代器和一个作为条件的**谓词**（//Predicate//）。''vi.begin(), vi.end()'' 分别表示了指向 ''vector'' 开始和结束的迭代器。
* ''less'' 是模板类，接收两个输入，通过对括号的重载，返回一个 ''Bool'' 类型：''return x < y''。
* ''bind2nd'' 是 ''adapter'' 的一种，接收的参数是一个操作和一个值，绑定第二个参数作为值，返回的值根据操作决定；但操作涉及的其他参数永远是第二个值。
* ''not1'' 也是 ''adapter'' 的一种，返回当前谓词取反结果。
===容器的范围与遍历===
绝大多数情况下，容器的范围都可以通过两个迭代器来决定：''begin()'' 和 ''end()''。''begin()'' 指向的是容器第一个元素的地址； ''end()'' 指向的是容器最后一个元素的下一个位置。容器的范围用区间来表达可以写成：
$$[Begin, end)$$
\\
通过上述的特点，我们可以使用迭代器对容器进行遍历：
Container::iterator iter = c.begin();
for (; iter != c.end(); ++iter)
....
而在 C++11 中，我们可以通过 ''auto'' 和 ''for range'' 来简化操作：
for (auto iter = c.begin(); iter != c.end(); ++iter)
....
====容器相关简介====
STL 提供了一系列的容器来作为内存使用的方案。容器按在内存中的存储结构分为三种：**顺序容器**（//Sequence Container//）、**关联容器**（//Associative Container//）、和**无序容器**（//Unordered Container, C++ 11//）。严格意义上来说，无序容器也算是关联容器的一种。
\\
\\
常见的顺序容器如下：
* STL //Array//, 特点是定长
* //Vector//，起点确定，元素从尾部增长
* //Deque//，双向队列
* //List//，双向链表
* //Forward_list//，单向链表
\\
关联容器的一个特点就是查找特别快，因为其通过关键字查找。常见的关联容器如下：
* //Set// / //Multiset//，关键字就是值，用红黑树实现。Set 中不允许出现重复的元素
* //Map// / //Multimap//，关键字和值成对出现，用红黑树实现。 Map 中不允许出现重复的元素
\\
无序容器和关联容器的一个不同在于无需容器使用哈希表实现。
\\
\\
以上内容均会在稍后详细讨论。
===容器的性能===
STL 中的各种容器是基于各种不同的基础数据结构来实现的；因此对于特定的需求选择合适的容器会有效的提高程序运行的效率。容器的运行效率并不是独立存在的，有时候必须要搭配恰当的算法才能达到更高效的水准。因此，我们有必要做一个粗略的效率测试来评估容器的性能。而对于这些数据结构的测试，我们一般考虑其读写效率：也就是**存储**和**查找**。
\\
\\
我们首先来看看容器的读写性能总览：
\\
\\
\\
\\
\\
值得说明的是，对于大部分容器，STL 都提供了泛型算法；但与此同时，该容器类很可能定义了自己的、用于实现与泛型算法相同功能的成员函数。**在两者都有的情况下，优先使用容器的成员函数**。
====顺序容器====
接下来我们对每个容器简单介绍一下其原理，以及测试的小细节。//由于本章老师并没有进行讨论算法，因此讨论范围仅限于老师例程中出现的算法。//
===Array===
标准 //Array// 是 C++11 的新内容。相比起内置的数组来说，标准库 //Array// 功能更强大，可以以对象为单位存储数据。标准库 //Array// 和传统数组的特性完全相同：**定长**，长度一旦确定后就不可更改。因此在内存里可以表现为如下结构：
\\
\\
\\
标准库 //Array// 的定义，及相关的算法使用如下：
array a; // array that holds 10 ints
a.size(); // return the number of element that hold by container
a.front(); // return the first element in container
a.back(); // return the last element in container
a.data(); // return the starting address of the container
===Vector===
相比 //Array//, //Vector// 是一种可变长的容器。//Vector// 在内存中的表现如下：
\\
\\
\\
\\
标准库 //Vector// 的定义，及相关的算法使用如下：
vector vi; // vector that holds 10 ints
/* Accessors */
vi.size(); // return the number of element that hold by container
vi.capacity(); // return the capacity of the container
vi.front(); // return the first element in container
vi.back(); // return the last element in container
vi.data(); // return the starting address of the container
/* Modifiers */
v.push_back(value); // Add value to end
\\
值得注意的是，//Vector// 的 ''size'' 和 ''capacity'' 并不相等。//Vector// 在内存中是变长的，其增长策略是**翻倍增长**。具体过程是当 ''size'' 达到或者超过 ''capacity'' 时，系统会直接申请一块两倍于当前 //Vector// 所占的空间，然后把当下的内容全复制过去。同时，因为//Vector// 从尾部操作的效率非常高，所以我们一般用 ''push_back()'' 对其添加元素。
===List===
//List// 的是通过双向链表数据结构来实现的容器，在内存中的结构可以表现为：
\\
\\
\\
\\
标准库 //List// 的定义，及相关的算法使用如下：
list li; // list that holds 10 ints
/* Accessors */
li.size(); // return the number of element that hold by container
li.max_size(); //return the maximum number of elements
li.front(); // return the first element in container
li.back(); // return the last element in container
/* Modifiers */
li.push_front(value);
l.push_back(value);
li.sort(); //List has its own sort function with O(n log n) complexity
\\
因为是链表，所以对 //List// 的删除添加操作的速度是非常快的；而因为是双向链表，所以我们可以在头部和尾部添加元素。同是我们也知道，链表是变长的，其内存增长的策略是按元素单位增长。相比起 //Vector// 来说，//List// 的空间利用率更高。
===Forward_list===
//Forward_list// 是通过单向链表数据结构来实现的容器；相对于 //List//, //Forward_list// 只能通过顺序访问查找元素。//Forward_list// 在内存中的结构示例如下：
\\
\\
\\
\\
标准库 //Forward_List// 的定义，及相关的算法使用如下：
forward_list fls; //forward list that holds 10 strings
/* Accessors */
fls.max_size(); // return the maximum number of elements
fls.front(); // return the first element in container
/* Modifiers */
fls.push_front(value);
因为 //Forward_list// 其本身数据结构的特性，决定了：
* 没有 ''size()'' / ''back()'' 访问函数
* 不能从尾部添加元素（即使用 ''push_back()''）
//Forward_List// 属于C++11 的新内容。在老版本的 GNU 中有一个 //Slist//，定义在 '''' 中，功能与其完全相同。
===Deque===
//Deque//是 双向开口的连续性存储容器。不过这种连续性只是**逻辑**上的。它在堆上分配了单位的 //Buffer//，//Buffer// 本身是连续的，而 //Deque// 通过 //Map// 将这些 //Buffer// 都组织起来，形成逻辑上的连续；我们称这样的连续为**分段连续**。只要通过 //Map// 对迭代器操作 ''++'' 的重载，我们就可以实现 //Deque// 逻辑上的连续。//Deque// 在内存中的表现形式如下：
\\
\\
\\
\\
标准库 //Deque// 的定义，及相关的算法使用如下：
Deque ds; // deque that holds 10 strings
/* Accessors */
ds.size();
ds.max_size();
ds.front();
ds.back();
/* Modifiers */
ds.push_front(value);
ds.push_back(value);
\\
从前面的图我们能发现，//Deque// 的内存增长策略其实是以 //Buffer// 为单位的。//Deque// 每次添加元素，都会申请一个 //Buffer// (512 Bytes) 的空间；从空间利用率上来说，//Deque// 介于 //List// 和 //Vector// 之间。但因为 //Deque// 在内存里的组织方式实际上比 //Vector// 复杂，它的性能损失比之 //Vector//，是几个数量级的差别。因此，//Deque// 要慎用。
==Queue 和 Stack==
//Queue// 和 //Stack// 作为两种独特的数据结构，在 STL 中都是基于 //Deque// 来实现的。由于这两种容器都没有单独定义自身的实现，因此我们又把这两种容器称为**容器适配器**（//Container// //Adaptor//）。//Stack// 是一种**先进后出**的数据结构，而 //Queue// 是一种**先进先出**的数据结构。
\\
\\
标准库 //Stack// 的定义，及相关的算法使用如下：
stack ss; // Make an empty stack
/* Accessors */
ss.top(); // Return the top element.
ss.size(); // Return current number of elements.
/* Modifiers */
ss.push(value); // Push value on top.
ss.pop(); // Pop value from top.
\\
标准库 //Queue// 的定义，及相关的算法使用如下：
queue qs; // Make an empty queue
/* Accessors */
qs.size();
qs.front();
qs.back();
/* Modifiers */
qs.push(value); // Add value to end of queue
qs.pop(); // Remove value from front
\\
需要注意的是：**我们不能使用迭代器对这两种容器进行操作**。如果提供了迭代器，那么就意味着我们可以使用迭代器对上述容器适配器任意位置的元素进行添加和删除；这样一来就破坏了这两种数据结构独有的特性（想想一下釜底抽薪和强行加塞）。
====关联容器====
STL 中关联容器是使用红黑树实现的。因为其并不是顺序结构，因此我们不能用 ''push_back()'' / ''push_front()'' 来对其进行操作。关联容器分为一般版本和 Mult 版本。不带 Mult 的代表该容器中**不允许元素的重复**，如果有重复则按一个元素计算。
\\
\\
关联容器主要分为两个版本：//Set// 和 //Map//。//Map// 的元素以键-值（key-value）对的形式组织：键用于元素在 //Map// 中的索引，而值则表示所存储和读取的数据。//Set// 仅包含一个键，该键计时器本身。
\\
\\
关联容器和顺序容器的本质差别在于：关联容器通过键（//key//）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。这也导致了关联容器查找速度非常的快。
===Set / Multiset===
在 //Set//中，关键字就是其本身的值。//Set// 和 //Multiset// 会将元素自动的排序，使之可以快速的进行查找。 //Set// 要求元素的唯一性，而 //Multiset// 允许元素重复。//Set// 在内存中的结构表示如下：
\\
\\
\\
\\
标准库 //Set// / //MultiSet// 的定义，及相关的算法使用如下：
set si; //empty set that can store int element
/* Accessors */
si.find(key); // set has its own find
si.lower_bound(key); // Return an iterator pointing to the first occurrence of an item in s not less than key, or s.end() if no such item is found
si.upper_bound(key); // Return an iterator pointing to the first occurrence of an item greater than key in s, or s.end() if no such item is found
si.count(key); // Returns the number of items equal to key in si
s.size(); // Return current number of elements
/* Modifiers */
s.insert(key);
//Set// 的删除操作主要依赖于泛型算法中的 ''erase()''。
===Map / Multimap===
//Map// 可以想象成是广义的 //Vector//：//Map// 可以通过下标去访问和赋值，而下标可以是任意的 Key（不限制于整型）。//Map// 也是由红黑树实现的；但与 //Set// 不同的是，//Map// 以 ''pair'' 为单位存储。因此，如果使用迭代器访问 //Map// 的指定元素，我们需要使用 ''pair'' 类的两个函数： ''first'' 和 ''second''。 //Map// 的结构在内存中表示如下：
\\
\\
\\
\\
标准库 Map/ Multimap 的定义，及相关的算法使用如下：
map mis; // a map with integer key and string value element
/* Accessors */
mis.find(key);
mis.lower_bound(key);
mis.upper_bound(key);
mis.size();
/* Modifiers */
mis[key] = value; // Store value under key in map
mis.insert(pair); // Inserts the pair into the map
===无序容器与哈希表===
**无序容器**（//Unordered Containers//）实现了与上述关联容器类似的功能，但实现的底层数据结构有异：无序容器是通过哈希表（//Hash Table//）来实现的；实际上，这些容器也可以被称为// Hash Map//。无序容器可以算是关联容器的一种；但其和关联容器本质上的区别，就是**无序**。当我们使用关联容器的时候，关联容器会自动将里面的元素排好序（默认使用 ''<'' 操作符）；但**无序容器并不要求对元素进行排序**；所以无序容器的元素并不带有小于操作符。这也导致了两者查找机制上的不同。在关键字类型的元素没有明显有序关系的情况下，无序容器是非常有用的。
==哈希表的应用==
要理解无序容器的一些特性，我们需要了解一下哈希表的结构。
\\
\\
哈希表在内存中的结构大致如下图：
\\
\\
\\
\\
按照上图，具体的来说，无序容器在存储上组织为一组**桶**（//Bucket//，侯老师称为篮子 LOL），每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。如果容器允许重复关键字，所有具有相同的关键字的元素也都会在同一个桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。
\\
\\
值得注意的是，哈希表中，桶和元素的关系是有一定联系的。试想如果一个桶包含的元素太多，势必影响查找的效率。因此，对于桶的管理，哈希表的策略是：**如果元素的数量超过桶的数量，那么桶数量又会重新扩充到大约两倍元素的数量**。
==无序容器的应用==
无序容器提供了一组如下管理桶的函数：
/* Accessors */
c.bucket_count(); //current buckets in use
c.max_bucket_count(); //buckets capacity
c.bucket_size(n); //number of elements in specified bucket
c.bucket(key); // find bucket that has keyword "key"
/* Hash related */
c.load_factor(); // return average numbers of each bucket, float
c.max_load_factor();
c.rehash(n); // reorganize storage with rule: bucket_count>=n && bucket_count>size/max_load_factor
c.reserve(n); // reorganize storage without rehash
