标签：const 迭代 iterator 元素 list vector 倒数

9.vector与list的区别与应用？怎么找某vector或者list的倒数第二个元素

1.vector数据结构 vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。因此能高效的进行随机存取，时间复杂度为o(1);但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。

另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。连续存储结构：vector是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。

它与数组最大的区别就是vector不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。

2.list数据结构 list是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);但由于链表的特点，能高效地进行插入和删除。非连续存储结构：list是一个双链表结构，支持对链表的双向遍历。每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。因此list可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。

区别：

• vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。
• list的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。
• 从遍历上来说，list是单向的，vector是双向的。
• vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。

int mySize = vec.size();vec.at(mySize -2);

list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历：

1.STL中的vector

1.vector概述

vector是最常用的容器之一，功能十分强大，可以储存、管理各种类型的数据。在很多情况下可以用来代替功能比较局限的普通数组，因为我们知道，普通数组只能实现一对一的映射而不能实现一对多的映射，vector就是专门为了解决这个问题而诞生的。vector也可以称为动态数组，因为其大小是根据实时更新而变化的，正因为如此vector显得更加灵活易用。

vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。

Vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。

C++语言既有类模板(class template)，也有函数模板，其中vector是个类模板。

模板本身不是类或函数，相反可以将模板看作为编译器生成类或函数编写的份说明。编译器根据模板创建类或函数的过程称为实例化（instantiation），当使用模板时，需要指出编译器应把类或函数实例化成何种类型。

NOTE：vector是模板而非类型，由vector，生成的类型必须包含vector中元素的类型，例如vector<int>。

vector能容纳绝大多数类型的对象作为其元素，但是因为引用不是对象，所以不存在包含引用的vector。除此之外，其他大多数（非引用）内置类型和类类型都可以构成vector对象，甚至组成vector的元素也可以是vector。

2.vector的定义和初始化

使用vector需要包含vector头文件如下：

#include<vector>
using std::vector;

和任何种类类型一样，vector模板控制着定义和初始化向量的方法。表3.4列出了vector对象的常用方法

表3.4: 初始化vector对象的方法
vector<T> v1	v1是一个空vector，它潜在的元素是T类型的，执行默认初始化
vector<T> v2(v1)	v2中包含有v1所有元素的副本
vector<T> v2 = v1	等价于v2(v1)， v2中包含有v1所有元素的副本
vector<T> v3(n, val)	v3包含了n个重复的元素，每个元素的值都是val
vector<T> v4(n)	v4包含了n个重复地执行了值初始化的对象
vector<T> v5{a,b,c...}	v5包含了初始值个数的元素，每个元素被赋予相应的初始值
vector<T> v5={a,b,c...}	等价于v5{a,b,c...}

例子：

vector<int> v1;//声明一个int型向量v1，默认初始化为0
vector<int> v2(v1);//声明并用向量v1初始化向量v2，v2是包含有v1所有元素的副本
vector<int> v2 = v1;//等价于v2(v1)，声明并用向量v1初始化向量v2，v2是包含有v1所有元素的副本
vector<int> v3(10, 1);//向量v3包含了10个重复的元素，每个元素都是1
vector<int> v4(10);//向量v1包含了10个重复地执行了值初始化的对象
vector<int> v5{a, b, c,..};//向量v1包含了初始值个数的元素，每个元素被赋予相应的初始值
vector<int> v5={ a, b, c,.. };//等价于v5{a, b, c,..};
vector<int> v6(a.begin(), a.begin() + 3);//将v6向量中从第0个到第2个(共3个)作为向量b的初始值
vector<string> v7 = { "hi","my","name","is","lee" };

int arr[] = { 0,1,2,3,4,5,6 };
vector<int>v8 = { 0,1,2,3,4 };//列表初始化
vector<int>v9(arr, arr + 3);//将arr数组的前是三个元素作为向量v9的初始值，区间为[arr,arr+3)
vector<int>v10(&arr[1], &arr[4]);//将arr[1]~arr[4]之间的元素作为向量v8的初始值

（1）值初始化

通常情况下，可以只提供vector对象容纳的元素数量而不用略去初始值。此时库会创建一个值初始化的(value-initialized)元素初值，并把它赋给容器中的所有元素。这个初值由vector对象中元素的类型决定。
如果vector对象的元素是内置类型，比如int，则元素初始值自动设为0。如果元素是某种类类型，比如string，则元素由类默认初始化 ：

vector<int> ivec(10);//10个元素，每个都初始化为0
vector<string> svec(10);//10个元素，每个都是空string

对这种初始化的方式有两个特殊限制：其一，有些类要求必须明确地提供初始值，如果vector对象中元素的类型不支持默认初始化，我们就必须提供初始的元素值。对这种类型的对象来说，只提供元素的数量而不设定初始值无法完成初始化工作。

其二，如果只提供了元素的数量而没有设定初始值，只能使用直接初始化：

vector<int> vi= 10;//错误：必须使用直接初始化的形式指定向量大小

这里的10是用来说明如何初始化vector对象的，我们用它的本意是想创建含有10个值初始化了的元素的vector对象，而非把数字10 “拷贝” 到vector中。因此，此时不宜使用拷贝初始化。

3.vector迭代器

迭代器	功能
begin()	返回指向向量第一个元素的迭代器
end()	返回指向向量最后一个元素之后位置的迭代器
rbegin()	返回指向向量最后一个元素的反向迭代器
rend()	返回指向向量第一个元素之前位置的反向迭代器
cbegin()	返回指向向量第一个元素的迭代器，不能用于修改元素
cend()	返回指向向量最后一个元素之后位置的迭代器，不能用于修改元素
crbegin()	返回指向向量最后一个元素的反向迭代器，不能用于修改元素
crend()	返回指向向量第一个元素之前位置的反向迭代器，不能用于修改元素

4.向vector对象中添加元素

（1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
（2）a.assign(4,2); //是a只含4个元素，且每个元素为2
（3）a.back(); //返回a的最后一个元素
（4）a.front(); //返回a的第一个元素
（5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07
（6）a.clear(); //清空a中的元素
（7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false
（8）a.pop_back(); //删除a向量的最后一个元素
（9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+         3（不包括它）
（10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
（11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
（12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
（13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8         ，插入元素后为1,4,5,9,2,3,4,5,9,8
（14）a.size(); //返回a中元素的个数；
（15）a.capacity(); //返回a在内存中总共可以容纳的元素个数
（16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
（17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
（18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才         显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） 
（19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
（20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<

对vector对象来说，直接初始化的方式适用于三种情况：初始值已知且数量较少、初始值是另一个vector对象的副本、所有元素的初始值都一样。然而更常见的情况是：创建一个vector对象时并不清楚实际所需的元素个数，元素的值也经常无法确定。还有 些时候即使元素的初值已知，但如果这些值总量较大而各不相同，那么在创建vector对象的时候执行初始化操作也会显得过于烦琐。

举个例子，如果想创建一个vector对象令其包含从0到9共10个元素，使用列表初始化的方法很容易做到这一点：但如果vector对象包含的元素是从0到99或者从0 到999呢？这时通过列表初始化把所有元素都一一罗列出来就不太合适了。对于此例来说，更好的处理方法是先创建一个空vector，然后在运行时再利用vector的成员函数 push_back向其中添加元素。push_back负责把一个值当成vector对象的尾元素“压到(push)”vector对象的“尾端(back) ”。例如：

vector<int> vec;
for (int i = 0; i != 100; i++)
{
    vec.push_back(i);
}    
// 循环结束后vec中100个元素，值从0到99            

同样的，如果直到运行时才能知道vector对象中元素的确切个数，也应该使用刚刚这种方法创建 vector对象并为其赋值。例如，有时需要实时读入数据然后将其赋予vector对象：

//从标准输入中读取单词，将其作为vector对象的元素存储
string word;
vector<string> text; //空vector对象
while (cin >> word)
{
	text.push_back(word);//把word添加到text后面
}

和之前的例子一样，本例也是先创建一个空vector，之后依次读入未知数量的值并保存到test中。

关键概念：vector对象能高效增长

C++标准要求vector应该能在运行时高效快速地添加元素。因此既然vector对 象能高效地增长，那么在定义vector对象的时候设定其大小也就没什么必要了，事实上如果这么做性能可能更差。只有一种例外情况，就是所有 (all) 元素的值都一样。一旦元素的值有所不同，更有效的办法是先定义一个空的vector对象，再在运行时向其中添加具体值。此外，允许我们进一步提升动态添加元素的性能。

开始的时候创建空的vector对象在运行时再动态添加元素，这一做法与C语言及其他大多数语言中内置数组类型的用法不同。特别是如果用惯了C或者Java，可以预计在创建vector对象时顺便指定其容量是最好的。然而事实上，通常的情况是恰恰相反。

（1）向vector对象添加元素蕴含的编程假定

由于能高效便捷地向vector对象中添加元素，很多编程工作被极大简化了。然而，这种简便性也伴随着一些对编写程序更高的要求：其中一条就是必须要确保所写的循环正确无误，特别是在循环有可能改变vector对象容量的时候。

随着对vector的更多使用，我们还会逐渐了解到其他一些隐含的要求，其中一条是现在就要指出的：如果循环体内部包含有向vector对象添加元素的语句，则不能使用范围for循环，因为在范围for语句中，预存了尾部位置相关的标记位置的值，增减元素会改变其值。

