顺序容器操作

除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除来改变容器大小。

forward_list有自己版本的instert和emplace，且不支持push_back和emplace_back。

需要注意不同容器使用了不同策略来分配元素空间，这些策略直接影响性能：

在vector或string的尾部之外的位置或者deque首尾之外的位置添加元素，都需要移动元素。甚至可能引起整个对象存储空间的重新分配。

push_back

除array和forward_list外均支持。
对push_back的调用在容器尾部创建一个新元素，使容器size+1，值为push_back参数的一个拷贝（而不是对象本身）。

push_front

list、forward_list、deque支持该操作。
每个元素都插入到新的开始位置（new beginning）

其他位置的插入

vector、deque、list和string均支持insert成员，而forward_list由一个特殊版本的insert。

insert接受迭代器作为第一个参数，以将第二个参数的内容添加到该迭代器指向位置的前一个位置。因此可以提供指向首地址到尾后的任意迭代器。

std::list<std::string> slist = {"Hello", "!"};
slist.insert(slist.begin() + 1, "World");

插入范围内元素

insert还可以接受更多参数:

迭代器+元素数目+元素值

std::vector<std::string> svec = {"Hello"};
svec.insert(svec.end(), 10, "!");

迭代器+一对迭代器

std::deque<std::string> sdq = {"Hello", "World"};
std::deque<std::string> sdq2 = {"A", "Beautiful"};
auto dqb = sdq.begin();
auto dqb2 = sdq2.begin();
auto dqe2 = sdq2.end();
sdq.insert(dqb+1, dqb2, dqe2);
for (auto i: sdq) cout<<i;

注意：迭代器对和指向目标位置的迭代器不能指向同一容器！

使用insert的返回值

int main(){
    std::vector<string> slst = {"_"};
    auto b = slst.begin();
    std::vector<string>::difference_type cond = 0;
    std::vector<string> strl = {"0","1","2","3","4","5","6","7","8","9"};
    auto* ps = &strl[0];
    while (cond<10){
        std::string st = *(ps + cond);
        b = slst.insert(b, st);  //返回值指向元素也前移一位
                                 //end指针似乎不能如此操作
        cond++;
    }
    for (auto i: slst) cout<<i;  //9876543210_
}

emplace操作

主要的三个成员：emplace_front, emplace, emplace_back
这些操作构造而不是拷贝元素。
push和insert将元素类型对象传递给他们并被拷贝到容器。
而emplace则是将参数传递给元素类型的构造函数。

相当于现场构造一个元素类的对象并添加到容器，对于嵌套的类型十分有用：

int main(){
    std::vector<int>vi = {1,1};
    std::vector<std::vector<int>> vvi = {vi, vi};

    //构造待插入元素，具备多种重载
    vvi.emplace_back(std::initializer_list<int>{0,0,0});
    vvi.emplace(vvi.end(), std::vector<int>(2,2)); 
    for (auto i: vvi){
        for (auto j: i){
            cout<<j;       //111100022
        }
    }
}

访问元素

at和下标操作只适用于string、vector、deque和array。
back不适用于forward_list。

访问成员函数返回的是引用

在容器中以上述方式访问返回的都是引用。如果容器是const则返回const引用。通常引用可以用于改变元素的值。

int main(){
    std::string str = "Hello";
    if (isupper(str.front()))
        str.front() = tolower(str.front());
    cout<<str<<endl;
    if (islower(str.at(0)))
        str.at(0) = toupper(str.at(0));
    cout<<str<<endl;
}

下标操作和安全随机访问

下标访问和at的区别：at会在越界时抛出out_of_range异常，而下标越界则行为未定义。

int main(){
    std::vector<int> vec = {0,0,0};
    try {
        //cout<<vec[6]; 使用下标访问可能无法捕获，发生错误
        cout<<vec.at(6);  //使用at则正常进行到下一步
    } catch (std::exception e) {
        cout<<e.what()<<endl;
    }
}

依然使用下标，则在越界时不会报错，直到出错才抛出异常，一定程度增大了容错率。

删除元素

pop成员函数

vector和string不支持pop_front()，forward_list不支持pop_back()，空容器不能弹出。

这些操作返回void，因此弹出的值应提前保存。

从容器中删除元素

erase通过指针指定位置进行删除。和insert类似，可以利用返回值进行迭代，区别在于insert向前走，erase向后走。

int main(){
    std::string str = "0123456789_";
    std::string::iterator it = str.begin();
    while (*it != '_'){
        //c_str(): 为了适应printf而将c++字符串改为c风格的方法
        std::printf("point to: %c \tstring: %s \n", *it, str.c_str());
        it = str.erase(it);
    }
    std::printf("final string: %c", *it);
}

若要删除多个元素，则一对迭代器指向的范围同样是左连续：

    std::vector<int> vec = {0,1,2,3,4,5};
    auto beg = vec.begin();
    auto end = vec.end();
    vec.erase(++beg, --end);
    for (auto i: vec) cout<<i;  //05

