C++标准库(第二版，作者_NicolaiMJosuttis)_第六章标准模板库_概述

本文是一篇读书笔记，可以在偏向文字叙述方面让你了解STL，代码涉及到的不多，如果你明天面试，看看整个也许有点帮助，笔者就曾经被人问到：vector和list有什么区别？很遗憾当时我没有回答上来，现在的话似乎好一点了。他们都可以在尾部添加元素，vector是可以动态扩展的数组，list是链表，优势是在任何位置插入和删除元素都很快。而vector是在尾部添加数据比较快，在中间插入元素就很慢了。

STL（standard template library）是一个泛型程序库。从程序员的角度来看，STL是由一些可适应不同需求的集合类和一些能够在这些数据集合上运作的算法构成。STL内的所有组件都由template构成，所以其元素可以是任意类型。更妙的是STL建立了一个框架，在此框架下可以提供其他集合类或算法，与现有的组件搭配共同运作。

6.1STL组件

容器（Container）：用来管理某类对象的集合。

迭代器（Iterator）：用来对一个对象集合内遍历元素。迭代器的好处是为所有各式各样的容器提供了一组很小的共通接口。每一种容器都提供了自己的迭代器，而这些迭代器了解容器的内部结构，知道该做什么。

算法（Algorithm）用来处理集合内的元素。它们可以是查找、排序、修改、使用元素。

STL的基本观念就是将数据和操作分离。数据由容器来加以管理，操作由可定制的算法来定义。迭代器在两者之间充当粘合剂，使得任何算法都可以和任何容器交互运作。

6.2容器

先来看一张图，该图非常好，帮助我们记忆STL的容器。

下面的是一个表格，说明白了啥是啥。来源于大师BJARNE STROUSTRUP 的书籍《C++程序设计语言》。 

上面的表格背景颜色也有含义，同色的是属于同一个种类的。请牢记上面的表格。

容器可以分为三大类：

序列式容器（Sequence container）：这是一种有序（ordered）集合（这个有序是order是由顺序的意思，不是大小的比较，那个的英文是sorted），每个元素均有确凿的位置--取决于插入时机和地点，与元素值无关。如果你以追加方式对一个集合置入6个元素，他们的排列次序和置入次序是一致的。五个序列式容器：array、vector、deque、list、forward_list。序列式容器（Sequence container）通常被实现为array或linked list。

关联式容器（Associative container）：这是一种已排序（sorted）集合，元素的位置取决于其value（或key 如果元素是个key /value pair）和某种排序规则。四个关联式容器：set、multiset、map、multimap。关联式容器（Associative container）通常被实现为binary tree。

无序容器（Unordered(associative) container）:这是一种无序集合，其内每个元素的位置无关紧要，唯一重要的是某特定元素是否位于集合内。元素值或者安插的顺序都不影响元素的位置，而且元素的位置有可能在容器生命周期内发生改变。由四个无序容器：unordered_set、unordered_multiset、unordered_map、unordered_multimap。（实在是其不出来新的名字了，干脆都加个unordered_得啦。）无序容器（Unordered(associative) container）通常被实现为hash table。

关联式容器自动对其元素排序，自动排序带来的优势是：查找元素可以带来更高的效率。可以使用二分查找法，它具有对数（logarithmic）复杂度，而不是线性复杂度。

6.2.1序列式容器（SequenceContainer）

从vector开始讲，array是TR1新引入的，和原来的STL有点不搭。

①Vector

Vetctor 将其元素置于一个dynamic array中管理。（这意思就是说可以随时添加元素呗）。

允许随机访问（就是允许用[i]来得到值呗）。

在array的尾部附加元素或移除元素都非常快，但是在array的中段或者起始部分安插元素就很慢，后面的元素都需要移动比较费劲了。

包含语句：include

下面语句创建了一个元素类型为int 的vecor：

vector coll;

Push_back()为容器附加新元素：coll.push_back(i);所有序列式容器都提供这个函数，因为在尾巴那添加一个元素总是可能的，而且效率相当高。

Size（）返回容器的元素个数。所有容器都由这个，除了forward_list 它没有（为啥没有？这个目前还没有说）。

②Deque（double-ended queue的缩写）

是一个dynamic array，可以在两端发展，在头部和尾部添加元素都很快，在中间插入元素比较费劲。

包含语句：include

下面语句创建了一个元素类型为float的空的deque：

deque coll;

Push_front()用来在最前面插入元素，Push_back()用来最后面插入元素。Vector并没有提供Push_front()因为太慢了。STL只提供那些具备良好时间效率的成员函数，所谓良好就是说时间复杂度为常量或者对数，以免菜鸟调用性能很差的函数。（是的，如果有，如果是我，我就说这没毛病，STL里面由这个函数，这肯定行！）

