C++ STL介绍和底层原理讲解

STL简介

  • 长久以来,软件界一直希望建立一种可重复利用的东西
  • C++的面向对象和泛型编程思想,目的就是复用性的提升
  • 大多情况下,数据结构和算法都未能有一套标准导致被迫从事大量重复工作
  • 为了建立数据结构和算法的一套标准,诞生了STL

c++的三种特性:封装,继承,多态

封装:相似的东西封装成一个类,提高复用性

继承:子类继承父类中的属性,行为,提高代码复用性

多态:一个函数名称有多个接口,父类指针指向子类对象,调用同一个接口时,由于对象的不同会产生不同的形态,提高了复用性。

简介

C++ STL 全名Standard Template Library,译为C++ 标准模板库,是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、栈。

  • STL从广义上分为:容器(container)算法(algorithm)迭代器(iterator)
  • 容器和算法之间通过迭代器进行无缝连接。
  • STL几乎所有的代码都采用了模板类或者模板函数

STL六大组件

  • 容器:各种数据结构,如vector、list、deque、set、map等,用来存放数据,从实现角度来看,STL容器是一种class template。
  • 算法:各种常用的算法,如sort、find、copy、for_each。从实现的角度来看,STL算法是一种function tempalte.
  • 迭代器:扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将operator* , operator->,operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
  • 仿函数:行为类似函数,可作为算法的某种策略。从实现角度来看,仿函数是一种重载了operator()的class 或者class template,如果一个类将 () 运算符重载为成员函数,这个类就称为函数对象类,这个类的对象就是仿函数(又称仿函数对象)。
  • 适配器:可以使一个类的接口(模板的参数)适配成用户指定的形式,从而让原本不能在一起工作的两个类工作在一起。值得一提的是,容器、迭代器和函数都有适配器。
  • 空间配置器:负责空间的配置与管理。从实现角度看,配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

STL六大组件的交互关系,容器通过空间配置器取得数据存储空间,算法通过迭代器存储容器中的内容,仿函数可以协助算法完成不同的策略的变化,适配器可以修饰仿函数。

核心组件

组件 描述
容器(Containers) 容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器,比如 deque、list、vector、map 等。
算法(Algorithms) 算法作用于容器。它们提供了执行各种操作的方式,包括对容器内容执行初始化、排序、搜索和转换等操作。
迭代器(iterator) 迭代器用于链接容器和算法。迭代器用于遍历对象集合的元素。这些集合可能是容器,也可能是容器的子集。

容器

容器:置物之所也

STL容器就是将运用最广泛的一些数据结构实现出来

常用的数据结构:数组,链表,树,栈,队列,集合,映射表等

容器种类 功能
序列容器 主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器,是因为元素在容器中的位置同元素的值无关,即容器不是排序的。将元素插入容器时,指定在什么位置,元素就会位于什么位置。
排序容器 包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的,即便是插入元素,元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
哈希容器 C++ 11 新加入 4 种关联式容器,分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同,哈希容器中的元素是未排序的,元素的位置由哈希函数确定。

后两类容器也可以统称为关联式容器。因此具体划分可以是

  • 序列式容器
  • 关联式容器
    • 排序容器
    • 哈希容器

注意,由于哈希容器直到 C++ 11 才被正式纳入 C++ 标准程序库,而在此之前,“民间”流传着 hash_set、hash_multiset、hash_map、hash_multimap 版本,不过该版本只能在某些支持 C++ 11 的编译器下使用(如 VS),有些编译器(如 gcc/g++)是不支持的。

序列容器大致包含以下几类容器:

  • array<T,N>(数组容器):表示可以存储 N 个 T 类型的元素,是C++本身提供的一种容器。此类容器一旦建立,其长度就是固定不变的,这意味着不能增加或删除元素,只能改变某个元素的值;
  • vector<T>(向量容器):用来存放T类型的元素,是一个长度可变的序列容器,即在存储空间不足时,会自动申请更多的内存。使用此容器,在尾部增加或删除元素的效率最高(时间复杂度为 O(1) 常数阶),在其它位置插入或删除元素效率较差(时间复杂度为 O(n) 线性阶,其中 n 为容器中元素的个数);
  • deque<T>(双端队列容器):和 vector 非常相似,区别在于使用该容器不仅尾部插入和删除元素高效,在头部插入或删除元素也同样高效,时间复杂度都是 O(1) 常数阶,但是在容器中某一位置处插入或删除元素,时间复杂度为 O(n) 线性阶;
  • list<T>(链表容器):是一个长度可变的、由 T 类型元素组成的序列,它以双向链表的形式组织元素,在这个序列的任何地方都可以高效地增加或删除元素(时间复杂度都为常数阶 O(1)),但访问容器中任意元素的速度要比前三种容器慢,这是因为​ list<T> 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素。
  • forward_list<T>(正向链表容器):和 list 容器非常类似,只不过它以单链表的形式组织元素,它内部的元素只能从第一个元素开始访问,是一类比链表容器快、更节省内存的容器。

注意,其实除此之外,stack<T>queue<T> ​本质上也属于序列容器,只不过它们都是在 deque 容器的基础上改头换面而成,通常更习惯称它们为容器适配器,有关它们的介绍,会放到后续章节中。

关联式容器包含如下几类:

C++ STL 标准库提供了 4 种关联式容器,分别为 map、set、multimap、multiset。

关联式容器和序列式容器不同,此类容器在存储元素值的同时,还会为各元素额外再配备一个值(又称为“键”,其本质也是一个 C++ 基础数据类型或自定义类型的元素),它的功能是在使用关联式容器的过程中,如果已知目标元素的键的值,则直接通过该键就可以找到目标元素,而无需再通过遍历整个容器的方式。

弃用序列式容器,转而选用关联式容器存储元素,往往就是看中了关联式容器可以快速查找、读取或者删除所存储的元素,同时该类型容器插入元素的效率也比序列式容器高。

也就是说,使用关联式容器存储的元素,都是一个一个的“键值对”( <key,value> ),这是和序列式容器最大的不同。除此之外,序列式容器中存储的元素默认都是未经过排序的,而使用关联式容器存储的元素,默认会根据各元素的键值的大小做升序排序

关联式容器所具备的这些特性,归咎于 STL 标准库在实现该类型容器时,底层选用了「红黑树」这种数据结构来组织和存储各个键值对。

容器名称 特点
map 定义在<map>​头文件中,使用该容器存储的数据,其各个元素的键必须是唯一的(即不能重复),该容器会根据各元素键的大小,默认进行升序排序(调用 std::less<T>​)。
set 定义在<set>​头文件中,使用该容器存储的数据,各个元素键和值完全相同,且各个元素的值不能重复(保证了各元素键的唯一性)。该容器会自动根据各个元素的键(其实也就是元素值)的大小进行升序排序(调用 std::less<T>​)。
multimap 定义在 <map>​ 头文件中,和 map 容器唯一的不同在于,multimap 容器中存储元素的键可以重复。
multiset 定义在 <set>​ 头文件中,和 set 容器唯一的不同在于,multiset 容器中存储元素的值可以重复(一旦值重复,则意味着键也是重复的)。

除此之外,C++ 11 还新增了 4 种哈希容器,即 unordered_mapunordered_multimap ​以及 unordered_setunordered_multiset。严格来说,它们也属于关联式容器,但由于哈希容器底层采用的是哈希表,而不是红黑树,因此本教程将它们分开进行讲解(有关哈希容器,将放在后续章节做详细讲解)。

算法

算法:问题之解法也

有限的步骤,解决逻辑或数学上的问题,这一门学科我们叫做算法(Algorithms)

