C++ Standard Library — Architecure & Sources

Tiny Rooms by Mohamed Chahin

引言

C++标准库是C++程序员不可或缺的生产工具和技术宝库。其中的大体量成份，我们称为STL (Standard Template Library/标准模板库)。本文将深入分析 STL 标准库的六大部件及其之间的体系结构，并分析其源码，引导高阶泛型编程。

开始之前

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

你應具備的基礎

C++ 基本語法（包括如何正確使用模板，templates）

我們的目標

level 0: 淺嘗 C++ 標準庫
level 1: 深入認識 C++ 標準庫
level 2: 良好使用 C++ 標準庫
level 3: 擴充 C++ 標準庫

C++ Standard Library vs. Standard Template Library

C++ 標準庫，版本

标准库的版本不会影响代码编写，各式各样的编辑器或是开发平台中标准库的用法都是一样的。

重要網頁，CPlusPlus.com

重要網頁，CppReference.com

重要網頁，gcc.gnu.org

書目誌

STL 体系结构基础介绍

STL 六大部件

程序的主体是由数据结构和算法构成，C++ 中全世界最好的团队把非常重要的算法和容器都做了出来，也是六大部件中最重要的两个。

我们最开始接触的应该是容器（Containers），容器要放东西，东西要占内存，所以容器的好处在于帮我们把内存的问题解决了。你看不到内存，只需要把东西放进容器或者取出就好了，所以它的背后需要有另外的东西去支持：分配器（Allocator），分配器是用来支持容器的。

容器里面放入的数据需要操作，有一些操作是在容器本身做，还有更多的操作被独立出来变成一个个模版函数放在算法（Algorithms）里。说到算法大家可能想到课上学的排序：冒泡排序、快速排序、希尔排序……搜索有线性查找、二分查找等等都包含在算法里。在面向对象的思想里鼓励类中存放数据和函数，而现在我们看到数据在容器内，操作数据的动作算法却不在这个类中，所以它的设计观念和方式和面向对象是不一样的。

算法与容器的桥梁是迭代器（Iterators），它就好像是一种泛化的指针。除此之外还有两个东西：适配器（Adapters）和仿函数（Functors），其中仿函数作用像是一个函数，适配器则是帮助我们转换：

容器适配器（Container Adapters）
迭代器适配器（Iterator Adapters）
仿函数适配器（Functor Adapters）

STL 六大部件關係

这里的容器使用的是 vector，而第二个参数 allocator<int> 则是允许你放一个分配器帮助其分配内存，你可以不写，在源代码里会有默认的分配器，所以大部分人都不会写这个模版参数。

接下来我需要操作它。这里选择的算法是 count_if，功能是计算出符合条件的元素有几个。之后我们使用迭代器传入之前元素 vi 的头 vi.begin() 和尾 vi.end()，放置的条件是小于 40 的元素，外加的 not1() 则条件变为大于等于 40。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int ia[6] = {27, 210, 12, 47, 109, 83};
    vector<int, allocator<int>> vi(ia, ia + 6);

    cout << count_if(vi.begin(), vi.end(),
            not1(bind2nd(less<int>(), 40)));

    return 0;
}

複雜度，Complexity，Big-oh

没有完美的容器，只有合适的容器，具体情况具体分析。

$O(1) \space\space O(c)$ 常數時間
$O(n)$ 線性時間
$O(\log_2{n})$ 次線性時間
$O(n^2)$ 平方時間
$O(n^3)$ 立法時間
$O(2^n)$ 指數時間
$O(n\log_2{n})$ 介於線性及二次方成長的中間之行為模式

“前閉後開”區間

所有的容器都有头有尾，提供 begin()、end() 这两个函数。头大家是没有疑虑的，而尾指的是最后一个元素的后一个位置，而不是最后一个元素本身，形成前闭后开区间。

Container<T> c;
...
Container<T>::iterator ite = c.begin();
for(; ite != c.end(); ++ite)
	...

range-based for statement (since C++11)

C++11 有一个新特性可以简化上面的迭代器写法：

for(decl : coll) {
	statement
}

举几个具体的例子：

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

std::vector<double> vec;
for(auto elem : vec) {
    std::cout << elem << std::endl;
}

for(auto& elem : vec) {
    elem *= 3;
}

auto keyword

list<string> c;
...
list<string>::iterator ite;
ite = ::find(c.begin(), c.end(), target);

对于 auto 关键字我们可以这样更改，但对于优秀的程序员还是需要知道变量的类型比较好，而为了写作舒适可以适量使用：

list<string> c;
...
auto ite = ::find(c.begin(), c.end(), target);

容器与各种测试

容器-結構與分類

这张图涵盖了容器的结构以及分类，最重要的是它内存中长什么样，元素间是什么样的关系（连续还是指针）。

容器分类大致分为两种：

Sequence Containers 序列式容器
这种容器适合做快速地查找。查找是很重要的事情，小时候听人家说电脑主要是放大量的资料以及很容易去找东西，当时我想电脑这么尖端科技的东西只是用来做这么简单的东西吗？后来发现生活中许多事情其实就是排序查找的一个过程
Associative Containers 关联式容器
Unordered Containers 不定序容器
C++11 （图中红框标记的均为新特性）新出现的容器，个人认为这种分类方法并不是很好，它其实就是一种关联式容器。元素放进这个容器没有一定的次序，其实就是用哈希表做的容器

Sequence Containers

在 Sequence Containers 中第一种就是 Array 数组，这个数组是把语言的数组包装为类。Array 就是一个连续空间，你要多大就分配多大，体现在图中就是封闭的两端，前面和后面是无法扩充的。

第二种容器则是 Vector，图中的起点是封闭的，而后面是可以扩充的，当它空间不够时会自动增长（容器分配器来处理这件事）。

第三种容器叫做 Deque，队列本来是先进先出，而这里是双向队列，图中展示出两端可进可出。它的弹性非常大非常好啊，但是怎么可能有一个内存可以前后都可以扩充的呢？再后面我们会讲它是怎么做的。

下面的容器是 List，每一个元素并没有连续地挂在一起，中间都是用指针串联起来，而且指针都是双向的。在源代码中它其实是一个双向环状链表，在使用上只需要知道它是双向的就可以了。

C++11 新加了单向链表 Forward-List，每一个元素的指针都是单向，而选择 List 耗用的内存一定比你使用 Forward-List 要多。

Associative Containers

对于大量查找来讲最有价值的是 Associative Containers，它主要表现为 Set 和 Map，内部是用高度平衡的红黑树（一种特殊的二分树）做的，避免了最坏的查找情况。

測試程序

long get_a_target_long() {
    long target = 0;
    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    return target;
}

string get_a_target_string() {
    long target = 0;
    char buf[10];
    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    snprintf(buf, 10, "%ld", target);
    return string(buf);
}

int compareLongs(const void* a, const void* b) {
    return (*(long*)a - *(long*)b);
}

int compareString(const void* a, const void* b) {
    if (*(string*) a > *(string*) b)
        return 1;
    else if (*(string*) a < *(string*) b)
        return -1;
    else
        return 0;
}

主函数部分如下，之后在 switch 语句中添加即可：

int main() {
    int choice;
    long value;

    cout << "\n\ntest_containers()......... \n";
    cout << "select: \n";
    cout << "       \t(1)array          \t(2)vector             \t(3)list               \t(4)forward_list \t(5)deque\t(6)multiset \n";
    cout << "       \t(7)multimap       \t(8)unordered_multiset \t(9)unordered_multimap \t(10)slist \n";
    cout << "       \t(11)hash_multiset \t(12)hash_multimap     \t(13)set               \t(14)map         \t(15)unordered_set \n";
    cout << "       \t(16)unordered_map \t(17)stack             \t(18)queue \n\n";
    cout << " (2),(3),(5),(6),(8) will test also moveable elements. \n";
    cin >> choice;
    if ( choice != 1 ) { 	//1 ==> array, use ASIZE
        cout << "how many elements: ";
        cin >> value;
    }

    switch (choice) {
        case 1 :
            ......
            break;
        default:
            break;
    }

    return 0;
}

使用容器 array

array<long, ASIZE> c;
clock_t timeStart = clock();
for (int i = 0; i < ASIZE; ++i) {
	c[i] = rand();
}

首先创建数组并用 rand() 随机数给数组赋值，clock() 记录耗时节点检测时间。

