【C++基础】第五十一课:[顺序容器]容器库概览

容器操作,iterator,const_iterator,size_type,difference_type,构造函数,赋值,swap,size(),max_size(),empty(),关系运算符,获取迭代器

Posted by x-jeff on September 9, 2022

【C++基础】系列博客为参考《C++ Primer中文版(第5版)》C++11标准)一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.容器库概览

容器类型上的操作形成了一种层次:

  • 某些操作是所有容器类型都提供的。
  • 另外一些操作仅针对顺序容器、关联容器或无序容器。
  • 还有一些操作只适用于一小部分容器。

本文将介绍对所有容器都适用的操作。

一般来说,每个容器都定义在一个头文件中,文件名与类型名相同。即,deque定义在头文件deque中,list定义在头文件list中,以此类推。容器均定义为模板类。例如对vector,我们必须提供额外信息来生成特定的容器类型。对大多数,但不是所有容器,我们还需要额外提供元素类型信息:

1
2
list<Sales_data> //保存Sales_data对象的list
deque<double> //保存double的deque

1.1.对容器可以保存的元素类型的限制

顺序容器几乎可以保存任意类型的元素。特别是,我们可以定义一个容器,其元素的类型是另一个容器。这种容器的定义与任何其他容器类型完全一样:在尖括号中指定元素类型(此种情况下,是另一种容器类型):

1
vector<vector<string>> lines; //vector的vector

较旧的编译器可能需要在两个尖括号之间键入空格,例如,vector<vector<string> >

虽然我们可以在容器中保存几乎任何类型,但某些容器操作对元素有其自己的特殊要求。我们可以为不支持特定操作需求的类型定义容器,但这种情况下就只能使用那些没有特殊要求的容器操作了。

例如,顺序容器构造函数的一个版本接受容器大小参数,它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器,但我们在构造这种容器时不能只传递给它一个元素数目参数:

1
2
3
//假定noDefault是一个没有默认构造函数的类型
vector<noDefault> v1(10, init); //正确:提供了元素初始化器
vector<noDefault> v2(10); //错误:必须提供一个元素初始化器

👉vector的值初始化

当后面介绍容器操作时,我们还会注意到每个容器操作对元素类型的其他限制。

2.迭代器

【C++基础】第十六课:迭代器

与容器一样,迭代器有着公共的接口:如果一个迭代器提供某个操作,那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。例如,标准容器类型上的所有迭代器都允许我们访问容器中的元素,而所有迭代器都是通过解引用运算符来实现这个操作的。类似的,标准库容器的所有迭代器都定义了递增运算符,从当前元素移动到下一个元素。

我们在这里列出了容器迭代器支持的所有操作,其中有一个例外不符合公共接口特点:forward_list迭代器不支持递减运算符(--)。在这里列出了迭代器支持的算术运算,这些运算只能应用于string、vector、deque和array的迭代器。我们不能将它们用于其他任何容器类型的迭代器(个人理解:因为list和forward_list的内存空间不连续,所以此处不适用)。

2.1.迭代器范围

迭代器范围的概念是标准库的基础。

一个迭代器范围(iterator range)由一对迭代器表示,两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置(one past the last element)。这两个迭代器通常被称为begin和end,或者是first和last(可能有些误导),它们标记了容器中元素的一个范围。

虽然第二个迭代器常常被称为last,但这种叫法有些误导,因为第二个迭代器从来都不会指向范围中的最后一个元素,而是指向尾元素之后的位置。迭代器范围中的元素包含first所表示的元素以及从first开始直至last(但不包含last)之间的所有元素。

这种元素范围被称为左闭合区间(left-inclusive interval),其标准数学描述为:

\[[ \text{begin}, \text{end} )\]

迭代器begin和end必须指向相同的容器。end可以与begin指向相同的位置(即空容器),但不能指向begin之前的位置。

对构成范围的迭代器的要求:

如果满足如下条件,两个迭代器begin和end构成一个迭代器范围:

  • 它们指向同一个容器中的元素,或者是容器最后一个元素之后的位置,且
  • 我们可以通过反复递增begin来到达end。换句话说,end不在begin之前。

⚠️编译器不会强制这些要求。确保程序符合这些约定是程序员的责任。

2.2.使用左闭合范围蕴含的编程假定

标准库使用左闭合范围是因为这种范围有三种方便的性质。假定begin和end构成一个合法的迭代器范围,则:

  • 如果begin与end相等,则范围为空
  • 如果begin与end不等,则范围至少包含一个元素,且begin指向该范围中的第一个元素
  • 我们可以对begin递增若干次,使得begin==end

