数组

数组的特点

• 数组是存放相同类型对象的容器，这些对象没有名字，需要通过其所在位置访问。
• 数组的大小固定不变，在定义时就为其开辟了固定的存储空间，因此不能随意向数组中添加元素，也不能缩减数组所占的存储空间。
• 因为数组的大小固定，所以损失了一部分灵活性，但性能相对来说更高。

数组的定义和初始化

数组的定义

数组的定义方式如a[n]，其中a为数组名，n为数组中元素个数，因此n必须大于0。数组中元素的个数在编译的时候必须是已知的，因此n必须是一个常量表达式。如

1

int arr[10];

合法，而

1

string str[get_size()];

仅在函数get_size为constexpr函数时合法。

此外，定义数组时不允许使用auto关键字。

数组的初始化

和内置类型的变量一样，当定义了内置类型的数组时，其所有元素的值被默认初始化（即在全局作用域中所有元素为0，在函数作用域中函数值为无意义的随机值）。

除默认初始化外，数组支持手动初始化，具体方式为列表初始化：

1

int a[3] = {1, 2, 3};

如果使用列表初始化的方式，允许不提供数组的大小：

1

int a[] = {1, 2, 3};

总而言之其实就是在编译时就要能够确定数组元素个数，无论是使用列表初始化还是用常量表达式指定元素个数，都是为了这一目的。

如果列表初始化时提供的值的个数与指定的数组元素个数不一致：

• 初始化提供的值多了，不合法。
• 初始化提供的值少了，那么使用提供的值初始化数组前几个元素，其余元素依然使用默认初始化的方式。

字符串的初始化

对于普通的字符数组，只是普通数组中存放的对象都是字符罢了。而如果希望字符数组作为字符串来使用，那么必须要注意字符串结束符'\0'的存储。

如果使用列表初始化的方法初始化一个字符串，应当显式地指定结束符'\0'：

1

char str[] = {'C', '+', '+', '\0'};

此外C++提供了更方便的初始化方式，这时不用显式地指定结束符：

1

char str[] = "C++";

而在这样初始化时，一定要注意显式指定数组长度时要考虑到结束符，如下面这样就是错误的，没有给结束符预留空间：

1

char str[3] = "C++";

如果把长度改为大于或等于4的值，就可以编译通过。

复杂的数组定义

对于以下较难理解的复杂的数组定义：

1
2
3
4

int *ptrs[10];
int (*Parray)[10] = &arr;
int (&arrRef)[10] = arr;
int *(&arry)[10] = ptrs;

ptrs是一个有10个元素的整型指针构成的数组（指针的数组），而Parray是一个指向具有十个整型元素的数组的指针（数组的指针）。

对于后两个，可以使用从内向外解读的方法，&arrRef代表arrRef是个引用，而后面[10]代表了引用的是具有10个整型元素的数组；&arry代表arry是个引用，引用的也是10个元素的数组，但是数组元素的类型为整型指针，也就是int *。

访问数组元素

访问数组元素通过下标来实现，一个具有n个元素的数组，其下标范围为0~n-1。

我们通常可以定义一个int i作为下标搭配for循环来用于迭代数组，而另一种做法为定义一个size_t类型的变量作为下标用于迭代数组，size_t是一种机器相关的无符号类型，它被设计得足够大以便能表示内存中任意对象的大小。在cstddef头文件中定义了size_t类型，使用时需要引用该头文件。

对于C++11标准，有更加简洁的遍历数组的方式，也就是范围for语句：

1
2
3

for(auto i : scores)
    cout<< i <<" ";
cout <<endl;

这样的话当仅仅是使用数组元素时，我们就不用过多关心下标是否越界了，不需要主动地控制下标。

指针和数组

数组与指针的关系

对数组的元素使用取地址运算符可得到该数组元素的地址，而数组名本身即为数组首元素的地址，即使用数组名即为使用该数组对象的首地址。

因此在一些时候，对数组对象的操作实际上是指针的操作，如使用auto推断的时候：

1
2

int a[3];
auto ap = a;

此时推断得到的ap类型为int *，即整型指针。

使用指针迭代数组元素