分类

  • 质变算法:是指运算过程中会更改区间内的元素的内容。例如拷贝,替换,删除等等
  • 非质变算法:是指运算过程中不会更改区间内的元素内容,例如查找、计数、遍历、寻找极值等等

迭代器

迭代器:容器和算法之间粘合剂

提供一种方法,使之能够依序寻访某个容器所含的各个元素,而无需暴露该容器的内部表示方式。

每个容器都有自己专属的迭代器

迭代器使用非常类似于指针,初学阶段我们可以先理解迭代器为指针

常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。主要介绍后面的这 3 种迭代器。

分类

  • 前向迭代器(forward iterator)

    假设p是一个前向迭代器,则p支持p++,++p,*p操作,还可以被复制和赋值,可以用和!=运算符进行比较,此外,两个正向迭代器还可以互相赋值。

  • 双向迭代器(bidirectional iterator)

    双向迭代器具有正向迭代器的全部功能,同时,双向迭代器还在正向迭代器的基础上进行–p,p–操作。

  • 随机访问迭代器(random access iterator)

    随机访问迭代器具有双向迭代器的全部功能,除此之外,假设p是一个随机访问迭代器,i是一个整型变量,则p还支持以下操作

    • p += i;使p向后移动i个位置
    • p -= i;使p往前移动i个位置
    • p + i;返回p后面第i个元素的迭代器
    • p – i;返回p前面第i个元素的迭代器
    • p[i];返回p后面第i个元素的引用

    ​ 此外,两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。另外,表达式 p2-p1 也是有定义的,其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差(也可以说是 p2 和 p1 之间的元素个数减一)。

不同容器的迭代器

容器 对应的迭代器类型
array 随机访问迭代器
vector 随机访问迭代器
deque 随机访问迭代器
list 双向迭代器
set / multiset 双向迭代器
map / multimap 双向迭代器
forward_list 前向迭代器
unordered_map / unordered_multimap 前向迭代器
unordered_set / unordered_multiset 前向迭代器
容器适配器
stack 不支持迭代器
queue / priority_queue 不支持迭代器

迭代器的定义

迭代器定义方式 具体格式
正向迭代器 容器类名::iterator 迭代器名;
常量正向迭代器 容器类名::const_iterator 迭代器名;
反向迭代器 容器类名::reverse_iterator 迭代器名;
常量反向迭代器 容器类名::const_reverse_iterator 迭代器名;

值得一提的是,表 2 中的反向迭代器全称为 “反向迭代器适配器”,后续章节会做详细讲解,这里读者只需要知道其用法即可。

通过定义以上几种迭代器,就可以读取它指向的元素,*迭代器名就表示迭代器指向的元素。其中,常量迭代器类似于常量指针,无法修改存储的值,但是可以修改指向的位置,另外,反向迭代器和正向迭代器的区别在于:

  • 对正向迭代器进行 ++ 操作时,迭代器会指向容器中的后一个元素;
  • 而对反向迭代器进行 ++ 操作时,迭代器会指向容器中的前一个元素。

注意,以上 4 种定义迭代器的方式,并不是每个容器都适用。有一部分容器同时支持以上 4 种方式,比如 array、deque、vector;而有些容器只支持其中部分的定义方式,例如 forward_list 容器只支持定义正向迭代器,不支持定义反向迭代器。

序列容器

array

array 容器是 C++ 11 标准中新增的序列容器,简单地理解,它就是在 C++ 普通数组的基础上,添加了一些成员函数和全局函数。和其它容器不同,array 容器的大小是固定的,无法动态的扩展或收缩,这也就意味着,在使用该容器的过程无法借由增加或移除元素而改变其大小,它只允许访问或者替换存储的元素。

使用容器前

#include <array>
using namespace std;

声明

//在 array<T,N> 类模板中,T 用于指明容器中的存储的具体数据类型,N 用于指明容器的大小,需要注意的是,这里的 N 必须是常量,不能用变量表示。

//方式一
array<int, 10> nums;
//array 容器不会做默认初始化操作,因此使用这种方式创建的容器中,各个元素的值是不确定的。

//方式二
array<int, 10> nums {}; //通过这种方式创建,可以将所有元素初始化为0

//方式三
array<double, 10> values {0.5,1.0,1.5,2.0}; // 可以像使用普通数组一样初始化,这里只初始化了4个值,那么剩余的值将被初始化为0

array容器成员函数汇总

成员函数 功能
begin() 返回指向容器中第一个元素的随机访问迭代器。
end() 返回指向容器最后一个元素之后一个位置的随机访问迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的随机访问迭代器。
rend() 返回指向第一个元素之前一个位置的随机访问迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回容器中当前元素的数量,其值始终等于初始化 array 类的第二个模板参数 N。
max_size() 返回容器可容纳元素的最大数量,其值始终等于初始化 array 类的第二个模板参数 N。
empty() 判断容器是否为空,和通过 size()0 的判断条件功能相同,但其效率可能更快。
这个函数实际上非常鸡肋,因为创建一个array<int, 0>的容器的意义在哪里呢?
at(n) 返回容器中 n 位置处元素的引用,该函数自动检查 n 是否在有效的范围内,如果不是则抛出 out_of_range 异常。
front() 返回容器中第一个元素的直接引用,该函数不适用于空的 array 容器。
back() 返回容器中最后一个元素的直接应用,该函数同样不适用于空的 array 容器。
data() 返回一个指向容器首个元素的指针。利用该指针,可实现复制容器中所有元素等类似功能。
fill(val) 将 val 这个值赋值给容器中的每个元素。
array1.swap(array2) 交换 array1 和 array2 容器中的所有元素,但前提是它们具有相同的长度和类型。

正是由于 array 容器中包含了 at() 这样的成员函数,使得操作元素时比普通数组更安全。

另外,在 头文件中还重载了 get() 全局函数,该重载函数的功能是访问容器中指定的元素,并返回该元素的引用。

array<int, 4> ar{1, 2, 3, 4};
cout << get<1>(array);
//输出:2

读者可能有这样一个疑问,即为什么 array 容器在重载 [] 运算符时,没有实现边界检查的功能呢?答案很简单,因为性能。如果每次访问元素,都去检查索引值,无疑会产生很多开销。当不存在越界访问的可能时,就能避免这种开销。因此,当程序员确定没有越界产生时,使用[],不确定时使用at。

vector

vector(向量容器):用来存放 T 类型的元素,是一个长度可变的序列容器,即在存储空间不足时,会自动申请更多的内存。使用此容器,在尾部增加或删除元素的效率最高(时间复杂度为 O(1) 常数阶),在其它位置插入或删除元素效率较差(时间复杂度为 O(n) 线性阶,其中 n 为容器中元素的个数)

使用vector类需包含头文件vector,并且vector在名称空间std中

#include <vector>
using namespace std;

基本函数

1.构造函数

  • vector():创建一个空vector
  • vector(int nSize):创建一个vector,元素个数为nSize
  • vector(int nSize,const t& t):创建一个vector,元素个数为nSize,且值均为t
  • vector(const vector&):复制构造函数
  • vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中,begin和end可以是迭代器或数组区间地址

初始化

vector v1; 保存类型为 T 对象。默认构造函数 v1 为空。
vector v2(v1); v2 是 v1 的一个副本。
vector v3(n, i); v3 包含 n 个值为 i 的元素。
vector v4(n); v4 含有值初始化的元素的 n 个副本。
vector v5, v6; 同时初始化两个对象
vector v7 = {1,2,3}; 使用基本数组初始化

