《C++ Primer》第3章 字符串、向量和数组（下）

3.4 迭代器介绍

除了下标运算符，迭代器也可以访问string对象的字符或vector对象的元素。

所有标准库容器都可以使用迭代器，但只有vector等少数容器支持下标运算符。

string对象不属于容器，但string支持迭代器等很多与容器类型类似的操作。

迭代器可以实现对对象的间接访问。

迭代器分为有效和无效。有效的迭代器指向某个元素或容器中尾元素的下一位置，其他的都是无效迭代器。

3.4.1 使用迭代器

有迭代器的类型同时拥有能够返回迭代器的成员。这些类型都拥有名为begin和end的成员。begin返回指向第一个元素的迭代器；end返回指向尾元素下一位置的迭代器，这个迭代器称为尾后迭代器。

迭代器运算符

如果两个迭代器指向的元素相同或都是同一个容器的尾后迭代器，则它们相等，否则不相等。

标准容器迭代器的运算符：

*iter          //返回迭代器iter所指的元素的引用
iter->mem    //解引用iter并获取该元素名为mem的成语，等价于(*iter).mem
++iter       //令iter指向容器内下一个元素
--iter        //指向容器内上一个元素
iter1 == iter2  //判断相等
iter1 != iter2

执行解引用的迭代器必须合法并确实指示着某个元素，解引用非法迭代器或尾后迭代器都是未被定义的行为。

将迭代器从一个元素移动到另外一个元素

注意：因为end返回的迭代器并不实际指示某元素，所以不能对其进行递增或解引用操作。

在for循环中使用！=来进行判断，而非<。

这是因为这种编程风格在标准库提供的所有容器上都是有效的。

所有标准库容器都定义了==和！=，但大多数没有定义<运算符。

要养成使用迭代器和！=的习惯。

迭代器类型

拥有迭代器的标准库类型使用iterator和const_iterator来表示迭代器的类型。

vector<int>::iterator it; //it能读写vector<int>的元素
string::iterator it2;     //it2能读写string对象中的字符

iterator的对象可读可写。

vector<int>::const_iterator it3;   //it3只能读元素，不能写元素
string::const_iterator it4;       //it4只能读字符，不能写字符

const_iterator的对象能读不能写。

begin和end运算符

begin和end返回的具体类型由对象是否是常量决定。如果对象是常量，则返回const_iterator；如果对象不是常量，则返回iterator。

vector<int> v;
const vector<int> cv;
auto it1 = v.begin();  //it1为vector<int>::iterator类型
auto it2 = cv.begin(); //it2为vector<int>::const_iterator类型

如果非常量类型想得到const_iterator呢？为了专门得到const_iterator，C++11新标准引入了cbegin和cend。

auto it3 = v.cbegin(); //it3的类型是vector<int>::const_iterator

无论对象本身是不是常量，cbegin和cend都返回const_iterator。

结合解引用和成员访问操作

通过迭代器访问对象的成员，有以下两种方式。

<stron>：先解引用，再执行点运算符访问成员</stron>

(*it).empty()     //注意圆括号必不可少

箭头运算符：把解引用和成员访问两个操作结合起来了。

it->empty()     

某些对vector对象的操作会使迭代器失效

vector对象可以动态增长，但也有限制：

1. 不能在范围for中向vector对象添加元素。
2. 任何一种可能改变vector对象容量的操作，比如push_back，都会使该对象的迭代器失效。

谨记：但凡是使用了迭代器的循环体，都不要向迭代器所属容器中添加元素。

3.4.2 迭代器运算

string和vector的迭代器提供了额外的运算符：

iter + n
iter - n
iter += n
iter -= n
iter1 - iter2     //两个迭代器相减的结果是它们之间的距离
>, >=, <, <=

迭代器的算术运算

auto mid = vi.begin() + vi.size()/2;  //mid将指向vi的中间位置的元素

string和vector的迭代器还可以使用关系运算符（<,<=,>,>=)进行比较。要求参与比较的两个迭代器必须合法且指向的是同一个容器的元素（或尾元素的下一位置）。