这些性质意味着我们可以像下面的代码一样用一个循环来处理一个元素范围,而这是安全的:

1
2
3
4
while (begin != end) {
	*begin = val; //正确:范围非空,因此begin指向一个元素
	++begin; //移动迭代器,获取下一个元素
}

3.容器类型成员

每个容器都定义了多个类型,如表9.2所示。我们已经使用过其中三种:size_typeiteratorconst_iterator

除了已经使用过的迭代器类型,大多数容器还提供反向迭代器。简单地说,反向迭代器就是一种反向遍历容器的迭代器,与正向迭代器相比,各种操作的含义也都发生了颠倒。例如,对一个反向迭代器执行++操作,会得到上一个元素。我们会在后续博文中介绍更多关于反向迭代器的内容。

剩下的就是类型别名了,通过类型别名,我们可以在不了解容器中元素类型的情况下使用它。如果需要元素类型,可以使用容器的value_type。如果需要元素类型的一个引用,可以使用reference或const_reference。这些元素相关的类型别名在泛型编程中非常有用,我们将在后续博文中介绍相关内容。

为了使用这些类型,我们必须显式使用其类名:

1
2
3
4
//iter是通过list<string>定义的一个迭代器类型
list<string>::iterator iter;
//count是通过vector<int>定义的一个difference_type类型
vector<int>::difference_type count;

👉difference_type

4.begin和end成员

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。这两个迭代器最常见的用途是形成一个包含容器中所有元素的迭代器范围。

如表9.2所示,begin和end有多个版本:带r的版本返回反向迭代器;以c开头的版本则返回const迭代器:

1
2
3
4
5
list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin(); //list<string>::iterator
auto it2 = a.rbegin(); //list<string>::reverse_iterator
auto it3 = a.cbegin(); //list<string>::const_iterator
auto it4 = a.crbegin(); //list<string>::const_reverse_iterator

与const指针和引用类似,可以将一个普通的iterator转换为对应的const_iterator,但反之不行。

1
2
3
4
5
vector<int> v = {1,2,3,4};
auto a1 = v.rbegin();
cout << *++a1 << endl; //3
auto a2 = v.rend();
cout << *--a2 << endl; //1

5.容器定义和初始化

每个容器类型都定义了一个默认构造函数。除array之外,其他容器的默认构造函数都会创建一个指定类型的空容器,且都可以接受指定容器大小和元素初始值的参数。

5.1.将一个容器初始化为另一个容器的拷贝

将一个新容器创建为另一个容器的拷贝的方法有两种:可以直接拷贝整个容器,或者(array除外)拷贝由一个迭代器对指定的元素范围。

为了创建一个容器为另一个容器的拷贝,两个容器的类型及其元素类型必须匹配。不过,当传递迭代器参数来拷贝一个范围时,就不要求容器类型是相同的了。而且,新容器和原容器中的元素类型也可以不同,只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。

1
2
3
4
5
6
7
8
9
//每个容器有三个元素,用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors); //正确:类型匹配
deque<string> authList(authors); //错误:容器类型不匹配
vector<string> words(articles); //错误:容器类型必须匹配
//正确:可以将const char*元素转换为string
forward_list<string> words(articles.begin(), articles.end());

由于两个迭代器表示一个范围,因此可以使用这种构造函数来拷贝一个容器中的子序列。例如,假定迭代器it表示authors中的一个元素,我们可以编写如下代码:

1
2
//拷贝元素,直到(但不包括)it指向的元素
deque<string> authList(authors.begin(), it);

5.2.列表初始化

1
2
3
//每个容器有三个元素,用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

当这样做时,我们就显式地指定了容器中每个元素的值。对于除array之外的容器类型,初始化列表还隐含地指定了容器的大小:容器将包含与初始值一样多的元素。

5.3.与顺序容器大小相关的构造函数

除了与关联容器相同的构造函数外,顺序容器(array除外)还提供另一个构造函数,它接受一个容器大小和一个(可选的)元素初始值。如果我们不提供元素初始值,则标准库会创建一个值初始化器:

1
2
3
4
vector<int> ivec(10, -1); //10个int元素,每个都初始化为-1
list<string> svec(10, "hi!"); //10个string,每个都初始化为"hi!"
forward_list<int> ivec(10); //10个元素,每个都初始化为0
deque<string> svec(10); //10个元素,每个都是空string

如果元素类型是内置类型或者是具有默认构造函数的类类型,可以只为构造函数提供一个容器大小参数。如果元素类型没有默认构造函数,除了大小参数外,还必须指定一个显式的元素初始值。

⚠️只有顺序容器的构造函数才接受大小参数,关联容器并不支持。