简单介绍

  1. vector<类型>标识符 //默认构造函数为空
  2. vector<类型>标识符(最大容量)
  3. vector<类型>标识符(最大容量,初始所有值)
  4. int i[5]={1,2,3,4,5}

    vector<类型>vi(i,i+2); ​ //得到i索引值为3以后的值

  5. vector<vector<int> [空格] >v; ​ //二维向量,这里最外的<>要有空格。否则在比较旧的编译器(C++11标准之前)下无法通过

2.增加函数

  • void push_back(const T& x):向量尾部增加一个元素X
  • iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
  • iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
  • iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
  • iterator insert(iterator it, initlist) :在迭代器 it 指定的位置之前,插入初始化列表(用大括号{}括起来的多个元素,中间有逗号隔开)中所有的元素,并返回表示第一个新插入元素位置的迭代器。

    nums.insert(nums.end(), {1, 2, 3, 4})
    

3.删除函数

  • iterator erase(iterator it):删除向量中迭代器指向元素
  • iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
  • void pop_back():删除向量中最后一个元素
  • void clear():清空向量中所有元素

4.遍历函数

  • reference at(int pos):返回pos位置元素的引用
  • reference front():返回首元素的引用
  • reference back():返回尾元素的引用
  • iterator begin():返回向量头指针,指向第一个元素
  • iterator end():返回向量尾指针,指向向量最后一个元素的下一个位置
  • reverse_iterator rbegin():反向迭代器,指向最后一个元素
  • reverse_iterator rend():反向迭代器,指向第一个元素之前的位置

5.判断函数

  • bool empty() const:判断向量是否为空,若为空,则向量中无元素

6.大小函数

  • int size() const:返回向量中元素的个数
  • int capacity() const:返回当前向量所能容纳的最大元素值
  • int max_size() const:返回最大可允许的 vector 元素数量值

7.其他函数

  • void swap(vector&):交换两个同类型向量的数据
  • void assign(int n,const T& x):设置向量中前n个元素的值为x
  • void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量区间内元素

8.总结

函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回实际元素个数。
max_size() 返回元素个数的最大值。这通常是一个很大的值,一般是 2^32-1,所以我们很少会用到这个函数。
resize() 改变实际元素的个数。(将原数组截断或者补0),
设置长度小于实际长度时会将后续元素全部丢弃,大于实际长度时,补0
capacity() 返回当前容量。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
reserve() 增加容器的容量。
当容器中本身存在的元素个数小于reserve设置的个数时,reserve将扩大容器容量,其余值初始化为0
当容器本身元素个数大于设置个数时,reserve不做任何处理。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
operator[ ] 重载了 [ ] 运算符,可以向访问数组中元素那样,通过下标即可访问甚至修改 vector 容器中的元素。
at() 使用经过边界检查的索引访问元素。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
data() 返回指向容器中第一个元素的指针。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
pop_back() 移出序列尾部的元素。
insert() 在指定的位置插入一个或多个元素。
erase() 移出一个元素或一段元素。
clear() 移出所有的元素,容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。(C++11)
注意:和insert的区别在于只能生成一个元素,即emplace(iterator pos, x),在效率方面和emplace_back于push_back的区别一样
emplace_back() 在序列尾部生成一个元素。(C++11)

注意:

  • 在使用反向迭代器进行 ++ 或 — 运算时,++ 指的是迭代器向左移动一位,– 指的是迭代器向右移动一位,即这两个运算符的功能也“互换”了。
  • 同时,使用reserve扩大容器应该注意,原来的迭代器可能会失效,这是因为,为了增加容器的容量,vector 容器的元素可能已经被复制或移到了新的内存地址。所以后续再使用这些迭代器时,最好重新生成一下。
  • vector 容器的容量(用 capacity 表示),指的是在不分配更多内存的情况下,容器可以保存的最多元素个数,可以使用reserve()来指定大小;而 vector 容器的大小(用 size 表示),指的是它实际所包含的元素个数。
  • emplace_back() 和 push_back() 的区别,就在于底层实现的机制不同。push_back() 向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动到容器中(如果是拷贝的话,事后会自行销毁先前创建的这个元素);而 emplace_back() 在实现时,则是直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。

    显然完成相同的操作,push_back()远没有emplace_back()快,实际开发中应优先使用emplace_back(),但是由于emplace_back()是C++11新加的,如果程序要兼顾之前的版本,还是应该使用push_back()

  • 小技巧:如果不在意容器中元素的排列顺序,可以结合 swap() 和 pop_back() 函数,同样可以实现删除容器中指定位置元素的目的。

其他

1 、基本操作

使用迭代器访问元素.

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
    cout<<*it<<endl;

(6)插入元素:vec.insert(vec.begin()+i,a); 在第i+1个元素前面插入a;

(7)删除元素:vec.erase(vec.begin()+2) ; 删除第3个元素

vec.erase(vec.begin()+i,vec.end()+j); 删除区间[ i,j-1] 区间从0开始

(8)向量大小: vec.size();

(9)清空: vec.clear();

3、算法

  1. 翻转数组
    #include <algorithm>
    reverse(v.begin(), v.end());//将数组翻转,即逆序排列
    
  2. 排序
    #include <algorithm>
    
    //默认升序
    sort(v.begin(), v.end());//其实就是sort(v.begin(), v.end(), less<int>());第三个参数是默认参数
    sort(v.begin(), v.end(), greater<int>());//降序排列
    
    //降序
    bool cmp(const int&a, const int &b)
    {  return a>b;  }
    sort(v.begin(), v.end(), cmp);
    

(C++)STL排序函数sort和qsort的用法与区别 – AndyJee – 博客园 (cnblogs.com)

vector的底层实现

以前一直以为在原来数组开辟的空间后面再增加,结果怎么想都没想明白。因为一般来说后面的内存已经被占用了,在后面增加是不可能的。结果是重新开辟了一个数组,把之前的值放到复制到新开辟的数组中来。这也可以解释为什么capacity的结果和size的结果不同

当 vector 的大小和容量相等(size=capacity)也就是满载时,如果再向其添加元素,那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步:

  1. 完全弃用现有的内存空间,重新申请更大的内存空间;
  2. 将旧内存空间中的数据,按原有顺序移动到新的内存空间中;
  3. 最后将旧的内存空间释放。
    这也就解释了,为什么 vector 容器在进行扩容后,与其相关的指针、引用以及迭代器可能会失效的原因。

    因此:当我们要在vector中push_back()1000个数时,应当首先设置reserve(1000),这样vector只进行了一次扩容,否则vector将进行多次扩容,导致效率下降

  • capacity显示当前容器的可容纳的大小,一般是2的倍数,即能容纳当前元素个数时的最小的2的倍数

    vector<int> nums;
    for (int i = 0; i < 65; i++)
    nums.push_back(i);
    cout << nums.capacity() << endl; // 结果是128,如果将65改为64,结果是64,即2的倍数
    

避免使用vector<bool>