cout << "milli-second : " << (clock() - timeStart) << endl;
cout << "array.size() = " << c.size() << endl;
cout << "array.front() = " << c.front() << endl;
cout << "array.back() = " << c.back() << endl;
cout << "array.data() = " << c.data() << endl;

这部分掉用了数组 array 的内置函数：

size()：数组大小
front()：数组的头部元素
back()：数组的尾部元素
data()：数组在内存的起点地址

接下来我使用 qsort() 进行排序，参数有数组的起点地址 data()、元素多少 ASIZE、每一个元素的大小 sizeof(long) 以及怎么比大小 compareLongs()：

qsort(c.data(), ASIZE, sizeof(long), compareLongs);

完整代码如下：

#include <array>
#include <ctime>
#include <cstdlib>  // qsort, bsearch, NULL
namespace arrayTest {
    void test_array() {
        cout << "\ntest_array().........\n";

        array<long, ASIZE> c;
        clock_t timeStart = clock();
        for (int i = 0; i < ASIZE; ++i) {
            c[i] = rand();
        }

        cout << "milli-second : " << (clock() - timeStart) << endl;
        cout << "array.size() = " << c.size() << endl;
        cout << "array.front() = " << c.front() << endl;
        cout << "array.back() = " << c.back() << endl;
        cout << "array.data() = " << c.data() << endl;

        long target = get_a_target_long();
        timeStart = clock();
        qsort(c.data(), ASIZE, sizeof(long), compareLongs);
        long* pItem = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);

        cout << "qsort() + bsearch(), millli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != NULL)
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
    }
}

使用容器 vector

void test_vector(long& value) {
	......
}

这里的 value 是指 main 函数中接收的容器大小。

for (long i = 0; i < value; ++i) {
	try {
		snprintf(buf, 10, "%d", rand());
		c.push_back(string(buf));
	}
	catch (exception& p) {
		cout << "i = " << i << " " << p.what() << endl;
		abort();
	}
}

push_back() 是容器放元素到尾部的动作，它没有 “push_front()”，因为 vector 的结构是左闭右开向右增长，如果向头部插入一个元素必须将后面所有元素右移一格，当数量级上去比如一百万个元素会很耗时间。绝大部分容器都有 push_back() 函数。

vector 以两倍速度增长空间：1、2、4、8……以此类推。

try 和 catch 的作用是抓取异常 exception 发生。为什么我要这么设计呢？当空间不够用时可能会发生异常，从注释也可以得到异常出现的边界情况：

// i= 58389486 then std::bad_alloc

这样就可以得到容器最大的容量是多少，发生异常时利用 abort() 退出程序。

cout << "milli-seconds : " << (clock() - timeStart) << endl;
cout << "vector.size() = " << c.size() << endl;
cout << "vector.front() = " << c.front() << endl;
cout << "vector.back() = " << c.back() << endl;
cout << "vector.data() = " << c.data() << endl;
cout << "vector.capacity() = " << c.capacity() << endl;

这里 size() 和 capacity() 的区别是实际元素的个数和容器容量。

string target = get_a_target_string();
timeStart = clock();
auto pItem = ::find(c.begin(), c.end(), target);
cout << "::find(), milli-seconds : " << (clock() - timeStart) << endl;
if (pItem != c.end())
	cout << "found, " << *pItem << endl;
else
	cout << "not found! " << endl;

:: 的作用在于如果在 vectorTest 作用域中找不到 find()，那么它会继续在全局范围内寻找。

这个 find() 传回的是一个 iterator，但前面我们说过迭代器写起来很长，我们可以使用 auto 关键字代替。当迭代器找到这个值时则解参考取值，否则打印未找到。

timeStart = clock();
sort(c.begin(), c.end());
string* qItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareString);
cout << "bsearch(), milli-seconds : " << (clock()-timeStart) << endl;
if (qItem != NULL)
	cout << "found, " << *qItem << endl << endl;
else
	cout << "not found! " << endl << endl;
c.clear();

上下两端用不同的方法来看看查找的速度，标准库的 find() 使用的是按序查找，比较吃运气；后面这种使用排序 + 二分查找。

完整代码如下：

#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib>    // abort()
#include <cstdio>     // snprintf()
#include <algorithm>  // sort()
namespace vectorTest {
    void test_vector(long& value) {
        cout << "\ntest_vector().........\n";
        vector<string> c;
        char buf[10];
        clock_t timeStart = clock();

        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_back(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                // i= 58389486 then std::bad_alloc
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "vector.size() = " << c.size() << endl;
        cout << "vector.front() = " << c.front() << endl;
        cout << "vector.back() = " << c.back() << endl;
        cout << "vector.data() = " << c.data() << endl;
        cout << "vector.capacity() = " << c.capacity() << endl;


        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "::find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;


        timeStart = clock();
        sort(c.begin(), c.end());
        string* qItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareString);
        cout << "bsearch(), milli-seconds : " << (clock()-timeStart) << endl;
        if (qItem != NULL)
            cout << "found, " << *qItem << endl << endl;
        else
            cout << "not found! " << endl << endl;
        c.clear();
    }
}

使用容器 list

刚刚我们看过了 array 和 vector，后面的测试都是一样的形式：以一种问答的形式询问要测试的容器以及容器的容量 value，然后用随机数填充容器并进行测试。

接下来我们来看看容器 list 双向链表。链表和刚刚的 vector 不太一样，vector 在放满后成长两倍，但它不可能在这个位置上成长，一定是在另外一个位置上找一个两倍大的空间，然后再把原来的元素一个个搬过来。所以成长这个过程是非常缓慢的。list 又不一样，它是一个萝卜一个坑，每放一个元素就在空间中找到一个节点大小。

cout << "milli-seconds : " << (clock() - timeStart) << endl;
cout << "list.size() = " << c.size() << endl;
cout << "list.max_size() = " << c.max_size() << endl;
cout << "list.front() = " << c.front() << endl;
cout << "list.back() = " << c.back() << endl;

链表居然有 max_size()，出乎我的意料。按照链表的结构，它的元素是动态分配，应该是只要内存能够供应就可以一直要，之后我们看到源码再来回顾这件事情。

c.sort();

我们调用的不是标准库的全局排序函数，而是容器内的排序函数 sort()。当全局和容器都有排序函数时使用容器内置的排序函数会比较快。

完整代码如下：

#include <string>
#include <stdexcept>
#include <cstdlib>   // abort()
#include <cstdio>    // snprintf()
#include <algorithm> // find()
namespace listTest {
    void test_list(long& value) {
        cout << "\ntest_list().........\n";
        list<string> c;
        char buf[10];
        clock_t timeStart = clock();

        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_back(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "list.size() = " << c.size() << endl;
        cout << "list.max_size() = " << c.max_size() << endl;
        cout << "list.front() = " << c.front() << endl;
        cout << "list.back() = " << c.back() << endl;

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "::find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;


        timeStart = clock();
        c.sort();
        cout << "c.sort(), milli-seconds : " << (clock() - timeStart) << endl;
    }
}

使用容器 forward_list

for (long i = 0; i < value; ++i) {
	try {
		snprintf(buf, 10, "%d", rand());
		c.push_front(string(buf));
	}
	catch (exception& p) {
		cout << "i = " << i << " " << p.what() << endl;
		abort();
	}
}

这里放入元素使用的是 push_front() 而不是之前的 push_back()。还需要注意一下如图所示它没有 back() 或是 size()，注释中许多方法是不提供的。

完整的代码如下：

#include <forward_list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace forwardlistTest {
    void test_forward_list(long& value) {
        cout << "\ntest_forward_list().........\n";

        forward_list<string> c;
        char buf[10];
        clock_t timeStart = clock();

        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_front(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "forward_list.max_size()= " << c.max_size() << endl;
        cout << "forward_list.front()= " << c.front() << endl;

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "::find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;

        timeStart = clock();
        c.sort();
        cout << "c.sort(), milli-seconds : " << (clock() - timeStart) << endl;
    }
}

使用容器 deque

下一个 deque 非常有趣，它是一个双向开口可进可出的结构。但是我们知道一个容器占用内存之后是不能再扩充，再扩充就可能碰到别人占用的内存，所以像 vector 需要在别的地方找到一块内存把原来的搬过去。

deque 的两边都可以扩充，图中的结构可以比较明确的表现出来。上图一共有五段 buffer，一个段落放了八个元素，deque 就是这样一段一段构成的，我们在术语上把它叫作分段延续。然而它的延续只是一种假象，之后我们会在源码部分解析。它每次扩充一个 buffer，所有的 buffer 通过指针依次连接。

完整代码如下：

#include <deque>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace dequeTest {
    void test_deque(long& value) {
        cout << "\ntest_deque().........\n";

        deque<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_back(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "deque.size()= " << c.size() << endl;
        cout << "deque.front()= " << c.front() << endl;
        cout << "deque.back()= " << c.back() << endl;
        cout << "deque.max_size()= " << c.max_size() << endl;

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;

        timeStart = clock();
        sort(c.begin(), c.end());
        cout << "sort(), milli-seconds : " << (clock() - timeStart) << endl;
        c.clear();
    }
}

使用容器 stack

完整代码如下：

#include <stack>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace stackTest {
    void test_stack(long& value) {
        cout << "\ntest_stack().........\n";

        stack<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << endl;
        cout << "stack.size()=" << c.size() << endl;
        cout << "stack.top()=" << c.top() << endl;
        c.pop();
        cout << "stack.size()=" << c.size() << endl;
        cout << "stack.top()=" << c.top() << endl;
    }
}

