三 标准库类型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<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的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返回的是同一个迭代器。

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

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 迭代器运算

计算得到最接近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，使程序陷入无穷循环。