[vector不是存储bool类型元素的vector容器! (biancheng.net)](http://m.biancheng.net/view/7393.html#:~:text=特别需要提醒的是,在使用 vector 容器时,要尽量避免使用该容器存储 bool 类型的元素,即避免使用 vector。 具体来讲,不推荐使用,vector 的原因有以下 2 个: 严格意义上讲,vector 并不是一个 STL 容器;)

vector<bool>不是一个STL容器,如果 vector<bool> 是一个 STL 容器,则下面这段代码是可以通过编译的:

vector<bool> cont{0, 1};
bool *p = &cont[0];

但不幸的是,此段代码不能通过编译。原因在于​ vector<bool> 底层采用了独特的存储机制。这里不具体介绍。如果将bool换为int,那么以上代码,就能够通过编译且不会报错

在实际场景中需要使用 vector<bool> 这样的存储结构,可以选择使用​ deque<bool> 或者 bitset 来替代 vector<bool>

要知道,deque 容器几乎具有 vecotr 容器全部的功能(拥有的成员方法也仅差 reserve() 和 capacity()),而且更重要的是,deque 容器可以正常存储 bool 类型元素。

deque

deque 是 double-ended queue 的缩写,又称双端队列容器。deque 容器和 vecotr 容器有很多相似之处,比如:

  • deque 容器也擅长在序列尾部添加或删除元素(时间复杂度为O(1)),而不擅长在序列中间添加或删除元素。
  • deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是,deque 还擅长在序列头部添加或删除元素,所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是,deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。而是分片段的存储。

使用deque需要如下代码:

#include <deque>
using namespace std;

构造函数

deque的构造函数,可以说几乎与vector一致

deque<int> de0;  //空deque
deque<int> de1(10);     //10个为0
deque<int> de2(10, 5);  //10个初始值为5
deque<int> de3(de2);    //使用这种方式的前提是两个容器是相同的
deque<int> de4(de2.begin(), de2.end());  //也要保证两者数据类型相同
deque<int> de5(arr, arr + n); // 针对普通数组的处理方法

具体函数声明:

函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值,一般是 232-1,我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
shrink_to_fit() 将内存减少到等于当前元素实际所使用的大小。
operator[ ] 重载了 [ ] 运算符,可以向访问数组中元素那样,通过下标即可访问甚至修改 deque容器中的元素。
at() 使用经过边界检查的索引访问元素。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。
insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素,容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() (c++11)在指定的位置直接生成一个元素。
emplace_front() (c++11)在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。
emplace_back() (c++11)在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。

和 vector 相比,额外增加了实现在容器头部添加和删除元素的成员函数(上表中黑体加粗的函数),同时删除了 capacity()、reserve() 和 data() 成员函数。这些函数的用法,和vector也基本类似。

除此之外,当向 deque 容器添加元素时,deque 容器会申请更多的内存空间,同时其包含的所有元素可能会被复制或移动到新的内存地址(原来占用的内存会释放),这会导致之前创建的迭代器失效。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int>d;
    d.push_back(1);
    auto first = d.begin();
    d.push_back(2);    //添加元素,会导致 first 失效
    cout << *first << endl;
    return 0;
}

注意,和 vector 容器不同,deque 容器没有提供 data() 成员函数,同时 deque 容器在存储元素时,也无法保证其会将元素存储在连续的内存空间中,因此尝试使用指针去访问 deque 容器中指定位置处的元素,是非常危险的。所以使用deque容器,建议使用迭代器的方式去访问。

deque容器的存储结构

和 vector 容器采用连续的线性空间不同,deque 容器存储数据的空间是由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以位于在内存的不同区域。

为了管理这些连续空间,deque 容器用数组(数组名假设为 map)存储着各个连续空间的首地址。也就是说,map 数组中存储的都是指针,指向那些真正用来存储数据的各个连续空间(如图 1 所示)。

deque容器的底层存储机制

通过建立 map 数组,deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说,当 deque 容器需要在头部或尾部增加存储空间时,它会申请一段新的连续空间,同时在 map 数组的开头或结尾添加指向该空间的指针,由此该空间就串接到了 deque 容器的头部或尾部。

有读者可能会问,如果 map 数组满了怎么办?很简单,再申请一块更大的连续空间供 map 数组使用,将原有数据(很多指针)拷贝到新的 map 数组中,然后释放旧的空间。

deque 容器的分段存储结构,提高了在序列两端添加或删除元素的效率,但也使该容器迭代器的底层实现变得更复杂。

deque底层的具体实现见:C++ STL deque容器底层实现原理(深度剖析) (biancheng.net),附一张底层实现原理图。

deque容器的底层实现

list

list 容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。这意味着,list 容器中的元素可以分散存储在内存空间里,而不是必须存储在一整块连续的内存空间中。在这个序列的任何地方都可以高效地增加或删除元素(时间复杂度都为常数阶 O(1)),但访问容器中任意元素的速度要比前三种容器慢,这是因为​ list<T> 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素。

std::list在大多数版本中都是实现为双向链表,而不是双向循环链表。列举常用的STL如下:

  • GNU Standard C++ Library (libstdc++): GNU Compiler Collection (GCC)使用的标准库。std::list在这个实现中是双向链表。
  • Microsoft Standard Library (MSVC STL): Microsoft Visual Studio使用的标准库。std::list在这个实现中也是双向链表。
  • LLVM Standard Library (libc++): LLVM项目的标准库实现。std::list在这个实现中同样是双向链表。

img

由双向链表的特性,不能随机访问元素,只能从头或从尾开始访问元素,因此可以知道list容器使用的迭代器为双向迭代器。因此不能通过容器名[x]这种方式访问元素,这是随机访问迭代器才具有的功能。

  • 基于这样的存储结构,list 容器可以在序列已知的任何位置快速插入或删除元素(时间复杂度为O(1))。
  • 缺点,它不能像 array 和 vector 那样,通过位置直接访问元素。

实际场景中,如何需要对序列进行大量添加或删除元素的操作,而直接访问元素的需求却很少,这种情况建议使用 list 容器存储序列。

使用该容器需要包括以下代码:

#include <list>
using namespace std;

构造函数

list<int> nums0;    //空list
list<int> nums1(10);    //含有10个元素的list
list<int> nums2(10, 5); //含有十个均为5的元素
list<int> nums3(nums2); //使用已知同类型容器初始化

int a[] = { 1,2,3,4,5 };
std::list<int> values(a, a+5);  //拷贝普通数组

array<int, 5>arr{ 11,12,13,14,15 };
list<int> nums4(arr.begin() + 2, arr.end());    //使用迭代器方式拷贝,如果是局部拷贝,要确保原容器支持随机访问迭代器
成员函数 功能
begin() 返回指向容器中第一个元素的双向迭代器。
end() 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
rbegin() 返回指向最后一个元素的反向双向迭代器。
rend() 返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
size() 返回当前容器实际包含的元素个数。
max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 2^32-1,所以我们很少会用到这个函数。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换容器中原有内容。
emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。
push_front() 在容器头部插入一个元素。
pop_front() 删除容器头部的一个元素。
emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同,但效率更高。
push_back() 在容器尾部插入一个元素。
pop_back() 删除容器尾部的一个元素。
insert() 在容器中的指定位置插入元素。
emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同,但效率更高。
erase() 删除容器中一个或某区域内的元素。
swap() 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。
resize() 调整容器的大小。
同其他容器一样,原长度比新长度小,整型补默认值,string补空字符串,bool补false;反之就裁剪
clear() 删除容器存储的所有元素。
splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。
remove(val) 删除容器中所有等于 val 的元素。
remove_if() 删除容器中满足条件的元素。
unique() 删除容器中相邻的重复元素,只保留一个。
merge() 合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的。
sort() 通过更改容器中元素的位置,将它们进行排序。
reverse() 反转容器中元素的顺序。

list其配备的迭代器类型为双向迭代器,而不再是随机访问迭代器。这意味着,假设 p1 和 p2 都是双向迭代器,则它们只支持使用 ++p1、 p1++、 p1–、 p1++、 *p1、 p1p2 以及 p1!=p2 运算符。

访问 list 容器中存储元素的方式很有限,即要么使用 front() 和 back() 成员函数,要么使用 list 容器迭代器。list 容器不支持随机访问,未提供下标操作符 [] 和 at() 成员函数,也没有提供 data() 成员函数。

