三 標(biāo)準(zhǔn)庫類型vector

標(biāo)準(zhǔn)庫類型vector表示對(duì)象的集合，其中所有對(duì)象的類型都相同。集合中每個(gè)對(duì)象都有一個(gè)與之對(duì)應(yīng)的索引。要想使用vector，需包含頭文件和聲明：

#include <vector>
using std::vector;

vector是一個(gè)類模版。
模版不是類或函數(shù)，相反可以將模版看作為編譯器生成類或函數(shù)編寫的一份說明。編譯器根據(jù)模版創(chuàng)建類或函數(shù)的過程稱為實(shí)例化。當(dāng)使用模版時(shí)，需要告訴編譯器把類或模版實(shí)例化成哪種類型。

vector<int> ivec;   // ivec保存int類型對(duì)象
vector<vector<string>> file;    // 向量元素是vector對(duì)象

注意：早期版本C++標(biāo)準(zhǔn)中，若vector的元素還是vector（或者其他模版類型），必須在外層vector對(duì)象的右尖括號(hào)和其元素之間添加一個(gè)空格，如寫成vector<vector<string> > file而非vector<vector<string>> file。

1 定義和初始化vector對(duì)象

列表初始化

如果提供的是初始元素值的列表，則只能把初始值都放在花括號(hào)里進(jìn)行列表初始化，而不能放在圓括號(hào)里。

vector<string> v1{"a", "an", "the"};    // 列表初始化
vector<string> v2("a", "an", "the");    // 錯(cuò)誤

創(chuàng)建指定數(shù)量的元素

還可以用vector對(duì)象容納的元素?cái)?shù)量和所有元素的統(tǒng)一初始值來初始化vector對(duì)象：

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

2 向vector中添加元素

對(duì)于大多數(shù)使用vector的情形，更多的是先創(chuàng)建一個(gè)空vector，再在運(yùn)行時(shí)利用vector的成員函數(shù)push_back向其中添加元素。push_back負(fù)責(zé)把一個(gè)值當(dāng)成一個(gè)vector對(duì)象的尾元素壓到（push）vector對(duì)象的尾端（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);

注意：如果循環(huán)體內(nèi)部包含有向vector對(duì)象添加元素的語句，則不能適用范圍for循環(huán)。因?yàn)榉秶鷉or語句體內(nèi)不應(yīng)改變其所遍歷序列的大小。

3 vector支持的操作

vector的size返回值類型是有vector定義的size_type類型。

注意：vector對(duì)象的類型總是包含著元素的類型。

vector<int>::size_type; // 正確
vector::size_type; // 錯(cuò)誤

成績分段統(tǒng)計(jì)：

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;
}

四 迭代器

所有標(biāo)準(zhǔn)庫容器都可以使用迭代器。嚴(yán)格來說string對(duì)象不屬于容器類型，但是string支持很多與容器類型類似的操作，例如迭代器。

1 使用迭代器

獲取迭代器不是使用取地址符，有迭代器的類型同時(shí)擁有返回迭代器的成員。比如這些類型都有名為begin和end的成員。其中begin成員負(fù)責(zé)返回指向的第一個(gè)元素的迭代器，end成員則負(fù)責(zé)返回指向容器（或string對(duì)象）“尾元素的下一位置（one past the end）”的迭代器。
如果容器為空，則begin和end返回的是同一個(gè)迭代器。

使用迭代器將輸入字符串轉(zhuǎn)換為大寫形式：

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

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

    cout << line << endl;

    return 0;
}

迭代器類型

擁有迭代器的標(biāo)準(zhǔn)庫類型使用iterator和const_iterator來表示迭代器的類型：

// 讀寫
vector<int>::iterator it;
string::iterator it2;
    
// 只讀
vector<int>const_iterator it3;
string::const_iterator it4;

結(jié)合解引用和成員訪問操作

解引用迭代器可獲得迭代器所指的對(duì)象，如果該對(duì)象的類型恰好是類，就有可能希望進(jìn)一步訪問它的成員。例如：

(*it).empty()   // 圓括號(hào)必不可少

箭頭運(yùn)算符（->）可簡化上述表達(dá)式，it->mem和(*it).mem表達(dá)的意思相同。

注意：任何使用迭代器的循環(huán)體，不可向迭代器所屬容器添加元素。

2 迭代器運(yùn)算

計(jì)算得到最接近vi中間元素的一個(gè)迭代器:

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操作很可能會(huì)出現(xiàn)溢出的風(fēng)險(xiǎn)。且從通用性考慮，如果arrbeg和arrend是指針或者迭代器無法編譯通過，因?yàn)橹羔樅偷鬟\(yùn)算不支持相加運(yùn)算，只支持相減運(yùn)算。
在循環(huán)之中，arrbeg = mid + 1的+ 1是必要的嗎？
答案是肯定的。循環(huán)終止時(shí)，mid或者等于arrend，或者指向要找的元素。由于迭代器end指向的是尾元素的下一位置，如若arrbeg不加1，在某些情形下， mid將始終到達(dá)不了arrend，使程序陷入無窮循環(huán)。