由于数组a的名字就代表了数组首元素的地址，因此可以使用数组名称a进行指针自增自减运算来遍历数组元素，如：

1
2
3
4

int a[6] = {1, 2, 3, 4, 5, 6};
int *e = &a[5];
for(int *b = a; b != e; ++b)
    cout << *b << endl;

可以看到这样来进行边界控制较为麻烦，实际上C++11标准提供了获取数组首尾元素地址的解决方案：

1
2
3
4

int a[6] = {1, 2, 3, 4, 5, 6};
int *e = end(a), *b = begin(a) ;
for(int *i = b; i != e; ++i)
    cout << *i << endl;

对于指针来说，其运算类型比较有限，常用的有：

• 解引用，运算结果是引用的对象。
• 递增递减，运算结果是指针。
• 与整数相加，运算结果是指针。
• 两指针相减，运算结果是ptrdiff_t，实质是一种带符号整数，定义在cstddef标准库。

下标运算的实质

我们常常可以看到使用下标运算的方式来访问数组元素，如a[3]，但对于下标运算的实现原理实际是指针的数加和解引用运算，即a[i]将被展开成为*(a+i)，从而实现访问对应元素的操作。

有趣的是，我们利用这一原理，将a[3]写成3[a]也是合法的，即a[3]等价于3[a]，在编译器中完全能够编译通过并不会出现问题，原因就在于3[a]会被展开为*(3+a)，这与*(a+3)显然是等价的。

因此，下标运算实际上是支持负数下标的，如：

1
2
3

int a[6] = {1, 2, 3, 4, 5, 6};
int *p = &a[2];
cout  <<  p[-2] << endl;

此时输出的值为1，也就是p[-2]等价于*(p-2)，即a[0]。

以上特性（负数下标）只适用于内置数组，标准库中的其他容器并不适用。

C风格字符串

C风格字符串就是将字符串存储在数组中，并以结束符'\0'结尾的字符串，它们本质就是字符数组，因此使用起来有诸多不便，对它们的操作一般需要cstring标准库中提供的函数来进行，这些函数并不对传入的字符串的合法性作检查，需要我们自己来维护，这样有很多不方便的地方。

C++提供了string对象来作为字符串使用，它实际上是基于数组的抽象封装，使用起来更加方便灵活。

多维数组

严格地来说，C++并没有提供多维数组，所谓的多维数组，其实是数组的数组。

多维数组在初始化时可以使用分层嵌套的列表，或者一维列表，如：

1
2
3
4
5

int ia[3][4]= {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11}
};

就是使用分层嵌套的列表来初始化二维数组，这样看起来层次分明、容易读懂，而

1

int ia[3][4]= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };

也是可以完成初始化的，因为虽然多维数组在逻辑上是多维的，但在存储结构中仍然是线性存储的。

此外，多层嵌套的列表可以做到只初始化每行的一部分值，如：

1

int ia[3][4]= { { 0 }, { 4 }, { 8 } };

没有了嵌套的括号则相当于只初始化了第一行（前几个值）：

1

int ia[3][4]= {0, 2, 4, 8 };

其他的元素使用默认初始化的方式进行默认初始化。

在使用多维数组下标时，只需要牢记多维数组就是数组的数组就行了，而对于较为复杂的定义，如：

1
2

int ia[3][4];
int (&row)[4] = ia[0];

要像之前理解复杂的指针、引用定义一样由内而外地理解这条定义。也就是定义了一个变量row，首先这个变量是一个引用，然后它是一个四个元素数组的引用，ia是包含了三个长度为4的数组的数组，然后把row绑定到了ia的第一个数组上。

使用范围for循环访问多维数组也是一样的，把多维数组当成数组的数组就可以了，如：

1
2
3
4
5
6

size_t cnt = 0 ;
for(auto &row : ia)
    for (auto &col : row){
        col = cnt;
    ++cnt;
}

在这个例子中我们使用引用是因为我们要写数组元素，那么当我们不需要写数组元素的时候，还是要把除了最内层的临时变量以外的临时变量定义成引用，如：

1
2
3

for(const auto &row : ia)
    for (auto col : row)
        cout << col << endl;

