C++标准库（STL）学习笔记（一）容器

经典废话

开始整标准库，了解一门语言最好的方式就是看标准库源码。确实能学到很多东西。前几天面试阿里的实习，问了个C++智能指针，还好最近看视频有看到，不然裂开了。所以学校里学的那点语言基础是完全不够用的，想找工作的话还是要自己多努力啊。

还有，最近查各种容器包括算法的接口发现个网站http://www.cplusplus.com/挺方便的，省的百度了不靠谱。

正文

1、标准库的内容

C++标准库主要有六大组件。容器（Container），算法（Algorithm），迭代器（Iterator），仿函数（Functor），适配器（Adapter），分配器（Allocator）。标准库中还包含一些其他部分，如cin和cout的实现。

这篇主要记录与容器相关的学习所得。

2、泛型编程之特化与偏特化

泛型编程就是在实现类或函数时不指定某些要用的类型，由使用者决定。我是有接触过一些泛型编程，没深入了解过。如果读者完全没接触过，建议先去了解一下。在C++标准库中大量应用泛型编程的手法，因为对于几乎所有的容器、算法等内容，都要给予使用者自己指定类型的权力。这里主要写新接触到的特化与偏特化。

使用泛型时，我们会把决定类型的权力完全留给使用者。但是对于某些类型，或者某一类类型（有点奇怪），我们希望有特定的实现。这时就可以使用特化和偏特化。

（1）特化

一个小例子，也许并没什么道理。我们想实现一个函数，传入一个数，返回它的平方。我们希望这个函数可以接受各种类型的参数，如int，float等，所以我们使用泛型，做了如下实现。

`

template <typename T>
T Sqr(T x){
    return x * x;
}

`

写完之后我们觉得，对于布尔值的变量，对它计算平方值其实并没有什么意义，因为0和1的平方都是自己。所以当传入的变量是布尔值的时候，直接返回它本身就可以了。于是我们写了一个特化的版本。

template <typename T>
T Sqr(T x){
    return x * x;
}

template <>
bool Sqr(bool x){
    return x;
}

这样在传入值为布尔类型的时候，编译器会找到并调用特化的版本。

特化主要用于在泛型编程中对某些指定模板类型做特殊的处理。在有特化实现的时候，会优先调用特化的版本。在泛型类的实现中也可以使用特化，这里为了例子简单使用的泛型函数。

（2）偏特化

继续借用刚才的例子。在实现完特化之后，我们忽然觉得如果传入的类型是指针类型的话，对它做平方运算并不合适。我们希望在使用者向我们的函数传入指针类型时，能够警告使用者这样做不合理。

template <typename T>
T Sqr(T x){
    return x * x;
}

template <>
bool Sqr(bool x){
    return x;
}

template <typename T>
T* Sqr(T* x){
    std::cout << "请勿对指针做平方运算。" << endl;
    return nullptr;
}

这样在使用者传入的参数为指针时（不管是指向什么类型的指针），编译器都会调用针对指针的偏特化版本。偏特化同样适用于对常量（const T），引用（T&）等类型。同时，如果函数或类具有多个模板类型，指定其中的一部分，即部分特化，也叫做偏特化。

特化和偏特化在C++标准库中大量使用并完成了很多看起来很神奇的功能实现，后面再说。

3、分配器（Allocator）

分配器在标准库的六大组件里大约是最没牌面的一个，很多课程都懒得去讲它。在我这里它也没牌面，被丢进写容器的文章里顺带写了。

分配器为容器服务，负责为容器分配合适的储存空间，也就是一个包装了几层的malloc。有的编译器和版本中的分配器有一些为了速度更快的设计，而大部分只是计算一下大小，用一下new而已。对使用者来讲，在绝大多数的情况下根本不需要关心分配器的事情。在声明一个容器时，编译器会自动给它指定一个默认的分配器。

当然，其实程序员可以自己写一个分配器，然后声明容器时指定使用自己的分配器。然而我比较懒，不知道你们怎么想。

4、各大容器及他们的关系

标准库中实现了很多的容器。下面列一个名单。其中非公开的意思是标准库不想给你用，你非要用的话大约也是可以的。

非公开：红黑树（rb_tree），哈希表（hashtable）。

序列容器：数组（array），向量（vector），双向队列（deque），单向链表（forward_list），链表（list）， 栈（stack），队列（queue），优先队列（priority_queue）。

关联容器：集合（set），多重集合（multiset），映射（map），多重映射（multimap）。（大约是这么翻译吧，我也不知道）

无序关联容器：无序集合（unorderd_set），无序多重集合（unordered_multiset），无序映射（unordered_map），无序多重映射（unordered_multimap）。

这些名字和分类看着奇奇怪怪的没关系，慢慢学嘛。用的多了就都了解了。后面写的时候可能会用英文名字多一些，因为我感觉英文名字好理解。如果你不习惯就多熟悉吧，毕竟写代码的时候他不能用中文啊。

