C++ STL学习
目录
容器库概览
对可以保存在容器中的元素的限制
容器需要支持拷贝操作，因此，保存在容器中的元素要能够支持拷贝操作。可以为不支持特定操作需求的元素类型定义容器，但是这样就只能使用容器那些不要求容器元素有特定操作的操作类型。
一般来说，每种容器都定义在一个与容器名相同的头文件中，对大多数容器，但不是所有容器，需要提供元素类型来生成特定的容器。
特别的，容器的元素的类型可以是另一种容器，只要在外层容器的中指定内层容器的类型即可。在老版本的编译器中，这种以其他容器为元素的容器，在声明或者定义时，需要在内层容器的和外层容器的之间插入空格，如vector v1，新版本的编译器则无此要求。
容器支持的操作
容器类型支持的操作可以根据容器的大类分成一定的层次：
- 顺序容器和关联容器都支持的操作；
- 仅部分顺序容器支持的操作；
- 仅部分关联容器支持的操作；
- 少数特殊的容器，如array、forward_list或者无序容器支持的操作。
所有容器都支持的操作或容器成员
下表是所有容器都支持的操作。
支持操作或成员说明类型别名iterator此容器类型的迭代器const_iteratorconst类型的iteratordifference_type有符号整型，足够表示此种容器的两个迭代器之间的距离value_type此容器的元素的类型size_type无符号整型，足够表示此种容器可能的最大容器大小reference元素的左值类型，等价于value_type &const_referenceconst版本的reference，等价于const value_type &构造函数C c默认构造函数，构造空容器C c1(c2)使用c2拷贝构造c1，c2和c1的容器类型和元素类型必须一样C c1 = c2使用c2拷贝构造c1，c2和c1的容器类型和元素类型必须一样C c(b, e)使用迭代器b和e的半开区间[b,e)拷贝构造c，不要求容器类型和元素类型一样，只要求[b, e)中的元素和c的元素类型相容C c{a, d, ...}列表初始化cC c = {a, b, ...}将c初始化为列表中元素的拷贝赋值和swapc1 = c2将c1种的元素替换为c2中的元素c1 = {a, b, ...}将c1中的元素替换为列表中的元素(《C++ Primer》中说array不支持此操作，其实使用g++测试发现array是支持此操作的)c1.swap(c2)交换c1和c2中的元素swap(c1, c2)等价于c1.swap(c2)添加、删除元素（array不支持，在不同的容器中，接口可能不同）c.insert(args)将args中的元素拷贝进cc.empalce(inits)使用inits在c中原地构造一个c的元素c.erease(args)将args指定的元素从c中删除c.clear()删除c中的所有元素，返回void比较操作==, !=相等（不相等）的关系运算符（无序关联容器不支持）小于、不大于、不小于、大于的关系运算符获取迭代器c.begin(), c.end()指向c的首元素和尾元素后一位置的迭代器c.cbegin(), c.cend()指向c的首元素和尾元素后一位置的const类型的迭代器反向容器的额外成员（forward_list不支持）reverse_iterator按逆序寻址元素的迭代器const_reverse_iteratorconst版本的reverse_ietatorc.rbegin()、c.rend()指向c的首元素之前位置和尾元素的迭代器c.crbegin()、c.crend()const版本的c.rbegin()、c.rend()迭代器
称某种数据类型是迭代器，当且仅当此类型支持一套操作，此套操作可以访问元素或者从某个元素移动到另一个元素。
迭代器有着相同的接口：如果某个迭代器可以提供某种操作，那么所有提供相同操作的迭代器在实现上都是相同的。
迭代器的公共操作
下表是所有的迭代支持都的操作。
操作说明iter1 == iter2当iter1和iter2指向同一个容器中的同一个元素或尾后迭代器时成立iter1 != iter2等价于!(iter1 == iter2)迭代器的类型
迭代器的const属性
所有的拥有迭代器的标准库类型使用两个关键字来表示迭代器类型：
- iterator表示通过此类迭代器可以对迭代器指向的元素进行读写；
- const_iterator表示通过此类型只能迭代器指向的元素进行读操作，不可改变迭代器指向的元素的值。
对于const类型的容器，只能使用const_iterator的迭代器。
迭代器的操作类型
可以按照迭代器的操作类型将迭代器分成5类，这5类迭代器形成一种操作层次：除输出迭代器外（输出迭代器可以看做输入迭代器在功能上的补集——输出迭代器只写而不读元素），高层次的迭代器支持低层次的迭器所支持的所有操作。它们所支持的操作范围可以用下列的不等式表示：
- 随机访问迭代器 > 双向迭代器 > 前向迭代器 > (输入迭代器（读元素），输出迭代器（写元素）)
- 读写元素 = 输入迭代器（读元素）+ 输出迭代器（写元素）
迭代器类型支持的操作输入迭代器除支持的公共操作外，支持前置的和后置的++，它使输入迭代器指向容器中的下一个元素位置。支持*解引用运算符，它只会出现在=右侧，用于读取元素。支持->箭头运算符，等价于(*it).mem，它解引用迭代器，并提取被指向对象的成员。输入迭代器只能顺序读取容器中的元素，递增迭代器可能使所有指向流的迭代器失效输出迭代器除支持的公共操作外，支持前置的和后置的++，它使输入迭代器指向容器中的下一个元素位置。支持*解引用运算符，它只会出现在=左侧，用于写元素。只能向一个输出迭代器赋值一次前向迭代器支持输入迭代器和输出迭代器的所有操作。只能在序列中沿着一个方向移动。可以多次读写同一个元素双向迭代器除支持前向迭代器的所有操作外，还支持前置的和后置的--运算符。可前向、后向移动，读写序列中的元素随机访问迭代器除支持双向迭代器的所有操作，还支持迭代器的算术运算。提供在常量时间内访问序列中任意元素的能力随机访问迭代器支持的算术运算如下表所示。
算术运算类型含义iter + n迭代器加上一个整型数，结果仍然是一个迭代器，指示的位置比iter指示的位置前进了n个单位，结果或是指向一个元素，或者一个尾后迭代器iter - n迭代器减去一个整型数，结果仍然是一个迭代器，指示的位置比iter指示的位置后退了n个单位，结果或是指向一个元素，或者一个尾后迭代器iter += n迭代器加法的复合赋值语句，将iter的值加上n后再赋值给iteriter -= n迭代器减法的复合赋值语句，将iter的值减去n后再赋值给iteriter1 - iter2迭代器相减的结果是它们之间的距离，表示ite2r向前移动差值个单位后将得到iter1。参与运算的两个迭代器必须是指向同一个容器的迭代器，或是同一个容器的尾后迭代器>, >=, c.size()，则多余的元素的值会被初始化为值t；若n < c.size()，则多余的元素会被舍弃vector对象的空间增长策略
对于string和vector容器，因为容器要保证逻辑上相邻的元素在内存中也相邻，所以，当容器中没有空间能再容纳新元素时，向容器中插入新元素，将导致容器重新申请内存空间。为了保证效率，标准库实现时，申请新的内存空间后的总容量将比实际需要的容量要大。容器会将旧元素全部拷贝到新的内存空间中去，再在新的内存空间中插入新元素。
管理容量的成员函数
下表是顺序容器用来管理容器容量的成员函数。
操作含义shrink_to_fit只适用于vector、deque和string容器，capacity和reserve只适用于vector和stringc.shink_to_fit将容器c的容量缩小到与c.size()相同大小，并不保证可以回退多余的空间，具体的实现可以忽略此请求c.capacity()不重新分配内存空间的情况下当前容器c可以保存的元素的最大数量c.reserve(n)使容器c分配至少能容纳n个元素的内存空间，只有当n > c.size()时才会重新分配内存空间注意：vector和string的内存增长策略随着实现的不同而不同，通常的做法是：在需要重新分配内存空间时将当前的内存空间的容量翻倍。所有的内存空间分配策略遵循着一个原则：使用push_back向容器中添加元素时有高效率，在一个初始为空的vector上调用n此push_back来创建一个n个元素的容器时，所花费的时间不能超过n的常数倍。
容器操作可能使迭代器失效
向容器中插入或删除元素可能会导致指向容器元素的迭代器、指针或引用失效，使用失效的指针、引用或是迭代器会引发严重的程序错误。
容器中插入或删除元素后指向容器的迭代器、指针和引用的情况如下表。
容器类型插入元素删除元素vector和string若重新分配内存空间，迭代器、指针和引用都会失效；未重新分配内存空间，指向插入元素位置之前的迭代器、引用和指针仍然有效，插入位置之后迭代器、指针和引用会失效指向被删除元素之后的迭代器、指针和引用会失效list和forward_list全部有效全部有效deque在除首尾位置外的其他位置插入元素会导致迭代器、指针和引用失效；在首元素位置插入元素将会导致迭代器失效，但是指针和引用仍然有效删除首元素，全部有效；删除尾元素，尾后迭代器失效；在首尾位置外的其他位置删除元素，会导致全部失效注意:每次删除或插入元素后都要重新计算end()返回的迭代器，不要使用end()迭代器的保存值。
额外的string操作
除了顺序容器的公共操作外，string还定义了一些额外操作，这些操作要么提供了string类和C风格字符数组之间的相互转换，要么增加了使用下标替代迭代器的版本。
构造string的其他方法
下表是除公共操作外的构造string的其他方法。
操作含义n、len、pos都是无符号整型值string s(cp, n)使用cp指向的数组的前n个字符拷贝初始化s，cp指向的数组应该至少包含n个字符string s(s2, pos)s是string类型的s2的从下标pos开始的字符的拷贝，若pos > s2.size()，函数行为未定义string s(s2, pos, len)s是string类型的s2的从下标pos开始的len个字符的拷贝，若pos > s2.size()，函数行为未定义，无论len是多大，拷贝构造函数之多拷贝s2.size() - pos个字符substr操作
下表是string类型的substr操作。
操作含义s.substr(pos)返回一个string，内容是s的从下标pos开始直到最后一个字符的strings.substr(pos, n)返回一个string，内容是从s的下标pos开始的n个字符，若n > s.size() - pos，则至多拷贝s.size() - n个字符关联容器
泛型算法
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