③Array

一个array对象是有固定大小的array（有时可以称之为static array 或C array）。不可以改变元素个数，只能改变元素的值。必须在建立的时候就指明大小。运行随机访问。

包含语句：include

下面语句创建了一个array，带有5个类型为string的元素：

Array coll;默认情况下这些元素都被元素的default构造函数初始化。

④List

从C++11开始，STL提供了两个List：class list<>和class  forward_list<>。

List由双向链表（double linked list）实现。意味着每个元素都有一部分内存指向前一个元素和其后继元素。

Lsit不提供随机访问，意味着如果你要访问第10个元素，你必须沿着链表依次走过前9个元素。因此一般的元素访问会花费较长的线性时间，这比vector和deque要慢很多了。

List的优势是：在任何位置上执行插入和删除动作都非常快，因为只改变链接就好了。也就是说在中间段移动元素比vector和deque快很多呢。

包含语句：include

下面语句创建了一个元素类型为char的list：list coll;

List 并不提供随机访问，因此操作符[]会带来低效率。（疑惑：到底是能不能用[]呢？待实践解惑）。

for（char elem :coll）{} 或（auto elem：coll）{}都可以，elem永远是当前正被处理的元素的一个拷贝。虽然你可以改动它，但是其影响只限于“针对此元素而调用的语句”，coll内部并没有任何东西被该动。如果你想改动传入的集合的元素，你必须将elem声明为一个非常量的reference：

for(auto& elem:coll){}

成员函数empty（）的返回值告诉我们容器中是否还有元素。（是空的吗？False,就是说不是空的，!coll.emptey()就是true，循环就继续）

While(!coll.empty()){}

Front（）返回第一个元素。

Pop_front()并不会返回被删除的元素，它是删除第一个元素。

⑤forward_list

这是一个由元素构成的单方向的linked list，每一个元素都有一段内存，为了节省内存，只是指向了下一个元素。它就是个受限的list，它不支持任何后退移动或者效率低下的操作。基于这个原因，它不提供成员函数push_back()乃至size（）。（这个我暂时无法理解，一定由什么原因在这里？）

Resize（）可以改变元素的个数。

Resize（）是个昂贵的动作，它具备线性的复杂度，因为想要到达尾部，你必须一个一个元素地前进，走遍整个list。

几乎所有的序列容器都会提供这resize，只有array没有，因为它是固定的大小，是固定不变的。

6.2.2关联式容器（AssociativeContainer）

关联式容器依据特定的排序规则，自动为其元素排序。元素可以是任何类型的value，也可以是key/value pair,key可以是任何类型，value也可以是任何类型。排序规则以函数形式呈现，用来比较key，或者key/value中的key，你可以提供自己的比较函数。

关联式容器由二叉树来实现，二叉树中每一个元素（节点）都有一个父节点和两个子节点，左子树的所有元素都比自己小，右子树都比自己大。

关联式容器的主要优点是：它能很快找出一个具有某个特定value的元素，因为它具备对数复杂度（logarithmic complexity）,而序列式容器的复杂度为线性。

关联式容器的主要缺点是：你不能直接改变元素的value，因为那样就破坏了元素的排列顺序。

Set元素依据其value自动排序，每一个元素只能出现一次，不允许重复。

Multiset与Set的唯一区别就是元素可以重复，也就是说Multiset可以包含多个value相同的元素。

Map每个元素都是key/value  pair，其中key是排序准则的基准。每一个key只能出现一次，不允许重复。Map也可被视为一种关联式数组（associative array），也就是“索引可为任意类型”的数组。

Multimap与Map的唯一区别式：Multimap允许元素可以重复，也即是说Multimap允许其元素拥有相同的key。Multimap可以当作字典来使用。

所有关联式容器都有一个可供选择的template实参，它指明了排序准则；默认采用操作符<。

可以将set看作是一种特殊的map：元素的key和value是相等的。

包含语句：include,来使用两个set。

包含语句：include

6.2.3无序容器（UnorderedContainer）

在无序容器中，元素没有明确的排列次序。我们唯一关心的是元素是否位于容器内。可以把它想像为袋子。

无序容器常以hash table来实现出来，内部结构是一个由linked list组成的array。通过某个hash函数的运算，确定元素位于整个array的位置。Hash函数运算的目标是：让每个元素的落点位置有助于用户快速访问。

无序容器的主要优点是：当你打算查找某个特定值的元素，其速度可能会超过关联式容器，前提是你有个好的hash函数。

Unordered Set 是无序元素的集合，每一个元素只能出现一次，不能重复。

Unordered Multiset和Unordered Set 的唯一差别是允许重复。

Unordered Map的元素都是key/value pair，每个key只出现一次，不能重复。

Unordered Multimap和Unordered Map的唯一差别是允许重复。