两个迭代器相减所得结果是两个迭代器的距离，所谓距离是指右侧的迭代器向前移动多少位置就能追上左侧的迭代器，其类型名为difference_type的带符号整型数。string和vector都定义了difference_type，距离可正可负。

使用迭代器运算

//使用迭代器完成二分搜索
//text必须有序
//beg和end表示搜索的范围
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end-beg)/2;
while (mid != end && *mid != sought){
   
	if (sought < *mid)
		end = mid;
	else
		beg = mid + 1;
	mid = beg + (end - beg)/2;
}

3.5 数组

数组：与vector相似的是：数组也是存放类型相同的对象的容器，这些对象本身 没有名字，需要通过其位置访问。

​ 与vector不同的是：数组大小确定不变，不能随意向数组中添加元素。

如果不清楚元素的确切个数，请使用vector。

3.5.1 定义和初始化内置数组

数组是复合类型。其声明形如a[d]，a为数组名，d是数组维度。维度必须大于0.

维度也属于数组类型的一部分，编译时维度应为已知。

即 维度必须是常量表达式。

unsigned cnt = 42;      //不是常量表达式
constexpr unsigned sz = 42; //是常量表达式
int arr[10];            //含有10个整数的数组
int *parr[sz];          //含有42个整型指针的数组
string bad[cnt];        //错误：cnt不是常量表达式
string strs[get_size()]; //当get_size()为constexpr时正确；否则错误

默认情况下，数组元素被默认初始化。

1. 与内置类型一样，如果在函数体内定义了某种内置类型的数组，那么默认初始化会使数组有未定义的值。
2. 不允许用auto关键字由初始值列表推断类型。
3. 数组的元素应为对象，所以不存在引用的数组。

显式初始化数组元素

可以对数组元素进行列表初始化，此时允许忽略数组维度。

int ia2[] = {
   0, 1, 2}; //含有3个元素的数组，元素值分别是0,1,2

如果没有声明维度，编译器会根据初始值数量计算并推测出来。如果声明了维度，那么初始值数量不能超过指定大小。

int a5[2] = {
   0,1,2};   //错误：初始值过多

如果维度比提供的初始值多，则用提供的初始值初始化靠前的元素，剩余元素默认初始化。

string a4[3] = {
   "hi", "ya"}; //等价于a4[3] = {"hi","ya", ""};
int a3[5] = {
   0, 1, 2}; //等价于a3[5] = {0, 1, 2, 0, 0};

字符数组的特殊性

字符数组额外的初始化形式：用字符串字面值初始化。

char a3[] = "C++";  //字符串字面值初始化，自动添加表示字符串结束的空字符\0
const char a4[6] = "Daniel"; //错误：没有空间存放空字符

一定要注意字符串字面值的结尾处还有一个空字符。

不允许拷贝和赋值

不能将数组的内容拷贝给其他数组作为其初始值，也不能用数组为其他数组赋值。

int a[] = {
   0, 1, 2};
int a2[] = a;  //错误
a2 = a;        //错误

有些编译器可能支持数组赋值，这属于编译器扩展。我们要避免使用这种非标准特性。

理解复杂的数组声明

数组可以存放大多数类型的对象，故可以定义存放指针的数组、数组的指针、数组的引用。

int *ptrs[10];           //ptrs是含有10个整型指针的数组
int &refs[10] = /*?*/;   //错误：不存在引用的数组
int (*Parray)[10] = &arr; //Parray是指针，指向一个含有10个整数的数组
int (&arrRef)[10] = arr; //arrRef是引用，绑定一个含有10个整数的数组
int *(&arry)[10] = ptrs; //arry是引用，绑定一个数组，该数组含有10个int型指针

要想理解数组声明的含义，最好的办法是从数组名字开始按照由内向外的顺序阅读。

3.5.2 访问数组元素

在使用数组下标时，通常将其定义为size_t类型。这是一种机器相关的无符号类型，在cstddef头文件中定义了它。

遍历string对象所有字符、vector对象所有元素、数组所有元素，最好的办法都是使用范围for语句。

检查下标的值

与vector和string一样，数组下标是否在合理范围之内由程序员负责检查，编译器不负责。

下标越界将导致缓冲区溢出错误。

3.5.3 指针和数组

