网站进入百度沙盒,百度免费网站申请注册,邯郸专业网站建设报价,百度网址导航主页C学习-入门到精通【13】标准库的容器和迭代器 目录 C学习-入门到精通【13】标准库的容器和迭代器一、标准模板库简介1.容器简介2.STL容器总览3.近容器4.STL容器的通用函数5.首类容器的通用typedef6.对容器元素的要求 二、迭代器简介1.使用istream_iterator输入#xff0c;使用…C学习-入门到精通【13】标准库的容器和迭代器 目录 C学习-入门到精通【13】标准库的容器和迭代器一、标准模板库简介1.容器简介2.STL容器总览3.近容器4.STL容器的通用函数5.首类容器的通用typedef6.对容器元素的要求 二、迭代器简介1.使用istream_iterator输入使用ostream_iterator输出2.迭代器类型和迭代器类型的层次3.容器对迭代器的支持4.预定义的迭代器typedef5.迭代器的操作 三、算法简介四、序列容器1.vectorvector的元素操作函数 2.list1.list的成员函数 3.deque 五、关联容器1.multiset2.set3.multimap4.map 六、容器适配器1.stack2.queue3.priority_queue 七、bitset类八、总结 一、标准模板库简介
STL(Standard Template Library)定义了强大的、基于模板的、可复用的组件实现了许多通用的数据结构及处理这些数据结构的算法。
容器、迭代器和算法
本章中将介绍STL并且将讨论它的三个关键组件——容器container流行的模板数据结构、迭代器iterator和算法algorithm。STL容器是能存放几乎所有类型的数据的数据结构。
各容器中共同的成员函数
每个STL容器都有相关的成员函数这些成员函数的一个子集在所有的STL容器中都有定义。
迭代器
STL迭代器和指针有着类似的属性它们用于操作STL容器中的元素。事实上标准的数组中的指针也可以作为STL容器来使用只要把标准的指针当作迭代器。
算法
STL算法是执行这些通用数据操作的函数模板例如搜索、排序和比较元素等等。它们中的大部分使用迭代器来访问容器中的元素。每个算法对于和它一起使用的迭代器类型都有一些最小的要求所以一个容器所支持的迭代器类型决定了这个容器是否可以用于一个特定的算法。
迭代器封装了访问容器元素的机制这种封装使得许多STL算法能够应用于多种容器而无须注意容器的底层实现细节。
自定义模板化数据结构
除了使用标准库提供的模板我们还可以建立我们自己的自定义模板化数据结构包括链表、队列、堆栈和树。在这些模板的实现中我们会大量使用指针基于指针的代码是复杂的且编译器并不会对指针使用出现的错误进行提示。
所以在我们自定义的模板化数据结构中我们也可以复用STL容器、迭代器及算法来实现一般的数据表示和操作。
1.容器简介
STL的容器可以分为4种类型序列容器sequence container、有序关联容器ordered associative container、无序关联容器unordered associative container和容器适配器container adapter。
标准库容器类描述序列容器array固定大小直接访问任意元素deque从前部或后部进行快速插入和删除操作直接访问任意元素forward_list单链表在任意位置快速插入或删除操作直接访问任意元素list双向链表在任意位置进行快速插入和删除操作vector从后部进行快速插入和删除操作直接访问任意元素有序关联容器set快速查找无重复元素multiset快速查找可有重复元素map一对一映射无重复元素基于键快速查找multimap一对一映射可胡重复元素基于键快速查找无序关联容器unordered_set快速查找无重复元素unordered_multiset快速查找可有重复元素unordered_map一对一映射无重复元素基于键快速查找unordered_multimap一对一映射可胡重复元素基于键快速查找容器适配器stack后进先出LIFOqueue先进先出FIFOpriority_queue优先级最高的元素先出
2.STL容器总览
序列容器描述了线性的数据结构例如数组、向量和链表。 关联容器描述非线性的容器它们通常可以快速锁定其中的元素。这种容器可以存储值的集合或者键-值对。C11中关联容器中的键是不可变的无法修改。
序列容器和关联容器一起被称为首类容器。
栈和队列都是在序列容器的基础上增加约束条件得到的因此STL把stack和queue作为容器适配器来实现这样就可以使程序以一种约束方式来处理线性容器。类型string支持的功能跟线性容器一样但是它只能用来存储字符数据。
3.近容器
除此之外有一些其他的容器种类被称为“近容器”C类型的基于指针的数组用于维护标志位的bitset以及用于进行高速向量运算的valarray。
这些类型被称为“近容器”是因为它们展现出的功能与首类容器类似但是不支持所有的首类容器的功能。
4.STL容器的通用函数
所有的STL容器提供了相近的功能。很多通用的的操作例如成员函数size可用于所有的容器。下图中显示了所有标准库容器中通用的函数。
注意priority_queue没有提供重载的运算符 、、、、和!无序关联容器没有提供重载运算符、、、 forward_list没有提供成员函数rbegin、rend、crbegin和crend。
我们在使用一个容器之前应该学习容器提供的功能。
STL容器的通用函数描述默认构造函数对容器进行默认初始化的构造函数。通常每种容器都有几种构造函数以提供不同的容器初始化方法拷贝构造函数将容器初始化为同类型已有容器的副本的构造函数转移构造函数C11中的新内容将一个已经存在容器中的元素转移到同类型的新容器中。转移构造函数避免了复制作为参数传入容器的每个元素的开销析构函数在容器不需要时执行处理工作empty容器中没有元素返回true否则返回falseinsert在容器中插入一个元素size返回当前容器中的元素个数copy operator 把一个容器赋值给另一个move operator 移动赋值运算符C11中的新内容将元素从一个容器移动到另一个容器避免了复制作为参数传入容器的每个元素的开销operator 若第一个容器小于第二个容器返回true否则返回falseoperator 若第一个容器小于或等于第二个容器返回true否则返回falseoperator 若第一个容器大于第二个容器返回true否则返回falseoperator 若第一个容器大于或等于第二个容器返回true否则返回falseoperator 若第一个容器等于第二个容器返回true否则返回falseoperator !若第一个容器不等于第二个容器返回true否则返回falseswap交换两个容器中的元素。在C11中有个新的非成员函数swap该函数使用移动操作而不是使用复制操作来交换它的两个参数中的元素值该函数只适用于首类容器max_size返回一个容器中能容纳的最大元素个数begin该函数有两个版本返回引用容器中第一个元素的iterator或const_iteratorend该函数有两个版本返回引用容器末端之后位置容器中最后一个元素后面的一个元素容器外部的iterator或const_iteratorcbegin(c11)返回引用容器第一个元素的const_iteratorcend(c11)返回引用容器末尾元素之后位置的const_iteratorrbegin该函数有两个版本返回引用容器末端位置的reverse_iterator或const_reverse_iteratorrend该函数有两个版本返回引用容器第一个元素之前位置的reverse_iterator或const_reverse_iteratorcrbegin(C11)返回引用容器末端位置的const_reverse_iteratorcrend(C11)返回引用容器第一个元素之前位置的const_reverse_iteratorerase删除容器中的一个或多个元素clear删除容器中所有元素
5.首类容器的通用typedef
下图中显示了首类容器中通用的typedef这些typedef在基于模板的变量、函数参数以及返回值的声明中使用。
typedef描述allocator_type用来分配容器内存的对象的类型不包含在类模板array中value_type容器中存储元素的类型reference对容器中存储的元素类型的引用const_reference对容器中存储元素类型的常量引用。这种引用只能用于读取容器中的元素及执行const操作pointer指向容器中存储元素类型的指针const_pointer指向容器中存储元素类型的常量指针这种指针只能用于读取容器中的元素及执行const操作iterator指向容器中元素类型的迭代器const_iterator指向容器中元素类型的常量迭代器只能用于读取元素及执行const操作reverse_iterator指向容器中存储元素类型的反向迭代器用于反向遍历容器const_reverse_iterator指向容器中存储元素类型的常量反向迭代器用于反向读取元素及执行const操作difference_type两个引用相同容器的迭代器之差的类型list和关联容器中没有定义size_type用于计算容器中的项目数及索引序列容器的类型list不能进行索引
6.对容器元素的要求
在使用STL容器之前首先要确定作为元素的类型可以支持的功能的最小集合。当把一个元素插入到容器中时便生成了这个元素的一个副本。因此该元素应该支持拷贝构造函数及赋值操作。
有序关联容器和很多算法要求元素可以相互比较因此这些容器中的元素类型应该提供运算符和运算符。
在C11中对象可以被移动到容器中作为元素所以对象类型需要实现转移构造函数和移动赋值运算符。关于移动的内容会在后续章节中介绍。
二、迭代器简介
迭代器有许多方面与指针类似它也是用于指向首类容器中的元素。它提供了一种访问容器中元素的方法而不需要了解容器内部的结构。
迭代器存有它们指向的特定容器的状态信息即迭代器对每种类型的容器都有一种实现。但有些迭代器的操作在容器间是统一。例如*运算符间接引用一个迭代器这样就可以使用它所指向的元素。运算符使得迭代器指向容器中的下一个元素和数组中指针递增后指向下一个元素类似。
STL首类容器中提供了begin和end函数函数begin返回一个指向容器中第一个元素的迭代器函数end返回一个指向容器中最后一个元素再后面一个元素的迭代器容器外常用于判断是否到达了容器的结束位置。
如果迭代器i指向一个特定元素那么i表示迭代器i指向下一个元素。*i指代的是i指向的元素。
从end函数中返回的迭代器只在相等或不等的比较中使用来判断迭代器i是否到达了容器的末端。
使用一个iterator对象来指向一个可以修改的容器元素使用一个const_iterator对象来指向一个不可修改的容器元素。
1.使用istream_iterator输入使用ostream_iterator输出
我们以序列也称排列的形式使用迭代器。这些序列可以在容器中也可以是输入序列或是输出序列。
下面程序中演示了使用istream_iterator从标准输入用于输入程序的数据序列输入使用ostream_iterator从标准输出用于输出程序的数据序列输出。
#include iostream
#include iterator
using namespace std;int main()
{cout Enter two integers: ;// 创建一个istream_iterator类型的迭代器从cin中读取int类型的数据istream_iteratorint inputInt(cin);int number1 *inputInt;inputInt;int number2 *inputInt;ostream_iteratorint outputInt(cout);cout The sum is: ;*outputInt number1 number2;cout endl;
}运行结果 在这个程序中我们使用了istream_iterator对象来从标准输入流cin中接收输入的int数值这里需要注意标准输入流具有动态的、单向的特点数据只能读取一次所以如果在当前输入流中已经有数据的情况下初始化一个istream_iterator对象来接收数据它会直接读取流中的第一个数据并且保存一份该数据的副本到对象中的value_type类型的数据成员中。 这是指向输入流的迭代器与普通迭代器的本质区别指向普通容器的迭代器内部通常就是一个指向容器元素的指针复制迭代器只是复制指针不会复制元素。而由于输入流的特点指向输入流的迭代器必须将当前读取的值缓存起来。
输出流迭代器与指向普通容器的迭代器一样也不缓存值它只是将赋值操作转换成了输出操作。在上面的程序中就是将*outputInt number1 number2;这个赋值操作等效成了cout number1 number2;。且这个迭代器的内容也不可以作为右值毕竟你不能从输出流中获取什么数据吧。同样的该迭代器的自增操作也是没有效果的。
2.迭代器类型和迭代器类型的层次
下图给出了STL中迭代器的类型每种类型都提供了一些特定的功能。
类型描述随机访问迭代器random access在双向迭代器基础上增加了直接访问容器中任意元素的功能即可以向前或向后跳转任意个元素双向迭代器bidirectional在前向迭代器基础上增加了向后移动的功能。支持多遍扫描算法前向迭代器forward综合输入和输出迭代器的功能并能保持它们在容器中的位置作为状态信息可以使用同一个迭代器两次遍历一个容器称为多遍扫描算法输出迭代器output用于将元素写入容器。输出迭代器每次只能向前移动一个元素。输出迭代器只支持一遍扫描算法不能使用相同的输出迭代器两次遍历一个序列容器输入迭代器input用于从容器中读取元素。输入迭代器每次只能向前移动一个元素。输入迭代器只支持一遍扫描算法不能使用相同的输入迭代器两次遍历一个序列容器
从上图我们可以看出这些迭代器是有层次划分的从层次的底部到顶部每种迭代器都支持其下层迭代器所具有的所有功能。下面是这些迭代器的层次图。注意这并非继承。 3.容器对迭代器的支持
每种容器所支持的迭代器类型决定了这种容器是否可以在指定的STL算法中使用。支持随机访问迭代器的容器可用于所有的STL算法除了那些需要改变容器大小的算法这样的算法无法在数组和array对象中使用。指向数组的指针可以代替迭代器用于几乎所有的STL算法中包括那些要求随机访问迭代器的算法。下图展示了每种STL容器所支持的迭代器类型。
容器支持的迭代器类型序列容器首类容器vector随机访问迭代器array随机访问迭代器deque随机访问迭代器list双向迭代器forward_list前向迭代器有序的关联容器首类容器set双向迭代器multiset双向迭代器map双向迭代器multimap双向迭代器无序的关联容器首类容器unordered_set双向迭代器unordered_multiset双向迭代器unordered_map双向迭代器unordered_multimap双向迭代器容器适配器stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器 4.预定义的迭代器typedef
下图中展示了STL容器的类定义中出现的几种预定义的迭代器typedef。并不是每一种typedef都出现在每个容器中。我们使用常量版本的迭代器来访问只读容器或是不应被修改的非只读容器使用反向迭代器来以相反的方向访问容器。
为迭代器类预先定义的typedef的方向读写能力iterator向前读/写const_iterator向前读reverse_iterator向后读/写const_reverse_iterator向后读
5.迭代器的操作
下图展示了每种迭代器上的操作除了给出的对于所有迭代器都有的运算符迭代器还必须提供默认构造函数、拷贝构造函数和拷贝赋值操作符。
前向迭代器支持和所有的输入和输出迭代器的功能。 双向迭代器支持--操作和所有前向迭代器的功能。 随机访问迭代器支持所有在表中给出的操作。
迭代器操作描述适用所有迭代器的操作p前置自增迭代器p后置自增迭代器p p1将一个迭代器赋值给另一个迭代器输入迭代器*p间接引用一个迭代器p-m使用迭代器读取元素mp p1比较两个迭代器是否相等p ! p1比较两个迭代器是否不相等**输出迭代器*p间接引用一个迭代器p p1把一个迭代器赋值给另一个前向迭代器前向迭代器提供了输入和输出迭代器所有的功能双向迭代器--p前置自减迭代器p--后置自减迭代器随机访问迭代器p i迭代器 p 前进 i 个位置p - i迭代器 p 后退 i 个位置p i 或 i p在迭代器 p 的位置上前进 i 个位置p - i在迭代器 p 的位置上后退 i 个位置p - p1表达式的值是一个整数代表同一个容器中两个元素之间的距离与指针 - 指针类似p[i]返回与迭代器p的位置相距 i 的元素等价于 *(p i)p p1若迭代器 p 小于 p1即容器中 p 在 p1 之前则返回true否则返回falsep p1若迭代器 p 小于或等于 p1即容器中 p 在 p1 前或两者位置相同则返回true否则返回falsep p1若迭代器 p 大于 p1即容器中 p 在 p1 之后则返回true否则返回falsep p1若迭代器 p 大于或等于 p1即容器中 p 在 p1 后或两者位置相同则返回true否则返回false
三、算法简介
STL提供了可以用于多种容器的算法其中很多算法都是常用的。插入、删除、搜索、排序及其他一些对部分或全部序列容器和关联适用的算法。
四、序列容器
C标准模板库中提供了五种序列容器array、vector、deque、list和forward_list。序列容器中的元素都是按照插入的顺序进行排序的。
其中array、vector和deque的类模板都是基于数组的 list和forward_list的类模板实现了一个链表数据结构。
提示
在vector的尾部进行插入操作是高效的。vector只是简单地变长来适应新加入的元素。但是在vector的中间插入或删除元素是低效的即在插入和删除的位置之后的整个部分都需要移动因为vector的元素在内存中占用的是连续空间和C/C的原生数组一样。需要经常在容器两端进行插入和删除操作的应用程序通常使用deque而不是vector。尽管可以在vector和deque的前后两端插入和删除元素但是deque类在前端进行插入删除操作时比vector效率更高。需要经常在容器的中部或者两端进行插入删除操作的应用程序通常使用list因为它可以高效地在数据结构的任意位置执行插入和删除操作
1.vector
vector类模板提供一种占用连续内存空间的数据结构。这使得它可以高效、直接地通过下标运算符[]访问vector的任一元素具有随机存取性。它与array类模板类似通常在容器中的数据数量不确定时使用vector类模板。当一个vector的内存空间耗尽时它会分配一个更大的连续空间把原先位置的数据复制或移动过来再把原空间释放。
vector支持随机访问迭代器。
使用vector和迭代器
下面的程序中说明了类模板vector的几个函数这些函数的大部分都存在于首类容器中。使用类模板vectro必须包含头文件vector。
#include iostream
#include vector
using namespace std;// 创建一个函数模板
template typename T void printVector(const vector T integers2);int main()
{const size_t SIZE 6;int values[SIZE] { 1, 2, 3, 4, 5, 6 };vector int integers;cout The initial size of integers is integers.size() \nThe initial capacity of integers is integers.capacity();// 往容器中添加一个元素vector、deque和list都适用integers.push_back(2);integers.push_back(3);integers.push_back(4);cout \nThe size of integers is integers.size() \nThe capacity of integers is integers.capacity();cout \n\nOutput build-in array using pointer notation: ;// 使用begin和end函数获取内置数组的开始和结束元素后一个元素的位置的指针// 标准库对于数组提供了特化begin和end函数获得的是指针并非迭代器for (const int* ptr begin(values); ptr ! end(values); ptr){cout *ptr ;}cout \nOutput vector using iterator notation: ;printVector(integers);cout \nReversed contents of vector integers: ;for (auto reverseIterator integers.crbegin();reverseIterator ! integers.crend(); reverseIterator){cout *reverseIterator ;}cout endl;
}template typename T
void printVector(const vector T integers2)
{for (auto constIterator integers2.cbegin();constIterator ! integers2.cend(); constIterator){cout *constIterator ;}
}运行结果 现在来对上面的代码进行分析 首先声明了一个函数模板用于输出不同元素类型的vector对象。 声明了一个大小为6的内置数组values声明了一个元素类型为int的vector对象integers
调用vector类模板中定义的成员函数size和capacity用于输出容器当前元素的个数以及当前容量。其中size函数除了forward_list不可用之外其他容器都可以使用。而capacity只对vector和deque有效。
随后调用成员函数push_back除了array和forward_list的其他序列容器均可用往容器中末端插入元素。如果在一个已满的vector中插入元素这个vector就会增加它的容量某些STL实现使得它的容量加倍。除了array和vector之外的序列容器还提供push_front函数。vector虽然也可以在容器起始位置进行插入但是在插入之后需要将所有其他元素往后移动一位开销较在末端插入更大所以不提供在头部插入的函数如果要在容器头部进行频繁的数据插入删除应该使用其他容器而非vector。
当vector需要更多空间时在原大小上加倍可能会比较浪费。例如一个已满的有1000000个元素的vector在插入一个元素后大小调整为2000000其中999999个元素的位置是未使用的。程序员可以使用resize函数来更好地控制空间的使用。 在修改vector之后再次使用size和capacity函数来显示vector对象当前的元素个数以及容量。我们可以对上述代码进行些许修改 integers.push_back(2);cout \nThe size of integers is integers.size() \nThe capacity of integers is integers.capacity();integers.push_back(3);cout \nThe size of integers is integers.size() \nThe capacity of integers is integers.capacity();integers.push_back(4);cout \nThe size of integers is integers.size() \nThe capacity of integers is integers.capacity();运行结果 从结果上来看当前程序使用vector类模板中是一个元素一个元素的增加容量。
vector的增长
vector在调整大小以容纳更多元素较为耗时的操作时所采用的方式在C标准文档中并没有指定。不同库的实现方法可能不相同依赖于编译器使用的vector版本。一些库实现者最初就分配一个较大的空间如果vector只存储少量的元素那么这样的大容量就会浪费不少空间但是如果某个程序在vector中添加很多元素时它又可以不那么频繁的重新分配空间减少了分配空间带来的额外开销提高的效率。
在往vector对象中插入元素之后又使用指针和指针算法来输出一个数组的内容。在这里使用了begin和end来获取数组的起始指针和末尾元素后一个元素的位置指针。注意这两个函数对内置数组进行了特化返回的并不是迭代器。
最后调用函数通过迭代器来输出一个vector对象的内容。crbegin即const_reverse_iterator它返回的是一个反向的常量迭代器。
C11shrink_to_fit 在C11中可以使用函数shrink_to_fit让vector或deque容器将额外的内存返回给系统。
vector的元素操作函数
#include iostream
#include array
#include vector
#include iterator
#include stdexcept
#include algorithm
using namespace std;int main()
{const size_t SIZE 6;arrayint, SIZEvalues { 1, 2, 3, 4, 5, 6 };vectorintintegers(values.cbegin(), values.cend()); // 使用重载的构造函数来初始化一个vector对象// 声明一个输出流迭代器ostream_iteratorint output(cout, ); // 以一个空格符作为两个输出之间的间隔cout Vector integers contains: ;copy(integers.cbegin(), integers.cend(), output);cout \nFirst element of integers: integers.front() \nLast element of integers: integers.back();integers[0] 7; // 将容器中第一个元素赋值为7integers.at(2) 10; // 将下标为2的元素赋值为10integers.insert(integers.cbegin() 1, 22); // 在第二个元素的前面插入一个元素22cout \n\nContents of vector integers after changes: ;copy(integers.cbegin(), integers.cend(), output);// 试图访问一个容器外的元素try{integers.at(17) 777;}catch(out_of_range ex){cerr \n\nException: ex.what() endl;}// 擦除第一个元素integers.erase(integers.cbegin());cout \n\nVector integers after erasing first element: ;copy(integers.cbegin(), integers.cend(), output);// 擦除剩余元素integers.erase(integers.cbegin(), integers.cend());cout \n\nAfter erasing all elements, vector integers (integers.empty() ? is : is not) empty.;// 将array对象中的元素插入到vector对象中integers.insert(integers.cbegin(), values.cbegin(), values.cend());cout \n\nContents of vector integers before clear: ;copy(integers.cbegin(), integers.cend(), output);// 清空vector对象clear函数会调用erase函数来清空容器integers.clear();cout \nAfter clear, vector integers: (integers.empty() ? is : is not) empty endl;
}运行结果 上面代码中声明了一个istream_iterator的对象来用于实现一个类型安全的输出机制它只输出int类型或者相容类型的值。这个与我们之前使用过的有点不一样这里使用的该对象的构造函数有两个参数第一个依旧表示输出流第二个参数是一个字符串指定了输出值之间的分隔符之前声明的对象其实分隔符也是一个空格空格就是默认实参。
copy算法
上面代码中还使用标准库中的算法copy在头文件algorithm中定义把vector容器中的全部内容复制到目标域此处为由output指向的输出流。
算法copy复制了容器中第一个迭代器参数指定的元素一直到但不包括第二个迭代器参数指定的元素之间的所有元素。这两个迭代器必须符合输入迭代器的要求必须要能通过它们从容器中读取数据。并且这两个迭代器应该指定同一片区域同一个容器中。这些元素被复制到输出迭代器通过这个迭代器可以存储或输出一个值指定的位置它是copy算法的第三个参数。
vector的成员函数front和back
front和back这两个函数大部分序列函数都有它们的定义分别确定vector中的第一个和最后一个元素。注意函数front和begin之间的区别其中函数front返回vector中第一个元素的引用而函数begin返回一个指向vector中第一个元素的随机访问迭代器。函数back和end也是类似的。back返回的一个元素的引用end返回的是一个迭代器。
vector必须是非空的否则front和back的结果是未定义的。
访问vector元素
我们可以使用重载的下标运算符[]返回指定位置元素的一个引用或常量值的引用这取决于容器是否为常量。 也可以使用成员函数at执行相同的操作不过成员函数版本有边界检查。函数at首先检查参数提供的值是否在vector的范围内若不是at会抛出out_of_range类型的异常。
下面是一些STL异常类型
STL异常类型描述out_of_range表示下标超出范围invalid_argument表示传递给函数的参数无效length_error表示试图创建过长的容器、字符串等bad_alloc表示试图使用new或分配器分配内存时因可用的内存不够而导致操作失败
vector的insert成员函数
大多数序列容器除了固定大小的array和用insert_list替代insert的forward_list都有多个重载的insert成员函数。该函数的第一个参数指向元素插入位置的前面。且有多个重载版本上面的程序中使用了两个不同的版本第一种是有两个参数第二个参数是要插入的元素第二种有三个参数后两个参数表示另一个容器中的一组值。 vector的成员函数erase
成员函数erase可以用于所有的首类容器除了固定大小的array和用erase_after代替的forward_list。 注意在删除范围内的元素时第二个迭代器指向的元素不会被删除。
通常情况下erase将会删除容器中的指定对象但是当要删除的元素中含有指向动态分配的对象的指针时并不会删除这个对象。因为这样会造成内存泄漏。如果元素是unique_ptr则这个unique_ptr会被删除其指向的动态分配的内存也会被删除。如果元素是shared_ptr则对应的动态分配的对象引用数减1直到引用数为0时动态分配的内存才会被删除。
vector的成员函数clear
在程序的最后调用成员函数clear来清空vector。这个函数会调用erase函数来清空vector所以并不会将vector所占的内存返回给系统vector是动态分配内存的容器。
所以我们在对上面的代码进行修改在每次调用erase函数之后显示当前容器的元素个数与容量。 2.list
序列容器list可以在容器的任意位置进行插入和删除操作。如果大部分插入和删除操作发生在容器的两端那么就应该使用deque来替换。
list类模板实现了一个双向链表list容器中的每个节点都有指向前一个元素和后一个元素的指针。这使得list类模板支持双向迭代器允许容器顺序或逆序遍历。所以任何要求输入、输出、前向和双向迭代器的算法均可以使用该类模板的对象。
C11容器forword_list C11新增序列容器forward_list通过单链表实现即每个节点中只含有指向下一个节点元素的指针。这使得该类模板支持前向迭代器允许顺序遍历。任何要求输入、输出和前向迭代器的算法均可以使用该类模板的对象。
1.list的成员函数
除了之前介绍的STL容器的通用成员函数和序列容器中的通用成员函数list类模板还提供了9个特别的成员函数 splice push_front pop_frontlist类、forward_list类和deque类特有的函数。 remove remove_if unique merger reverse sort
其中forward_list和deque也支持push_front和pop_front它们也会操作容器起始位置的元素。
示例代码
#include iostream
#include array
#include list
#include iterator
#include algorithm
using namespace std;// 建立一个函数模板用于输出list容器的值
template class T void printList(const list T listRef);int main()
{const size_t SIZE 4;array int, SIZE ints { 2, 6, 4, 8 };list int values;list int otherValues;values.push_front(1);values.push_front(2);values.push_back(4);values.push_back(3);cout values contains: ;printList(values); // 输出list对象values中的值values.sort(); // 因为values中的值为int类型可以使用关系运算符进行比较cout \nvalues after sorting contains: ;printList(values);// 将一个容器中的元素插入到另一个容器中otherValues.insert(otherValues.cbegin(), ints.cbegin(), ints.cend());cout \nAfter insert, otherValues contains: ;printList(otherValues);// 将otherValues对象中的元素全部移动到values对象的尾部values.splice(values.cend(), otherValues);cout \nAfter splice, values contains: ;printList(values);cout \nAfter splice, otherValues contains: ;printList(otherValues);// 对values对象进行排序values.sort();cout \nAfter sort, values contains: ;printList(values);// 将ints对象中的内容插入otherValues对象中otherValues.insert(otherValues.cbegin(), ints.cbegin(), ints.cend());cout \nAfter insert, otherValues contains: ;printList(otherValues);otherValues.sort();cout \nAfter sort, otherValues contains: ;printList(otherValues);// 合并两个已排序的list对象将参数合并到调用的对象中values.merge(otherValues);cout \nAfter merge: \n\tvalues contains: ;printList(values);cout \n\totherValues contains: ;printList(otherValues);// 移除values的第一个元素和最后一个元素values.pop_front();values.pop_back();cout \nAfter pop_front and pop_back: \n\tvalues contains: ;printList(values);// 调用unique函数移除容器中的重复元素values.unique();cout \nAfter unique, values contains: ;printList(values);// 调用swap函数交换values对象和otherValues对象中的元素values.swap(otherValues);cout \nAfter swap: \n\tvalues contains: ;printList(values);cout \n\totherValues contains: ;printList(otherValues);// 重写values中的元素values.assign(otherValues.cbegin(), otherValues.cend());cout \nAfter assign, values contains: ;printList(values);// 再次将两个对象合并values.merge(otherValues);cout \nAfter merge, values contains: ;printList(values);// 删除values中等于4的元素values.remove(4);cout \nAfter remove(4), values contains: ;printList(values);cout endl;
}template class T
void printList(const listT listRef)
{// 判断list容器是否为空if (listRef.empty()){cout List is empty.;}else{ostream_iteratorT output(cout, );copy(listRef.cbegin(), listRef.cend(), output);}
}运行结果 上面的代码还使用了list的成员函数swap和assgin
3.deque
deque类有vector和list的多种优点。deque是“double-ended queue”的缩写。deque类的实现提供了有效的索引访问下标访问可以读取或修改它的元素与vector类似。deque还提供了在它的首部和尾部进行高效插入和删除操作的功能这与list类似list不仅在首部和尾部有高效的插入删除操作在其中部也有。
deque类支持随机访问迭代器所以deque支持所有STL算法。deque最常用的功能是实现一个队列FIFO。
deque增加的空间可以按照内存块的形式分配在deque的两端这些内存块通常使用一个指向它们的指针数组来记录。由于deque中内存分布的不连续性deque的迭代器必须比那些vector或数组的迭代器更加智能。
提示
通常deque的开销比vector略高deque对在其中间插入、删除元素进行了优化以减少元素的复制所以在进行这类操作时比vector更高效但是还是不如list
#include iostream
#include deque
#include iterator
#include algorithm
using namespace std;int main()
{dequedouble values;ostream_iteratordouble output(cout, );values.push_front(2.2);values.push_front(3.5);values.push_back(1.1);cout values contains: ;for (size_t i 0; i values.size(); i){cout values[i] ;}values.pop_front();cout \nAfter pop_front, values contains: ;copy(values.cbegin(), values.cend(), output);values[1] 5.4;cout \nAfter values[1] 5.4, values contains: ;copy(values.cbegin(), values.cend(), output);cout endl;
}运行结果 deque类提供了和vector相同的基本操作但如list一样增加了成员函数push_front和pop_front分别在deque的首部插入和删除元素。
五、关联容器
STL的关联容器可以通过关键字被称为搜索关键字来直接存取元素。有4种关联容器
multisetsetmultimapmap
每种关联容器都按已排序的方式保存着所有的关键字。 还有4种对应的无序关联容器分别是
unordered_multisetunordered_setunordered_multimapunordered_map
它们提供与有序关联容器相似的大部分功能。有序与无序关联容器的主要区别在于关键字的存储是否是按序的。
但是这里与序列容器的按照插入的次序进行排序不同关联容器中的排序是按照键的排序规则进行排序的。
multiset和set类提供了控制数值集合的操作其中元素的值就是关键字。multiset和set最大的区别就是multiset中允许出现重复的关键字而set中不允许。
multimap和map类提供了处理与关键字相关联的值的功能。multimap与map的主要区别在于multimap允许存在与数值相关的重复关键字而map只允许存放与数值有关的唯一关键字。
除了一般容器的成员函数之外所有的关联容器还提供一些其他的成员函数包括find、lower_bound、upper_bound和count。
1.multiset
有序关联容器multiset可以快速存取关键字并允许出现重复的关键字。元素的顺序的是由一个比较函数对象决定的。例如在一个整数multiset中使用比较函数对象lessint来排列关键字可以使元素按照递增的顺序排列。
所有关联容器中关键字的数据类型必须支持比较函数对象中指定的比较操作使用lessT的关键字就必须支持运算符。若在关联容器中使用的是自定义的数据类型那么这些类型必须提供相应的比较操作。
multiset支持双向迭代器。
示例代码
#include iostream
#include array
#include set
#include algorithm
#include iterator
using namespace std;int main()
{const size_t SIZE 10;array int, SIZE a { 7, 22, 9, 1, 18, 30, 100, 22, 85, 13 };multisetint, lessint intMultiset; // 创建一个multiset对象ostream_iteratorint output(cout, );// 输出容器中关键字为15的元素个数cout There are currently intMultiset.count(15) values of 15 in the multiset\n;// 往容器中插入两个关键字为15的元素intMultiset.insert(15);intMultiset.insert(15);cout After inserts, there are intMultiset.count(15) values of 15 in the multiset\n\n;// 在容器中查找关键字为15的元素并返回一个指向它的迭代器auto result intMultiset.find(15);if (result ! intMultiset.end()){cout Found value 15\n;}result intMultiset.find(20);if (result intMultiset.end()){cout Did not found value 20\n;}// 将array对象中的元素插入到intMultiset对象中intMultiset.insert(a.cbegin(), a.cend());cout \nAfter insert, intMultiset contains:\n;copy(intMultiset.cbegin(), intMultiset.cend(), output);// 显示第一个不小于22的元素cout \n\nLower bound of 22: *(intMultiset.lower_bound(22));// 显示第一个超过22的元素cout \nUpper bound of 22: *(intMultiset.upper_bound(22));// 返回一对迭代器auto p intMultiset.equal_range(22);cout \n\nequal_range of 22: \n\tLower bound: *(p.first) \n\tUpper bound: *(p.second);cout endl;
}运行结果 创建一个multiset 该类模板可以只指定容器中元素的类型该类的默认排序是按照lesskey也就是升序。
上面程序中调用了multiset的成员函数count、insert、find、lower_bound、upper_bound和equal_range。它们的函数原型如下 其中equal_range函数返回的是一个std::pair类型的对象该类原型如下
2.set
关联容器set用于快速存取和检索唯一的关键字。除了必须有唯一的关键字之外set和multiset的实现相同。如果试图往一个set容器中插入重复的关键字那么就会忽略重复的值。
set支持双向迭代器与multiset相同。
#include iostream
#include set
#include array
#include iterator
#include algorithm
using namespace std;int main()
{const size_t SIZE 5;arraydouble, SIZE a { 2.1, 4.2, 9.5, 2.1, 3.7 };setdouble, greaterdouble doubleSet(a.begin(), a.end()); // 降序ostream_iteratordouble output(cout, );cout doubleSet contains: ;copy(doubleSet.begin(), doubleSet.end(), output);// 往容器中插入元素13.8返回一对值第一个值为一个指向插入值的迭代器第二个值为一个bool值表明插入是否成功auto p doubleSet.insert(13.8);cout \n\n *(p.first) (p.second ? was: was not) inserted;cout \ndoubleSet contains: ;copy(doubleSet.cbegin(), doubleSet.cend(), output);p doubleSet.insert(9.5);cout \n\n *(p.first) (p.second ? was : was not) inserted;cout \ndoubleSet contains: ;copy(doubleSet.cbegin(), doubleSet.cend(), output);cout endl;
}运行结果 set类模板中的insert函数
3.multimap
关联容器multimap用于快速存取关键字和相关值通常称为关键字-值对。multimap和map的元素都是关键字-值对并不是单一的值。在往这两个容器中插入时使用的是一个包含了关键字和值的pair对象前面已经使用过了。相同的容器中元素的排序仍是由一个比较函数对象来决定。例如lessint用来比较关键字类型为int类型的对象。
在multimap中关键字是可以重复的所以多个值可以和同一个关键字对应。通常称这种关系为一对多关系。例如一个老师有多个学生一个学生可以学习多门课程。
multimap使用双向迭代器。 #include iostream
#include array
#include map
#include iterator
#include algorithm
using namespace std;int main()
{// 创建一个multimap对象multimapint, double, lessint pairs;cout There are currently pairs.count(15) pairs with key 15 in the multimap\n;// 往容器中插入两个pair对象// 使用utility头文件中的非成员函数来创建键值对pairs.insert(make_pair(15, 2.7));pairs.insert(make_pair(15, 99.3));cout After inserts, there are pairs.count(15) pairs with key 15 in the multimap\n;pairs.insert(make_pair(30, 111.11));pairs.insert(make_pair(10, 22.22));pairs.insert(make_pair(25, 33.333));pairs.insert(make_pair(20, 9.345));pairs.insert(make_pair(5, 77.54));cout \nMultimap pairs contains: \nKey\tValues\n;for (auto mapItem : pairs){cout mapItem.first \t mapItem.second \n;}cout endl;
}运行结果 multimap的成员函数insert 上面程序使用了成员函数insert来插入一个元素元素的类型为一个pair对象该对象使用头文件utility中的非成员函数make_pair来创建。 在C11中除了使用非成员函数来创建一个pair对象之外还可以使用列表的初始化方法来创建。例如pairs.insert({15, 2.7});与程序中使用的语句等价。 C11使用列表初始化关键字-值对
在创建一个multimap对象时也可以使用列表初始化器来对该对象进行初始化。例如 multimapint, double, lessint pairs { { 10, 22.222 }, { 20, 9.345 }, { 5, 77.54} };
4.map
关联容器map用于快速存取唯一的关键字和关联的值。在map中关键字是不能重复的所以一个关键字只能和一个值进行关联一对一映射。例如学号是一个唯一的用来描述学生的关键字。
使用map可以从一个指定的关键字快速得到相关的值。所以map通常又被称为关联数组。在map的下标运算符[]中使用关键字可以锁定与那个关键字相关的值。
在map的任意位置都可以进行插入和删除操作。
map支持双向迭代器。
示例代码
#include iostream
#include map
using namespace std;int main()
{mapint, double, lessint pairs;pairs.insert({ 15, 2.7 });pairs.insert({ 30, 111.11 });pairs.insert({ 5, 1010.1 });pairs.insert({ 10, 22.72 });pairs.insert({ 25, 345.67 });pairs.insert({ 5, 2.7 }); // 关键字相同被忽略pairs.insert({ 20, 9.234 });pairs.insert({ 35, 2.7 });cout pairs contains: \nKey\tValue\n;for (auto mapItem : pairs){cout mapItem.first \t mapItem.second \n;}// 使用下标运算符修改一个元素的值pairs[25] 9999.99;// 使用下标运算符插入一个元素pairs[40] 11.11;cout \nAfter subscript operations, pairs contains:\nKey\tValue\n;for (auto mapItem : pairs){cout mapItem.first \t mapItem.second \n;}cout endl;
}运行结果 从结果中可以看出map容器中不能出现重复的关键字但是不同关键字对应的值可以相同。
六、容器适配器
STL提供三种容器适配器
stackqueueprioriy_queue
适配器并非首类容器因为它们不提供真正的用于存储元素的数据结构实现而且它们也不支持迭代器。
适配器的好处在于程序员可以选择合适的底层数据结构这三种适配器类都支持成员函数push和pop通过它们可以在适配器数据结构中插入和删除元素。
1.stack
stack类在头文件stack中定义可以在底层数据结构的一端插入和删除元素LIFO。stack可以使用任意一种序列容器vectorlist或deque来实现不使用array来实现的原因是array对象的长度不可变。默认的stack实现使用的是deque。
stack的操作包括把元素插入到stack顶端的push实现是调用底层容器的push_back函数从stack顶端删除元素的pop实现是调用底层容器的pop_back函数获得顶端元素引用的top实现是调用底层容器的back函数确定stack是否为空的empty实现是调用底层容器的empty函数以及获得stack内元素个数的size实现是调用底层容器的size函数。 下面的代码中展示了使用三种不同的底层数据结构来创建stack对象。
#include iostream
#include stack
#include vector
#include list
#include deque // 可以不包含因为stack默认使用的就是deque
using namespace std;// 创建两个函数模板
// 用于压栈
templateclass T void pushElements(T stackRef);
// 用于出栈
templateclass T void popElements(T stackRef);int main()
{// 底层数据结构使用deque对象stackint intDequeStack;// 底层数据结构使用vector对象stackint, vectorint intVectorStack;// 底层数据结构作用list对象stackint, listint intListStack;// 向这三个Stack的对象中压入0-9这10个数字cout Pushing onto intDequeStack: ;pushElements(intDequeStack);cout \nPushing onto intVectorStack: ;pushElements(intVectorStack);cout \nPushing onto intListStack: ;pushElements(intListStack);cout \n\n;// 向这三个Stack的对象中压入0-9这10个数字cout Poping onto intDequeStack: ;popElements(intDequeStack);cout \nPoping onto intVectorStack: ;popElements(intVectorStack);cout \nPoping onto intListStack: ;popElements(intListStack);cout \n\n;
}template class T
void pushElements(T stackRef)
{for (int i 0; i 10; i){stackRef.push(i);cout stackRef.top() ;}
}template class T
void popElements(T stackRef)
{while(!stackRef.empty()){cout stackRef.top() ;stackRef.pop();}
}运行结果 注意push和pop函数都不返回任何值。stack类模拟中只有top函数可以返回元素。
2.queue
队列queue顾名思义该适配器的行为是先进先出FIFO。
queue可以使用STL的list或deque容器实现不使用array的原因同样是因为它的容量是固定的而不使用vector的原因是在vector的首部插入删除元素会移动后续所有元素开销过大。
默认情况下queue也使用deque来实现。queue的通用操作包括将元素插入到队列尾的push底层使用push_back函数实现、将首部元素删除的pop底层使用pop_front函数实现、获得队列首部的元素front底层使用front函数实现、获得队列尾部元素的back底层使用back函数实现、确定队列是否为空的empty底层使用empty函数实现和获得队列中元素个数的size底层使用size函数实现。 示例代码
#include iostream
#include deque
#include list
#include queue
using namespace std;int main()
{// 默认使用deque容器来作为queue实现的底层数据结构queuedouble dequeValues;// 指定list作为queue实现的底层数据结构queuedouble, listdouble listValues;// 往队列中插入元素dequeValues.push(3.2);dequeValues.push(4.8);dequeValues.push(9.9);listValues.push(5.5);listValues.push(3.4);listValues.push(6.6);cout Poping from dequeValues: ;while (!dequeValues.empty()){cout dequeValues.front() ;dequeValues.pop();}cout \n\nPoping from listValues: ;while (!listValues.empty()){cout listValues.front() ;listValues.pop();}cout endl;
}运行结果 3.priority_queue
priority_queue类在queue头文件中定义提供了在底层数据结构按序插入元素及在底层数据结构首部删除元素的功能。该类可以使用deque和vector来实现。默认情况下使用vector作为底层数据结构。
当把元素插入到priority_queue中时它们按照优先顺序排序。如此以来高优先级的元素由对象创建时使用比较函数对象来决定将是priority_queue中最先删除的。这通常使用堆排序技术来实现。默认的比较函数对象是lessT程序员也可以自己提供比较函数。
priority_queue的通常操作在该对象的适当位置插入元素的push使用底层数据结构的push_back函数再使用heapsort算法重新排序实现、删除最高优先级元素的pop使用底层数据结构的pop_front函数实现、获得对象中顶端元素的引用的top使用底层数据结构的front函数实现、确定是否为空的empty使用底层数据结构中的empty函数实现和获得对象中元素个数的size使用底层数据结构的size函数实现。 示例代码
#include iostream
#include queue
using namespace std;int main()
{// 默认使用vector容器使用lessT作为比较函数对象priority_queuedouble priorities;priorities.push(1.1);priorities.push(3.4);priorities.push(5.5);cout Poping from priorities: ;while (!priorities.empty()){cout priorities.top() ;priorities.pop();}cout endl;
}运行结果 七、bitset类
bitset类使创建和操作位集合更加容易这在描述一些标志位的集合时特别有用。bitset在编译时就确定了大小。 使用示例
// 创建了一个有3个位长度的bitset对象b
bitset3 b; // 调用默认的构造函数将所有位全部初始化为 0(off)
// 将第bitNumber位的值设为 1(on)次序从1开始与下标从0开始不同
b.set(bitNumber);
// 或者将整个对象的值全部设为 on
b.set();
// 将整个对象的值全部设为 off
b.reset(); // 也可以指定将第几个位设为 off
// 将指定位置的位反转
b.flip(bitNumber);
// 或全部反转
b.flip();// 返回一个指定位的引用
b[bitNumber];
// 还可以使用函数来实现这个操作且使用函数会进行边界检查
// 在没有越界的情况下指定位为 on 返回true否则返回false
// 如果越界抛出一个 out_of_range 类型的异常
b.test(bitNumber); // 返回对象b中有多少位
b.size();
// 返回对象b中有多少位被设为 on
b.count();// 检测所有位全部被设为 on 返回true否则返回false
b.all();
// 检测所有位如果有一个为 on 返回true否则返回false
b.any();
// 检测所有位如果没有一个为 on 返回true否则返回false
b.none();// 可以使用关系运算符 和 ! 比较两个类对象是否相等
b1 b2; // 两个对象中所有位都一一相等时返回true否则返回false
b1 ! b2; // 两个对象中有一个位不相等时返回true否则返回false// 任何位运算符赋值运算符都可以用来操作 bitset 的对象
// 比如, |, ^
b1 b2; // 在 b1 和 b2 之间逐位执行 逻辑与 操作并将返回值保存在 b1 中。// 移位运算符当然也可以使用
// 将对象 b 中的位右移 n 位
b n;// 将对象 b 转换成其他形式
b.to_string(); // 将 b 转换成一个字符串例如对象 b 中的位为 10101 使用该函数就可以得到 10101 这个字符串
b.to_ulong(); // 将 b 转换成一个 ulong 类型的值八、总结
本章中学习了标准模板库STL并讨论了它的三个主要组成部分容器、算法和迭代器。至于为什么要有STL呢这是因为在C中我们最主要的思想就是面向对象编程实现泛型编程通过模板实现使得同一套代码可以适用于不同的数据类型。举个例子编程比作造汽车使用了STL模板库我们就不需要再自己造轮子而是直接拿来使用即可这大大的提高编程的效率。且使用迭代器来访问容器对容器中的元素进行操作不需要像指针一样那么复杂容易出错。
对于容器可以分为三个部分首类容器(可分为序列容器、关联容器、容器适配器和近容器。
近容器本质是非标准库容器提供类似容器的接口它们基于C风格的指针或进行了简单封装。bitset就是一个近容器
序列容器包括array静态数组、vector动态数组、list双向链表、deque双向队列和forward_list单链表。这类容器用于描述线性的数据结构。
关联容器包括有序关联容器和无序关联容器其中有序的关联容器有set、multiset、map和multimap这些容器基本都是由红黑树来实现而无序的关联容器有unordered_set、unordered_multiset、unordered_map和unordered_multimap这些容器基本都是由哈希桶来实现
容器适配器这部分是因为本身没有具体的实现而是通过组合已有容器的功能来实现。包括stack栈、queue队列和priority_queue具有优先级的队列。
对于迭代器我们可以将其简单的理解成指针但是它们本身是一个模板类的对象封装了对容器中元素进行操作的函数。根据层次可以分为随机访问迭代器、双向迭代器、前向迭代器、输入迭代器和输出迭代器后两个迭代器并列。其中只有array、vector和deque支持随机访问迭代器只有stack、queue和priority_queue不支持迭代器其余的容器全部都支持双向迭代器。
而算法则是STL提供的一些常用功能的实现。会在下一章详细介绍。
