C++学习手记二：向量和迭代器

三 标准库类型vector

标准库类型vector表示对象的集合，其中所有对象的类型都相同。集合中每个对象都有一个与之对应的索引。要想使用vector，需包含头文件和声明：

#include <vector>
using std::vector;

vector是一个类模版。
模版不是类或函数，相反可以将模版看作为编译器生成类或函数编写的一份说明。编译器根据模版创建类或函数的过程称为实例化。当使用模版时，需要告诉编译器把类或模版实例化成哪种类型。

vector<int> ivec;   // ivec保存int类型对象
vector<vector<string>> file;    // 向量元素是vector对象

注意：早期版本C++标准中，若vector的元素还是vector（或者其他模版类型），必须在外层vector对象的右尖括号和其元素之间添加一个空格，如写成vector<vector<string> > file而非vector<vector<string>> file。

1 定义和初始化vector对象

vector操作	含义
vector<typeName> v1	默认v1为空，潜在元素类型为typeName
vector<typeName> v2(v1) 或 v2=v1 或 vector<typeName> v2(v1.begin(), v1.end())	v2是v1的一个副本，若v1.size()>v2.size()则赋值后v2.size()被扩充为v1.size()
vector<typeName> v3(n,i)	v3包含n个值为i的typeName类型元素
vector<typeName> v4(n)	v4含有n个执行了初始化的元素
vector<typeName> v5{a,b,c…} 或 vector<typeName> v5={a,b,c…}	v5包含初始值个数的元素，每个元素被赋予相应的初始值

列表初始化

如果提供的是初始元素值的列表，则只能把初始值都放在花括号里进行列表初始化，而不能放在圆括号里。

vector<string> v1{"a", "an", "the"};    // 列表初始化
vector<string> v2("a", "an", "the");    // 错误

创建指定数量的元素

还可以用vector对象容纳的元素数量和所有元素的统一初始值来初始化vector对象：

vector<int> ivec(10, -1);
vector<string> svec(10, "hi!");

2 向vector中添加元素

对于大多数使用vector的情形，更多的是先创建一个空vector，再在运行时利用vector的成员函数push_back向其中添加元素。push_back负责把一个值当成一个vector对象的尾元素压到（push）vector对象的尾端（back）。

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

string word;
vector<string> text;

while(cin >> word)
    text.push_back(word);

注意：如果循环体内部包含有向vector对象添加元素的语句，则不能适用范围for循环。因为范围for语句体内不应改变其所遍历序列的大小。

3 vector支持的操作

vector操作	含义
v.clear()	删除容器中的所有元素
v.empty()	判断vector是否为空
v.erase(pointer1, pointer2)	删除pointer1到pointer2中间（包括pointer1所指）的元素
v.size()	返回容器中数据的个数
v.push_back(t)	在容器的最后添加一个值为t的数据
v[n] 或 v.at(n)	返回v中位置为n的元素，后者更加安全
v1==v2	判断v1与v2是否相等
!=、<、<=、>、>=	保持这些操作符惯有含义

vector的size返回值类型是有vector定义的size_type类型。

注意：vector对象的类型总是包含着元素的类型。

vector<int>::size_type; // 正确
vector::size_type; // 错误

成绩分段统计：

int main()
{
    vector<unsigned> scores(11, 0);
    unsigned grade;

    while(cin >> grade)
        if(grade <= 100)
            ++scores[grade / 10];

    for(unsigned item: scores)
        cout << item << endl;

    return 0;
}

四 迭代器

所有标准库容器都可以使用迭代器。严格来说string对象不属于容器类型，但是string支持很多与容器类型类似的操作，例如迭代器。

1 使用迭代器

获取迭代器不是使用取地址符，有迭代器的类型同时拥有返回迭代器的成员。比如这些类型都有名为begin和end的成员。其中begin成员负责返回指向的第一个元素的迭代器，end成员则负责返回指向容器（或string对象）“尾元素的下一位置（one past the end）”的迭代器。
如果容器为空，则begin和end返回的是同一个迭代器。

迭代器操作	含义
*iter	返回迭代器iter所指元素的引用
iter->mem	解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem
++iter	令iter指示容器中的下一个元素
--iter	令iter指示容器中的下一个元素
iter1 == iter2，iter1 != iter2	判断两个迭代器是否相等或不等，如果两个迭代器指示的是同一个元素或者是同一个容器的尾后迭代器，则相等

使用迭代器将输入字符串转换为大写形式：

int main()
{
    string line;
    getline(cin, line);

    for(auto it = line.begin(); it != line.end(); ++it)
        *it = toupper(*it);

    cout << line << endl;

    return 0;
}

迭代器类型

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

// 读写
vector<int>::iterator it;
string::iterator it2;
    
// 只读
vector<int>const_iterator it3;
string::const_iterator it4;

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

解引用迭代器可获得迭代器所指的对象，如果该对象的类型恰好是类，就有可能希望进一步访问它的成员。例如：

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

箭头运算符（->）可简化上述表达式，it->mem和(*it).mem表达的意思相同。

注意：任何使用迭代器的循环体，不可向迭代器所属容器添加元素。

2 迭代器运算

string和vector迭代器支持的运算	含义
iter + n	迭代器加上一个整数仍是一个迭代器，指示的新位置与原来位置相比向前移动若干个元素
iter – n	迭代器减去一个整数仍是一个迭代器，指示的新位置与原来位置相比向后移动若干个元素
iter += n	迭代器加法复合赋值语句
iter –= n	迭代器减法复合赋值语句
iter1 – iter2	两个迭代器相减的结果是它们之间的距离，类型名为difference_type的带符号整数
<、<=、>、>=	关系运算符，如果某迭代器只想的容器位置在另一个迭代器所指位置之前，则说前者小于后者

计算得到最接近vi中间元素的一个迭代器:

auto mid = vi.begin() + vi.size() / 2;

使用迭代器完成二分搜索：

int main()
{
    vector<int> arr;
    const int cnt = 10;
    int num;
    for(int i=0; i<cnt; ++i) {
        cin >> num;
        arr.push_back(num);
    }

    int goal;
    cin >> goal;
    auto arrbeg = arr.begin();
    auto arrend = arr.end();
    auto mid = arrbeg + (arrend - arrbeg) / 2;

    while(mid != arrend && *mid != goal) {
        // cout << "MID IS " << *mid << endl;
        if(goal > *mid)
            arrbeg = mid + 1;
        else
            arrend = mid;
        mid = arrbeg + (arrend - arrbeg) / 2;
    }

    if(*mid == goal)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}

插曲：为什么用的是mid = arrbeg + (arrend - arrbeg) / 2，而不是mid = (arrend + arrbeg) / 2？
arrbeg＋arrend操作很可能会出现溢出的风险。且从通用性考虑，如果arrbeg和arrend是指针或者迭代器无法编译通过，因为指针和迭代器运算不支持相加运算，只支持相减运算。
在循环之中，arrbeg = mid + 1的+ 1是必要的吗？
答案是肯定的。循环终止时，mid或者等于arrend，或者指向要找的元素。由于迭代器end指向的是尾元素的下一位置，如若arrbeg不加1，在某些情形下， mid将始终到达不了arrend，使程序陷入无穷循环。