5.vector类常用的函数

5.1构造函数

vector():创建一个空vector
vector(int nSize):创建一个vector，元素个数为nSize
vector(int nSize,const T& t):创建一个vector，元素个数为nSize，且值均为t
vector(const vector&):复制构造函数
vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

例1：

//#include "stdafx.h"  
#include<iostream>  
#include<vector>  
using namespace std;

class A
{
    //空类  
};

int main(int argc, char* argv[])
{
    //int型vector  
    vector<int> vecInt;

    //float型vector  
    vector<float> vecFloat;

    //自定义类型，保存类A的vector  
    vector<A> vecA;

    //自定义类型，保存指向类A的指针的vector  
    vector<A*> vecPointA;

    return 0;
}

例2：

// vectorsample.cpp : 定义控制台应用程序的入口点。  
//  
//#include "stdafx.h"  
#include<iostream>  
#include<vector>  
using namespace std;

class A
{
    //空类  
};

int main(int argc, char* argv[])
{
    //int型vector，包含3个元素  
    vector<int> vecIntA(3);

    //int型vector,包含3个元素且每个元素都是9  
    vector<int> vecIntB(3, 9);

    //复制vecIntB到vecIntC  
    vector<int> vecIntC(vecIntB);

    int iArray[] = { 2,4,6 };
    //创建vecIntD  
    vector<int> vecIntD(iArray, iArray + 3);

    //打印vectorA，此处也可以用下面注释内的代码来输出vector中的数据  
    /*for(int i=0;i<vecIntA.size();i++)
    {
        cout<<vecIntA[i]<<"     ";
    }*/

    cout << "vecIntA:" << endl;
    for (vector<int>::iterator it = vecIntA.begin(); it != vecIntA.end(); it++)
    {
        cout << *it << "     ";
    }
    cout << endl;

    //打印vecIntB  
    cout << "VecIntB:" << endl;
    for (vector<int>::iterator it = vecIntB.begin(); it != vecIntB.end(); it++)
    {
        cout << *it << "     ";
    }
    cout << endl;

    //打印vecIntC  
    cout << "VecIntB:" << endl;
    for (vector<int>::iterator it = vecIntC.begin(); it != vecIntC.end(); it++)
    {
        cout << *it << "     ";
    }
    cout << endl;

    //打印vecIntD  
    cout << "vecIntD:" << endl;
    for (vector<int>::iterator it = vecIntD.begin(); it != vecIntD.end(); it++)
    {
        cout << *it << "     ";
    }
    cout << endl;

    return 0;
}

输出：

vecIntA:
0     0     0
VecIntB:
9     9     9
VecIntB:
9     9     9
vecIntD:
2     4     6

例3：

#include<iostream>  
#include<vector>  
using namespace std;

void printVector(vector<int>& v)
{	//利用迭代器打印 v
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}

void text01()
{
    vector<int> v1;                       
    for (int i = 0; i < 5; ++i)
    {
        v1.push_back(i);//向v1末尾添加数据
    }
    vector<int> v2(v1.begin(), v1.end());
    vector<int> v3(5, 5);                
    vector<int> v4(v3);                  
    cout << "打印v2: ";
    printVector(v2);
    cout << "打印v3: ";
    printVector(v3);
    cout << "打印v4: ";
    printVector(v4);
}

int main(int argc, char* argv[])
{
    text01();

    return 0;
}

输出：

打印v2: 0 1 2 3 4
打印v3: 5 5 5 5 5
打印v4: 5 5 5 5 5

5.2增加函数

void push_back(const T& x):向量尾部增加一个元素X
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

例子：

// vectorsample.cpp : 定义控制台应用程序的入口点。  
// vectorsample.cpp : 定义控制台应用程序的入口点。 
//#include "stdafx.h"  
#include<iostream>  
#include<vector>  

using namespace std;


int main(int argc, char* argv[])
{
    //int型vector,包含3个元素  
    vector<int> vecIntA;

    //插入1 2 3  
    vecIntA.push_back(1);
    vecIntA.push_back(2);
    vecIntA.push_back(3);

    int nSize = vecIntA.size();

    cout << "vecIntA:" << endl;

    //打印vectorA,方法一：  
    for (int i = 0; i < nSize; i++)
    {
        cout << vecIntA[i] << "     ";
    }
    cout << endl;

    //打印vectorA,方法二：      
    for (int i = 0; i < nSize; i++)
    {
        cout << vecIntA.at(i) << "     ";
    }
    cout << endl;

    //打印vectorA,方法三：  
    for (vector<int>::iterator it = vecIntA.begin(); it != vecIntA.end(); it++)
    {
        cout << *it << "     ";
    }
    cout << endl;

    return 0;
}

上述代码对一个整形向量类进行操作，先定义一个整形元素向量类，然后插入3个值，并用3种不同的方法输出，程序运行结果如下：

vecIntA:
1     2     3
1     2     3
1     2     3

例子2：

// vectorsample.cpp : 定义控制台应用程序的入口点。  
//  
//#include "stdafx.h"  
#include<iostream>  
#include<vector>  
using namespace std;

class A
{
public:
    int n;
public:
    A(int n)
    {
        this->n = n;
    }
};

int main(int argc, char* argv[])
{
    //int型vector,包含3个元素  
    vector<A> vecClassA;

    A a1(1);
    A a2(2);
    A a3(3);

    //插入1 2 3  
    vecClassA.push_back(a1);
    vecClassA.push_back(a2);
    vecClassA.push_back(a3);


    int nSize = vecClassA.size();

    cout << "vecClassA:" << endl;

    //打印vecClassA,方法一：  
    for (int i = 0; i < nSize; i++)
    {
        cout << vecClassA[i].n << "     ";
    }
    cout << endl;

    //打印vecClassA,方法二：    
    for (int i = 0; i < nSize; i++)
    {
        cout << vecClassA.at(i).n << "     ";
    }
    cout << endl;

    //打印vecClassA,方法三：  
    for (vector<A>::iterator it = vecClassA.begin(); it != vecClassA.end(); it++)
    {
        cout << (*it).n << "     ";
    }
    cout << endl;

    return 0;
}

上述代码通过定义元素为类的向量，通过插入3个初始化的类，并通过3种方法输出，运行结果如下：

vecClassA:
1     2     3
1     2     3
1     2     3

上述代码通过定义元素为类指针的向量，通过插入3个初始化的类指针，并通过3种方法输出指针指向的类，运行结果如下：

vecClassA:
1       2       3
1       2       3
1       2       3

5.3删除函数

iterator erase(iterator it) :删除向量中迭代器指向元素
iterator erase(iterator first, iterator last) : 删除向量中[first, last)中元素
void pop_back() :删除向量中最后一个元素
void clear() : 清空向量中所有元素

例1：

// vectorsample.cpp : 定义控制台应用程序的入口点。  
//#include "stdafx.h"  
#include<iostream>  
#include<vector>  
using namespace std;

int main(int argc, char* argv[])
{
    //int型vector,包含3个元素  
    vector<int> vecIntA;

    //循环插入1 到10  
    for (int i = 1; i <= 10; i++)
    {
        vecIntA.push_back(i);
    }

    vecIntA.erase(vecIntA.begin() + 4);

    cout << "删除第5个元素后的向量vecIntA:" << endl;
    //打印vectorA  
    for (vector<int>::iterator it = vecIntA.begin(); it != vecIntA.end(); it++)
    {
        cout << *it << "\t";
    }
    cout << endl;

    //删除第2-5个元素  
    vecIntA.erase(vecIntA.begin() + 1, vecIntA.begin() + 5);

    cout << "删除第2-5个元素后的vecIntA:" << endl;
    //打印vectorA  
    for (vector<int>::iterator it = vecIntA.begin(); it != vecIntA.end(); it++)
    {
        cout << *it << "\t";
    }
    cout << endl;

    //删除最后一个元素  
    vecIntA.pop_back();

    cout << "删除最后一个元素后的vecIntA:" << endl;
    //打印vectorA  
    for (vector<int>::iterator it = vecIntA.begin(); it != vecIntA.end(); it++)
    {
        cout << *it << "\t";
    }
    cout << endl;

    return 0;
}

程序运行结果如下：

删除第5个元素后的向量vecIntA:
1       2       3       4       6       7       8       9       10
删除第2-5个元素后的vecIntA:
1       7       8       9       10
删除最后一个元素后的vecIntA:
1       7       8       9

5.4遍历函数

reference at(int pos) :返回pos位置元素的引用
reference front() : 返回首元素的引用
reference back() : 返回尾元素的引用
iterator begin() : 返回向量头指针，指向第一个元素
iterator end() : 返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin() : 反向迭代器，指向最后一个元素
reverse_iterator rend() : 反向迭代器，指向第一个元素之前的位置

5.5判空函数

bool empty() const:判断向量是否为空，若为空，则向量中无元素

5.6大小函数

int size() const:返回向量中元素的个数
int capacity() const:返回当前向量所能容纳的最大元素值
int max_size() const:返回最大可允许的vector元素数量值

5.7其他函数

void swap(vector&):交换两个同类型向量的数据
void assign(int n,const T& x):设置向量中第n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素
resize(num)重新指定队列的长度。（往往用来增加vector的长度，小->大 ok 大->小 没用！）
reserve()保留适当的容量。
front() 返回指向向量第一个元素的引用
back()返回指向向量最后一个元素的引用

