C++ STL学习

容器库概览

对可以保存在容器中的元素的限制

容器需要支持拷贝操作，因此，保存在容器中的元素要能够支持拷贝操作。可以为不支持特定操作需求的元素类型定义容器，但是这样就只能使用容器那些不要求容器元素有特定操作的操作类型。

一般来说，每种容器都定义在一个与容器名相同的头文件中，对大多数容器，但不是所有容器，需要提供元素类型来生成特定的容器。

特别的，容器的元素的类型可以是另一种容器，只要在外层容器的<>中指定内层容器的类型即可。在老版本的编译器中，这种以其他容器为元素的容器，在声明或者定义时，需要在内层容器的<>和外层容器的<>之间插入空格，如vector<vector<int> > v1，新版本的编译器则无此要求。

容器支持的操作

容器类型支持的操作可以根据容器的大类分成一定的层次：

1. 顺序容器和关联容器都支持的操作；
2. 仅部分顺序容器支持的操作；
3. 仅部分关联容器支持的操作；
4. 少数特殊的容器，如array、forward_list或者无序容器支持的操作。

所有容器都支持的操作或容器成员

下表是所有容器都支持的操作。

迭代器

称某种数据类型是迭代器，当且仅当此类型支持一套操作，此套操作可以访问元素或者从某个元素移动到另一个元素。

迭代器有着相同的接口：如果某个迭代器可以提供某种操作，那么所有提供相同操作的迭代器在实现上都是相同的。

迭代器的公共操作

下表是所有的迭代支持都的操作。

迭代器的类型

迭代器的const属性

所有的拥有迭代器的标准库类型使用两个关键字来表示迭代器类型：

1. iterator表示通过此类迭代器可以对迭代器指向的元素进行读写；
2. const_iterator表示通过此类型只能迭代器指向的元素进行读操作，不可改变迭代器指向的元素的值。

对于const类型的容器，只能使用const_iterator的迭代器。

迭代器的操作类型

可以按照迭代器的操作类型将迭代器分成5类，这5类迭代器形成一种操作层次：除输出迭代器外（输出迭代器可以看做输入迭代器在功能上的补集——输出迭代器只写而不读元素），高层次的迭代器支持低层次的迭器所支持的所有操作。它们所支持的操作范围可以用下列的不等式表示：

1. 随机访问迭代器 > 双向迭代器 > 前向迭代器 > (输入迭代器（读元素），输出迭代器（写元素）)
2. 读写元素 = 输入迭代器（读元素）+ 输出迭代器（写元素）

随机访问迭代器支持的算术运算如下表所示。

迭代器范围

一个迭代器范围由一对迭代器表示，这个两个迭代器分别指向同一个容器中的元素，或是同一个容器中的尾后位置。这两个迭代器分别用begin和end表示（或是用first和last表示），他们标记了一个容器中的一个元素范围。

通常end或last不会指向容器中的一个元素，而是指向容器中的尾后位置，这样的元素范围被称为左闭合区间，其数学描述为：[begin,end),表示范围自begin起，至end前结束，begin和end可以指向相同的位置，但是不能指向容器首元素之前的位置。

使用左闭合区间的编程假定

标准库使用左闭合区间表示元素范围是因为左闭合区间有下面三种方便的性质，假定begin和end表示一个合法的迭代器范围，则有：

1. 范围为空当且仅当begin == end；
2. 若begin != end，则范围内至少存在一个元素；
3. 可以通过递增begin使begin == end。

顺序容器

顺序容器的特点是元素在容器中的相对位置和元素加入容器时的先后顺序有关，元素之间的逻辑结构是线型的。

关联容器的特点是元素在容器中的相对位置和与每个元素绑定的关键字有关，元素之间的逻辑结构是非线型的，如树型结构、表型结构或者其他非线型结构。

顺序容器概述

顺序容器的类型和特点

C++标准库提供了如下的顺序容器。

顺序容器在以下两个方面有不同程度的性能折中：

1. 向容器中添加和删除元素的开销；
2. 非顺序访问元素的开销。

确定使用哪种顺序容器

如无必要，使用vector容器,除非你有充分的理由选择其他容器。

