顺序容器概述

C++标准库中的顺序容器为程序员提供了控制元素存储和顺序访问元素的能力，包括vector，string，array，deque，list，forward_list。

string和vector将元素保存在连续的内存空间中，由于元素是连续存储的，由元素下标来计算其它地址是非常快速的，但是在这两种容器的中间位置添加或删除元素会非常耗时：在一次插入或删除操作后，需要移动插入或删除位置后的所有元素来保持连续存储，而且，添加一个元素有时可能还需要分配额外的存储空间。

deque与vector类似，只是deque在头尾插入或删除速度都很快。

list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速，作为代价，这两个容器不支持元素的随机访问，为了访问一个元素，需要遍历整个容器，而且与vector，deque，array相比，这两个容器的额外内存开销也很大。

与内置数组相比array是一种更安全，更容易使用的数组类型，与内置数组类似，array对象的大小是固定的。

forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能，因此它没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。

确定使用哪种顺序容器

• 除非有更好的理由，否则应该使用vector。
• 如果程序要求随机访问，应使用vector或deque。
• 如果程序要求在容器的头尾插入或删除元素，应使用deque。
• 如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。
• 如果程序有很多小的元素且空间额外开销很重要，则不要使用list或forward_list。
• 如果程序在输入时才需要在容器的中间插入元素，随后需要随机访问元素，那么可以将元素追加到vector，然后使用sort函数重排元素来避免在中间位置插入元素；或者输入阶段使用list或forward_list，随后拷贝到vector。
• 如果程序又要在容器的中间插入或删除元素，又要随机访问元素，那么就看程序中时插入或删除比较多，还是访问比较多，插入或删除比较多使用list或forward_list，访问比较多使用vector或deque。

容器类型成员

每个容器都定义了多种类型，其中包括：

容器的定义和初始化

每个容器都定义了一个默认构造函数，除array外其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数。

将一个新容器创建为另一个容器的拷贝的方法有两种：可以直接拷贝整个容器或拷贝由一个迭代器对指定的元素范围(array除外)，前一种方法要求容器类型匹配，后者则只要求拷贝的元素能转换即可。

int main()
{
    list<const char*> list1{ "hello","world","!!!"};//容器的列表初始化
    //list<string> list2(list1);//错误，容器类型不匹配
    list<string> list2(list1.begin(),list1.end());//正确，拷贝迭代器对指定的元素范围
    list<const char*> list3(list1);//正确，容器类型匹配
    for (auto& element : list3) {
        cout << element<<" ";
    }
    system("pause");
}

除了与关联容器相同的构造函数外，顺序容器(array除外)还提供了另一个构造函数，它接受一个容器大小和一个元素初始值，如果我们不提供元素初始值，则标准库会创建一个值初始化器。

int main()
{
    vector<int> value1(10);//10个元素每个都是0
    cout << value1.size() << endl;//10
    vector<int> value2{10};//一个元素，10
    cout << value2.size() << endl;//1
    vector<int> value3(10,100);//10个元素每个都是100
    cout << value3.size() << endl;//10
    system("pause");
}

与内置数组一样，标准库array的大小也是类型的一部分，定义一个array时，除了指定元素类型，还要指定容器大小。

与其它容器不同，一个默认构造的array是非空的，它包含了与其大小一样多的元素，这些元素都被默认初始化。

如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小，否则编译器会报错，如果初始值的数目小于array的大小，则它们被用来初始化array中靠前的元素，剩余元素会进行值初始化(内置类型零初始化，类类型默认初始化)。

虽然不能对内置数组类型进行拷贝或对象赋值操作，但array并无此限制。

int main()
{
    array<int,10> value1;//10个元素每个都是默认值
    for (auto& e : value1) {
        cout <<hex<< e << endl;//全是0xcccccccc
    }
    array<int, 10> value2{ 0,1,2,3,4,5,6,7,8,9 };//列表初始化
    for (auto& e : value2) {
        cout << e << endl;
    }
    array<int, 10> value3{100};//第一个元素为100，其它元素为0
    for (auto& e : value3) {
        cout << e << endl;
    }
    value3[9] = 1000;
    value3 = {1,2,3};//前三个元素为1，2,3，其它元素为0
    for (auto& e : value3) {
        cout << e << endl;
    }
    system("pause");
}

