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相关资源

STL体系简介

STL 主要分为六的大部分：

容器（Containers）：扮演了数据结构的角色，解决在STL中的数据存储问题。
分配器（Allocators）：用于帮助容器将内存分配和对象的构造进行分离。
算法（Algorithms）：一系列对容器操作的模板函数。
迭代器（Iterators）：泛化的指针，作为算法和容器沟通的渠道。
适配器（Adapters）：适配器分为容器 / 迭代器 / 仿函数适配器，对指定的部分进行转换。
仿函数（Functors）：一些功能类似于函数的类。

具体的关系图如下图：

<html>

</html>

容器的范围与遍历

绝大多数情况下，容器的范围都可以通过两个迭代器来决定：begin() 和 end()。begin() 指向的是容器第一个元素的地址； end() 指向的是容器最后一个元素的下一个位置。容器的范围用区间来表达可以写成： $$[Begin, end)$$
通过上述的特点，我们可以使用迭代器对容器进行遍历：

Container<T>::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 中的各种容器是基于各种不同的基础数据结构来实现的；因此对于特定的需求选择合适的容器会有效的提高程序运行的效率。容器的运行效率并不是独立存在的，有时候必须要搭配恰当的算法才能达到更高效的水准。因此，我们有必要做一个粗略的效率测试来评估容器的性能。而对于这些数据结构的测试，我们一般考虑其读写效率：也就是存储和查找。

我们首先来看看容器的读写性能总览：

<html>

</html>

值得说明的是，对于大部分容器，STL 都提供了泛型算法；但与此同时，该容器类很可能定义了自己的、用于实现与泛型算法相同功能的成员函数。在两者都有的情况下，优先使用容器的成员函数。

顺序容器

接下来我们对每个容器简单介绍一下其原理，以及测试的小细节。由于本章老师并没有进行讨论算法，因此讨论范围仅限于老师例程中出现的算法。

Array

标准 Array 是 C++11 的新内容。相比起内置的数组来说，标准库 Array 功能更强大，可以以对象为单位存储数据。标准库 Array 和传统数组的特性完全相同：定长，长度一旦确定后就不可更改。因此在内存里可以表现为如下结构：

<html>

</html>
标准库 Array 的定义，及相关的算法使用如下：

array<int, 10> 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 在内存中的表现如下：

<html>

</html>

标准库 Vector 的定义，及相关的算法使用如下：

vector<int, 10> 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 的是通过双向链表数据结构来实现的容器，在内存中的结构可以表现为：

<html>

</html>

标准库 List 的定义，及相关的算法使用如下：

list<int> 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 在内存中的结构示例如下：

<html>

</html>

标准库 Forward_List 的定义，及相关的算法使用如下：

forward_list<string> 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，定义在 <ext\slist> 中，功能与其完全相同。

Deque

Deque是双向开口的连续性存储容器。不过这种连续性只是逻辑上的。它在堆上分配了单位的 Buffer，Buffer 本身是连续的，而 Deque 通过 Map 将这些 Buffer 都组织起来，形成逻辑上的连续；我们称这样的连续为分段连续。只要通过 Map 对迭代器操作 ++ 的重载，我们就可以实现 Deque 逻辑上的连续。Deque 在内存中的表现形式如下：

<html>

</html>

标准库 Deque 的定义，及相关的算法使用如下：

Deque<string> 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<string> 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<string> 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 在内存中的结构表示如下：

<html>

</html>

标准库 Set / MultiSet 的定义，及相关的算法使用如下：

set<int> 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<key, value> 为单位存储。因此，如果使用迭代器访问 Map 的指定元素，我们需要使用 pair 类的两个函数： first 和 second。 Map 的结构在内存中表示如下：

<html>

</html>

标准库 Map/ Multimap 的定义，及相关的算法使用如下：

map<int, string> 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 <key, value> pair into the map

无序容器与哈希表

无序容器（Unordered Containers）实现了与上述关联容器类似的功能，但实现的底层数据结构有异：无序容器是通过哈希表（Hash Table）来实现的；实际上，这些容器也可以被称为 Hash Map。无序容器可以算是关联容器的一种；但其和关联容器本质上的区别，就是无序。当我们使用关联容器的时候，关联容器会自动将里面的元素排好序（默认使用 < 操作符）；但无序容器并不要求对元素进行排序；所以无序容器的元素并不带有小于操作符。这也导致了两者查找机制上的不同。在关键字类型的元素没有明显有序关系的情况下，无序容器是非常有用的。

哈希表的应用

要理解无序容器的一些特性，我们需要了解一下哈希表的结构。

哈希表在内存中的结构大致如下图：

<html>

</html>

按照上图，具体的来说，无序容器在存储上组织为一组桶（Bucket，侯老师称为篮子），每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。如果容器允许重复关键字，所有具有相同的关键字的元素也都会在同一个桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

值得注意的是，哈希表中，桶和元素的关系是有一定联系的。试想如果一个桶包含的元素太多，势必影响查找的效率。因此，对于桶的管理，哈希表的策略是：如果元素的数量超过桶的数量，那么桶数量又会重新扩充到大约两倍元素的数量。

无序容器的应用

无序容器提供了一组如下管理桶的函数：

/* 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

目录

STL与泛型编程第一周

标准模板库STL

STL的提供方式

STL相关资源

STL体系简介

相关代码示例

容器的范围与遍历

容器相关简介

容器的性能

顺序容器

Array

Vector

List

Forward_list

Deque

Queue 和 Stack

关联容器

Set / Multiset

Map / Multimap

无序容器与哈希表

哈希表的应用

无序容器的应用

目录

STL与泛型编程 第一周

标准模板库STL

STL的提供方式

STL相关资源

STL体系简介

相关代码示例

容器的范围与遍历

容器相关简介

容器的性能

顺序容器

Array

Vector

List

Forward_list

Deque

Queue 和 Stack

关联容器

Set / Multiset

Map / Multimap

无序容器与哈希表

哈希表的应用

无序容器的应用

STL与泛型编程第一周