1.assign函数介绍

函数原型：

void assign(const_iterator first, const_iterator last);
void assign(size_type n, const T& x = T());

void assign( std::initializer_list<T> ilist );//(C++11 起) (C++20 前)
constexpr void assign( std::initializer_list<T> ilist );//(C++20 起)

void assign(const_iterator first, const_iterator last);

功能：将区间[first,last)的元素赋值到当前的vector容器中，或者赋n个值为x的元素到vector容器中，这个容器会清除掉vector容器中以前的内容。

例1：

// vector assign
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
    std::vector<double> first{ 1.9, 2.9, 3.9, 4.9, 5.9 }; /*初始化源数组*/
    std::vector<double> second;                           /*声明空数组*/
    std::vector<int> third;
    std::vector<string> forth;

    std::vector<double>::iterator it;
    it = first.begin();

    second.assign(it, first.end());
    std::cout << "Size of second: " << int(second.size()) << '\n';
    for (int i = 0; i < second.size(); i++)
        cout << second[i] << " ";
    cout << endl;
    //结果：
    //Size of second: 5
    //1.9 2.9 3.9 4.9 5.9


    second.assign(it + 1, first.end() - 1);
    std::cout << "Size of second: " << int(second.size()) << '\n';
    for (int i = 0; i < second.size(); i++)
        cout << second[i] << " ";
    cout << endl;
    //Size of second: 3
    //2.9 3.9 4.9


    third.assign(it, first.end());
    std::cout << "Size of third: " << int(third.size()) << '\n';
    for (int i = 0; i < third.size(); i++)
        cout << third[i] << " ";
    cout << endl;
    //Size of third: 5
    //1 2 3 4 5

    int myints[] = { 1776,7,4 };
    third.assign(myints, myints + 3);  /* assign with array*/
    std::cout << "Size of third: " << int(third.size()) << '\n';
    for (int i = 0; i < third.size(); i++)
        cout << third[i] << " ";
    cout << endl;
    //Size of third: 3
    //1776 7 4

    //third.assign (myints,myints+4); /*error usage，有结果但是行为错误*/
    //1776 7 4 787800
    // third = first; /*error usage*/
    // forth.assign(it,first.end()); /*error usage*/
    return 0;
}

输出：

Size of second: 5
1.9 2.9 3.9 4.9 5.9
Size of second: 3
2.9 3.9 4.9
Size of third: 5
1 2 3 4 5
Size of third: 3
1776 7 4

void assign(size_type n, const T& x = T());

功能：将调用者中内容替换成n个x

例2：

// vector assign
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
    vector<double> first{ 1.9, 2.9, 3.9, 4.9, 5.9 }; /*初始化源数组*/
    cout << "Size of first: " << int(first.size()) << '\n';
    for (int i = 0; i < first.size(); i++)
        cout << first[i] << " ";
    cout << endl;

    first.assign(10, 5);
    cout << "Size of first: " << int(first.size()) << '\n';
    for (int i = 0; i < first.size(); i++)
        cout << first[i] << " ";
    cout << endl;

    return 0;
}

输出：

Size of second: 5
1.9 2.9 3.9 4.9 5.9
Size of second: 10
5 5 5 5 5 5 5 5 5 5

void assign( std::initializer_list<T> ilist );//(C++11 起) (C++20 前)
constexpr void assign( std::initializer_list<T> ilist );//(C++20 起)

功能：将当前vector内容替换成ilist中内容

// vector assign
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
    vector<double> first{ 1.9, 2.9, 3.9, 4.9, 5.9 }; /*初始化源数组*/
    vector<double> second{ 1, 2, 3, 4, 5 }; /*初始化源数组*/

    cout << "Size of first: " << int(first.size()) << '\n';
    for (int i = 0; i < first.size(); i++)
        cout << first[i] << " ";
    cout << endl;

    second.assign({1, 2, 3});
    cout << "Size of second: " << int(second.size()) << '\n';
    for (int i = 0; i < second.size(); i++)
        cout << second[i] << " ";
    cout << endl;

    return 0;
}

输出：

Size of first: 5
1.9 2.9 3.9 4.9 5.9
Size of second: 3
1 2 3

2.reserve和resize

vector 的reserve增加了vector的capacity，但是它的size没有改变！而resize改变了vector的capacity同时也增加了它的size！

原因如下：
reserve是容器预留空间，但在空间内不真正创建元素对象，所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用push_back()/insert()函数。

resize是改变容器的大小，且在创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。此时再调用push_back()函数，是加在这个新的空间后面的。

两个函数的参数形式也有区别的，reserve函数之后一个参数，即需要预留的容器的空间；resize函数可以有两个参数，第一个参数是容器新的大小， 第二个参数是要加入容器中的新元素，如果这个参数被省略，那么就调用元素对象的默认构造函数。

（1）resize用法：

void resize(size_type new_size);  
void resize(size_type new_size, const value_type& value);

void resize(size_type new_size); 

①new_size>size()时，如果new_size>capacity()，那么size()和capacity()大小同时变为new_size，重新分配出来的空间执行默认初始化。如果size()<new_size<capacity()，size()大小变为new_size、capacity()不变，size()和new_size之间的数据执行默认初始化，new_size和capacity()之间的数据无法访问。

②new_size<size()时，size()大小变为new_size，capacity()不变，new_size和capacity()之间数据无法访问

例1：

#include <iostream>  
#include <vector>  
using namespace std;

int main() 
{
    std::vector<int> vec(5); // 创建一个大小为5的向量  
    for (int i = 0; i < vec.size(); i++) 
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    
    for (int i = 0; i < vec.size(); i++)
    {
        vec[i] = 2*i;
        cout << vec[i] << " ";
    }
    
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.resize(7); // 改变向量的大小为7  
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }

    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.resize(5); // 改变向量的大小为5  
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }

    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    return 0;
}

输出：

0 0 0 0 0
0 2 4 6 8
vec.size():5, vec.capacity():5
===========================================================
0 2 4 6 8 0 0
vec.size():7, vec.capacity():7
===========================================================
0 2 4 6 8
vec.size():5, vec.capacity():7
===========================================================

void resize(size_type new_size, const value_type& value);

①new_size<size()时，结果是容器的size()减小到new_size，删除n之后的元素，capacity()不变

②size()<new_size<capacity()时，结果是容器的size()增加到new_size，增加的元素值初始化为value，capacity()不变

③new_size>capacity()时，结果是容器的size()和capacity()增加到new_size，增加的元素值初始化为value

例2：

#include <iostream>  
#include <vector>  
using namespace std;

int main() 
{
    std::vector<int> vec(5); // 创建一个大小为5的向量  
    for (int i = 0; i < vec.size(); i++) 
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < vec.size(); i++)
    {
        vec[i] = 2*i;
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.resize(3,6); // 改变向量的大小为3
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.resize(4, 6); // 改变向量的大小为3
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.resize(7, 6); // 改变向量的大小为3
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    return 0;
}

输出：

0 0 0 0 0
0 2 4 6 8
vec.size():5, vec.capacity():5
===========================================================
0 2 4
vec.size():3, vec.capacity():5
===========================================================
0 2 4 6
vec.size():4, vec.capacity():5
===========================================================
0 2 4 6 6 6 6
vec.size():7, vec.capacity():7
===========================================================

（2）reserve用法：

void reserve( size_type new_cap );//(C++20 前)
constexpr void reserve( size_type new_cap );//(C++20 起)

①new_cap < capacity()时，size与capacity均不发生改变；

②new_cap > capacity()时，此时会重新分配一块空间，使得capacity扩容至n，size不发生改变。

#include <iostream>  
#include <vector>  
using namespace std;

int main() 
{
    std::vector<int> vec(5); // 创建一个大小为5的向量  
    for (int i = 0; i < vec.size(); i++) 
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < vec.size(); i++)
    {
        vec[i] = 2*i;
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.reserve(3); // 改变向量的大小为3
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    vec.reserve(9);
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    cout << "vec.size():" << vec.size() << ", vec.capacity():" << vec.capacity() << endl;
    cout << "===========================================================" << endl;

    return 0;
}

输出：

0 0 0 0 0
0 2 4 6 8
vec.size():5, vec.capacity():5
===========================================================
0 2 4 6 8
vec.size():5, vec.capacity():5
===========================================================
0 2 4 6 8
vec.size():5, vec.capacity():9
===========================================================

例1：

#include<iostream>  
#include<vector>  
using namespace std;

void printVector(vector<int>& v)
{	//利用迭代器打印 v
    int i = 0;
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout  << *it << " ";
        i++;
        if(i%10 == 0)
            cout << endl;
    }
    cout << endl;
}

int main(int argc, char* argv[])
{
    vector<int> myVec;
    myVec.reserve(100);     // 新元素还没有构造,
    // 此时不能用[]访问元素
    for (int i = 0; i < 100; i++)
    {
        myVec.push_back(i); //新元素这时才构造
    }
    myVec.resize(102);      // 用元素的默认构造函数构造了两个新的元素
    myVec[100] = 1;           //直接操作新元素
    myVec[101] = 2;

    printVector(myVec);
    return 0;
}

5.8综合示例

// vectorsample.cpp : 定义控制台应用程序的入口点。  
//  
//#include "stdafx.h"
#include<iostream>  
#include<vector>  
#include<string>  
using namespace std;