使用容器 queue

由于这两种容器里面没有自己的数据结构，所以很多人从技术上不把这两个容器叫作容器，而是把它叫作容器的适配器 Adapters。

完整代码如下：

#include <queue>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace queueTest {
    void test_queue(long& value) {
        cout << "\ntest_queue().......... \n";

        queue<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "queue.size()= " << c.size() << endl;
        cout << "queue.front()= " << c.front() << endl;
        cout << "queue.back()= " << c.back() << endl;
        c.pop();
        cout << "queue.size()= " << c.size() << endl;
        cout << "queue.front()= " << c.front() << endl;
        cout << "queue.back()= " << c.back() << endl;
    }
}

前面介绍的那些容器需要再次提醒，有些容器因为它功能上的限制不允许在前段或后段加元素，所以它们不提供 iterator 的操作。以先进后出的 stack 为例，如果它提供迭代器，你很可能用它去改变元素或者删除插入某些元素，而这些操作又会破坏容器先进后出的独特性质，queue 的先进先出也是一样。

使用容器 multist

multiset 可以把它想象成小型的关联数据库，底层结构是红黑树，它的查找是非常快的。

cout << "\ntest_multiset().......... \n";

multiset<string> c;
char buf[10];
clock_t timeStart = clock();
for (long i = 0; i < value; ++i) {
	try {
		snprintf(buf, 10, "%d", rand());
		c.insert(string(buf));
	}
	catch (exception& p) {
		cout << "i = " << i << p.what() << endl;
		abort();
	}
}

这里的安插元素使用的是 insert()，那么它安插的是头是尾呢？都不是，它会安插到它该安插的位置，这棵树是有一定的规则可循的。

完整的代码如下：

#include <set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace multisetTest {
    void test_multiset(long& value) {
        cout << "\ntest_multiset().......... \n";

        multiset<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "multiset.size()=" << c.size() << endl;
        cout << "multiset.max_size()=" << c.max_size() << endl;


        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;


        timeStart = clock();
        auto qItem = c.find(target);
        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, " << *qItem << endl;
        else
            cout << "not found! " << endl;
    }
}

红黑树是高度平衡的，查找也非常快，元素安插的速度慢一些。当你可以接受安插元素慢一些而更关注后面查找的速度，关联式容器是非常不错的选择。

使用容器 multimap

 cout << "\ntest_multimap().........\n";

multimap<long, string> c;
char buf[10];
clock_t timeStart = clock();
for (long i = 0; i < value; ++i) {
	try {
		snprintf(buf, 10, "%d", rand());
		c.insert(pair<long, string>(i, buf));
	}
	catch (exception& p) {
		cout << "i = " << i << " " << p.what() << endl;
		abort();
	}
}

这里插入必须将键值对的形式组合起来，再调用 insert()。key 一定是唯一的，value则是随机数不唯一。

完整的代码如下：

#include <map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace multimapTest {
    void test_multimap(long& value) {
        cout << "\ntest_multimap().........\n";

        multimap<long, string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(pair<long, string>(i, buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "multimap.size()=" << c.size() << endl;
        cout << "multimap.max_size()=" << c.max_size() << endl;

        long target = get_a_target_long();
        timeStart = clock();
        auto pItem = c.find(target);
        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, value = " << (*pItem).second << endl;
        else
            cout << "not found! " << endl;

        c.clear();
    }
}

使用容器 unordered_multiset

接下来的 unordered_multiset 底层不是用红黑树做支撑，而是哈希表。

cout << "milli-seconds : " << (clock() - timeStart) << endl;
cout << "unordered_multiset.size()=" << c.size() << endl;
cout << "unordered_multiset.max_size()=" << c.max_size() << endl;
cout << "unordered_multiset.bucket_count()=" << c.bucket_count() << endl;
cout << "unordered_multiset.load_factor()=" << c.load_factor() << endl;
cout << "unordered_multiset.max_load_factor()=" << c.max_load_factor() << endl;
cout << "unordered_multiset.max_bucket_count()=" << c.max_bucket_count() << endl;

这里 bucket_count() 是篮子的个数，看图发现篮子比元素个数还要多，这个合理吗？合理，图中有的篮子挂了许多元素，而有的篮子没有挂载元素，代码中也把前 20 个篮子有几个元素打印出来：

for (unsigned i = 0; i < 20; ++i) {
	cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements." << endl;
}

所以篮子比元素多不是什么了不起的事情。事实上篮子一定比元素多，这是它在设计上一个内部的考量：为了查找速度，每一个篮子链表不能太长，经验法则告诉大家如果元素个数大于篮子，那么这个篮子就要重新扩充为大约两倍。

而 load_factor() 是载重因子，我们之后再去谈它。

完整代码如下：

#include <unordered_set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace unordered_multisetTest {
    void test_unordered_multiset(long& value) {
        cout << "\ntest_unordered_multiset().........\n";

        unordered_multiset<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "unordered_multiset.size()=" << c.size() << endl;
        cout << "unordered_multiset.max_size()=" << c.max_size() << endl;
        cout << "unordered_multiset.bucket_count()=" << c.bucket_count() << endl;
        cout << "unordered_multiset.load_factor()=" << c.load_factor() << endl;
        cout << "unordered_multiset.max_load_factor()=" << c.max_load_factor() << endl;
        cout << "unordered_multiset.max_bucket_count()=" << c.max_bucket_count() << endl;
        for (unsigned i = 0; i < 20; ++i) {
            cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements." << endl;
        }


        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;


        timeStart = clock();
        auto qItem = c.find(target);
        cout << "c.find(), ,milli-seconds : " << (clock() - timeStart) << endl;
        if (qItem != c.end())
            cout << "found, " << *qItem << endl;
        else
            cout << "not found! " << endl;

        c.clear();
    }
}

使用容器 unordered_multimap

完整代码如下：