原因是如果不定义为引用，那么auto推断出的类型会是指针，那么下一层的范围for就无法使用了。当直接使用多维数组的名字时，它也会被视为指针。但是要注意，除非指针指向最内层元素，否则定义指针时必须要注意指向的数组的形状，如：

1
2
3

int ia[3][4];
int (*p)[4] = ia;
&ia[2];

这里的指针p要定义为指向长度为4的数组的指针，因为对于二维数组来说，它的第一个元素是一个长度为4的数组，假如是一维数组，它的第一个元素就是一个int，因此不必考虑形状——也就是数组名字代表的指针指向它的第一个元素；指针本身隐含了指向的对象的长度信息，这样自增自减、数加类的指针运算才能正确使用。

使用指针来迭代多维数组的例子：

1
2
3
4
5

for (auto p = ia; p != ia + 3; ++p）{
    for (auto q = *p; q != *p +4; ++q)
        cout<< *q<< ' ';
    cout <<endl;
}

此外，想要简化数组类型的表示还可以使用类型别名：

1
2

using int_array = int[4];
typedef int int_array[4];

vector

vector简介

vector用于表示对象的集合，它本身也是个对象，因此vector也是容器。

vector与数组相同的地方有：

• 它们所能容纳的对象都必须是同一类型的。
• 每个对象都需要通过索引访问。

vector与数组有区别的地方是：

• 数组是内置的，vector需要引入标准库头文件才可以使用。
• vector是通过类模板实现的。
• 数组长度固定，操作不方便，使用复杂，vector长度可变，可以随意添加删除元素，并且有丰富的方法和函数对其进行操作。

vector的定义

首先，使用vector要先引入头文件：

1

#include<vector>

由于vector是通过模板类来实现的，因此需要使用模板类的定义方式来定义一个vector，即需要在类名称后使用尖括号提供类型名称，来定义vector对象：

1
2
3

vector<int> ivec;
vector<Sales_item> sales_vec;
vector<vector<string>> file;

其中最后一个例子定义了一个嵌套的vector，即file作为一个vector其存放的元素都是vector<string>对象。

vector是模板类而不是类型，因此一定要带有尖括号提供实例化的参数类型才能当类使用。

需要注意的是在早期C++标准中嵌套的vector定义时与C++11有所不同，在新标准中可以使用上例中的定义方式，而在早期标准中，定义类型时最后两个右尖括号中间要有一个空格，即：

1

vector<vector<string> > file;

初始化vector

模板类规定了它本身的初始化方式，vector的初始化方式主要有以下几种：

• vector<T> v1：默认初始化，v1是一个指定类型的空vector。
• vector<T> v2(v1)：v2中包含有v1所有元素的副本。
• vector<T> v2 = v1：等价于v2(v1)，v2中包含有v1所有元素的副本。
• vector<T> v3(n, val)：v3包含了n个重复的元素，每个元素的值都是val。
• vector<T> v4(n)：v4包含了n个重复地执行了值初始化的对象。
• vector<T> v5{a,b,c…}：v5包含了初始值个数的元素，每个元素被赋予相应的初始值。
• vector<T> v5 = {a,b,c…}：等价于v5{a,b,c…}。
• vector<T> v6(begin(arr),end(arr))：使用数组初始化vector，只需提供数组的首地址和尾后地址。

最常见的方式就是先定义一个空vector，然后当运行时获取到元素的值后再逐一添加。

在使用一个vector来初始化另一个vector时，它们中的元素类型必须相同。

第五种初始化方式只提供了vector内元素的数量而没有指定值，这时采用的是值初始化的方式，而不是默认初始化的方式，默认初始化得到的值是随机的，值初始化则是固定的初始值：

• 当vector内元素为内置类型时，值初始化为0。
• 当vector内元素为其他对象时，调用该对象所属类规定的默认初始化方法，但是当该类型不支持默认初始化时，这种方法就不能用了。

此外，当使用列表初始化失败时，编译器会尝试将列表中提供的值作为参数来初始化，如

1
2
3
4
5

vector<string> v1{"hi"};
vector<string> v2("hi");
vector<string> v3{10};
vector<string> v4{10, "hi"};
vector<string> v5{v1};

中v2是非法的，v1成功执行了列表初始化，v3和v4、v5列表初始化没有成功但是将列表内的值作为初始化参数进行初始化成功了，它们其实等价于

1
2
3

vector<string> v3(10);
vector<string> v4(10, "hi");
vector<string> v5(v1);

向vector中添加对象

向尾端添加元素

对于vector对象，我们可以使用push_back成员函数将一个对象加入到vector的末尾，这时的vector就可以像一个栈一样使用。

在实际使用时我们往往就是创建一个空的vector，再通过这样的方法将需要的对象插入到其中：

1
2
3

vector<int> v2;
for (int i = 0; i != 100; ++i)
    v2.push_back(i);

对vector添加元素时的注意事项

• 由于vector在定义时不显式地指定初始值列表，而是通常使用一个for循环来将值依次插入vector，因此要求在编程时所写的循环准确无误，尤其是vector的大小可能被改变时，使用循环来操作vector很容易出现逻辑错误。
• 如果在循环体内有添加元素的操作时，不能使用范围for循环，或者说在范围for循环中不应改变其所遍历的序列的大小。

其他vector操作

检查vector的尺寸

与vector尺寸有关的两个成员函数主要为empty和size：

empty检查vector对象是否包含元素然后返回一个布尔值；size则返回vector对象中元素的个数，返回值的类型是由vector定义的size_type类型，它实际上是个无符号的整型（注意区别数组下标）。

要使用size_type，需首先指定它是由哪种类型定义的，vector对象的类型总是包含着元素的类型：

1

vector<int>::size_type

vector的比较

两个vector对象相等的条件是：两个vector的长度相等并且对应位置上的元素也相等。

两个vector进行比较是按照字典序比较的：

• 如果一个vector1的所有元素与另一个vector2的前一部分元素完全相同，且1和2的长度不同（即1比2短），那么vector1<vector2。
• 如果两个vector在同一位置有不同的元素，那么它们的大小取决于它们第一对不同元素的大小。

此外，vector的比较还包含了一个隐含的条件：vector中的元素能够比较时，vector才能比较。

vector的下标运算

和数组一样，vector的下标从0开始，可以直接通过下标来访问对应位置上的元素或赋值，下标的数据类型也是对应元素类型的size_type类型。

在使用下标时要保证不能下标越界。

此外，不能使用下标形式添加元素。

对vector赋值

用v2中元素的拷贝替换v1中的元素：

1

v1 = v2;

用列表中元素的拷贝替换v1中的元素：

1

v1 = {a, b, c, ……};

string

使用string

标准库类型string表示可变长的字符序列，使用string类型必须首先包含string头文件。作为标准库的一部分，string定义在命名空间std中。

对string的初始化主要有以下几种类型：

• string s1：默认初始化，s1是一个空串。
• string s2(s1)：s2是s1的副本。
• string s2 = s1：等价于s2(s1)，s2是s1的副本。
• string s3 ("value")：s3是字面值"value"的副本，除了字面值最后的那个空字符外。
• string s3 = "value"：等价于s3 ("value")，s3是字面值"value"的副本。
• string s4(n,'c')：把s4初始化为由连续n个字符c组成的串。

使用等号的是拷贝初始化，不使用等号的是直接初始化。

string操作

与vector相同的操作：

• 检查string的长度：size和empty成员函数。
• 索引访问、赋值。
• 拷贝副本。
• 两个字符串比较。

string独有的操作：

• getline(is, s)：从输入流is中读取一行赋给s，返回is。
• s1+s2：字符串连接，返回连接后的结果，此外+=运算符也是支持的。

注意：使用getline函数读入字符串时将读取一行，遇到换行符停止；而使用cin读取时，和C语言中使用scanf一样，遇到空白符停止。其中换行符和空白符均不会被读入。此外，使用cin读取时，开头的空白符也会被忽略，就像对字符串使用了strip一样。

和vector一样，string的size成员函数返回的类型也是对应的size_type类型，即string::size_type。

字符串相加时可以让string和字面值相加，但不能让字面值和字面值相加。

处理string中的字符

判断字符的类别

cctype头文件提供了一系列判断和处理字符类别的函数，主要有：

• isalnum(c)：当c是字母或数字时为真。
• isalpha(c)：当c是字母时为真。
• iscntrl(c)：当c是控制字符时为真。
• isdigit(c)：当c是数字时为真。
• isgraph(c)：当c不是空格但可打印时为真。
• islower(c)：当c是小写字母时为真。
• isprint(c)：当c是可打印字符时为真（即c是空格或c具有可视形式）。
• ispunct(c)：当c是标点符号时为真（即c不是控制字符、数字、字母、可打印空白中的一种）。
• isspace (c)：当c是空白时为真（即c是空格、横向制表符、纵向制表符、回车符、换行符、进纸符中的一种）。
• isupper(c)：当c是大写字母时为真。
• isxdigit(c)：当c是十六进制数字时为真。
• tolower(c)：如果c是大写字母，输出对应的小写字母，否则原样输出c。
• toupper(c)：如果c是小写字母，输出对应的大写字母，否则原样输出c。

迭代string中的字符

通常情况下，使用范围for语句来迭代string中的字符是很方便的，但是如果需要改变字符的值，在使用范围for语句时需要将临时变量定义为引用：

1
2
3
4

string s ("Hello World! !!");
for (auto &c : s)
    c = toupper(c);
cout << s << endl;

而当只需要处理字符串中的一部分字符时，使用下标来访问或者使用迭代器是更好的选择。使用下标访问的时候同样需要注意控制边界。

混用string对象与C风格字符串

实际上字符串字面值也是C风格字符串，在编译程序时，编译器会为字面值开辟一个大小恰好合适的字符数组（临时区域）来存放这个字符串，并且该字面值实际上是这个字符数组的首地址。

（1）为了能从一个C风格字符串得到string对象，允许使用C风格字符串来初始化string对象：

1

string s ("Hello World" );

（2）为了能从string对象中得到其对应的字符数组，string提供了成员函数c_str：

1

const char *str = s.c_str();

（3）允许string与C风格字符串进行相加（连接）。

迭代器

使用迭代器

由于容器是一个经过了封装的对象，因此无法使用指针。类比使用指针迭代数组，标准库提供了使用迭代器，可以像使用指针一样来迭代容器对象。所有的标准库容器都支持迭代器。

我们知道，通过begin和end函数可以获得数组的首指针和尾后指针，而通过容器对象的begin和end方法，也可以得到该容器的首迭代器和尾后迭代器。

以vector来举例：vector的迭代器的类型应当是vector<T>::iterator，因此我们可以这样来定义迭代器：

1
2

vector<int>::iterator it;
string::iterator it2;

除了iterator之外，还有const_iterator类型：

1
2

vector<int>::const_iterator it3;
string::const_iterator it4;

就像常量指针一样，const_iterator是常量迭代器，它指向的对象是只读的，不可以修改，而iterator对象指向的对象可读也可写。与const_iterator配套的成员函数cbegin和cend返回的是常量迭代器。

就像使用指针一样，迭代器也可以用*来解引用得到其指向的对象，同时也可使用自增自减运算符来移动迭代器指向的位置，这样就可以实现对容器的迭代：

1
2

for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
    *it= toupper(*it); 

对于迭代器指向的对象，要想使用其成员变量或成员函数，可以像使用指针一样使用指针成员访问运算符（->）。

迭代器运算

自增自减运算

可以通过自增运算符++和自减运算符–来推移迭代器的位置，每次移向上一个元素或下一个元素。

数加运算

自增自减运算符一次只能推移一个位置，而数加运算一次可以推移多个位置：

1
2

it = it + n;
it = it - n;

其中n为整数。当然也可以表示为以下形式：

1
2

it += n;
it -= n;

相减运算

可以计算两个迭代器相差的元素个数，如：

1

n = it1 - it2;

在此基础上可以实现迭代器的算术运算，如在二分查找时常常能够这样：

1
2

auto beg = text.begin() , end = text.end () ;
auto mid = text.begin () + (end - beg)/2;

比较运算

两个对同一对象的迭代器可以进行比较，支持的比较运算有>、>=、<、<=、==、!=等。

通过比较运算可以实现边界的判断等。

如果一个容器对象为空，那么它的首迭代器和尾后迭代器是相等的。