class Student
{
public:
    string m_strNO;
    string m_strName;
    string m_strSex;
    string m_strDate;
public:
    Student(string strNO, string strName, string strSex, string strDate)
    {
        m_strNO = strNO;
        m_strName = strName;
        m_strSex = strSex;
        m_strDate = strDate;
    }
    void Display()
    {
        cout << m_strNO << "\t";
        cout << m_strName << "\t";
        cout << m_strSex << "\t";
        cout << m_strDate << "\t";
    }
};

class StudCollect
{
    vector<Student> m_vStud;
public:
    void Add(Student& s)
    {
        m_vStud.push_back(s);
    }
    Student* Find(string strNO)
    {
        bool bFind = false;
        int i;
        for (i = 0; i < m_vStud.size(); i++)
        {
            Student& s = m_vStud.at(i);
            if (s.m_strNO == strNO)
            {
                bFind = true;
                break;
            }
        }
        Student* s = NULL;
        if (bFind)
            s = &m_vStud.at(i);
        return s;
    }
};

int main(int argc, char* argv[])
{
    Student s1("1001", "zhangsan", "boy", "1988-10-10");
    Student s2("1002", "lisi", "boy", "1988-8-25");
    Student s3("1003", "wangwu", "boy", "1989-2-14");

    StudCollect s;
    s.Add(s1);
    s.Add(s2);
    s.Add(s3);

    Student* ps = s.Find("1002");
    if (ps)
        ps->Display();
    return 0;
}

代码运行实例如下：

1002    lisi    boy     1988-8-25

参考：vector容器用法详解 - 蒲公英110 - 博客园 (cnblogs.com)

6.vector容器的底层实现机制

作者建议还是稍微看一下底层机制，vector主要有三个指针(迭代器) 来表示的：

●_Myfirst 和 _Mylast 可以用来表示 vector 容器中目前已被使用的内存空间；
●_Mylast 和 _Myend 可以用来表示 vector 容器目前空闲的内存空间；
●_Myfirst 和 _Myend 可以用表示 vector 容器的容量。

对于空的 vector 容器，由于没有任何元素的空间分配，因此 _Myfirst、_Mylast 和 _Myend 均为 null。

vector扩容本质

另外需要指明的是，当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：

1.完全弃用现有的内存空间，重新申请更大的内存空间；
2.将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
3.最后将旧的内存空间释放。

这也就解释了，为什么 vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效的原因。

由此可见，vector 扩容是非常耗时的。为了降低再次分配内存空间时的成本，每次扩容时 vector 都会申请比用户需求量更多的内存空间（这也就是 vector 容量的由来，即 capacity>=size），以便后期使用。

vector 容器扩容时，不同的编译器申请更多内存空间的量是不同的。以 VS 为例，它会扩容现有容器容量的 50%。

参考：C++ STL vector容器(深入了解,一文学会)

2.STL中的list

1.list的介绍

1.list是序列容器，允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作，并在两个方向进行迭代。
2.list容器使用双链表实现；双链表将每个元素存储在不同的位置，每个节点通过next，prev指针链接成顺序表。
3.list与其他标准序列容器（array，vector和deque）相比，list通常可以在容器内的任何位置插入、提取和移动元素。
4.list与其他标准序列容器（array，vector和deque）相比，list和forward_list（单链表实现）的主要缺点是他们不能通过位置直接访问元素；例如，要访问列表中的第五个元素，必须从已知位置（开始或结束）迭代到该位置，需要线性时间开销。
5.存储密度低，list要使用一些额外的内容空间（next，prev）来保持与每个元素相关联（前后续的线性）的链接信息，从而导致存储小元素类型（如char，short，int等）的列表的存储密度低。

2.list函数说明

2.1成员类型

成员类型	定义
value_type	T
allocator_type	Allocator
size_type	无符号整数类型（通常是 std::size_t ）
difference_type	有符号整数类型（通常是 std::ptrdiff_t ）
reference	value_type&
const_reference	const value_type&
pointer	value_type*
const_pointer	const value_type*
iterator	指向 value_type 的双向迭代器
const_iterator	指向 const value_type 的双向迭代器
reverse_iterator	std::reverse_iterator
const_reverse_iterator	std::reverse_iterator<const_iterator>

2.2构造函数

函数	功能
list();	默认构造函数。构造拥有默认构造的分配器的空容器
list( size_type count,const T& value);	构造拥有 count 个有值 value 的元素的容器。
explicit list( size_type count );	构造拥有个 count 默认插入的 T 实例的容器。
list( InputIt first, InputIt last, const Allocator& alloc = Allocator() );	构造拥有范围 [first, last) 内容的容器。
list( const list& other );	复制构造函数。构造拥有 other 内容的容器。
list& operator=( const list& other );	复制赋值运算符。以 other 的副本替换内容。
list& operator=( std::initializer_list ilist );	以 initializer_list ilist 所标识者替换内容。
void assign( size_type count, const T& value );	以 count 份 value 的副本替换内容。
template< class InputIt >
void assign( InputIt first, InputIt last );	以范围 [first, last) 中元素的副本替换内容。
void assign( std::initializer_list ilist );	以来自 initializer_list ilist 的元素替换内容

例子：

#include <iostream>
#include <list>

using namespace std;

template<class T>
void Print(const list<T>& my)
{
	class list<T>::const_iterator it = my.begin();
	for (; it != my.end(); it++)
	{
		cout << *it << "\t";
	}

	cout << endl;
}

int main()
{
	list<int> list1 = { 12,23,34 };
	list<int> list2(3, 11);
	list<int> list3(list2);

	list<string> list4 = { "This","is","windows" };
	list<string> list5;
	list<string> list6;

	list5 = list4;

	list6.assign(3, "This");

	Print(list1);
	Print(list2);
	Print(list3);
	Print(list4);
	Print(list5);
	Print(list6);

	return 0;
}

输出：

12      23      34
11      11      11
11      11      11
This    is      windows
This    is      windows
This    This    This

2.3元素访问

元素访问	功能
reference front();	返回到容器首元素的引用
const_reference front() const;	返回到容器首元素的引用
reference back();	返回到容器中最后一个元素的引用
const_reference back() const;	返回到容器中最后一个元素的引用

例子：

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> list1 = { 12,23,34 };

	cout << "list1.front()：" << list1.front() << endl;
	cout << "list1.back()：" << list1.back() << endl;

	return 0;
}

输出：

list1.front()：12
list1.back()：34

2.4迭代器

迭代器	功能
iterator begin();	返回指向 list 首元素的迭代器
若 list 为空，则返回的迭代器将等于 end()
const_iterator begin() const;	返回指向 list 首元素的迭代器
若 list 为空，则返回的迭代器将等于 end()
iterator end();	返回指向 list 末元素后一元素的迭代器
const_iterator end() const;	返回指向 list 末元素后一元素的迭代器
reverse_iterator rbegin();	返回指向逆向 list 首元素的逆向迭代器
const_reverse_iterator rbegin() const;	返回指向逆向 list 首元素的逆向迭代器
reverse_iterator rend();	返回指向逆向 list 末元素后一元素的逆向迭代器
const_reverse_iterator rend() const;	返回指向逆向 list 末元素后一元素的逆向迭代器

例子：

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> list1 = { 12,23,34 };

	list<int>::const_iterator it1 = list1.begin();
	for (; it1 != list1.end(); it1++)
	{
		cout << *it1 << "\t";
	}

	cout << endl;

	list<int>::reverse_iterator it2 = list1.rbegin() ;
	for (; it2 != list1.rend(); it2++)
	{
		cout << *it2 << "\t";
	}

	cout << endl;
	
	return 0;
}

输出：

12      23      34
34      23      12

2.5容量

容量	功能
bool empty() const;	检查容器是否无元素，即是否 begin() == end()
size_type size() const;	返回容器中的元素数，即 std::distance(begin(), end())
size_type max_size() const;	返回根据系统或库实现限制的容器可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end())

例子：

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> list1 = { 12,23,34 };

	cout << "list1.empty():" << list1.empty() << endl;
	cout << "list1.size():" << list1.size() << endl;
	cout << "list1.max_size():" << list1.max_size() << endl;

	return 0;
}

输出：

list1.empty():0
list1.size():3
list1.max_size():768614336404564650

2.6修改器

修改器	功能
void clear();	从容器擦除所有元素。此调用后 size() 返回零
iterator insert( iterator pos, const T& value );	在 pos 前插入 value
void insert( iterator pos, size_type count, const T& value );	在 pos 前插入 value 的 count 个副本
template< class InputIt >
void insert( iterator pos, InputIt first, InputIt last);	在 pos 前插入来自范围 [first, last) 的元素
iterator insert( const_iterator pos, std::initializer_list ilist );	在 pos 前插入来自 initializer_list ilist 的元素
iterator erase( iterator pos );	移除位于 pos 的元素
iterator erase( iterator first, iterator last );	移除范围 [first; last) 中的元素
void pop_back();	移除容器的末元素
void push_front( const T& value );	前附给定元素 value 到容器起始
void push_back( const T& value );	后附给定元素 value 到容器尾
void pop_front();	移除容器首元素
void resize( size_type count );	重设容器大小以容纳 count 个元素
void resize( size_type count, T value = T() );	count - 容器的大小，value - 用以初始化新元素的值
void swap( list& other );	将内容与 other 的交换

例子：

#include <iostream>
#include <list>

using namespace std;