#include <unordered_map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace unordered_multimapTest {
    void test_unordered_multimap(long& value) {
        cout << "\ntest_unordered_multimap().........\n";

        unordered_multimap<long, string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(pair<long, string>(i, buf));
            }
            catch (exception& p) {
                cout << "i = " << i << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "unordered_multimap.size()=" << c.size() << endl;
        cout << "unordered_multimap.max_size()=" << c.max_size() << endl;


        long target = get_a_target_long();
        timeStart = clock();
        auto pItem = c.find(target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "c.find(), value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}

当你需要大量搜寻某些元素时，可以考虑关联式容器，有用红黑树做底层的，有用哈希表散列表做底层的。

使用容器 set

前面四种容器前面都有 multi 字眼允许重复的 key 存在，接下来的四种容器的 key 必须是独一无二的。

因为 key 不可以重复，而随机数很有可能出现重复，所以在这里 set 放进去的一定不是原来的数量。

完整代码如下：

namespace setTest {
    void test_set(long& value) {
        cout << "\ntest_set().........\n";

        set<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "set.size()=" << c.size() << endl;
        cout << "set.max_size()=" << c.max_size() << endl;

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;


        timeStart = clock();
        auto qItem = c.find(target);
        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
    }
}

使用容器 map

刚刚在讲 set 的时候说一共放进去 32768 个元素，现在我也放 100 万次，按道理讲我现在放进去东西容器的大小也应该 32768，但 map 大小却是 100 万。原因是键值对的 key 是 for loop 中的 i，并不会重复，而 value 重复并不影响，所以可以放入 100 万个 value 进去。

完整代码如下：

namespace mapTest {
    void test_map(long& value) {
        cout << "\ntest_set().........\n";

        map<long, string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(pair<long, string>(i, buf));
            }
            catch (exception& p) {
                cout << "i = " << i << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "set.size()=" << c.size() << endl;
        cout << "set.max_size()=" << c.max_size() << endl;

        long target = get_a_target_long();
        timeStart = clock();
        auto pItem = c.find(target);
        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}

后面的 unordered_set 和 unordered_map 和之前类似。

使用容器 unordered_set

完整源码如下：

#include <unordered_set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime>
namespace unordered_setTest {
    void test_unordered_set(long& value) {
        cout << "\ntest_unordered_set().........\n";

        unordered_set<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch (exception& p) {
                cout << "i = " << i << " " <<  p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "unordered_set.size()=" << c.size() << endl;
        cout << "unordered_set.max_size()=" << c.max_size() << endl;
        cout << "unordered_set.bucket_count()=" << c.bucket_count() << endl;
        cout << "unordered_set.load_factor()=" << c.load_factor() << endl;
        cout << "unordered_set.max_load_factor()=" << c.max_load_factor() << endl;
        cout << "unordered_set.max_bucket_count()=" << c.max_bucket_count() << endl;
        for (unsigned i = 0; i < 20; ++i) {
            cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements.\n";
        }

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

    }
}

使用容器 unordered_map

namespace unordered_mapTest {
    void test_unordered_map(long& value) {
        cout << "\ntest_unordered_map().........\n";

        unordered_map<long, string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i < value; ++i) {
            try {
                snprintf(buf, 10, "%d", rand());
                c[i] = string(buf);
            }
            catch (exception& p) {
                cout << "i = " << i << " " << p.what() << endl;
                abort();
            }
        }

        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "map.size()=" << c.size() << endl;
        cout << "map.max_size()=" << c.max_size() << endl;

        long target = get_a_target_long();
        timeStart = clock();
        auto pItem = c.find(target);
        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}

使用分配器 allocator

前面我们介绍的都是容器，容器的背后需要一个东西来支持内存的使用，这个东西就是分配器。在理想的情况下我们最好是不知道这个东西，你不用写出来容器就有一个默认的分配器。从图中可以知道每一个容器都声明为模板，它们的默认参数都是 std::allocator。

除了标准库的分配器，gnu 还给了许多分配器：

array_allocator 队列分配器
mt_allocator 多线程分配器
debug_allocator 调试分配器
pool_allocator 内存池分配器
……

它们都放在 #include <ext/...> 底下，是非标准库 _gnu_cxx:: 的。

图中代码以 list 双向链表为例，创建出这些容器之后，测试程序会询问我要选择多少个元素并使用不同分配器分配内存，这也是搭配不同分配器在容器上的写法。

有一个疑惑：有没有可能直接使用容器？当然是可以的，分配器就提供两个函数 allocate() 和 deallocate()。有没有必要呢？没有必要，因为真正的工具是容器，实在没有必要用它背后的分配器去拿内存、还内存。右侧代码对每一个容器都见一个分配器，调用 allocate() 和 deallocate()。

为什么说不值得呢？因为如果不使用容器你可能会使用 new 搭配 delete，或者 malloc 搭配 free。而如果还需要记住指针带着的字节，显然没有人受得了。总之就是不建议使用分配器，负担会很重，在程序中应该尽量使用容器，而小量的内存需求则应该选择传统的 new 搭配 delete，或者 malloc 搭配 free。

源代码分布

上几讲我们写了一个测试程序，用了标准库中很多容器以及分配器，对体系结构我们有了一些了解，整个 STL 六大部件有着非常紧密的联系。但是要深入了解这些体系结构，我们必须要看源代码。

源码在你面前，只要能看得懂，还有什么秘密可言呢？你需要相当程度的了解 STL才能够把它用的非常好，才能选择一个好的算法，选择一个好的容器。从另外一个角度来看，标准库对于 C++ 从业者是一个宝库，如果我们可以看懂源代码我们可以学到很多很多技巧，包括算法的技术、容器和数据结构的技术以及语言本身的技巧。

你應該具備的基礎

標準庫版本

OOP 面向对象编程 vs. GP 泛型编程

整个 C++ 标准库并不是用面向对象设计出来的。面向对象需要类，然后要有继承关系，最重要的是还有一些扮演重要角色的虚函数，在早期的标准库版本它的继承关系非常少，所以比较容易看，现在我们来谈谈 OOP 和 GP 差别在哪里。

以 OOP 的理念来说数据需要结合方法，所以 sort() 函数被设计在 list 内如上图所示。

GP 的设计中 vector 和 deque 都没有 sort()，排序操作被单独设计为两个版本的全局函数：第一个版本参数为数据的头和尾，这样就可以定位出整个数据的范围；第二个版本则是增加了排序条件。GP 的理念是将数据和操作分开，那操作又是如何得到数据本身呢？

还记得第一节课讲的嘛？左边是容器 Containers，右边是算法 Algorithms，两者需要迭代器 Iterators 来联系。所以当我们要对这种容器做排序的时候，我们一般这么写：

::sort(c.begin(), c.end());

调用 sort() 全局函数并且把它要操作的范围告诉它，调用容器的 begin() 和 end() 得到头尾两根泛化指针（或是迭代器），右手边的算法就可以开始排序了。

sort() 函数可能非常复杂，不容易找到关键的地方。我们以最简单的取最大最小的源代码为例：

template<class T>
inline const T& min(const T& a, const T& b) {
    return b < a ? b : a;
}

template<class T>
inline const T& max(const T& a, const T& b) {
    return a < b ? b : a;
}

在 min() 函数中接收 a 和 b 两个参数，找出谁比较小。它接收模板类型 T 的参数，当然类型必须相同，至于怎么比大小只要用 < 操作符。如果传进来的是 int 整型，那么数字之间本来就可以比大小，语言已经规定好了。

如果传进来的是两个 stone 石头，这不是我 min() 需要关心的事情，石头怎么比大小由石头自己决定，具体来讲是重载 < 操作符。因为这个思路，在标准库里操作符重载扮演非常重要的角色。

回来之前，为什么 list 不能使用 ::sort() 排序？可以看到源码：

template<class RandomAccessIterator, class T, class Size>
void _introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*, Size depth_limit) {
    ...
    RandomAccessIterator cut = _unguarded_partition(first, last, T(_median(*first, *(first + (last - first)/2), *(last - 1))));    
    ...    
}

这里出现了 first + (last - first)/2 这样一个动作，只有随机访问迭代器 RandomAccessIterator 才能进行这样的加减乘除运算，而链表 list 是以指针串起一个个节点，它并不是连续的空间，所以它的迭代器不能够跳来跳去的，不能够 +5 亦或是 +10。这样看下来标准库的 sort() 算法需要一定的条件，而这个条件是链表 list 提供的迭代器所不能满足的。

所谓算法，最终涉及的操作无非是比大小。查找一个东西，如果它既不大于也不小于，那就是等于咯。如果是排序，也就是把大大小小的位置移动，也都是在比大小。

bool strLonger(const string& s1, const string& s2) {
    return s1.size() < s2.size();
}

cout << "max of zoo and hello:" << max(string("zoo"), string("hello")) << endl;
cout << "longest of zoo and hello:" << max(string("zoo"), string("hello"), strLonger) << endl;

template<class T, class Compare>
inline const T& max(const T& a, const T& b, Compare comp) {
    return comp(a, b)? b : a;  
}

操作符重载及模板基础

Operator Overloading 操作符重載

template<class T, class Ref, class Ptr>
struct _list_iterator {
    typedef _list_iterator<T, Ref, Ptr> self;
    typedef bidirectional_iterator_tag iterator_category;
    typedef T 	value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef _list_node<T>* link_type;
    typedef ptrdiff_t difference_type;
    
    link_type node;
    
    reference operator*() const { return (*node).data; }
    pointer operator->()  const { return &(operator*()); }
    self& operator++()			{ node = (link_type)((*node).next); return *this; }
    self operator++(int)		{ self tmp = *this; ++*t; }
    ...
}

Templates 模板

Class Templates 類模板

template <typename T>
class complex {
public:
    complex(T r = 0, T i = 0): re(r), im(i) {}        
    
    complex& operator += (const complex&);
    T real() const { return re; }
    T imag() const { return im; }
private:
    T re, im;
    
    friend complex& _doapl(complex*, const complex&);
}

{
    complex<double> cc1(2.5, 1.5);
    complex<int> c2(2, 6);
    ...
}

这里复数的设计使用了模板，我们可以把这些部分先保留，这就形成了一个类模板。在使用时需要告诉编译器要把 T 替换为什么，上面的例子分别是 double 和 int。

Function Templates 函數模板

template <class T>
inline const T& min(const T& a, const T& b) {
    return b < a ? b : a;
}

class stone {
public:
    stone(int w, int h, int we): _w(w), _h(h), _weight(we) {}
    
    bool operator<(const stone& rhs) const { return _weight < rhs._weight; }

private:
    int _w, _h, _weight;
}


stone r1(2, 3), r2(3, 3), r3;
r3 = min(r1, r2);

min() 这个写法更泛化，传进来的 a 和 b 都无所谓暂定为 T，而比大小则依赖于小于号 <。

现在我有一个 stone 石头类，调用 min() 编译器会在调用时候对函数模版进行实参推导，把 T 推导为 stone。推出之后里面比大小会去看 stone 设计的时候有没有操作符重载，发现是以石头的重量比大小。

Member Templates 成員模板

Specialization 特化

类模板又有一个独特的小东西：泛化和特化。GP 泛型编程也叫泛化，刚刚提的类模板里的 T 允许绑定任何东西，可是我们在设计类模板的时候通常会有这样的疑惑：我可能设计出非常泛化的版本，接收任何指令的 T，但设计者想到如果遇到某一个独特的 type 我有另外一种更棒的做法，这样我想要写出专属的独特做法该怎么办呢？

比如计算机图形学中绘制一条直线，数学上的直线方程是一种泛化；应用到电脑绘图里它的每一个点坐标都是整数，我们就可以用特殊的算法绘制直线，这就是特化。

C++ 为我们提供了这个方式，图中从语法上讲由于泛化类型 class type 已经被绑定为 int 了，于是就被抽空为 template<>。使用上如果为 <Foo> ，那么就执行泛化模版；若为 int 或 double 则执行相应的特化模板。

STL 标准库的源代码更有说服力：

template <class Key> struct hash {}

_STL_TEMPLATE_NULL struct hash<char> {
    size_t operator()(char x) const { return x; }
}

_STL_TEMPLATE_NULL struct hash<short> {
    size_t operator()(short x) const { return x; }
}

_STL_TEMPLATE_NULL struct hash<unsigned short> {
    size_t operator()(unsigned short x) const { return x; }
}

_STL_TEMPLATE_NULL struct hash<int> {
    size_t operator()(int x) const { return x; }
}

_STL_TEMPLATE_NULL struct hash<unsigned int> {
    size_t operator()(unsigned int x) const { return x; }
}

_STL_TEMPLATE_NULL struct hash<long> {
    size_t operator()(long x) const { return x; }
}

_STL_TEMPLATE_NULL struct hash<unsigned long> {
    size_t operator()(unsigned long x) const { return x; }
}

这一部分正是哈希表/散列表的源代码。_STL_TEMPLATE_NULL 其实是一个 typedef 被转换为 template<>，表示我们要特化以下类型：

char
short
unsigned short
int
unsigned int
long
unsigned long

template<typename _Tp> class allocator;

// allocator<void> specialization
template<>
class allocator<void> {
public:
    typedef size_t		size_type;
    typedef ptrdiff_t	difference_type;
    typedef void*		pointer;
    typedef const void* const_pointer;
    typedef void		value_type;
    
    template<typename _Tp1>
    struct rebind { typedef allocator<_Tp1> other; };
}

上面是泛化的类模版 allocator，它可以接收任意的 T。但如果这个 T 为 void 则执行下面的特化模版。

Partial Specialization 偏特化

特化又被一些人称为全特化，全部、完整的特化，那么自然就有局部的特化：偏特化。

左侧可以看到 vector 有一个泛化版本，它接收两个模版参数 T 和 Alloc，下面的版本两个模版参数绑定其中一个为 bool。也就是说 vector 可以绑定任意类型去作为元素，但如果我指定 T 为 bool，标准库会有一个特别的设计，可能是效率更高，也可能是空间利用率变高。

另外还有一种范围的偏特化。interator_traits 有一个泛化版本接收任意参数，而下面如果接收的是指针，则有特殊的设计，但此时 T 是什么仍然不知道。同理另一个偏特化版本针对常量指针，又略有不同。

分配器

以 STL 的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在容器的背后默默工作付出；但若以 STL 的实现角度而言，第一个需要介绍的就是空间分配器，因为整个 STL 的操作对象都存放在容器之内，而容器需要一定的空间。

operator new 和 malloc

void* operator new(size_t size, const std::nothrow_t&)
    _THROW0() {
    // try to allocate size bytes
    void *p;
    while((p == malloc(size)) == 0) {
        // buy more memory or return null pointer
        _TRY_BEGIN
        if (_callnewh(size) == 0) break;
        _CATCH(std::bad_alloc) return(0);
        _CATCH_END;
    }
    return(p);
}


// inline versions of the nothrow_t versions of new & delete operators
inline void* _RTLENTRY operator new(size_t size, const std::nothrow_t &) {
    size = size ? size : 1;
    return malloc(size);
}

可以观察到 new 调用了 malloc 分配内存，在磁盘中如图所示还包含许多额外开销 overhead：红色的边界 Cookie、灰色的 Debug 以及绿色的调整边界 Pad。这些细节会在内存管理章节详细讲解，我们现在只需要知道 malloc 给你的比你所要的大小还多不少。

VC6 STL 对 allocator 的使用

上图是 VC6 中四个容器对 allocator 的使用，它们默认使用的分配器是 allocator：

template<class _Ty, class _A = allocator<_Ty>>
class vector {
    ...
};

template<class _Ty, class _A = allocator<_Ty>>
class list {
    ...
};

template<class _Ty, class _A = allocator<_Ty>>
class deque {
    ...
};

template<class _Ty, class _Pr = less<_K>,
	class _A = allocator<_Ty>>
class set {
    ...
};

分配器最重要的两个函数：allocate() 和 deallocate()。其中 allocate() 调用了 _Allocate()，深入定义看到调用的是 ::operator new，::operator delete 也是同理，没有任何特殊的设计。

int* p = allocator<int>().allocate(512, (int*)0);
allocator<int>().deallocator(p, 512);

它很难用的地方在于必须告诉它当初要了多少空间，而非我们平时直接释放指针，但容器使用它没有这方面的困扰。

BC5 STL 对 allocator 的使用

所有的容器第二个模版参数默认都是 allocator<T>，我们来看看有没有什么独特的设计。

和之前一样，这个 allocator 最重要的两个函数就是 allocate() 和 deallocate()，也是调用 ::operator new 和 ::operator delete，没有任何特殊的设计。

BC++ 比 VC 贴心的地方在于 allocator 的第二参数有默认值为 0，而 VC 没有默认值。

int* p = allocator<int>().allocate(512);
allocator<int>().deallocator(p, 512);

G2.9 STL 对 allocator 的使用

虽然 G2.9 给出了合乎标准库规范的分配器设计，但在容器中使用的却是另一个分配器 alloc。

void* p = alloc::allocate(512);
alloc::deallocate(p, 512);

这个特殊分配器 alloc 主要诉求是减少 malloc 次数从而减少额外开销 overhead。它设计了 16 条链表，每条链表负责特定大小的区块，大小以 8 的倍数增长（这也是为什么空间分配会有 Pad）。

G4.9 STL 对 allocator 的使用

G4.9 分配器又回到了 VC/BC 的情况，使用 ::operator new 和 ::operator delete，没有任何特殊的设计。

之前 G2.9 的 alloc 依然在 G4.9 保留，名称换为了 _pool_alloc。如果想使用，用例如下：

vector<string, _gnu_cxx::_poll_alloc<string>> vec;

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

现在我们来谈谈六大部件中的容器。

这张图在第一讲出现过，大家可以感受到各个容器大致的结构以及内存分配。

容器，結構與分類

上图让我们体会到不同容器之间的关联性。

这里的 rb_tree 与 set、map 是复合关系而非继承，所以我们可以说 set 或 map 里有一个红黑树 rb_tree 作为支撑来管理各个元素。同样的我们可以说 heap 或 priority_queue 里有一个 vector ，stack 或 queue 里头有一个 deque。

题外话，如果想在 Class A 中调用 Class B 的方法，我们可以选择继承或者拥有。在 G2.9 的标准库设计中尽量避免使用继承。

容器及其迭代器

深度探索 list

我们第一个要谈的容器是 list，因为它最具代表性。

容器 list

template <class T, class Alloc = alloc>
class list {
protected:
    typedef _list_node<T> list_node;
public:
    typedef list_node* link_type;
    typedef _list_iterator<T, T&, T*> iterator;

protected:
    link_type node;
......    
};

list 中包含一个 _link_node 类型的 node 指针，其中 _link_node 的定义如下：

template<class T>
struct _list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}

所以 list 本身是一个指针，指向结构体 _list_node，其中包含了数据本身 data 和双向链表的正/逆向指针 next、prev。可以观察到 G2.9 版本中两个指针都是 void* 类型，在程序中还要去转型，而后面的 G4.9 有了明显的改善。

在 list 中可以调用起点和终点，就是通过迭代器实现的。因为链表是非连续空间，所以迭代器不能够是指针：

template<class T, class Ref, class Ptr>
struct _list_iterator {
    typedef T	value_type;
    typedef Ptr pointer;
    typedef Ref reference;
......        
};

我们在第一节讲过前闭后开区间，这里环状双向链表的空白节点体现出的就是最后一个元素的下一个元素不属于容器本身，图中用灰色加以表示。

list’s iterator

迭代器里会有大量的操作符重载用于模拟指针，这里我们以 operator++ 为例：

self& operator++() {
    node = (link_type)((*node).next);
    return *this;
}

node 被赋值为自己的下个节点 next，从而达到 operator++ 的目的。

self operator++(int) {
    self tmp = *this;
    ++*this;
    return tmp;
}

reference operator*() const {
    return (*node).data;
}

prefix form 和 postfix form 区别于一个实际上并没有用的实际参数，postfix 中的 ++*this 调用了 prefix 的 operator++。需要注意到前向和后向 self& 和 self 的不同，这是操作符重载向整数的致敬，整数怎么做那么我们就跟着怎么做：

int i(6);
++++i;	// ++(++i)
i++++;	// (i++)++ ERROR!

list<int> c;
...
auto ite = c.begin();    
++++ite; // ++(++ite) 
ite++++; // (ite++)++ ERROR!

C++ 不允许后++两次，所以迭代器设计也遵循了这个原则。

reference operator*() const {
    return (*node).data;
}

pointer operator->() const {
    return &(operator*());
}

我们可以举个例子：

list<Foo>::iterator ite;
...
*ite;
ite->method();
// (*ite).method();
// (&(*ite))->method();

ite->field = 7;
// (*ite).field = 7;
// (&(*ite))->field = 7;

新版本 G4.9 的迭代器设计中取消了三个参数（即 T、&T 和 *T），只保留一个模版参数 T，传进去之后再定义指针和引用，可读性更高并且易于理解。不仅如此，新版节点的设计被分为 _List_node_base 与 _List_node，链表的指针指向自己而非空指针。

但是 G4.9 也把一些很单纯的东西变得很复杂。在 G2.9 只有 list 包含一个节点 list_node，而新版 list 继承于一个 _List_base 基类，其内置的一个 _List_impl 又继承了分配器，并且内含了 _List_node_base，非常复杂。

迭代器设计原则

Iterator 需要遵守的原則

迭代器是容器与算法之间的桥梁，比如让算法知道它要处理的元素范围，通常我们会传入容器的 begin() 和 end() 两个迭代器交给算法去处理。并且算法需要知道迭代器有哪些性质，它需要进行一些最优的操作动作。

我们举 rotate() 算法为例，rotate() 调用了 std::_rotate()，其参数调用了 _iterator_category()。在图中第一步的萃取器调用了函数 _iterator_category() 想获得迭代器的分类，所谓分类指的是它移动的性质，有的迭代器只能勇往直前向前走；有的还可以后退；有的还可以跳着走……这就是分类，所以这里获取分类以便采取最优的操作策略。第二、三步还想知道它的 difference_type 和 value_type，比如我在容器中放入一百万个字符串 string，那么 value_type 就是 string；difference_type 则是表示两个迭代器的距离。

这张图可以看出算法 rotate() 需要知道 iterator 的三个 associated types，所以算法提出问题，迭代器需要有能力回答问题。这样的提问在 C++ 标准库开发过程中设计出五种，本例出现三种，另外两种未在标准库中被使用：reference 和 pointer。

Iterator 必須提供的 5 種 associated types

回到 G2.9 链表的迭代器设计：

template<class T, class Ref, class Ptr>
struct _list_iterator {
    typedef bidirectional_iterator_tag
        			  iterator_category;	// (1)
    typedef T		  value_type;			// (2)
    typedef Ptr		  pointer;				// (3)
    typedef Ref		  reference;			// (4)
    typedef ptrdiff_t difference_type;		// (5)
    ...
};

G4.9 也是同理，在迭代器这里必须 typedef 这五个 associated types。

值得注意的是 difference_type 使用的类型是 ptr_diff，在标准库的某一个头文件中由某个现成的类型比如 unsign_long 定义。而 iterator_category 的类型为 bidirectional_iterator_tag，表示双向。

回到算法这一端，模版迭代器以 I 表示，提问只需要 I::... 就可以获取想要的 type：

template<typename I>
inline void algorithm(I first, I last) {
    ...
    I::iterator_category
    I::pointer
    I::reference
    I::value_type
    I::difference
    I::difference_type
}

Traits 特性特徵特質

如果 Iterator 不是 class，例如自然指针，这时我们就需要萃取机 Iterator Traits 识别这几种情况。

template<class T>
struct iterator_traits {
	typedef typename I::value_type value_type;
}

// partial specialization
template<class T>
struct iterator_traits<T*> {
	typedef T value_type;
}

template<class T>
struct iterator_traits<const T*> {
	typedef T value_type;
}

...

template<typename I, ...>
void algorithm(...) {
	typename iterator_traits<I>::value_type v1;
}

为了解决自然指针的情况我们设置了中间层 Traits，由萃取机转问迭代器问题，利用偏特化语法分离出指针作回答。

template<class I>
struct iterator_traits {
	typedef typename I::iterator_category;
	typedef typename I::value_type;
	typedef typename I::difference_type;
	typedef typename I::pointer;
	typedef typename I::reference;
}


// partial specialization for regular pointers
template<class T>
struct iterator_traits<T*> {
	typedef random_access_iterator_tag iterator_category;
	typedef T		  value_type;
	typedef ptrdiff_t difference_type;
	typedef T*		  pointer;
	typedef T&		  reference;
}

// partial specialization for regular const pointers
template<class T>
struct iterator_traits<const T*> {
	typedef random_access_iterator_tag iterator_category;
	typedef T		  value_type;
	typedef ptrdiff_t difference_type;
	typedef const T*  pointer;
	typedef const T&  reference;
}

如果是指针，那么迭代器类型 iterator_category 是 random_access_iterator_tag。

各式各樣的 Traits

深度探索 vector

容器 vector

template<class T, class Alloc = alloc>
class vector {
public:
	typedef T			value_type;
	typedef value_type* pointer;
	typedef value_type* iterator;
	typedef value_type& reference;
	typedef size_t		size_type;
	typedef ptrdiff_t	difference_type;
	
protected:
	iterator start;
	iterator finish;
	iterator end_of_storage;
	
public:
	iterator begin() { return start; }
	iterator end() { return finish; }
	
	size_type size() const {
		return size_type(end() - begin());
	}
	
	size_type capacity() const {
		return size_type(end_of_storage - begin());
	}
	
	bool empty() const {
		return begin() == end();
	}
	
	reference operator[](size_type n) {
		return *(begin() + n);
	}
	
	reference front() {
		return *begin();
	}
	
	reference back() {
		return *(end() - 1);
	}
}

vector 通过三根指针控制整个容器，因此 vector 对象本身的大小就是 start、end 以及 end_of_storage 三根指针，在 32 位电脑上一个指针是 4 个字节，一共 12 字节。

我们还注意到只要是连续空间特性的容器，就必须提供 operator[] 的运算符重载。

push_back() 先检查有没有空间放入新的元素，如果有空间就放入元素；否则调用 insert_aux() 函数：

void push_back(const T& x) {
	if(finish != end_of_storage) {  // 尚有备用空间
		construct(finish, x);
		++finish;
	}
	else  // 已无备用空间
		insert_aux(end(), x);
}


template<class T, class Alloc = alloc>
void vector<T, Alloc>::insert_aux(interator position, const T& x) {
	if(finish != end_of_storage) {  // 尚有备用空间
		// 在备用空间起始处构建一个元素，并以vector最后以最后一个元素值为其初值
        construct(finish, *(finish - 1));
		++finish;
		T x_copy = x;
		copy_backward(position, finish - 2, finish - 1);
		*position = x_copy;
	} else {  // 已无备用空间
		...
	}
}

这里的疑惑是前面已经检查过是否有备用空间了，在函数中为何又一次重复判断呢？原因在于 insert_aux() 不仅被 push_back() 调用，还会被其他函数调用需要对备用空间做检查。

else {  // 已无备用空间
	const size_type old_size = size();
	const size_type len = old_size != 0 ? 2 * old_size : 1;
	// 如果原大小为0，则分配1个元素大小
	// 如果原大小不为0，则分配原大小的两倍
	
	iterator new_start = data_allocator::allocate(len);
	iterator new_finish = new_start;
	try {
		...
	} catch(...) {
		...
	}
	
	// 析构并释放原vector
	destroy(begin(), end());
	deallocate();
	
	// 调整迭代器指向新vector
	start = new_start;
	finish = new_finish;
	end_of_storage = new_start + len;
}

首先调用 size() 记下原来的大小 old_size，然后判断 old_size 是否为 0：如果原大小为 0，则分配 1 个元素的大小；否则分配原大小的两倍，也就是我们之前提到的两倍成长。

假设 vector 现在有 8 个元素，放入第 9 个元素进去以两倍成长。于是空间大小由 8 变为 16，然后要把原来的元素拷贝到新的地方，再把第 9 个元素放入新空间中：

try {
    // 将原vector的内容拷贝到新vector
	new_start = uninitialized_copy(position, start, new_start);
	construct(new_finish, x);  // 为新元素设定初值x
	++new_finish;
	// 将安插点的原内容也拷贝过来
	new_finish = uninitialized_copy(position, finish, new_finish);
	
} catch(...) {
	// "commit or rollback" semantics
	destory(new_start, new_finish);
	data_allocator::deallocate(new_start, len);
	throw;
}

在 try 语句中先调用 uninitialized() 将原来的内容拷贝到新的vector，后将新的元素设定初值。后面代码将安插点后的原内容也拷贝过来，这是因为这个函数可能会被 insert(p, x) 调用。

所以 vector 非常容易使用，概念也非常简单。但要注意一点，源代码表明每次扩容就会有大量元素拷贝移动，而元素的拷贝会调用拷贝构造函数，原先的空间也要一个个删除调用析构函数，在使用时需要注意这其中的成本问题。

vector’s iterator

接下来我们看看 vector 的迭代器。

既然 vector 是连续空间，那么它的迭代器就不必设计的太复杂，前面的链表的迭代器就是特殊设计保证前后迭代。在 G2.9 使用指针实现了 vector 的迭代器：

template<class T, class Alloc = alloc>
class vector {
public:
	typedef T value_type;
	typedef value_type* iterator;  // T*
	...
}

之前的 Traits 源码如下：

template<class I>
struct iterator_traits {
	typedef typename I::iterator_category;
	typedef typename I::value_type;
	typedef typename I::difference_type;
	typedef typename I::pointer;
	typedef typename I::reference;
}


// partial specialization for regular pointers
template<class T>
struct iterator_traits<T*> {
	typedef random_access_iterator_tag iterator_category;
	typedef T		  value_type;
	typedef ptrdiff_t difference_type;
	typedef T*		  pointer;
	typedef T&		  reference;
}

// partial specialization for regular const pointers
template<class T>
struct iterator_traits<const T*> {
	typedef random_access_iterator_tag iterator_category;
	typedef T		  value_type;
	typedef ptrdiff_t difference_type;
	typedef const T*  pointer;
	typedef const T&  reference;
}

相比 G2.9，G4.9 的设计更复杂抽象。vector 继承自 _Vector_base父类，父类内含一个 _Vector_impl，而 _Vector_impl 继承自 std::allocator。

这里比较有意思的是 _Vector_impl 是 public 继承，在面向对象的概念里强调“是一种”的关系，而这里的继承只是为了让 _Vector_base 能够用到分配器，所以应该使用 private 继承，在这里设计的并不理想。

G2.9 版非常单纯，新版曲曲折折绕了一大堆路，最终实现实际上和原来是一样的。结论是乱七八糟，舍近求远，何必如此？

深度探索 array

容器 array

array 比起 vector 又更简单，因为它是 C 语言和 C++ 本身存在的数组，但是为什么要把这个东西包装成容器来用呢？如果不这么包装，array 就被摒弃于整个六大结构之外了，无法享受到算法、仿函数的便利。

template<typename _Tp, std::size_t _Nm>
struct array {
	typedef _Tp			value_type;
	typedef _Tp*		pointer;
	typedef value_type* iterator;
	
	// Support for zero-sized arrays mandatory
	value_type _M_instance[_Nm? _Nm : 1];
	
	iterator begin()
		return iterator(&_M_instance[0]);
	
	iterator end()
		return iterator(&_M_instance[_Nm]);
    ...
}

使用方法如下：

array<int, 10> myArray;
auto ite = myArray.begin();
// array<int, 10>::iterator ite = ...
ite += 3;
cout << *ite;

相比其他容器的可扩充性，array 必须指定大小 _Nm，其数据为数组 _M_instance[_Nm]。

在 G4.9 版本数据类型为 _AT_Type::_Type，而 _array_traits 的源代码显示模版为 _Tp。如此复杂的设计真的有之前的版本好么，这里我要打一个问号。

深度探索 forward_list

之前已经介绍过双向链表了，设计思路上是完全一样的，就不再赘述。

深度探索 deque

容器 deque

deque 的组织方式是分段然后串联起来：有许多连续空间的 buffer 存放真正的数据，由一个控制中心 map 来管理这些空间（底层实现使用的是 vector），连续是假象分段是事实。迭代器为了维持这种假象，走到边界（first 或 last）时必须有能力跳到下个节点/缓冲区 node 去，而 cur 表示正在指向的元素。

容器包含四个数据：首尾迭代器 start、finish、控制中心指针 map 以及大小 map_size。因为控制中心底层由 vector 实现，如果向图中放置100万个元素，map 也会以两倍空间增长直至容量足够。

template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public:
	typedef T value_type;
	typedef _deque_iterator<T, T&, T*, BufSiz> iterator;
protected:
	typedef pointer* map_pointer;	// T**
protected:
	iterator start;
	iterator finish;
	map_pointer map;
	size_type map_size;
public:
	iterator begin() return start;
	iterator finish() return finish;
	size_type size() const return finish - start;
...
}

deque’s iterator

迭代器包含之前提到的四个指针，大小为 16 个字节。

template<class T, class Ptr, size_t BufSiz>
struct _deque_iterator {
	typedef random_access_iterator_tag iterator_category;	// (1)
	typedef T value_type;									// (2)
	typedef Ptr pointer;									// (3)
	typedef Ref reference;									// (4)
	typedef size_t size_type;								
	typedef ptrdiff_t difference_type;						// (5)
	typedef T** map_pointer;
	typedef _deque_iterator self;

	T* cur;
	T* first;
	T* last;
	map_pointer node;
...
};

这里的 BufSiz 用于计算缓冲区可以容纳多少元素，如果不为 0 则由使用者自己传入 n 设置；否则看看元素多大：如果元素大于 512 字节，它就让一个缓冲区只放一个元素；如果元素小于 512，那么一个缓冲区放 512/value_type：

inline size_t _deque_buf_size(size_t n, size_t sz) {
    return n != 0? n : (sz < 512? size_t(512 / sz): size_t(1));
}

deque<T>::insert()

// 在position处安插一个元素，其值为x
iterator insert(iterator position, const value_type& x) {
    if (position.cur == start.cur) {	// 如果安插点是deque最前端
        push_front(x);					// 交给push_front()做
        return start;
    } else if (position.cur == finish.cur) {	// 如果安插点是deque最尾端
        push_back(x);							// 交给push_front()做
        iterator tmp = finish;
        --tmp;
        return tmp;
    } else {
        return insert_aux(position, x);
    }
}

这里的巧妙之处在于 deque 可以判断从哪里插入是最优策略。在代码中首先判断 index 与前后之间的位置关系，如果头端移动元素较少则在头部插入第一个元素，然后到插入点之前全部前移；如果尾端移动元素较少则在尾部插入最后一个元素，插入点之后全部后移。

template<class T, class Alloc = alloc, size_t BufSiz>
typename deque<T, Alloc, BufSiz>::iterator
deque<T, Alloc, BufSiz>::insert_aux(iterator pos, const value_type& x) {
	difference_type index = pos - start;	// 安插点之前的元素个数
    value_type x_copy = x;
    if (index < size() / 2) {				// 如果安插点之前的元素个数较少
        push_front(front());				// 在最前端加入与第一元素同值的元素
        ...
        copy(front2, pos1, front1);			// 元素搬移
    } else {								// 安插点之后的元素个数较少
        push_back(back());					// 在尾端加入与最末元素同值的元素
        ...
		copy_backward(pos, back2, back1)
    }
    *pos = x_copy;							// 在安插点上设定新值
    return pos;
}

deque 如何模擬連續空間

对于 deque 剩下一个主题是它怎么模拟连续空间。当然实现上依赖于迭代器的加加减减等等，它一定能够检查边界，跳到另一个缓冲区这些隐藏功能，让使用者不知不觉。

front() 传回头元素，back() 传回 finish （最后一个元素的下一位置）倒退的前一个位置 tmp。而 size() 计算中的减法一定做了运算符重载，它要去看这两个迭代器中间有多少个缓冲区，再把缓冲区个数乘以缓冲区内元素的个数。

reference operator[](size_type n) {
    return start[difference_type(n)];
}

reference front() return *start;
reference back() {
    iterator tmp = finish;
    --tmp;
    return tmp;
}

size_type size() const return finish - start;
bool empty() const return finish == start;

这里的 * 是对迭代器取值 cur，-> 借用了 *：

reference operator*() const return *cur;
pointer operator->() const return &(operator*());

两个迭代器相减算出元素的思路如前面所述：

difference_type operator-(const self& x) const {
	return difference_type(buffer_size()) * (node - x.code - 1) // 两个iterator之间的buffer总长度
        + (cur - first)											// 两个iterator自己的buffer长度
        + (x.last - x.cur);										
}

这里都是后加加调用前加加，后减减调用前减减。作为一个迭代器加加就是移到后一个元素去，所以 cur 指向后一个元素，此时判断是否到达了边界，若到达则跳转至下一节点的起点位置。减减同理，如果到达边界则跳转至前一节点的末尾：

void set_node(map_pointer new_node) {
    node = new_node;
    first = *new_node;
    last = first +
           difference_type(buffer_size());
}

self& operator++() {
    ++cur;					// 切换至下一元素
    if (cur == last) {		// 如果抵达缓冲区尾端
        set_node(node + 1); // 就跳至下一节点（缓冲区）的起点
        cur = first;
    }
    return *this;
}

self operator+++(int) {
	self tmp = *this;
    ++*this;
    return tmp;
}

self& operator--() {		
    if (cur == first) {		// 如果目前在缓冲区首端
        set_node(node - 1); // 就跳至前一节点（缓冲区）的最末端
        cur = last;
    }
    --cur;					// 往前移一元素
    return *this;
}

self operator--(int) {
    self tmp = *this;
    --*this;
    return tmp;
}

刚才的 ++、-- 都是移动一个位置，而 deque 号称是连续空间，所以应该可以移动 n 个位置而不是每次移动一个位置。通过判断计算完后 offset 是否还在同一个缓冲区，如果不在需要计算正确的缓冲区：

self& operator+=(difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset >=0 && offset < difference_type(buffer_size()))
        // 目标位置在同一缓冲区内
        cur += n;
    else {
        // 目标位置不在同一缓冲区内
        difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size())
            										: -difference_type((-offset - 1) / buffer_size()) - 1;
        // 切换至正确的缓冲区
    	set_node(node + node_offset);
        // 切换至正确的元素
        cur = first + (offset - node_offset * difference_type(buffer_size()));
    }
    
    return *this;
}