5.4.标准库array具有固定大小

内置数组一样,标准库array的大小也是类型的一部分。当定义一个array时,除了指定元素类型,还要指定容器大小:

1
2
array<int, 42> //类型为:保存42个int的数组
array<string, 10> //类型为:保存10个string的数组

为了使用array类型,我们必须同时指定元素类型和大小:

1
2
array<int, 10>::size_type i; //数组类型包括元素类型和大小
array<int>::size_type j; //错误:array<int>不是一个类型

由于大小是array类型的一部分,array不支持普通的容器构造函数。这些构造函数都会确定容器的大小,要么隐式地,要么显式地。而允许用户向一个array构造函数传递大小参数,最好情况下也是多余的,而且容易出错。

array大小固定的特性也影响了它所定义的构造函数的行为。与其他容器不同,一个默认构造的array是非空的:它包含了与其大小一样多的元素。这些元素都被默认初始化,就像一个内置数组中的元素那样。如果我们对array进行列表初始化,初始值的数目必须等于或小于array的大小。如果初始值数目小于array的大小,则它们被用来初始化array中靠前的元素,所有剩余元素都会进行值初始化。在这两种情况下,如果元素类型是一个类类型,那么该类必须有一个默认构造函数,以使值初始化能够进行:

1
2
3
array<int, 10> ia1; //10个默认初始化的int
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; //列表初始化
array<int, 10> ia3 = {42}; //ia3[0]为42,剩余元素为0

‼️值得注意的是,虽然我们不能对内置数组类型进行拷贝或对象赋值操作,但array并无此限制:

1
2
3
4
int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; //错误:内置数组不支持拷贝或赋值
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; //正确:只要数组类型匹配即合法

与其他容器一样,array也要求初始值的类型必须与要创建的容器类型相同。此外,array还要求元素类型和大小也都一样,因为大小是array类型的一部分。

6.赋值和swap

表9.4中列出的与赋值相关的运算符可用于所有容器。赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝:

1
2
c1 = c2; //将c1的内容替换为c2中元素的拷贝
c1 = {a,b,c}; //赋值后,c1大小为3

第一个赋值运算后,左边容器将与右边容器相等。如果两个容器原来大小不同,赋值运算后两者的大小都与右边容器的原大小相同。第二个赋值运算后,c1的size变为3,即花括号列表中值的数目。

1
2
3
4
5
array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 5> a2 = {0,1,2,3,4};
array<int, 10> a3 = {0};
a2 = a1; //错误:大小不一样
a3 = a1; //正确:a3为{0,1,2,3,4,5,6,7,8,9}

6.1.使用assign(仅顺序容器)

赋值运算符要求左边和右边的运算对象具有相同的类型。它将右边运算对象中所有元素拷贝到左边运算对象中。顺序容器(array除外)还定义了一个名为assign的成员,允许我们从一个不同但相容的类型赋值,或者从容器的一个子序列赋值。assign操作用参数所指定的元素(的拷贝)替换左边容器中的所有元素。例如,我们可以用assign实现将一个vector中的一段char*值赋予一个list中的string:

1
2
3
4
5
list<string> names;
vector<const char*> oldstyle;
names = oldstyle; //错误:容器类型不匹配
//正确:可以将const char*转换为string
names.assign(oldstyle.cbegin(), oldstyle.cend());

由于其旧元素被替换,因此传递给assign的迭代器不能指向调用assign的容器。

assign的第二个版本接受一个整型值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素:

1
2
3
4
//等价于slist1.clear();
//后跟slist1.insert(slist1.begin(), 10, "Hiya!");
list<string> slist1(1); //1个元素,为空string
slist1.assign(10, "Hiya!"); //10个元素,每个都是"Hiya!"

6.2.使用swap

swap操作交换两个相同类型容器的内容。调用swap之后,两个容器中的元素将会交换:

1
2
3
vector<string> svec1(10); //10个元素的vector
vector<string> svec2(24); //24个元素的vector
swap(svec1, svec2);

调用swap后,svec1将包含24个string元素,svec2将包含10个string。除array外,交换两个容器内容的操作保证会很快—元素本身并未交换,swap只是交换了两个容器的内部数据结构。

这里交换两个容器的内部数据结构是指交换容器中各元素的内存地址,并不是交换各个元素变量所存储的值。

除array外,swap不对任何元素进行拷贝、删除或插入操作,因此可以保证在常数时间内完成。