template<class T>
void Print(const list<T>& my)
{
	typename list<T>::const_iterator it = my.begin();
	for (; it != my.end(); it++)
	{
		cout << *it << "\t";
	}

	cout << endl;
}

int main()
{
	list<int> list1 = { 12,23,34 };
	list<int> list2 = { 1,2,3,4,5 };
	
	Print(list1);
	Print(list2);
	auto it = list1.begin();
	list1.insert(it, 55);
	Print(list1);
	it++;
	list1.insert(it, 3, 55);
	Print(list1);

	list1.erase(it);
	Print(list1);

	list1.swap(list2);
	Print(list1);
	Print(list2);


	return 0;
}

输出：

12      23      34
1       2       3       4       5
55      12      23      34
55      12      55      55      55      23      34
55      12      55      55      55      34
1       2       3       4       5
55      12      55      55      55      34

2.7操作

操作	功能
void merge( list& other );	归并二个已排序链表为一个。链表应以升序排序
void splice( const_iterator pos, list& other );	从 other 转移所有元素到 *this 中。元素被插入到 pos 所指向的元素之前。操作后容器 other 变为空
void splice( const_iterator pos, list& other, const_iterator it );	从 other 转移 it 所指向的元素到 *this 。元素被插入到 pos 所指向的元素之前
void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);	从 other 转移范围 [first, last) 中的元素到 *this 。元素被插入到 pos 所指向的元素之前
void remove( const T& value );	移除所有满足特定标准的元素。value - 要移除的元素的值
void reverse();	逆转容器中的元素顺序
void unique();	从容器移除所有相继的重复元素。只留下相等元素组中的第一个元素
void sort();	以升序排序元素。保持相等元素的顺序。用 operator< 比较元素
template< class Compare >
void sort( Compare comp );	以升序排序元素。保持相等元素的顺序。用给定的比较函数 comp

例子：

#include <iostream>
#include <list>

using namespace std;

template<class T>
void Print(const list<T>& my)
{
	typename list<T>::const_iterator it = my.begin();
	for (; it != my.end(); it++)
	{
		cout << *it << "\t";
	}

	cout << endl;
}

int main()
{
	list<int> list1 = { 2,1,9,5,3,7 };
	list<int> list2 = { 1,8,3,6,0,1,5 };
	
	Print(list1);
	Print(list2);

	list1.sort();
	list2.sort();

	Print(list1);
	Print(list2);

	list2.unique();
	Print(list2);

	list1.merge(list2);
	Print(list1);
	Print(list2);

	return 0;
}

输出：

2       1       9       5       3       7
1       8       3       6       0       1       5
1       2       3       5       7       9
0       1       1       3       5       6       8
0       1       3       5       6       8
0       1       1       2       3       3       5       5       6       7       8       9

2.8vector和list区别

区别	vector	list
底层实现	连续存储的容器，动态数组，在堆上分配空间	动态双向链表，在堆上
空间利用率	连续空间，不易造成内存碎片，空间利用率高	节点不连续，易造成内存碎片，小元素使节点密度低，空间利用率低
查询元素	iterator operator[];find O(n);binary_search O(logn)	iterator find O(n)
插入和删除	在最后插入（空间够）：push_back(val);O(1)。在最后插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。在之间插入（空间够）：内存拷贝。在之间插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。Insert(it,va) ,O(n)。在最后删除：pop_back()，O(1)。在之间删除：内存拷贝，不需要释放内存。erase(it),O(n)。resize(10)：开辟空间，存储数据。reserve(10)：只开辟空间，不存储数据。初始化vector空间，提高vector的使用效率。版权声明：本文为CSDN博主「愚蠢的土拨鼠。」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。	插入：O(1),需要申请内存。push_back()，O(1)；erase(it) ,O(n);
迭代器	随机迭代器，迭代器检查越界。支持++，–，+，+=，<，>，!=，==	双向迭代器，迭代器检查越界。支持++,–,==,!=
迭代器失效	插入和删除元素都会导致迭代器失效	插入元素

总结

1.vector底层实现是数组；list是双向链表。
2.vector支持随机访问，list不支持。
3.vector是顺序内存，list不是。
4.vector在中间节点进行插入删除会导致内存拷贝，list不会。
5.vector一次性分配好内存，不够时才进行扩容；list每次插入新节点都会进行内存申请。
6.vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

vector和list的使用场景

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机存取，而不在乎插入和删除的效率（很少使用插入和删除操作），选用vector
list 拥有一段不连续的内存空间，如果需要大量的插入和删除的操作，随机存取很少使用，选用list。

参考: C++中list详解_c++ list_愚蠢的土拨鼠。的博客-CSDN博客

3.STL中list的实现

3.1接口总览

namespace qgw 
{
	/// @brief list 中每个节点
	/// @tparam T 节点存储的数据的类型
	template <class T>
	struct _list_node
	{
		_list_node(const T& data = val());	// 节点类的构造函数

		_list_node<T>* _prev;				// 指向前一节点
		_list_node<T>* _next;				// 指向后一节点
		T _data;							// 存储节点数据
	};

	/// @brief list 的迭代器
	/// @tparam T list 数据的类型
	/// @tparam Ref 数据的引用类型
	/// @tparam Ptr 数据的指针类型
	template <class T, class Ref, class Ptr>
	struct _list_iterator 
	{
		typedef _list_iterator<T, T&, T*>		iterator;
		typedef _list_iterator<T, Ref, Ptr>		self;

		typedef Ptr		pointer;
		typedef Ref		reference;
		typedef _list_node<T> list_node;

		// 构造函数
		_list_iterator(list_node* node = nullptr);

		// 各种运算符重载
		bool operator==(const self& x) const;
		bool operator!=(const self& x) const;
		reference operator*() const;
		pointer operator->() const;
		self& operator++();
		self operator++(int);
		self& operator--();
		self operator++(int);

		list_node* _node;	// 指向对应的 list 节点
	};

	template <class T>
	class list 
	{
	public:
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef _list_node<T>	list_node;
		typedef _list_iterator<T, T&, T*>             iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

	public:
		// 默认成员函数
		list();
		list(const list<T>& other);
		list<T>& operator=(const list<T>& other);
		~list();

		// 元素访问
		reference front();
		const_reference front() const;
		reference back();
		const_reference back() const;

		// 迭代器
		iterator begin();
		const_iterator begin() const;
		iterator end();
		const_iterator end() const;

		// 容量
		bool empty() const;
		size_t size() const;

		// 修改器
		void clear();
		iterator insert(iterator pos, const_reference val);
		void push_front(const_reference val);
		void push_back(const_reference val);
		iterator erase(iterator pos);
		void pop_front();
		void pop_back();
		void swap(list& other);

		// 操作
		void splice(iterator pos, list& other);
		void splice(iterator pos, list& other, iterator it);
		void splice(iterator pos, list& other, iterator first, iterator last);
		void merge(list& other);
		void remove(const_reference value);
		void reverse();
		void unique();

	private:
		list_node* _node;	// 指向链表头节点
	};
}

3.2list 的节点

list 的节点我们设计成一个 _list_node 类，里面有三个成员变量，分别为前后指针和数据。

它的构造函数将数据初始化为给定数据，再将前后指针初始化为空。

/// @brief 节点类的构造函数
/// @param data 用来构造节点的初值
_list_node(const T& data = T()) : _data(data) 
{
    _prev = nullptr;
    _next = nullptr;
}

3.3默认成员函数

3.3.1默认构造函数

SGI list 不仅是一个双向链表，还是一个带头的循环链表。

/// @brief 构造一个空链表
list()
{
    _node = new list_node;	// 创建一个头节点
    _node->_prev = _node;	// 前面指向自己
    _node->_next = _node;	// 后面指向自己
}

3.3.2析构函数

list 的析构函数，先调用 clear 释放数据资源，再 delete 掉头节点即可。

/// @brief 释放资源
~list() 
{
    clear();
    delete _node;
    _node = nullptr;
}

3.3.3拷贝构造函数

用另一容器创建新对象。

先申请一个头节点，然后遍历 other 容器，将 other 中的数据逐一尾插到 *this 中。

/// @brief 用给定容器初始化
/// @param other 用来初始化的容器
list(const list<T>& other)
{
    _node = new list_node;
    _node->_next = _node;
    _node->_prev = _node;
    for (const auto& e : other) 
    {
        push_back(e);
    }
}

3.3.4复制赋值函数

先创建给定容器的拷贝 tmp，然后交换 *this 和 tmp，最后返回 *this。

/// @brief 替换容器内容
/// @param other 用作数据源的另一容器
/// @return *this
list<T>& operator=(const list<T>& other)
{
    // tmp 出了作用域就销毁了
    list<T> tmp(other);
    swap(tmp);
    // 返回引用可以连续赋值
    return *this;
}

3.3.5构造函数

list 的迭代器中成员变量只有一个节点指针，将其指向给定节点即可。

/// @brief list 迭代器的构造函数
/// @param node 用来构造的节点
_list_iterator(list_node* node = nullptr) 
{
    _node = node;
}

3.3.6运算符重载

①operator==

判断两迭代器指向的节点是否为同一个，直接比较迭代器中节点的指针即可。切记不能比较指针中的值，因为不同节点的值可能相同。

/// @brief 判断两迭代器指向的节点是否相同
/// @param x 用来比较的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const
{
    return _node == x._node;
}

②operator!=