self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n;
}

在 G4.9 版本设计结构同样相当复杂，容器由单一的类变为上图的复杂情况：deque 继承自一个基类 _Deque_base，而 _Deque_base 又包含了 _Deque_impl，这个 _Deque_impl 包含了迭代器 _Deque_iterator 并继承了分配器 std::allocator。

新版本不允许指派 buffer size 有好有坏，好处在于没必要让使用者知道这些复杂的事情；坏处则在于对于很清楚里面结构的人也许我可以调整缓冲区里面元素的个数，第三参数可以用于调试，而现在没有这个途径了。

容器 queue

queue 的数据类型为 Sequence，底层容器就是 deque，我们只需要封装其中的一些功能就可以使用，调用 c 的功能函数：

template<class T, class Sequence = deque<T>>
class queue {
	...
public:
	typedef typename Sequence::value_type value_type;
	typedef typename Sequence::size_type size_type;
	typedef typename Sequence::reference reference;
	typedef typename Sequence::const_reference const_reference;

protected:
	Sequence c;	// 底层容器
public:	
	bool empty() const return c.empty();
	size_type size() const return c.size();
	reference front() return c.front();
	const_reference front() const return c.front();
	reference back() return c.back();
	const_reference back() const return c.back();
	void push(const value_type& x) c.psuh_back(x);
	void pop() c.pop_front();
}