list 模板类中,与“添加或插入新元素”相关的成员方法有如下几个:

  • push_front():向 list 容器首个元素前添加新元素;
  • push_back():向 list 容器最后一个元素后添加新元素;
  • emplace_front():在容器首个元素前直接生成新的元素;
  • emplace_back():在容器最后一个元素后直接生成新的元素;
  • emplace():在容器的指定位置直接生成新的元素;
  • insert():在指定位置插入新元素;
  • splice():将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。

以上这些成员方法中,除了 insert() 和 splice() 方法有多种语法格式外,其它成员方法都仅有 1 种语法格式。

插入函数

insert()

语法格式 用法说明
iterator insert(pos,elem) 在迭代器 pos 指定的位置之前插入一个新元素 elem,并返回表示新插入元素位置的迭代器。
iterator insert(pos,n,elem) 在迭代器 pos 指定的位置之前插入 n 个元素 elem,并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,first,last) 在迭代器 pos 指定的位置之前,插入其他容器(例如 array、vector、deque 等)中位于 [first,last) 区域的所有元素,并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,initlist) 在迭代器 pos 指定的位置之前,插入初始化列表(用大括号 { } 括起来的多个元素,中间有逗号隔开)中所有的元素,并返回表示第一个新插入元素位置的迭代器。

splice()

和 insert() 成员方法相比,splice() 成员方法的作用对象是其它 list 容器,其功能是将其它 list 容器中的元素添加到当前 list 容器中指定位置处。

语法格式 功能
void splice (iterator position, list& x); position 为迭代器,用于指明插入位置;x 为另一个 list 容器。 此格式的 splice() 方法的功能是,将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator i); position 为迭代器,用于指明插入位置;x 为另一个 list 容器;i 也是一个迭代器,用于指向 x 容器中某个元素。 此格式的 splice() 方法的功能是将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator first, iterator last); position 为迭代器,用于指明插入位置;x 为另一个 list 容器;first 和 last 都是迭代器,[fist,last) 用于指定 x 容器中的某个区域。 此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处。

具体代码实现见:C++ STL list添加(插入)元素方法详解 (biancheng.net)

删除函数

对 list 容器存储的元素执行删除操作,需要借助该容器模板类提供的成员函数。幸运的是,相比其它STL容器模板类,list 模板类提供了更多用来实现此操作的成员函数。

成员函数 功能
pop_front() 删除位于 list 容器头部的一个元素。
pop_back() 删除位于 list 容器尾部的一个元素。
erase() 该成员函数既可以删除 list 容器中指定位置处的元素,也可以删除容器中某个区域内的多个元素。
erase(pos)或者erase(begin, end)
clear() 删除 list 容器存储的所有元素。
remove(val) 删除容器中所有等于 val 的元素。
unique() 删除容器中相邻的重复元素,只保留一份。
remove_if() 删除容器中满足条件的元素。

其中unique具有两种形式,一种无参,一种含参,无参就是直接去重,而含参的可自定义去重规则,这里了解即可,同时remve_if的条件,这里不进行仔细讨论。

C++ STL list删除元素详解 (biancheng.net)

list底层实现

list容器的底层是用双向链表实现的。list底层源码如下:

template<typename T,...>
struct __List_node{
    //...
    __list_node<T>* prev;
    __list_node<T>* next;
    T myval;
    //...
}

可以看到,list 容器定义的每个节点中,都包含 prev、next 和 myval。其中,prev 指针用于指向前一个节点;next 指针用于指向后一个节点;myval 用于存储当前元素的值。

扩展:empty()和size()都可以判断容器是否为空,谁更好? (biancheng.net)

forward_list

forward_list 是 C++11 新添加的一类容器,其底层实现和 list 容器一样,采用的也是链表结构,只不过 forward_list 使用的是单链表,而 list 使用的是双向链表。

单链表和双向链表

  • forward_list 容器具有和 list 容器相同的特性,即擅长在序列的任何位置进行插入元素或删除元素的操作,但对于访问存储的元素,没有其它容器(如 array、vector)的效率高。
  • 由于单链表只能从前向后遍历,而不支持反向遍历,因此 forward_list 容器只提供前向迭代器,而不是双向迭代器。这意味着,forward_list 容器不具有 rbegin()、rend() 之类的成员函数。
  • 那么,既然 forward_list 容器具有和 list 容器相同的特性,list 容器还可以提供更多的功能函数,forward_list 容器有什么存在的必要呢?

    当然有,forward_list 容器底层使用单链表,也不是一无是处。比如,存储相同个数的同类型元素,单链表耗用的内存空间更少,空间利用率更高,并且对于实现某些操作单链表的执行效率也更高。

使用forward_list容器需要包括

#include <forward_list>
using namespace std;

构造函数和list完全一致,这里就不在重复说明

成员函数 功能
before_begin() 返回一个前向迭代器,其指向容器中第一个元素之前的位置。
begin() 返回一个前向迭代器,其指向容器中第一个元素的位置。
end() 返回一个前向迭代器,其指向容器中最后一个元素之后的位置。
cbefore_begin() 和 before_begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
front() 返回第一个元素的引用。
assign() 用新元素替换容器中原有内容。
push_front() 在容器头部插入一个元素。
emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。
pop_front() 删除容器头部的一个元素。
emplace_after() 在指定位置之后插入一个新元素,并返回一个指向新元素的迭代器。和 insert_after() 的功能相同,但效率更高。
insert_after() 在指定位置之后插入一个新元素,并返回一个指向新元素的迭代器。
erase_after() 删除容器中某个指定位置或区域内的所有元素。
swap() 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。
resize() 调整容器的大小。
clear() 删除容器存储的所有元素。
splice_after() 将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后。
remove(val) 删除容器中所有等于 val 的元素。
remove_if() 删除容器中满足条件的元素。
unique() 删除容器中相邻的重复元素,只保留一个。
merge() 合并两个事先已排好序的 forward_list 容器,并且合并之后的 forward_list 容器依然是有序的。
sort() 通过更改容器中元素的位置,将它们进行排序。
reverse() 反转容器中元素的顺序。

具体介绍:C++ STL forward_list容器完全攻略 (biancheng.net)

类模板

pair

考虑到“键值对”并不是普通类型数据,C++STL 标准库提供了 pair 类模板,其专门用来将 2 个普通元素 first 和 second(可以是 C++ 基本数据类型、结构体、类自定的类型)创建成一个新元素<first, second>。通过其构成的元素格式不难看出,使用 pair 类模板来创建“键值对”形式的元素,再合适不过。

C++ STL pair用法详解 (biancheng.net)

C++ pair的基本用法总结(整理)_sevencheng798的博客-CSDN博客_c++ pair

pair在头文件<utility>

pair 类模板,其专门用来将 2 个普通元素 first 和 second(可以是 C++ 基本数据类型、结构体、类自定的类型)创建成一个新元素<first, second>。其中第一个元素作为键(key),第二个元素作为值(value)。

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {
    // 调用默认构造函数
    pair <string, double> pair1;
    // 调用第 2 种构造函数
    pair <string, string> pair2("STL教程","http://c.biancheng.net/stl/");  
    // 调用拷贝构造函数
    pair <string, string> pair3(pair2);
    //调用移动构造函数
    pair <string, string> pair4(make_pair("C++教程", "http://c.biancheng.net/cplus/"));
                        //make_pair() 函数,它也是 <utility> 头文件提供的,其功能是生成一个 pair 对象。
    // pair4 的等价初始化形式 pair <string, string> pair4 = make_pair("C++教程", "http://c.biancheng.net/cplus/");
    // 调用第 5 种构造函数
    pair <string, string> pair5(string("Python教程"), string("http://c.biancheng.net/python/"));  

    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: "<< pair2.first << " " << pair2.second << endl;
    cout << "pair3: " << pair3.first << " " << pair3.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl;
    cout << "pair5: " << pair5.first << " " << pair5.second << endl;
    return 0;
}
输出结果:
pair1:  0
pair2: STL教程 http://c.biancheng.net/stl/
pair3: STL教程 http://c.biancheng.net/stl/
pair4: C++教程 http://c.biancheng.net/cplus/
pair5: Python教程 http://c.biancheng.net/python/