!= 的比较方法和 == 一样。

/// @brief 判断两迭代器指向的节点是否不同
/// @param x 用来比较的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const
{
    return _node != x._node;
}

③operator*

迭代器是模仿指针的，让我们可以像使用指针一样。因此可以对迭代器进行解引用操作，该操作得到的是迭代器中节点指针指向的数据，并且返回引用，因为有可能修改该数据。

/// @brief 获取指向节点中的数据值
/// @return 返回指向节点数据的引用
reference operator*() const
{
    return _node->_data;
}

④operator->

-> 运算符的重载稍显复杂，让我们先看下面这个场景。

也就是 list 中存储的是自定义类型，自定义类型中又有多个成员变量，我们想取出指定的成员变量，当然这里用 . 也可以做到。

// 有一个学生类，里面有姓名和学号两个成员
struct Stu
{
	string name;
	string id;
};

list<Stu> s;
Stu s1 = { "qgw", "001" };
Stu s2 = { "wlr", "002" };
s.push_back(s1);
s.push_back(s2);
list<Stu>::iterator ptr = s.begin();
// 输出第一个学生的姓名和学号
cout << (*ptr).name << endl;
cout << s.begin()->id << endl;

看到这你可能会疑惑，operator-> 返回的是节点的数据的地址，也是说上面 s.begin()-> 得到的是一个地址，那这条语句是怎么执行的？

实际上这里确实应该有两个箭头像这样 s.begin()->->id，但这种方式的可读性太差了，所以编译器对此做了优化，在编译为我们添加一个箭头。

⑤operator++

operator++ 运算符的作用十分清晰，就是让迭代器指向链表中下一节点。

前置实现的思路是：通过迭代器中的节点指针找到下一节点，然后赋值给迭代器中的节点指针。

后置实现的思路是：先保存当前位置迭代器，然后调用前置 ++，最后返回临时变量。

需要注意的是：前置 ++ 返回的是前进后迭代器的引用，后置 ++ 返回的是一个临时变量。

/// @brief 前置 ++
/// @return 返回前进一步后的迭代器
self& operator++() 
{
    _node = _node->_next;
    return *this;
}

/// @brief 后置 ++
/// @param  无作用，只是为了与前置 ++ 进行区分，形成重载
/// @return 返回当前的迭代器
self operator++(int)
{
    self tmp = *this;
    // 直接调用前置 ++
    ++(*this);
    return tmp;
}

⑥operator--

前置实现的思路是：通过迭代器中的节点指针找到前一节点，然后赋值给迭代器中的节点指针。

后置实现的思路是：先保存当前位置迭代器，然后调用前置 --，最后返回临时变量。

/// @brief 前置 --
/// @return 返回后退一步后的迭代器
self& operator--()
{
    _node = _node->_prev;
    return *this;
}

/// @brief 后置 --
/// @param  无作用，只是为了与前置 -- 进行区分，形成重载
/// @return 返回当前的迭代器
self operator--(int) 
{
    self tmp = *this;
    --(*this);
    return tmp;
}

3.4list 的迭代器

list 的节点在内存中不是连续存储的，因此不能使用原生指针作为 list 的迭代器。list 的迭代器必须有能力指向 list 的节点，并能够正确的递增、递减、取值、成员存取等操作。正确的操作是指：递增时指向下一节点，递减时指向上一节点，取值时取的是节点的数据值，成员取用的是节点的成员。

由于 STL list 是一个双向链表（double linked-list），迭代器必须具备前移、后移的能力，所以 list 提供的是 Bidirectional Iterators。

3.4.1begin

begin() 获取的是首元素的迭代器，根据上图，直接返回头节点的下一位置即可。

/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() 
{
    // 根据节点指针构造迭代器
    return iterator(_node->_next);
}

// const 版本供 const 容器使用
const_iterator begin() const
{
    return const_iterator(_node->_next);
}

3.4.2end

end() 获取的是最后一个元素下一个位置的迭代器，根据上图就是 _node 所指向的节点。

/// @brief 返回指向 forward_list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() 
{
    // 调用 iterator 构造函数
    return iterator(_node);
}

const_iterator end() const 
{
    return const_iterator(_node);
}

3.5元素访问

3.5.1front

front() 获取容器首元素的引用，调用 begin() 得到首元素的迭代器，再解引用即可。

因为 forward_list 的迭代器只能单向移动，故不能快速获得链表中最后一个节点。

/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front() 
{
    return *begin();
}

// 与上面唯一不同就是用于 const 容器
const_reference front() const
{
    return *begin();
}

3.6容量

3.6.1empty

begin() 和 end() 指向相同，说明链表此时只有一个头节点，链表为空。

/// @brief 检查容器是否无元素
/// @return 若容器为空则为 true，否则为 false
bool empty() const 
{
    return begin() == end();
}

3.7修改器

3.7.1insert_after

根据 STL 的习惯，插入操作会将新元素插入于指定位置之前，而非之后。然而 forward_list 是一个单向链表，它没有任何方便的方法可以定位出前一个位置，它必须从头找。因此，forward_list 中提供的插入操作，是插入在指定位置之后。

下图为：只有 0、1 两个元素的单链表，在 0 之后插入元素值为 2 的节点的示意图。

插入的过程非常简单：

1.创建一个要插入的节点

2.插入节点的 _next 指向 pos 后一位置的节点

3.pos 的 _next 指向要插入的节点

/// @brief 在容器中的指定位置后插入元素
/// @param pos 内容将插入到其后的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入元素的迭代器
iterator insert_after(iterator pos, const_reference val)
{
    forward_list_node* tmp = new forward_list_node(val);	// 创建要插入的节点
    tmp->_next = pos._node->_next;							// (1)
    pos._node->_next = tmp;									// (2)
    return tmp;
}

3.7.2push_front

push_front 的作用是在容器起始处插入元素。

直接调用 insert_after() 插入就行，需要注意的是，insert_after() 是在给定位置之后插入，所以应传入头节点对应的迭代器位置。

/// @brief 头插给定元素 val 到容器起始
/// @param val 要头插的元素值
void push_front(const_reference val) 
{
	// end() 返回头节点位置的迭代器，在这之后插入是头插
	insert_after(end(), val);
}

3.7.3erase_after

下图为：有三个元素 0、1、2 的链表，删除 pos 指向节点之后节点（值为 1）的示意图。

删除的过程非常简单：

1.记录 pos 的下一节点 nextNode

2.将 pos 的 _next 指向 nextNode 的下一个节点

3.delete 释放掉 nextNode 所指向的节点

/// @brief 从容器移除 pos 后面一个元素
/// @param pos 指向要被移除元素前一个元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase_after(iterator pos) 
{
    forward_list_node* nextNode = pos._node->_next;		// 记录 pos 指向节点的下一节点
    pos._node->_next = nextNode->_next;					// (1)
    delete (nextNode);
    return (iterator)(pos._node->_next);
}

3.7.4pop_front

pop_front() 移除容器的首元素，也就是 end() 指向的下一节点。

/// @brief 移除容器首元素
void pop_front() 
{
    erase_after(end());
}

3.7.5clear

clear() 用于清空容器所有数据，不清理头节点。

要注意 erase_after() 删除给定位置下一个节点，end 的下一个是第一个元素，这样以次删除直到容器为空，即只剩一个头节点。

/// @brief 从容器擦除所有元素
void clear() 
{
    while (!empty())
    {
        erase_after(end());
    }
}

3.7.6swap

swap() 用来交换两个 forward_list容器，不用交换 forward_list 中每个元素的值，直接交换 _node 指针即可。

/// @brief 将内容与 other 的交换
/// @param other 要与之交换内容的容器
void swap(forward_list& other) 
{
    std::swap(_node, other._node);
}

参考：STL forward_list 模拟实现

4.forward_list

forward_list为单向链表的泛化容器，与list双向链表容器一样，实现了线性表数据的链表存储，数据元素不必在物理内存中连续分布。STL中List是双向链表，而Slist是单向链表。它们的区别：Slist的迭代器是单向的Forward Iterator，而list的迭代器是双向的Bidirectional Iterator。Slist所耗用的空间更小，操作更快。它们共同的特点是，插入、移除、接合等操作并不会造成原有的迭代器失效。slist插入时，需要从前遍历，找到插入点的位置。为了更快插入，提供了insert_after，erase_after。slist提供push_front()操作，故其元素次序与元素插入顺序相反。

4.1forward_list技术原理

forward_list内部的链表由头指针、头节点和元素节点组成，每个节点含有指向后继节点的指针，最后一个节点的指针为null，可见forward_list没有形成一个环形回路。

头节点一般不存储数据，为了使各个元素节点都有前驱节点的指针指向它以便能够不加区别的对第一个元素节点和其他元素节点进行统一处理，所以构造头节点。

slist应用基础
list对象的创建和vector一样，不多解释。元素的删除、归并、排序与list相同。

使用时需要包含头文件

// 包含头文件
#include <forward_list>

4.2初始化

通常使用push_front函数进行初始化，由于slist的头节点仅有一个指针域保存首元素地址，而没有存放最后一个元素的地址，因此slist没有提供类似的push_back函数能够在容器尾部添加元素。push_front函数在链表首元素前面，插入一个新元素，使之成为首元素。