元素不会被移动的事实意味着,除string外,指向容器的迭代器、引用和指针在swap操作之后都不会失效。它们仍指向swap操作之前所指向的那些元素。但是,在swap之后,这些元素已经属于不同的容器了。例如,假定iter在swap之前指向svec1[3]的string,那么在swap之后它指向svec2[3]的元素。与其他容器不同,对一个string调用swap会导致迭代器、引用和指针失效。

因为string存储的是字符串,在string变量中真正存储字符串的是一个叫_Ptr的指针,它指向string所存储的字符串首地址,而字符串并没有固定地址,而是存储在一个临时内存区域中,所以当字符串发生改变时,会发生内存的重新分配,所以会导致迭代器、引用和指针失效。

与其他容器不同,swap两个array会真正交换它们的元素。因此,交换两个array所需的时间与array中元素的数目成正比。

因此,对于array,在swap操作之后,指针、引用和迭代器所绑定的元素保持不变,但元素值已经与另一个array中对应元素的值进行了交换(这点和其他顺序容器不同,见下述例子)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
using namespace std;
int main()
{
    array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
    array<int, 5> a2 = {10,11,12,13,14};
    array<int, 5> a3 = {0,1,2,3,4};
    vector<int> v1 = {0,1,2};
    vector<int> v2 = {9,8,7,6};
    int* p1 = &a1[0];
    int* p2 = &v1[0];
    int* p3 = &a2[0];
    swap(a1,a2); //错误:交换的两个array必须元素数目一样
    swap(a2,a3); //正确
    cout << *p3 <<endl; //输出0
    swap(v1,v2);
    cout << *p2 <<endl; //输出0,注意和array的不同,指针也会随着被交换
}

在新标准库中,容器既提供成员函数版本的swap,也提供非成员版本的swap。而早期标准库版本只提供成员函数版本的swap。非成员版本的swap在泛型编程中是非常重要的。统一使用非成员版本的swap是一个好习惯。

1
2
3
4
5
//之前的例子都是非成员版本的swap
//这里给出成员函数版本的swap
vector<int> v1 = {0,1,2};
vector<int> v2 = {9,8,7,6};
v1.swap(v2);

7.容器大小操作

除了一个例外,每个容器类型都有三个与大小相关的操作:

  1. 成员函数size返回容器中元素的数目;
  2. empty当size为0时返回布尔值true,否则返回false;
  3. max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。
1
2
3
4
5
6
7
vector<int> v1 = {0,1,2};
vector<int> v2 = {0,1,2,3,4};
cout << v1.size() << endl; //输出:3
cout << v2.size() << endl; //输出:5
cout << v1.max_size() << endl; //输出:4611686018427387903
cout << v2.max_size() << endl; //输出:4611686018427387903
//从这个例子可以看出max_size返回的是vector<int>所能容纳的最大的int型元素的数目

⚠️forward_list支持max_size和empty,但不支持size。

8.关系运算符

每个容器类型都支持相等运算符(==!=);除了无序关联容器外的所有容器都支持关系运算符(>>=<<=)。关系运算符左右两边的运算对象必须是相同类型的容器,且必须保存相同类型的元素。即,我们只能将一个vector<int>与另一个vector<int>进行比较,而不能将一个vector<int>与一个list<int>或一个vector<double>进行比较。

比较两个容器实际上是进行元素的逐对比较。这些运算符的工作方式与string的关系运算符类似:

  • 如果两个容器具有相同大小且所有元素都两两对应相等,则这两个容器相等;否则两个容器不等。
  • 如果两个容器大小不同,但较小容器中每个元素都等于较大容器中的对应元素,则较小容器小于较大容器。
  • 如果两个容器都不是另一个容器的前缀子序列,则它们的比较结果取决于第一个不相等的元素的比较结果。
1
2
3
4
5
6
7
8
vector<int> v1 = {1,3,5,7,9,12};
vector<int> v2 = {1,3,9};
vector<int> v3 = {1,3,5,7};
vector<int> v4 = {1,3,5,7,9,12};
v1 < v2 //true
v1 < v3 //false
v1 == v4 //true
v1 == v2 //false

8.1.容器的关系运算符使用元素的关系运算符完成比较

只有当其元素类型也定义了相应的比较运算符时,我们才可以使用关系运算符来比较两个容器。

容器的相等运算符实际上是使用元素的==运算符实现比较的,而其他关系运算符是使用元素的<运算符。如果元素类型不支持所需运算符,那么保存这种元素的容器就不能使用相应的关系运算。例如,我们之前定义的Sales_data类型并未定义==<运算。因此,就不能比较两个保存Sales_data元素的容器:

1
2
vector<Sales_data> storeA, storeB;
if (storeA < storeB) //错误:Sales_data没有<运算符

9.参考资料

  1. 为何string调用swap导致迭代器失效