在以下情况时可以考虑使用别的容器：

1. 如果程序要求在容器中间添加、删除元素，使用list或者更forward_list；
2. 如果要求程序在头尾添加、删除元素，但是不会在中间添加、删除元素，使用deque。

顺序容器的操作

顺序容器的定义和初始化

除所有容器都支持的容器的定义和初始化操作外，仅有顺序容器（除array外）还支持接受一个大小参数的构造函数，如下表所示。

向顺序容器添加元素

下表是

初始化和插入操作的关键概念

1. 被插入容器中的元素是传递给容器的元素的拷贝，而不是传递给容器的元素本身，在初始化操作或者插入操作完成后，容器中的元素对象和提供值的元素之间就没有关系了，对容器中的元素对象的操作不会对提供值的元素对象产生影响，反之亦然。
2. 在插入操作中，insert、push操作和emplace操作由效率上的区别。如果传递给容器的参数是容器元素的一个左值，则insert和push操作会调用容器元素的拷贝构造函数，将传给容器的对象拷贝给容器元素的对象来完成插入操作；如果传递给容器的参数是容器元素的一个右值，则可能会调用容器元素对象的移动构造函数（具体情况视编译器的实现而定），而emplace操作会直接调用与传入容器的对象相匹配的构造函数来在容器的内存空间中就地构造元素对象，没有了拷贝操作。
3. 在使用insert进行插入的操作中，迭代器可以是反向迭代器，这样最新被插入的元素是序列中的第一个元素。

访问操作

下表定义了顺序容器对容器中成员的访问操作

删除元素的操作

下表定义了顺序容器删除元素的操作

注意：删除元素的成员函数不检查其参数，在删除元素前需要保证被删除的元素是存在的。

特殊的forward_list的操作

在单向链表中删除或者插入一个元素，被删除或者插入元素的前驱节点的链接会发生变化，但是单链表只能单向访问元素，无法从被删除的元素访问到其前驱节点，因此，对于forward_list容器，删除或者插入元素是通过改变待删除或是插入元素的前驱节点实现的。

单链表forward_list定义了一个首前迭代器before_begin()，允许我们删除首元素或是在首元素之前插入元素。

下表是forward_list支持的删除或是插入元素的操作

注意：上述的和迭代器p相关的操作，都需要程序员保证迭代器有效，否则函数行为未定义。

改变容器的大小

顺序容器支持的容器大小操作如下表所示。

vector对象的空间增长策略

对于string和vector容器，因为容器要保证逻辑上相邻的元素在内存中也相邻，所以，当容器中没有空间能再容纳新元素时，向容器中插入新元素，将导致容器重新申请内存空间。为了保证效率，标准库实现时，申请新的内存空间后的总容量将比实际需要的容量要大。容器会将旧元素全部拷贝到新的内存空间中去，再在新的内存空间中插入新元素。

管理容量的成员函数

下表是顺序容器用来管理容器容量的成员函数。

注意：vector和string的内存增长策略随着实现的不同而不同，通常的做法是：在需要重新分配内存空间时将当前的内存空间的容量翻倍。所有的内存空间分配策略遵循着一个原则：使用push_back向容器中添加元素时有高效率，在一个初始为空的vector上调用n此push_back来创建一个n个元素的容器时，所花费的时间不能超过n的常数倍。

容器操作可能使迭代器失效

向容器中插入或删除元素可能会导致指向容器元素的迭代器、指针或引用失效，使用失效的指针、引用或是迭代器会引发严重的程序错误。
容器中插入或删除元素后指向容器的迭代器、指针和引用的情况如下表。

注意:每次删除或插入元素后都要重新计算end()返回的迭代器，不要使用end()迭代器的保存值。

额外的string操作

除了顺序容器的公共操作外，string还定义了一些额外操作，这些操作要么提供了string类和C风格字符数组之间的相互转换，要么增加了使用下标替代迭代器的版本。

构造string的其他方法

下表是除公共操作外的构造string的其他方法。

substr操作

下表是string类型的substr操作。

关联容器

泛型算法

热门相关：我和超级大佬隐婚了   黑暗血时代   总裁大人，又又又吻我了   花都保镖   唐朝小官人