forward_list<类型名>	链表名; 单向链表
forward_list<int> f1;	创建一个名为f1的单向链表，f1中的元素类型为int
forward_list<int> f1(100,7);	f1中的元素为100个7
forward_list<int> f1{1,2,3,……};	f1{1,2,3,……}; 元素为1,2,3,……的f1
forward_list<int> f2(f1);	链表f2中包含和链表f1一样的元素
forward_list<int> f2=f1;	链表f2中包含和链表f1一样的元素

4.3forward_list构造

构造函数	功能
forward_list();(1)	默认构造函数。构造拥有默认构造的分配器的空容器。
explicit forward_list(const Allocator& alloc);(2)	构造拥有给定分配器 alloc 的空容器。
forward_list(size_type count, const T& value, const Allocator& alloc = Allocator());(3) (C++11 起)	构造拥有 count 个有值 value 的元素的容器。
explicit forward_list(size_type count);(C++11 起)(4)(C++14 前)
explicit forward_list(size_type count, const Allocator& alloc = Allocator());(4)(C++14 起)	构造拥有 count 个 默认插入的 T 实例的容器。不进行复制。
template< class InputIt > forward_list(InputIt first, InputIt last, const Allocator& alloc = Allocator());(5) (C++11 起)	构造拥有范围 [first, last) 内容的容器。如果 InputIt 是整数类型，那么此构造函数拥有的效果同forward_list(static_cast<size_type>(first), static_cast<value_type>(last), a)。 (C++11 前) 此重载只有在InputIt 满足老式输入迭代器 (LegacyInputIterator) 时才会参与重载决议，以避免和重载 (3) 的歧义。(C++11 起)
forward_list(const forward_list& other);(6) (C++11 起)	复制构造函数。构造拥有 other 内容的容器。 如同通过调用 std::allocator_traits<allocator_type>::select_on_container_copy_construction( other.get_allocator()) 获得分配器。
forward_list(const forward_list& other, const Allocator& alloc);(7) (C++11 起)	构造拥有 other 内容的容器，以 alloc 为分配器。 在进行类模板实参推导时，只会从首个实参推导模板形参 Allocator。(C++23 起)
forward_list(forward_list&& other);(8) (C++11 起)	移动构造函数。用移动语义构造拥有 other 内容的容器。分配器通过属于 other 的分配器移动构造获得。
forward_list(forward_list&& other, const Allocator& alloc);(9) (C++11 起)	有分配器扩展的移动构造函数。以 alloc 为新容器的分配器，从 other 移动内容；如果 alloc != other.get_allocator() ，那么它会导致逐元素移动。在进行类模板实参推导时，只会从首个实参推导模板形参 Allocator。(C++23 起)
forward_list(std::initializer_list init, const Allocator& alloc = Allocator());(10) (C++11 起)	构造拥有 initializer_list init 内容的容器。

参数

alloc	用于此容器所有内存分配的分配器
count	容器的大小
value	以之初始化容器元素的值
first, last	复制元素的来源范围
other	用作初始化容器元素来源的另一容器
init	用作初始化元素来源的 initializer_list

构造、复制与析构

函数	功能
forward_list<Elem> c;	默认构造函数；创建一个空forward_list
forward_list<Elem> c(c2);	复制构造函数；创建一个新的forward_list作为c2的副本（所有元素都被复制）
forward_list<Elem> c = c2;	复制构造函数；创建一个新的forward_list作为c2的副本（所有元素都被复制）
forward_list<Elem> c(rv);	移动构造函数；使用右值对象rv创建一个新forward_list
forward_list<Elem> c = rv;	移动构造函数；使用右值对象rv创建一个新forward_list
forward_list<Elem> c(n) ;	使用默认构造函数创建含有n个元素的forward_list
forward_list<Elem> c(n,elem) ;	创建一个forward_list，并使用n个elem进行初始化
forward_list<Elem> c(beg,end) ;	创建一个forward_list，并使用beg到end范围内的值进行初始化
forward_list<Elem> c(initlist);	创建一个forward_list，并使用初始化列表进行初始化
forward_list<Elem> c = initlist;	创建一个forward_list，并使用初始化列表进行初始化
c.~forward_list() ;	销毁所有元素并释放内存

4.4赋值

表达式	功能
c = c2；	将c2所有元素赋值给c
c = rv；	将右值对象rv的所有元素移动赋值给c
c = initlist；	使用初始化列表进行赋值
c.assign(initlist)；	使用初始化列表进行赋值
c.assign(n,elem)；	使用n个elem元素进行赋值
c.assign(beg,end)；	使用beg到end范围内的元素进行赋值
c1.swap(c2)；	交换c1和c2的数
swap(c1,c2)	交换c1和c2的数

4.5非变动性操作

表达式	功能
c.empty()	判断容器是否为空
c.max_size()	返回可容纳的元素最大数量
c1 == c2	判断c1与c2是否相等
c1 != c2	判断c1与c2是否不相等，等同于!(c1==c2)
c1 < c2	判断c1是否小于c2
c1 > c2	判断c1是否大于c2
c1 <= c2	判断c1是否小于等于c2
c1 >= c2	判断c1是否大于等于c2

4.6迭代器相关函数

表达式	功能
c.begin()	返回一个双向迭代器，指向第一个元素
c.end()	返回一个双向迭代器，指向最后一个元素
c.cbegin()	返回一个双向常迭代器，指向第一个元素
c.cend()	返回一个双向常迭代器，指向最后一个元素
c.before_begin()	返回一个前向迭代器，指向第一个元素之前的位置
c.cbefore_begin()	返回一个前向常迭代器，指向第一个元素之前的位置

4.7插入和移除元素

表达式	功能
c.push_front(elem)	在头部添加一个elem副本
c.pop_front()	移除头部元素（但不回传）
c.insert_after(pos,elem)	在迭代器位置之后插入一个elem副本，并返回新元素的位置
c.insert_after(pos,n,elem)	在迭代器位置之后插入n个elem副本，并返回第一个新元素的位置；若无新插入值，返回原位置
c.insert_after(pos,beg,end)	在迭代器位置之后插入范围beg到end的所有元素的副本，并返回第一个新元素的位置；若无新插入值，返回原位置
c.insert_after(pos,initforward_list)	在迭代器位置之后插入初始化列表的所有元素的副本，并返回第一个新元素的位置；若无新插入值，返回原位置
c.emplace_after(pos,args...)	在迭代器位置之后插入一个使用args初始化的元素副本，并返回新元素的位置
c.emplace_front(args...)	在头部添加一个使用args初始化的元素副本，无返回值
c.erase_after(pos)	移除迭代器位置的元素，无返回值
c.erase_after(beg,end)	移除beg到end范围内的所有元素，无返回值
c.remove(val)	移除所有值为val的元素
c.remove_if(op)	移除所有满足op条件的元素
c.resize(num)	将元素数量设为num（如果size()增大，多出来的元素使用默认构造函数创建）
c.resize(num,elem)	将元素数量设为num（如果size()增大，多出来的元素都是elem的副本）
c.clear()	移除所以元素，清空容器

4.8特殊修改操作

表达式	功能
c.unique()	若存在相邻而数值相等的元素，移除重复元素
c.unique(op)	若存在相邻而数值相等的元素，且满足op条件时，移除重复元素
c.splice_after(pos,c2)	将c2内的所有元素转移到c1内pos所指的位置之后
c.splice_after(pos,c2,c2pos)	将c2内c2pos之后的元素转移到c1内pos所指的位置之后
c.splice_after(pos,c2,c2beg,c2end)	将c2内从c2beg到c2end区间内的所有元素转移到c1内pos所指的位置之后
c.sort()	以operator<为准则，对所有元素排序
c.sort(op)	以op为准则，对所有元素排序
c.merge(c2)	假设c1和c2都包含已序元素，将c2的全部元素转移到c1.并保证合并后的forward_list仍为已序
c.merge(c2,op)	假设c1和c2都包含op原则下已序元素，将c2的全部元素转移到c1.并保证合并后的forward_list在op原则下仍为已序
c.reverse()	将所有元素反序

参考：STL学习笔记— —容器forward_list

4.9实现

4.9.1接口总览

namespace qgw 
{
	/// @brief forward_list 中每个节点
	/// @tparam T 节点存储的数据类型
	template <class T>
	struct _forward_list_node 
	{
		_forward_list_node(const T& data = T());	// 节点类的构造函数

		_forward_list_node<T>* _next;				// 指向后一节点
		T _data;									// 存储节点数据
	};

	/// @brief forward_list 的迭代器
	/// @tparam T forward_list 数据的类型
	/// @tparam Ref 数据的引用类型
	/// @tparam Ptr 数据的指针类型
	template <class T, class Ref, class Ptr>
	struct _forward_list_iterator
	{
		typedef _forward_list_iterator<T, T&, T*>		iterator;
		typedef _forward_list_iterator<T, Ref, Ptr>		self;

		typedef Ptr pointer;
		typedef Ref reference;
		typedef _forward_list_node<T> forward_list_node;

		// 构造函数
		_forward_list_iterator(forward_list_node* node = nullptr);

		// 各种运算符重载
		bool operator==(const self& x) const;
		bool operator!=(const self& x) const;
		reference operator*() const;
		pointer operator->() const;
		self& operator++();
		self operator++(int);

		forward_list_node* _node;	// 指向对应的 forward_list 节点
	};

	template <class T>
	class forward_list 
	{
	public:
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef _forward_list_node<T>	forward_list_node;
		typedef _forward_list_iterator<T, T&, T*>             iterator;
		typedef _forward_list_iterator<T, const T&, const T*> const_iterator;