<utility>头文件中除了提供创建 pair 对象的方法之外,还为 pair 对象重载了​ <、<=、>、>=、==、!= 这 6 种运算符,其运算规则是:对于进行比较的 2 个 pair 对象,先比较 pair.first 元素的大小,如果相等则继续比较 pair.second 元素的大小。

注意,比较的 2 个 pair 对象,其对应的键和值的类型比较相同,否则将没有可比性,同时编译器提示没有相匹配的运算符。

pair类模板还提供有一个 swap() 成员函数,能够互换 2 个 pair 对象的键值对,其操作成功的前提是这 2 个 pair 对象的键和值的类型要相同。

pair1.swap(pair2);//交换pair1和pair2

tuple

C++11 标准新引入了一种类模板,命名为 tuple(中文可直译为元组)。tuple 最大的特点是:实例化的对象可以存储任意数量、任意类型的数据。

tuple 的应用场景很广泛,例如当需要存储多个不同类型的元素时,可以使用 tuple;当函数需要返回多个数据时,可以将这些数据存储在 tuple 中,函数只需返回一个 tuple 对象即可。

C++11 tuple元组详解 (biancheng.net)

tuple 本质是一个以可变模板参数定义的类模板,它定义在<tuple>头文件并位于 std 命名空间中。因此要想使用 tuple 类模板,程序中需要首先引入以下代码:

#include <tuple>
using std::tuple;

示例

#include <tuple>
using namespace std;

int main()
{
    tuple<int, char, char> first;                  // 1)   first{}
    tuple<int, char> second(first);                // 2)   second{}
    tuple<int, char> third(make_tuple(20, 'b'));   // 3)   third{20,'b'}
    tuple<long, char> fourth(third);               // 4)的左值方式, fourth{20,'b'}
    tuple<int, char> fifth(10, 'a');               // 5)的右值方式, fifth{10.'a'}
    tuple<int, char> sixth(make_pair(30, 'c'));    // 6)的右值方式, sixth{30,''c}
    return 0;
}

make_tuple()函数

它以模板的形式定义在 <tuple> 头文件中,功能是创建一个 tuple 右值对象(或者临时对象)。

auto first = make_tuple (10,'a');   // tuple < int, char >
const int a = 0; int b[3];
auto second = make_tuple (a,b);     // tuple < int, int* >

常用函数

函数或类模板 描 述
tup1.swap(tup2) swap(tup1, tup2) tup1 和 tup2 表示类型相同的两个 tuple 对象,tuple 模板类中定义有一个 swap() 成员函数,<tuple> 头文件还提供了一个同名的 swap() 全局函数。 swap() 函数的功能是交换两个 tuple 对象存储的内容。
get<num>(tup) tup 表示某个 tuple 对象,num 是一个整数,get() 是 <tuple> 头文件提供的全局函数,功能是返回 tup 对象中第 num+1 个元素。
tuple_size<type>::value tuple_size 是定义在<tuple>头文件的类模板,它只有一个成员变量 value,功能是获取某个 tuple 对象中元素的个数,type 为该tuple 对象的类型。
tuple_element<I, type>::type tuple_element 是定义在 <tuple> 头文件的类模板,它只有一个成员变量 type,功能是获取某个 tuple 对象第 I+1 个元素的类型。
forward_as_tuple<args...> args… 表示 tuple 对象存储的多个元素,该函数的功能是创建一个 tuple 对象,内部存储的 args… 元素都是右值引用形式的。
tie(args...) = tup tup 表示某个 tuple 对象,tie() 是 <tuple> 头文件提供的,功能是将 tup 内存储的元素逐一赋值给 args… 指定的左值变量。
tuple_cat(args...) args… 表示多个 tuple 对象,该函数是 <tuple> 头文件提供的,功能是创建一个 tuple 对象,此对象包含 args… 指定的所有 tuple 对象内的元素。

tuple 模板类对赋值运算符 = 进行了重载,使得同类型的 tuple 对象可以直接赋值。此外,tuple 模板类还重载了 、!=、<、>、>=、<= 这几个比较运算符,同类型的 tuple 对象可以相互比较(逐个比较各个元素)。

关联式容器

等待更新

容器适配器

容器适配器本质上还是容器,只不过此容器模板类的实现,利用了大量其它基础容器模板类中已经写好的成员函数。当然,如果必要的话,容器适配器中也可以自创新的成员函数。

简单的理解容器适配器,其就是将不适用的序列式容器(包括 vector、deque 和 list)变得适用。即通过封装某个序列式容器,并重新组合该容器中包含的成员函数,使其满足某些特定场景的需要。

STL 提供了 3 种容器适配器,分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先级队列适配器。

容器适配器 基础容器筛选条件 默认基础容器
stack 基础容器需包含以下成员函数:empty()size()back()push_back()pop_back()满足条件的基础容器有 vector、deque、list。 deque
queue 基础容器需包含以下成员函数:empty()size()front()back()push_back()pop_front()满足条件的基础容器有 deque、list。 deque
priority_queue 基础容器需包含以下成员函数:empty()size()front()push_back()pop_back()满足条件的基础容器有vector、deque。 vector

不同场景下,由于不同的序列式容器其底层采用的数据结构不同,因此容器适配器的执行效率也不尽相同。但通常情况下,使用默认的基础容器即可。当然,我们也可以手动修改,具体的修改容器适配器基础容器的方法,后续讲解具体的容器适配器会详细介绍。

stack

stack 栈适配器是一种单端开口的容器(如图所示),实际上该容器模拟的就是栈存储结构,即无论是向里存数据还是从中取数据,都只能从这一个开口实现操作。

stack适配器示意图

和其他序列容器相比,stack 是一类存储机制简单、提供成员函数较少的容器。

#include <stack>
stack<elementType> st;
//例如: stack<int> st;

使用list作为基础容器的stack适配器

stack<int, list<int>> st;

可以用一个基础容器来初始化 stack 适配器,只要该容器的类型和 stack 底层使用的基础容器类型相同即可。

list<int> name;
stack<int, list<int>> st(name);
成员函数 功能
empty() 当 stack 栈中没有元素时,该成员函数返回 true;反之,返回 false。
size() 返回 stack 栈中存储元素的个数。
top() 返回一个栈顶元素的引用,类型为 T&。如果栈为空,程序会报错。
push(const T& val) 先复制 val,再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj) 以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop() 弹出栈顶元素。
emplace(arg…) arg… 可以是一个参数,也可以是多个参数,但它们都只用于构造一个对象,并在栈顶直接生成该对象,作为新的栈顶元素。
swap(stack & other_stack) 将两个 stack 适配器中的元素进行互换,需要注意的是,进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

stack是没有迭代器的,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。

queue

和 stack 栈容器适配器不同,queue 容器适配器有 2 个开口,其中一个开口专门用来输入数据,另一个专门用来输出数据,如图所示。

queue容器适配器

queue 容器适配器和 stack 有一些成员函数相似,但在一些情况下,工作方式有些不同。

#include <queue>
queue<emelentType> que;
//例如: queue<int> que;

使用list作为基础容器的queue适配器

queue<int, list<int>> que;