很多地方（包括）把栈、队列、优先队列分类为容器适配器（container adaptor），我因为懒，就丢一起了。其实官方分进容器里面的也有的其实是容器适配器，没必要研究这些字眼。总之都可以当容器用。

在标准库的容器中，并不是每一种都做了独立实现。很多容器的实现是对其他容器的包装。标准库中包装的方式是复合，即类中拥有一个其他类的成员。容器关系如下：

stack，queue衍生自deque。

priority_queue衍生自queue。

set，map，multiset，multimap衍生自红黑树。

unordered家族都衍生自哈希表。

红黑树和哈希表之所以不作为公开容器，就是因为这些容器对它们做了足够完备的包装。使用这些衍生容器就可以完成几乎所有的要求。然而他确实在那。

5、List

C++中的List是双向链表，单向的叫forward_list，是把list包了包做出来的。List的实现是一个环状双向链表，尾端添加了一个空白节点，以复合标准库前闭后开的规范。很简单，没什么好说。

6、Array

Array容器是对数组的包装，内部就是一个数组。如果给Array传入0大小，会自动创建一个1大小的数组。Array容器的迭代器是纯正的一根指针，没有构造和析构函数。

7、Deque

Deque是stack和queue的基础，如果写算法题的话，估计可以说一直在用deque。Deque用法上像一个双向的vector，头尾都可以添加和删除。

Deque的实现是分段连续，每一个buffer中是连续的，不同buffer天各一方，由deque中一个指针类的vector（控制中心）记录每一个buffer的位置。大概就和盛饭一样，一碗一碗盛，装不下了就下一碗。Deque通过重载访问操作符和特殊设计的迭代器来造成连续的假象，其实也就是在迭代器加减移动的时候多判断一下会不会超出buffer边界，如果会的话，就跑回控制中心然后跳到对应的buffer里去。

Deque支持insert，然而因为他是连续的，就要移动很多个元素。比vector好的是他有两头，可以找近的一边，然后把那一边的元素都挪一下腾个地方插入。

Deque的迭代器由四个指针构成。一个指向当前位置，这是每个迭代器都有的。第二个指向deque的控制中心里目前buffer对应的位置。剩下两个指向目前buffer的头尾，用来对是否越界做判断。

stack和queue就是deque删了一些功能，讲道理的话完全属于多此一举，跟用deque没区别。然而我也天天用，懒，那能咋办。多说一句，其实stack和queue可以指定list为底层容器，然而可以想见的会慢一些。

8、rb_tree

红黑树是set和map的基础，而且也是在学数据结构时常常会听到的传说。这个东西他确实比较复杂，我也不打算写他具体运行的规则，虽然我研究过。有兴趣的话可以去找来看看，反正估计观看过程不会很愉快。

简单地理解，红黑树就是一种平衡的二叉搜索树。一个节点有两个子节点，并且他内部的神奇操作让整个树处于平衡的状态。平衡大概就是每根枝子差不多长，如果画出来看会比较饱满，不会一边戳上天了另一边没长，这句话一点都不严谨，就是表达个意思。操作方式大概就是在加入元素和删除元素时晃悠晃悠，让他继续保持平衡，嗯，我也不知道我在说什么。

红黑树也具有二叉搜索树的特性，是一个有序的容器。在这里说一句，红黑树包括set和map的头（front）是最小的元素，并不是根节点。

红黑树的元素为键值对，key用来确定元素的位置，value是元素的内容。

9、Set和Map

为什么这两个被没有牌面地挤在了一起呢，因为他俩孪生兄弟，可以理解吧。这两个都是红黑树亲生孩子，只不过使用红黑树的方式有些许不同。他们都要求插入的元素的key在容器中独一无二。

Set插入的是单一元素，也就是元素的key就是value。Set的元素不允许插入后修改，因为会影响它在树中的位置。Set的迭代器也是const 迭代器。。

Map插入的是键值对。Map的元素可以修改，但修改的不是key，只能是value部分。Map的[]操作符会返回key对应的value，如果该key不存在，会创建一个使用该key的元素，并且为它的value赋默认值，然后返回。

multiset和multimap分别是上面两个的分裂体，都可以插入多个key相同的元素。

10、Hashtable

哈希表也是数据结构中的老生常谈了。具体原理我也不讲了，大概就是根据hashfunction，每个元素会获得一个号码牌，根据号码牌就能找到该存的地方。

Hashtable跟之前的容器都不一样的地方在于，他不接受任意类的元素。如果你自己写了一个类想用哈希表存储，你还需要给出一个hashfunction，因为标准库并不知道怎么给自定义的类发号码牌。标准库只给出了对于基本类的hashfunction。

写哈希函数就很技术了，好的坏的效果差距很大。如果只是想能用的话，可以把自定义类中的一个或多个基本类的成员拿出来，分别使用他们的哈希函数算出来几个号码牌，然后把它们用某种方式结合一下。

unordered家族全都是从这里来的，里面具体的区别跟上面一栏讲的是一样的，可以自己联想一下。

• 还没有人评论，欢迎说说您的想法！