	public:
		// 默认成员函数
		forward_list();
		forward_list(const forward_list<T>& other);
		forward_list<T>& operator=(const forward_list<T>& other);
		~forward_list();

		// 元素访问
		reference front();
		const_reference front() const;

		// 迭代器
		iterator begin();
		const_iterator begin() const;
		iterator end();
		const_iterator end() const;

		// 容量
		bool empty() const;

		// 修改器
		void clear();
		iterator insert_after(iterator pos, const_reference val);
		void push_front(const_reference val);
		iterator erase_after(iterator pos);
		void pop_front();
		void swap(forward_list& other);

	private:
		forward_list_node* _node;
	};
}

4.9.2forward_list 的节点

forward_list 节点的设计与 list 的节点类似，只需两个成员变量：一个节点指针和数据。

构造函数将数据初始化为给定数据，再将 _next 指针初始化为空。

/// @brief 节点类的构造函数
/// @param data 用来构造节点的初值
_forward_list_node(const T& data = T()) : _data(data) 
{
    _next = nullptr;
}

4.9.3默认成员函数

①默认构造函数

因为实现的是的单向带头循环链表，所以要在构造函数创建一个头节点，并将 _next 指针指向自己。

/// @brief 构造一个空链表
forward_list() 
{
    _node = new forward_list_node;	// 创建一个头节点
    _node->_next = _node;			// 后面指向自己
}

②析构函数

forward_list 的析构函数，先调用 clear() 释放数据资源，再 delete 掉头节点即可。

/// @brief 释放资源
~forward_list() 
{
    clear();
    delete _node;
    _node = nullptr;
}

③forward_list 的迭代器

forward_list 的节点在内存中不是连续存储的，因此不能使用原生指针作为 forward_list 的迭代器。

由于 forward_list 是一个单向链表，迭代器必须具备后移的能力，所以 forward_list 提供的是 Forward Iterator。

④构造函数

forward_list 的迭代器中成员变量只有一个节点指针，将其初始化为给定的节点指针。

/// @brief 迭代器的构造函数
/// @param node 用来构造的节点
_forward_list_iterator(forward_list_node* node = nullptr)
{
    _node = node;
}

⑤operator==

两个 forward_list 迭代器的比较，实际上比较的是迭代器所指向的节点，指向同一节点即为两迭代器相同。

/// @brief 判断两迭代器指向的节点是否相同
/// @param x 用来比较的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const
{
    return _node == x._node;
}

⑥operator!=

operator!= 的实现可以借助 operator==，直接调用判断是否相等的函数，然后返回相反的结果。

/// @brief 判断两迭代器指向的节点是否不同
/// @param x 用来比较的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const 
{
    return !operator==(x);
}

⑦operator*

当我们对一个指针进行解引用时会发生什么，我们会得到指针指向的数据。同理，我们对迭代器进行解引用，得到的是迭代器中节点指针所指向变量的值。

/// @brief 获取指向节点中的数据值
/// @return 返回指向节点数据的引用
reference operator*() const 
{
    return (*_node)._data;
}

⑧operator->

假如我们有如下数据类：

// 有一个 Person 类，里面有身高和体重两个成员
struct Person 
{
	double height;
	double weight;
};

此时，我们的数据不再是单一的变量了，而是一个结构体变量。我们想读取其中的数据，该怎么操作呢？

Person p1 = { 165, 105 };
Person* p = &p1;
cout << (*p).height << endl;	// 获取身高数据
cout << p->weight << endl;		// 获取体重数据

我们可以先对直接解引用得到一个 Person 对象，再用 . 操作符访问其中的变量。

当然我们也可以选择对 Person* 使用 -> 操作符访问结构体内的变量。

于是乎，operator-> 的功能也就很清晰了。当我们对迭代器使用 -> 时我们可以直接访问节点中的变量。也就是说，我们有一迭代器 iter，其中迭代器中存储的数据类型为 Person，当我们使用 iter->height 时，可以直接获取到身高。

/// @brief 获取节点中数据的地址
/// @return 返回节点指向的数据的地址
pointer operator->() const 
{
    return &(operator*());
}

看了实现你可能会疑惑 iter-> 获得的明明是结构体的指针，后面应该再跟一个 -> 箭头才对。是的没错，确实应该是这样，不过 iter->->height 的可读性比较差，所以编译器会在编译时自动为我们添加一个箭头。

⑨operator++

operator++ 运算符的作用是让迭代器指向 forward_list 中下一节点。因为 forward_list 是单链表不能向前移动，所以不用实现 operator--。

前置实现的思路是：通过迭代器中的节点指针找到下一节点，然后赋值给迭代器中的节点指针。

后置实现的思路是：先拷贝一份当前位置的迭代器，然后调用前置 ++，最后返回临时变量。

需要注意的是：前置 ++ 返回的是前进后迭代器的引用，后置 ++ 返回的是一个临时变量。

/// @brief 前置 ++
/// @return 返回前进一步后的迭代器
self& operator++()
{
    _node = _node->_next;
    return *this;
}

/// @brief 后置 ++
/// @param  无作用，只是为了与前置 ++ 进行区分，形成重载
/// @return 返回当前的迭代器
self operator++(int)
{
    self tmp = *this;
    ++(*this);
    return tmp;
}

4.9.4元素访问

①front

front() 获取容器首元素的引用，调用 begin() 得到首元素的迭代器，再解引用即可。

因为 forward_list 的迭代器只能单向移动，故不能快速获得链表中最后一个节点。

/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front()
{
    return *begin();
}

// 与上面唯一不同就是用于 const 容器
const_reference front() const 
{
    return *begin();
}

②迭代器

③begin

begin() 获取的是首元素的迭代器，根据上图，直接返回头节点的下一位置即可。

/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() 
{
    // 根据节点指针构造迭代器
    return iterator(_node->_next);
}

// const 版本供 const 容器使用
const_iterator begin() const
{
    return const_iterator(_node->_next);
}

④end

end() 获取的是最后一个元素下一个位置的迭代器，根据上图就是 _node 所指向的节点。

/// @brief 返回指向 forward_list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() 
{
    // 调用 iterator 构造函数
    return iterator(_node);
}

const_iterator end() const 
{
    return const_iterator(_node);
}

4.9.5修改器

①insert_after

根据 STL 的习惯，插入操作会将新元素插入于指定位置之前，而非之后。然而 forward_list 是一个单向链表，它没有任何方便的方法可以定位出前一个位置，它必须从头找。因此，forward_list 中提供的插入操作，是插入在指定位置之后。

下图为：只有 0、1 两个元素的单链表，在 0 之后插入元素值为 2 的节点的示意图。

插入的过程非常简单：

1.创建一个要插入的节点

2.插入节点的 _next 指向 pos 后一位置的节点

3.pos 的 _next 指向要插入的节点

/// @brief 在容器中的指定位置后插入元素
/// @param pos 内容将插入到其后的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入元素的迭代器
iterator insert_after(iterator pos, const_reference val)
{
    forward_list_node* tmp = new forward_list_node(val);	// 创建要插入的节点
    tmp->_next = pos._node->_next;							// (1)
    pos._node->_next = tmp;									// (2)
    return tmp;
}

②push_front

push_front 的作用是在容器起始处插入元素。

直接调用 insert_after() 插入就行，需要注意的是，insert_after() 是在给定位置之后插入，所以应传入头节点对应的迭代器位置。

/// @brief 头插给定元素 val 到容器起始
/// @param val 要头插的元素值
void push_front(const_reference val)
{
	// end() 返回头节点位置的迭代器，在这之后插入是头插
	insert_after(end(), val);
}

③erase_after

下图为：有三个元素 0、1、2 的链表，删除 pos 指向节点之后节点（值为 1）的示意图。

删除的过程非常简单：

1.记录 pos 的下一节点 nextNode

2.将 pos 的 _next 指向 nextNode 的下一个节点

3.delete 释放掉 nextNode 所指向的节点

/// @brief 从容器移除 pos 后面一个元素
/// @param pos 指向要被移除元素前一个元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase_after(iterator pos) 
{
    forward_list_node* nextNode = pos._node->_next;		// 记录 pos 指向节点的下一节点
    pos._node->_next = nextNode->_next;					// (1)
    delete (nextNode);
    return (iterator)(pos._node->_next);
}

④pop_front

pop_front() 移除容器的首元素，也就是 end() 指向的下一节点。

/// @brief 移除容器首元素
void pop_front() 
{
    erase_after(end());
}

⑤clear

clear() 用于清空容器所有数据，不清理头节点。

要注意 erase_after() 删除给定位置下一个节点，end 的下一个是第一个元素，这样以次删除直到容器为空，即只剩一个头节点。

/// @brief 从容器擦除所有元素
void clear()
{
    while (!empty())
    {
        erase_after(end());
    }
}

⑥swap

swap() 用来交换两个 forward_list容器，不用交换 forward_list 中每个元素的值，直接交换 _node 指针即可。

/// @brief 将内容与 other 的交换
/// @param other 要与之交换内容的容器
void swap(forward_list& other)
{
    std::swap(_node, other._node);
}

参考：[STL forward_list 模拟实现](

标签：const,迭代,iterator,元素,list,vector,倒数
From： https://www.cnblogs.com/codemagiciant/p/17602007.html