容器 stack

stack 也是一样的道理，源代码如下：

template<class T, class Sequence = deque<T>>
class stack {
	...
public:
	typedef typename Sequence::value_type value_type;
	typedef typename Sequence::size_type size_type;
	typedef typename Sequence::reference reference;
	typedef typename Sequence::const_reference const_reference;

protected:
	Sequence c;	// 底层容器
public:	
	bool empty() const return c.empty();
	size_type size() const return c.size();
	reference top() return c.back();
	const_reference top() const return c.back();
	void push(const value_type& x) c.psuh_back(x);
	void pop() c.pop_back();
}

深度探索 RB-tree

容器 rb-tree

之前探讨的容器都是循序式容器，从这一章开始我们开始讨论关联式容器。关联式的容器非常有用，因为它查找和元素安插非常快，甚至可以把它想象为小型数据库。

关联式容器底层实现在标准库中使用的是红黑树和哈希表，许多容器在此基础上被封装。

引言

开始之前

你應具備的基礎

我們的目標

C++ Standard Library vs. Standard Template Library

C++ 標準庫，版本

重要網頁，CPlusPlus.com

重要網頁，CppReference.com

重要網頁，gcc.gnu.org

書目誌

STL 体系结构基础介绍

STL 六大部件

STL 六大部件關係