删除奇数或者偶数项，并避免循环内写入条件分支：

int main(){
    std::vector<int> ivec(100, 0);
    int cnt = 0;
    for (int& i: ivec) i = cnt++;

    auto iter = ivec.begin();

    bool erase_odd = 1;  //1:删除奇数项

    if (erase_odd){
        if (!ivec.size()%2)
            ivec.push_back(0);
            //迭代器失效
            iter = ivec.begin();
    }
    else {
        ivec.erase(iter);
        if (ivec.size()%2) {
            ivec.push_back(0);
            //迭代器失效
            iter = ivec.begin();
        }
    }

    while (iter != ivec.end()){
        iter = ivec.erase(++iter);
    }

    for (int& i: ivec) cout<<i<<' ';
}

forward_list的特殊操作

forward_list属于单向链表，改变后继元素会同时改变前一个元素的值。
难以访问一个元素的前驱元素，向该容器添加元素是通过改变给定元素之后的元素完成的。即，若增删element3，需要操作element2。
这些容器操作在forward_list中命名为：insert_after,emplace_after,erase_after。
为了使对首个元素的操作生效，该容器还定义了before_begin，返回一个首前（off-the-beginning）迭代器。

#include <forward_list>

int main(){
    std::forward_list<int> flst = {0,1,2,3,4};
    decltype(flst)::iterator it = flst.before_begin();
    cout<<*(++it);
}

改变容器大小

使用resize增大或缩小容器，可以接受两个参数（大小和新元素初值）。array不支持resize。

未给新元素初值则默认初始化。

对于类类型容器进行resize则必须给初值或者元素具有默认构造函数。

    std::vector<int> vi(10, 0);
    auto vbg = vi.begin();
    auto ved = vi.end();
    cout<<*vbg<<*(--ved)<<endl;

    vi.resize(11, 1);  
    //此resize为两个参数的版本，仅新增加的元素变为1
    //先前的迭代器、引用和指针均已经失效

    vbg = vi.begin();
    ved = vi.end();
    cout<<*vbg<<endl;   //是0不是1，仅新增的是1

容器操作和迭代器失效

使用不表示任何元素的迭代器/指针/引用可能导致与指针未初始化类似的严重问题。

发生失效是【迭代器需要使用增删操作的返回值赋值】才能继续的原因。

添加元素的情况

• vector或string
• • 若储存空间被重新分配则i/p/r全部失效
• • 若未重新分配，则仅插入位置之前的i/p/r有效。
• deque
• • 插入除首尾外的元素则i/p/r均失效
• • 在首尾添加元素，迭代器失效但指向现存元素的r/p不失效
• list和forward_list，i/p/r均有效（包括首前和尾后迭代器）

删除元素的情况

• 指向被删除元素的i/p/r一定失效
• list和forward_list，指向被删除元素以外的i/p/r均有效（包括首前和尾后迭代器）
• deque
• • 在首尾之外的位置删除元素，则指向被删除元素以外的i/p/r均失效；
• • 删除尾元素，则仅尾后迭代器失效
• • 删除首元素，则仅首迭代器失效
• vector和string，被删除元素后储存空间一般不重新分配，则指向被删除元素之前的i/p/r均有效；之后的包括尾后迭代器均失效。

//未失效的i/p/r指向的元素不变
//首迭代器+1或尾后迭代器-2则不受删除首尾元素影响
int main(){
    std::deque<int> idq = {0, 1, 2, 3, 4, 5, 6};
    auto dqb = idq.begin();
    auto dqe = idq.end();
    auto* dqp = &idq[3];
    auto& dqr = idq[4];

    idq.pop_front(); //首迭代器失效
    cout<<(*--dqe)<<(*dqp)<<dqr<<endl;  //634

    idq = {0, 1, 2, 3, 4, 5, 6};
    dqb = idq.begin();
    dqe = idq.end();
    dqp = &idq[3];
    dqr = idq[4];

    idq.pop_back(); //尾后迭代器失效
    cout<<(*dqb)<<(*dqp)<<dqr<<endl;  //034
}

不要保存end返回的迭代器

由上述规则可知，尾后迭代器最容易失效，如vector和string增删任意元素、deque增删非首元素等情况。因此在每次进行容器操作后应该反复调用end而不能用循环前保存的end。为此，C++标准库中的end()操作都很快。

std::vector<int> iv(10,0);
auto beg = iv.begin();
auto end = iv.end();
//循环中不推荐的写法
while (beg != end) {
    ++begin;
    beg = iv.insert(beg, 1)  //end保存到迭代器已经失效
    ++begin;
}
//正确的写法
while (beg != iv.end()){
    ++begin;
    beg = iv.insert(beg, 1)
    ++begin;
}