数组特性：在很多用到数组名字的地方，编译器都会自动地将其替换成为一个指向数组首元素的指针。

string nums[] = {
   "one", "two", "three"};
string *p = &nums[0]; //p指向nums的第一个元素
string *p2 = nums; //等价于string *p2 = &nums[0]

在大多数表达式中，使用数组类型的对象其实使用一个指向该数组首元素的指针。

因此，在一些情况下，数组的操作其实是指针的操作。其中一个就是：使用auto推断数组的类型时，得到的是指针，而非数组。

int ia[] = {
   0, 1, 2, 3};
auto ia2(ia);      //ia2是一个指针，指向ia第一个元素
ia2 = 42;          //错误：不能用int值给指针赋值

必须指出：当使用decltype时，上述转换不会发生，decltype(ia)返回的类型是由4个整数构成的数组。

decltype(ia) ia3 = {
   4, 5, 6, 7};   //ia3是含有4个整数的数组

指针也是迭代器

string和vector的迭代器支持的运算，数组的指针全都支持。

其中获取尾后指针按如下操作：

int arr[] = {
   0,1,2};
int *e = &arr[3];    //e为指向arr尾元素下一位置的指针

标准库函数begin和end

为了更方便得到尾后指针，引入了begin和end函数。它们定义在iterator头文件中。

与vector和string的begin和end相区别，因为数组不是类类型，所以begin和end不是成员函数。

正确使用形式是把数组作为它们的参数：

int ia[] = {
   0, 1, 2};
int *beg = begin(ia);     //beg指向ia首元素
int *last = end(ia);      //last指向ia尾元素的下一位置

指针运算

指针加减一个整数得到一个新指针，新指针指向的元素与原指针相比向前或向后移动该整数值个位置。

注意：新指针不能超出数组的维度，否则将发生错误。

两个指针相减的结果的类型为ptrdiff_t，这是一种标准库类型，带符号，其定义在头文件cstddef中。

解引用和指针运算的交互

int ia[] = {
   0, 1, 2, 3};
int last = *(ia + 3); //last初始化为8，也就是ia[3]的值

下标和指针

string和vector的下标类型为其其各自的size_type，是无符号类型。

而数组用的是内置的下标运算符，其所用的索引不是无符号类型，可以处理负值，但是也要在数组合理范围内。

3.5.4 C风格字符串

尽管C++支持C风格字符串，但在C++中尽量不要用。

习惯用string代替char[]。

C风格字符串：存放在char数组中，并以空字符结束。

3.5.5 与旧代码的借口

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

任何出现字符串字面值的地方都可以用C风格字符串来替代：

• 允许使用C风格字符串初始化string对象或为string对象赋值。

• 在string对象的加法运算中允许其中一个运算对象是C风格字符串（不能两个都是）；

  允许在string对象复合赋值运算中以C风格字符串作为其右侧运算对象。

使用数组初始化vector对象

允许使用数组初始化vector对象。只需指明要拷贝区域的首元素地址及尾后地址即可。

int arr[] = {
   0, 1, 2, 3, 4, 5};
vector<int> ivec(arr+1, arr+4); //ivec中的元素值为1,2，3

现代C++程序应尽量使用vector和迭代器，避免使用内置数组和指针；

尽量使用string，避免使用C风格的基于数组的字符串。

3.6 多维数组

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

二维数组第一个维度为行，第二个维度为列。

多维数组的初始化

int ia[3][4] = {
      //3个元素，每个元素都是大小为4的数组
	{
   0, 1, 2, 3},  //第一行的初始值
	{
   4, 5, 6, 7},  //第二行的初始值
	{
   8, 9, 10,11}  //第三行的初始值
};             //内层嵌套的花括号非必需

int ia[3][4] = {
   {
   0}, {
   4}, {
   8}}; //初始化每行的首元素，其他元素默认初始化

int ia[3][4] = {
   0, 3, 6, 9};    //初始化第一行，其他元素默认初始化

使用范围for语句处理多维数组

要使用范围for语句处理多维数组，除了最内层的循环，其他所有循环的控制变量都应是引用类型。

指针和多维数组

使用多维数组名转换得来的指针实际上是指向第一个内层数组的指针。