複雜度，Complexity，Big-oh

“前閉後開”區間

range-based for statement (since C++11)

auto keyword

容器与各种测试

容器-結構與分類

Sequence Containers

Associative Containers

測試程序

使用容器 array

使用容器 vector

使用容器 list

使用容器 forward_list

使用容器 deque

使用容器 stack

使用容器 queue

使用容器 multist

使用容器 multimap

使用容器 unordered_multiset

使用容器 unordered_multimap

使用容器 set

使用容器 map

使用容器 unordered_set

使用容器 unordered_map

使用分配器 allocator

源代码分布

你應該具備的基礎

標準庫版本

OOP 面向对象编程 vs. GP 泛型编程

操作符重载及模板基础

Operator Overloading 操作符重載

Templates 模板

Class Templates 類模板

Function Templates 函數模板

Member Templates 成員模板

Specialization 特化

Partial Specialization 偏特化

分配器

operator new 和 malloc

VC6 STL 对 allocator 的使用

BC5 STL 对 allocator 的使用

G2.9 STL 对 allocator 的使用

G4.9 STL 对 allocator 的使用

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

容器，結構與分類

容器及其迭代器

深度探索 list

容器 list

list’s iterator

迭代器设计原则

Iterator 需要遵守的原則

Iterator 必須提供的 5 種 associated types

Traits 特性 特徵 特質

各式各樣的 Traits

深度探索 vector

容器 vector

vector’s iterator

深度探索 array

容器 array

深度探索 forward_list

深度探索 deque

容器 deque

deque’s iterator

deque<T>::insert()

deque 如何模擬連續空間

容器 queue

容器 stack

Traits 特性特徵特質