赋值和swap

使用赋值运算符可以将左边容器中的元素替换为右边容器中元素的拷贝，如果两个容器原来的大小不同，赋值运算后两者的大小都与右边容器的原大小相同。

int main()
{
    vector<int> value1{ 1,2,3,4 };
    vector<int> value2{ 100,200,300};
    value1 = value2;
    for (auto e : value1) {
        cout << e << endl;//100,200,300
    }
    system("pause");
}

赋值运算符要求左边和右边的运算对象具有相同的类型，顺序容器(array除外)还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或从容器的一个子序列赋值。或用指定数目的元素的拷贝替换原有元素。

int main()
{
    string value1("hello");
    string value2;
    value2.assign(value1);
    cout << value2 << endl;//hello
    value2.assign(++value1.begin(), value1.end());
    cout << value2 << endl;//ello
    value2.assign(3,'c');
    cout << value2 << endl;//ccc

    list<string> value3;
    vector<const char*> value4 = { "123","4567" };
    value3.assign(value4.begin(), value4.end());
    cout << *value3.begin() << endl;//123
    system("pause");
}

使用swap能交换两个相同类型容器的内容，调用swap后，两个容器中的元素将会交换，除array外，swap不对任何元素进行拷贝，删除，插入操作，因此可以保证在常数时间内完成。

元素不会被移动意味着指向容器的迭代器，引用和指针在swap操作后都不会失效(string除外)，它们仍然指向swap之前指向的那些元素，但是在swap之后，这些元素已经属于不同的容器了。与其它容器不同，对于string，swap会导致迭代器，引用和指针失效。

与其它容器不同，swap两个array会真正交换它们的元素，因此，交换两个array所需的时间与array中元素的数目成正比。

在标准库中，容器既提供成员函数版本的swap，也提供非成员版本的swap，非成员版本的swap在泛型编程中非常重要，统一使用非成员版本的swap是一个好习惯。

int main()
{
    vector<string> value1 = { "123","456","789"};
    vector<string> value2 = { "1","2","3","4" };
    auto begin = value1.begin();
    auto end = value1.end();
    swap(value1, value2);
    cout << *begin << endl;//123
    cout << *value1.begin() << endl;//1
    system("pause");
}

容器大小操作

除了forward_list不支持size外，每个容器类型都有三个与大小相关的操作，成员函数size返回容器中元素的数目，empty当size为0时返回true，max_size返回容器能容纳的最大元素数量。

int main()
{
    array<string,100> value1;
    vector<string> value2 = { "1","2","3","4" };
    cout << value1.max_size() << endl;//100
    cout << value2.max_size() << endl;//153391689
    system("pause");
}

关系运算符

每个容器都支持相等运算符，除了无序关联容器外所有容器都支持关系运算符，关系运算符左右两边的运算对象必须是相同类型的容器。只有当元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。比较两个容器实际上是进行元素的逐对比较，工作方式如下：

• 如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等。
• 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
• 如果两个容器都不是另一个容器的前缀子序列，则他们的比较结果取决于第一个不相等元素的比较结果。

向顺序容器中添加元素

除array外，顺序容器都定义了添加元素的操作，其中forward_list不支持push_back和emplace_back，forward_list有自己版本的insert和emplace，vector和string不支持push_front和emplace_front。

将一个对象添加到容器中时，放入到容器中的是对象值的一个拷贝，而不是对象本身，向vector，string，deque添加元素会使所有指向容器的迭代器，引用和指针失效。

访问顺序容器中的元素

每个顺序容器都有一个front成员函数，而除了forward_list的顺序容器都有一个back成员函数，这两个操作分别返回首元素和尾元素的引用，不要对一个空容器调用front和back，就像使用一个越界的下标一样，这是一种严重的程序设计错误。 at和下标操作只适用于string，vector，deque，array。