可以用一个基础容器来初始化 queue 适配器,只要该容器的类型和 queue 底层使用的基础容器类型相同即可。

list<int> name;
queue<int, list<int>> que(name);
成员函数 功能
empty() 如果 queue 中没有元素的话,返回 true。
size() 返回 queue 中元素的个数。
front() 返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
back() 返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
push(const T& obj) 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
emplace() 在 queue 的尾部直接添加一个元素。
push(T&& obj) 以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop() 删除 queue 中的第一个元素。
swap(queue &other_queue) 将两个 queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

和 stack 一样,queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。

priority_queue

priority_queue中文翻译叫优先级队列。而数据结构——堆(heap)是优先级队列的一种实现方法。

C++ STL priority_queue详解

priority_queue 容器适配器模拟的也是队列这种存储结构。但是,priority_queue 容器适配器中元素的存和取,遵循的并不是 “First in,First out”(先入先出)原则,而是“First in,Largest out”原则。指的就是先进队列的元素并不一定先出队列,而是优先级最大的元素最先出队列。

“First in,Largest out”原则是笔者为了总结 priority_queue 存取元素的特性自创的一种称谓,仅为了方便理解。

priority_queue 容器适配器模板位于头文件queue中,并定义在std命名空间中

#include <queue>
using namespace std;
priority_queue<int> prique; 
//等价于: priority_queue<int, deque<int>, less<int> > prique;
//其中第二个参数和第三个参数是默认参数

指定底层容器(默认deque)和优先级(默认less)规则:

  • 先指定容器,后指定规则,默认容器是deque
priority_queue<int, deque<int>, greater<int>> prque;
演示输出:217 219 359 417 438

//优先级规则:less<int>(默认) 或 greater<int>,第一个top返回优先级最高(元素为int时返回最大的元素)的元素
  • 基本类型
    priority_queue<int, deque<int>, greater<int>> prque;
    演示输出:217 219 359 417 438
    
  • pair类型
    priority_queue<pair<int, int> > a;
    a.push(pair<int, int>(1, 3));
    a.push(pair<int, int>(2, 3));
    a.push(pair<int, int>(1, 2));
    //输出结果 2 3, 1 3, 1 2
    
  • 结构体类型(创建自定义排序规则)
    //方法1
    struct tmp1 //运算符重载<
    {
      int x;
      tmp1(int a) {x = a;}
      bool operator<(const tmp1& a) const
      {
          return x < a.x; //大顶堆 
          //第一个元素小于第二个元素时,说明第二个元素优先级更高,输出时,top是第二个元素,因为top得到的是优先级最高的元素
      }
    };
    
    //方法2
    struct tmp2 //重写仿函数
    {
      bool operator() (tmp1 a, tmp1 b) 
      {
          return a.x < b.x; //大顶堆
          //同tmp1的运算符重载函数
      }
    };
    
    int main() 
    {
      //方法一
      priority_queue<tmp1> d;
      tmp1 a(1); tmp1 b(2); tmp1 c(3);
      d.push(b); d.push(c); d.push(a);
      while (!d.empty())
      {
          cout << d.top().x << ' ';
          d.pop();
      }
      cout << "\t";
    
      //方法二
      priority_queue<tmp1, deque<tmp1>, tmp2> f;
      f.push(c); f.push(b); f.push(a);
      while (!f.empty()) 
      {
          cout << f.top().x << ' ';
          f.pop();
      }
    }
    //输出结果 3 2 1  3 2 1
    
成员函数 功能
empty() 如果 priority_queue 为空的话,返回 true;反之,返回 false。
size() 返回 priority_queue 中存储元素的个数。
top() 返回 priority_queue 中第一个元素的引用形式。
push(const T& obj) 根据既定的排序规则,将元素 obj 的副本存储到 priority_queue 中适当的位置。
push(T&& obj) 根据既定的排序规则,将元素 obj 移动存储到 priority_queue 中适当的位置。
emplace(Args&&… args) Args&&… args 表示构造一个存储类型的元素所需要的数据(对于类对象来说,可能需要多个数据构造出一个对象)。此函数的功能是根据既定的排序规则,在容器适配器适当的位置直接生成该新元素。
pop() 移除 priority_queue 容器适配器中第一个元素。
swap(priority_queue& other) 将两个 priority_queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

和 queue 一样,priority_queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。

自定义比较函数

  • less<T>来定义大顶堆
  • greater<T>来定义小顶堆
  • 方式一:struct或class重载运算符()

    通过struct重载()操作符,定义了一个函数对象

    struct cmp{
     bool operator()(vector<int>&a,vector<int>&b){
         return a[0]>b[0];
     }
    };
    // 两者效果相同
    class cmp{
    public:
      bool operator()(vector<int>&a,vector<int>&b){
          return a[0]>b[0];
      }
    };
    priority_queue<vector<int>, vector<vector<int>>, cmp> q;//小顶堆
    
  • 方式二:对自定义的类型使用比较函数
    static type{
      int number;
      bool operator<(type & t){
          return number > t.number;
      }
    };
    priority_queue<type, vector<type>> q; //小顶堆
    
  • 方式三:定义函数

    首先定义一个比较函数

    bool cmp(vector<int>&a,vector<int>&b){
        return a[0]>b[0];
    }
    priority_queue<vector<int>,vector<vector<int>>,decltype(&cmp)> q(cmp);//小顶堆
    
  • 方式四:lambda表达式
    auto cmp=[](vector<int>&a,vector<int>&b)->bool{
              return a[0]>b[0];
          };
    priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆
    

其他容器

string

使用该类应包含string头文件,注意不是string.h

string.h是c语言风格字符串的处理函数,包含了常用的strlen,strcat,strncat等等

构造

  • string();默认构造函数,创建一个空字符串
  • string(const string& str);拷贝构造函数,使用一个string对象初始化另一个string对象
  • string(const char *s)含参构造函数,使用c风格字符串初始化string
  • string(int n, char c)含参构造函数,使用n个字符c初始化string

赋值

  • string & operator=(const string &s);将一个string对象赋值给当前字符串
  • string & operator=(const char *s);
  • string & operator=(const char c)字符赋值给当前字符串

成员函数assign

  • string & assign(const string & s)把字符串s赋给当前字符串
  • string & assign(const char *s)
  • string & assign(const char *s, int n)把c风格字符串s的前n给字符赋值给string对象
  • string & assign(int n, char c)把n给字符c赋给当前字符串
  • string & assign(const string & s, int start, int n)将字符串s中从start开始的n个字符赋值给string对象

存取

  • string & operator[](int n)通过[]下标方式获取字符

    使用下标操作符读取字符时,如果下标越界,程序会强行终止

  • char & at(int n)通过at方法读取字符

    使用at方法读取字符时,如果下标越界,程序会抛出异常

拼接

  • string & operator+=(const string & str)将字符串str追加到当前字符串末尾
  • string & operator+=(const char *str)
  • string & operator+=(const char c)将字符c追加到当前字符串末尾

成员函数

  • string & append(const string & s)将字符串s追加到当前字符串末尾
  • string & append(const char *s)
  • string & append(const char* s,int n)将字符串s前n个字符追加到当前字符串末尾
  • string & append(const string & str, int pos, int n)将str从pos位置开始的n个字符追加到当前字符串
  • string & append(int n, char c)在当前字符串中追加n个c字符

查找

成员函数(npos ​ -> no-position)

  • int find(const string& str, int pos=0)在当前字符串中查找str第一次出现的位置,pos为初始查找位置,默认为0
  • int find(const char * str, int pos=0)同上
  • int find(const char * str, int pos, int n)在当前字符串中查找str的前n个字符出现的位置,注意pos没有初始化值
  • int find(const char c, int pos = 0)在当前字符串查找字符c的第一次出现位置,pos为初始查找位置