删除顺序容器中的元素

删除元素会改变容器的大小，所以array不支持删除操作，forward_list有特殊版本的erase，forward_list不支持pop_back，vector和string不支持pop_front。

删除deque除首尾之外的任何元素都会使所有迭代器，引用和指针失效，指向string或vector中删除点之后位置的迭代器，引用，和指针都会失效。

删除元素的成员函数并不检查其参数，在删除元素前，程序员必须确保它是存在的。

改变顺序容器大小

我们可以用resize来增大或缩小容器，与往常一样，array不支持resize。如果当前大小大于所要求的大小，容器后部的元素会被删除，如果当前大小小于新大小，会将新元素添加到容器后部。

resize接受一个可选的元素值参数，用来初始化添加到容器中的元素，如果调用者未提供此参数，新元素进行值初始化。

如果resize缩小容器，则指向被删除元素的迭代器，引用和指针都会失效，对vector，string，deque进行resize可能导致迭代器，指针和引用失效。

容器操作可能使迭代器失效

在向容器添加元素后：

• 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器，指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器，指针和引用仍然有效，但指向插入位置之后元素的迭代器，指针和引用将会失效。
• 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器，指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
• 对于list和forward_list，指向容器的迭代器(包括尾后和首前迭代器)，指针和引用仍然有效。

在向容器删除元素后：

• 指向被删除元素的迭代器，指针和引用会失效。
• 对于vector或string，删除点之后位置的迭代器(包括尾后迭代器)，引用，和指针都会失效。
• 对于deque，如果删除首尾之外任何位置的元素，所有迭代器，引用和指针失效，删除尾元素会使尾后迭代器失效，其它迭代器，引用和指针不受影响，删除首元素，这些也不会有影响。
• 对于list和forward_list，指向容器的迭代器(包括尾后和首前迭代器)，指针和引用仍然有效。

编写改变容器的循环程序

添加/删除vector，string，deque元素的循环程序必须考虑迭代器，引用和指针可能失效的问题，程序必须保证每个循环中都更新迭代器，引用和指针，使用迭代器很容易在循环中添加或删除元素。

在我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，原来的end返回的迭代器会失效，因此，添加/删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器。

int main()
{
    //删除偶数元素，复制奇数元素
    vector<int> value{ 0,1,2,3,4,5,6,7,8,9 };
    auto iter = value.begin();
    while (iter != value.end()) {//每次都重新调用end()来判断
        if (*iter % 2) {
            iter = value.insert(iter, *iter);//复制当前元素
            iter += 2;//跳过当前元素以及插入到它之前的元素
        } else {
            iter = value.erase(iter);//删除偶数元素
        }
    }
    for (auto e : value) {
        cout << e << endl;
    }
    system("pause");
}

特殊的forward_list操作

当添加或删除一个元素时，添加或删除的元素之前的那个元素的后继会发生改变，所以为了添加或删除元素，我们需要访问其前驱，但是forward_list是单向链表，没有简单的方法来获取一个元素的前驱，出于这个原因，在一个forward_list中添加或删除元素是通过改变给定元素之后的元素来完成的。为了支持这种操作，forward_list定义了before_begin，它返回一个首前迭代器。

vector和string是如何管理内存的

为了支持快速随机访问，vector和string将元素连续存储，在添加元素时，为了保证元素连续存储，容器必须分配新的内存空间来保存已有元素和新元素，释放旧存储空间，如果我们每添加一个新元素，容器就执行一次这样的内存分配释放操作，性能会很慢。

为了避免这种代价，vector和string采用了可以减少容器空间重新分配次数的策略，当不得不获取新的内存空间时，vector和string通常会分配比新空间需求更大的内存空间，容器预留这些空间备用，这样就不需要每次添加新元素都重新分配内存空间了。

vector和string提供了一些成员函数供我们管理内存分配：