当查找失败,find会返回-1,在string中,-1被封装为string静态成员常量string::npos

static const size_t npos = -1;

find方法查找子串第一次出现的位置,而rfind则是查找最后一次出现位置,与find不同点在于初始位置pos是npos,rfind当查找到时返回下标,查找不到时返回npos

替换

  • string & replace(int pos, int n, const string & str)替换从pos开始的n个字符为str
  • string & replace(int pos, int n, const char *str)

比较

  • int compare(const string &s)与字符串s进行比较
  • int compare(const char *s)

compare函数依靠字典序比较,在当前字符串比给定字符串小于返回-1,相等时返回0,当前字符串比给定字符串大时返回1

重载比较操作符

  • bool operator<(const string & str)bool operator<(const char *str)
  • bool operator<=(const string &str)bool operator<=(const char* str)
  • bool operator==(const string &str)bool operator==(const char* str)
  • bool operator>=(const string &str)bool operator>=(const char* str)
  • bool operator>(const string &str)bool operator>(const char* str)
  • bool operator!=(const string &str)bool operator!=(const char* str)

子串

  • string substr(int pos = 0, int n = npos)返回由pos开始的n个字符组成的字符串

插入

  • string & insert(int pos, const string& s)在pos位置插入字符串
  • string & insert(int pos, const char *s)
  • string & insert(int pos, int n, char c)在pos位置插入n个字符c

删除

  • void clear()清空string字符串
  • iterator erase(int pos, int n = npos)删除从pos位置开始的n个字符
  • iterator erase(iterator begin, iterator end)删除一个区间的字符
  • iterator erase(iterator p)删除迭代器指向的字符
  • iterator pop_back()删除字符串最后一个字符

bitset

bitset不是容器,是一个模板类,因此不支持迭代器的访问方式,bitset 模板类由若干个位(bit)组成,它提供一些成员函数,使程序员不必通过位运算就能很方便地访问、修改其中的任意一位。

bitset的大小是按照4字节的倍数来分配的,最小为4字节,即number长度为1-32时,当大于32,为八字节,以此类推

最重要的一点,我们知道计算机中数据的存储是使用补码的形式,使用规则

  • 正数 原码 = 反码 = 补码
  • 负数
    • 原码 = 在该数的绝对值上的原码,符号位设置为1
    • 反码 = 在原码基础上除符号位外,各位取反
    • 补码 = 在反码基础上+1

因此,对bitset对象赋值十进制数时,实际上是转换为对应的补码形式,并存储在bitset对象串中

#include <bitset>
bitset<number> bit;
//例如:bitset<32> bit;//其中number必须为整数

//对bit赋值
bit = 10; // bit = 0000 1010
//在c++中,10是十进制整型常量,赋值给bit会转换位对应二进制

bit[0] = 1 // bit = 0000 1011
//对bit某一个位进行修改时,用二进制的思想来想,其低位是0,也就是最右边

bit = -10 // bit = 1111 0110(补码形式)
//计算机中数据是以补码的形式存储

C++ bitset类详解 (biancheng.net)

常用函数有:

bitset 有许多成员函数,有些成员函数执行的就是类似于位运算的操作。bitset 成员函数列表如下:

设置

设置的位置pos,是以右边为0号元素左计数的

  • bitset <N> & set(); //将所有位全部设成 1
  • bitset <N> & set(size_t pos, bool val = true); //将第 pos 位设为 val
  • bitset <N> & reset(); //将所有位全部设成0
  • bitset <N> & reset (size_t pos); //将第 pos 位设成 0
  • bitset <N> & flip(); //将所有位翻转(0变成1,1变成0)
  • bitset <N> & flip(size_t pos);//翻转第 pos 位

转换

  • unsigned long to_ulong() const; //将对象中的0、1串转换成10进制整数
  • string to_string () const;//将对象中的0、1串转换成二进制字符串(Visual Studio 支持,Dev C++不支持)

统计

  • size_t count() const; //计算 1 的个数
  • size_t size () const; //返回总位数,也就是设置时给定的大小

其他

  • bool operator == (const bitset \<N\> & rhs) const;
  • bool operator != (const bitset \<N\> & rhs) const;
  • bool test(size_t pos) const; //测试第 pos 位是否为 1**
  • bool any() const; //判断是否存在某一位为1
  • bool none() const; //判断是否全部为0

访问元素

  • reference operator[] (size_t pos); //返回对第 pos 位的引用
  • bool operator[] (size_t pos) const; //返回第 pos 位的值
  • reference at(size_t pos); //返回对第 pos 位的引用
  • bool at (size_t pos) const; //返回第 pos 位的值

位操作

  • bitset <N> & operator &= (const bitset <N> & rhs); //和另一个 bitset 对象进行与操作
  • bitset <N> & operator |= (const bitset <N> & rhs); //和另一个 bitset 对象进行或操作
  • bitset <N> & operator ^= (const bitset <N> & rhs); //和另一个 bitset 对象进行异或操作
  • bitset <N> & operator <<= (size_t num); //左移 num 位
  • bitset <N> & operator >>= (size_t num); //右移 num 位
  • bitset <N> operator ~ (); //返回取反后的结果
  • bitset <N> operator << (size_t pos) const; //返回左移 pos 位后的结果
  • bitset <N> operator >> (size_t pos) const; //返回右移 pos 位后的结果
  • bitset <N> operator & (const bitset <N> & rhs) const; //返回和另一个 bitset 对象 进行与运算的结果
  • bitset <N> operator | (const bitset <N> & rhs) const; //返回和另一个 bitset 对象 进行或运算的结果
  • bitset <N> operator ^ (const bitset <N> & rhs) const; //返回和另一个 bitset 对象进行异或运算的结果

容器时间复杂度对比

容器名 特点 插入 删除 查找
set、multiset、map、multimap 底层实现是红黑树,键值有序,set 和 map 键不可重复,而 multiset 和 multimap 可重复; O(logN) O(logN) O(logN)
unordered_set,unordered_map,unordered_multiset,unordered_multimap 底层实现是哈希表,键值无序,unordered_set 和 unordered_map 键不可重复,而另外两个可以重复; 平均O(1),最坏O(N) 平均O(1),最坏O(N) 平均O(1),最坏O(N)
vector 底层实现是数组,动态成倍扩容 push_back(),O(1);insert(),O(N) pop_back(),O(1);erase(),O(N) O(1)
list 底层实现双向链表 push_front(),O(1);push_back(),O(1);insert(),O(1) pop_front(),O(1);pop_back(),O(1);erase(),O(1) O(N)
deque 底层是分段连续的线性空间,它是一种具有队列和栈的性质的数据结构,其插入和删除操作限定在两端进行 push_front(),O(1);push_back(),O(1);insert(),O(N) pop_front(),O(1);pop_back(),O(1);erase(),O(N) O(1)
stack 底层实现一般用 list 或 deque,封闭头部即可,数据先进后出,不支持随机访问 O(1) O(1) (取栈顶)O(N)
queue 底层实现一般用 list 或 deque,数据先进先出,不支持随机访问 O(1) O(1) (取队头)O(1)
priority_queue 底层用堆实现,队列中各个元素被赋予优先级 O(logN) O(logN) (取堆顶)O(1)
作者:WuQiling
文章链接:https://www.wqlblog.cn/cpp-stl/
文章采用 CC BY-NC-SA 4.0 协议进行许可,转载请遵循协议
暂无评论

发送评论 编辑评论


				
默认
贴吧
上一篇
下一篇