本节我们将介绍 STL 中的 list 容器使用。

list<T> 是定义在 list 头文件中容器模板，是 T 类型对象的双向链表。
在数据结构中我们知道，
链表插入和删除元素的时间复杂度是 级别的，数组中是
链表访问的时间复杂度是 ，数组能随机访问，时间复杂度为 。

这也就意味着，list 容器具有 vector 和 deque 容器所不具备的优势，它可以在常规时间内，在序列已知的任何位置插入或删除元素。
list 的缺点是无法使用位置来直接访问序列中的元素，即不能索引元素。为了访问 list 内部的一个元素，必须一个一个地遍历元素，通常从第一个元素或最后一个元素开始遍历。

双向链表的示意图如下：

image.png

list<T> 容器的每个 T 类型对象通常都被封装在一个内部节点中，该节点对象维护了两个指针，一个指向前一个节点，另一个指向下一个节点。这些指针将节点连接成一个链表。通过指针可以从任何位置的任一方向来遍历链表。第一个元素的前向指针总是为 null,因为它前面没有元素，尾部元素的后向指针也总为 null。这使我们可以检测到链表的尾部。list<T> 实例保存了头部和尾部的指针。这允许我们从两端访问链表，也允许从任一端开始按顺序检索列表中的元素。

同时我们可以使用和其他序列容器相同的方式，来获取 list 容器的迭代器。鉴于不能随机访问 list 中的元素，因此获取到的迭代器都是双向迭代器。以 list 为参数，调用 begin() 可以得到指向 list 中第一个元素的迭代器。通过调用 end()，可以得到一个指向最后一个元素下一个位置的迭代器，从而可以像其他序列容器一样，用它们来指定整个范围的元素。

也可以像其他容器一样，使用 rbegin()、rend()、crbegin()、crend()、cbegin()、cend() 来获取反向迭代器和 const 迭代器。

list 容器的初始化

list 容器初始化的用法类似于 vector 或 deque 容器。
1.使用默认的构造函数生成 list 容器，容器中没有任何元素，大小为0。

list<string> data;

2.可以生成给定元素个数的 list 容器，每一个元素都由构造函数生成。
容器内所有元素为空

list<string> data{7};

或者，容器内所有元素为 "null" 。

list<string> data{7,"null"};

3.可以用初始化列表来生成 list 容器。

list<string> data{"one","null","three","four","null","six","seven"};

4.也可以用由两个迭代器标识的一段元素来初始化它。

list<string> data {"one","null","three","four","null","six","seven"};
list<string> data_ {data};

或者

list<string> data {"one","null","three","four","null","six","seven"};
auto begin_iter = begin(data);
auto end_iter = end(data);
// 只能使用自增或自减运算符
begin_iter++;
end_iter--;
list<string> data_ {begin_iter,end_iter};

注意，list 容器的 begin() 和 end() 函数返回的都是双向迭代器，所以不能用它们加减整数。修改双向迭代器的唯一方式是使用自增或自减运算符。
当然，在上面的语句中，初始化列表中的迭代器可以代表任意容器的一段元素，而不仅仅只是 list 容器。
接下来，我们汇总下 list 容器的初始化。

#include <bits/stdc++.h>
using namespace std;

int main(){
    list<string> data_1;
    list<string> data_2(7);
    list<string> data_3(7,"null");
    list<string> data_4 {"one","null","three","four","null","six","seven"};
    //全部复制
    list<string> data_5{data_4};
    auto begin_iter = begin(data_4);
    list<string>::iterator end_iter = end(data_4);
    //注意迭代器只能自增或自减运算
    begin_iter++;
    begin_iter++;
    end_iter--;
    end_iter--;
    //部分复制
    list<string> data_6{begin_iter,end_iter};
    cout<<"data_1: "<<data_1.size()<<endl;
    for(auto d : data_1){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_2: "<<data_2.size()<<endl;
    for(auto d : data_2){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_3: "<<data_3.size()<<endl;
    for(auto d : data_3){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_4: "<<data_4.size()<<endl;
    for(auto d : data_4){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_5: "<<data_5.size()<<endl;
    for(auto d : data_5){
        cout<<d<<" ";
    }
    cout<<endl;
    cout<<"data_6: "<<data_6.size()<<endl;
    for(auto d : data_6){
        cout<<d<<" ";
    }
    cout<<endl;
    return 0;
}

结果如下：

image.png

list 容器添加元素

和 deque 容器类似，list 容器不仅能在容器尾部增加和删除元素，在头部也可以增加和删除元素。
示例如下：

list<string> data {"one","two","three","four"};
//在头部增加一个元素
data.push_front("zeros");
//删除头部的元素
data.pop_front();
//在尾部增加一个元素
data.push_back("five");
//删除尾部的元素
data.pop_back();

成员函数 emplace() ，emplace_front() 和 emplace_back() 也可以实现相同功能，而且其效率更高效。
1). emplace() 在迭代器指定的位置构造一个元素；
2). emplace_front() 在 list 的第一个元素之前构造元素；
3). emplace_back() 在 list 的尾部元素之后构造元素。
示例如下：
使用 emplace() 插入元素:

list<string> data {"one","two","three","four"};
auto iter = end(data);
//使用 emplace() 容器尾部添加一个 "AAA"
data.emplace(iter,3,'A');
iter = end(data);
//注意迭代器只能自增或自减运算
iter--;
//在 data 的倒数第一个元素前加上一个 "AAAA"
data.emplace(iter,4,'A');

使用 emplace_front() 和 emplace_back() 插入元素:

list<string> data{"one","two","three"};
//在头部插入元素 "zeros"
data.emplace_front("zeros");
//在尾部插入元素 "four"
data.emplace_back("four");

或者

list<string> data{"one","two","three"};
string word = "zeros four";
//从word中截取,从6开始的4个字符,在尾部加入
data.emplace_back(word,6,4);
//从word中截取,从0开始的5个字符,在头部加入
data.emplace_front(word,0,5);

同样地，注意迭代器只能自增或自减运算。

可以使用成员函数 insert() 在 list 容器内部添加元素。像其他序列容器一样，它有三种使用方法。

在迭代器指定的位置插入一个新的元素

list<string> data {"one","two","three","four"};
auto iter = begin(data);
iter++;
data.insert(iter,"one_two");

data 的内容为：

{"one","one_two","two","three","four"}

begin() 返回的双向迭代器自增后，指向下个元素。
list 容器插入元素不必移动现有的元素。生成新元素后，这个过程需要将 4 个指针重新设为适当的值，回忆数据结构中双向链表的插入和删除过程。
第一个元素的 next 指针指向新的元素，原来的第二个元素的 pre 指针也指向新的元素。新元素的 pre 指针指向第一个元素，next 指针指向序列之前的第二个元素。
和 vector、deque 容器的插入过程相比，这个要快很多，并且无论在哪里插入元素，花费的时间都相同。

可以在给定位置插入多个元素

list<string> data {"one","two","three","four"};
auto iter = begin(data);
//移动 iter,相对于 iter 自增三次
advance(iter,3);
//在 iter 处增加两个 "null"
data.insert(iter,2,"null");

data 的内容为：

{"one","two","three","null","null","four"}

iter 是 list<int>::iterator 类型。insert() 函数的第一个参数是用来指定插入位置的迭代器，第二个参数是被插入元素的个数，第三个参数是被重复插入的元素。
为了得到第 3 个元素，可以使用定义在 iterator 头文件中的全局函数 advance()，将迭代器增加 3。
因为 list 容器的迭代器只能自增和自减，所以迭代器不能直接加 3，advance() 函数会在循环中自增迭代器。

如果想减小迭代器的话，可以这样操作：

list<string> data {"one","two","three","four"};
auto iter = end(data);
//移动 iter,相对于 iter 自减三次
advance(iter,-3);
//在 iter 处增加两个 "null"
data.insert(iter,2,"null");

data 的内容为：

{"one","null","null","two","three","four"}

插入一段由迭代器指定的元素。

list<string> data {"one","two","three","seven"};
list<string> data_ {"null","null","four","five","six","null"};
auto begin_iter = begin(data_);
auto end_iter = end(data_);
auto iter = end(data);
//移动 iter,相当于 iter 自减 1 次
advance(iter,-1);
// 移动 begin_iter,相当于 iter 自增 2 次
advance(begin_iter,2);
// end_iter 自减 1 次
end_iter--;
data.insert(iter,begin_iter,end_iter);

insert() 的第一个参数是一个迭代器，它指向 data 的倒数第一个元素。第二和第三个参数指定了 data_ 中被插入元素的范围，因此从 data 中倒数第二个元素开始，依次插入 begin_iter 和 end_iter 两个迭代器指定范围的元素。
代码执行后，data 中的内容如下：

{"one","two","three","four","five","six","seven"}

在 insert() 中，第二和第三个参数两个迭代器若指定元素类型与 data 相同，也是可以插入的。

list<string> data {"one","two","three","seven"};
vector<string> data_ {"null","null","four","five","six","null"};
auto begin_iter = begin(data_);
auto end_iter = end(data_);
auto iter = end(data);
//移动 iter,相当于 iter 自减 1 次
advance(iter,-1);
//vector 的迭代器可以进行加减运算
begin_iter += 2;
end_iter--;
data.insert(iter,begin_iter,end_iter);

第二和第三个参数指定了 data_ 中被插入元素的范围，同时元素类似和 data 相同，因此从 data 中倒数第二个元素开始，依次插入 begin_iter 和 end_iter 两个迭代器指定范围的元素。
代码执行后，data 中的内容如下：

{"one","two","three","four","five","six","seven"}

注意，list 元素的迭代器只会在它所指向的元素被删除时才会失效。

list 容器删除元素

list 的成员函数有 clear() 和 erase()，它们的使用方式和效果和之前的序列容器相同。
使用 clear():

list<string> data {"one","two","three","seven"};
data.clear();

clear() 清除了容器内的所有元素。
使用 erase():

list<string> data {"one","two","three","four","five","null","seven"};
//移除一个元素
auto iter = end(data);
advance(iter,-2);
data.erase(iter);
//data = {"one","two","three","four","five","seven"}
//移除一段元素
list<string>::iterator begin_iter = begin(data);
auto end_iter = end(data);
advance(begin_iter,2);
advance(end_iter,-2);
data.erase(begin_iter,end_iter);

最后，data 的内容为：

{"one","two","five","seven"}

list 容器的成员函数 remove() 则移除和参数匹配的元素。例如：

list<string> data {"one","two","null","four","five","null","seven"};
// 移除所有为 "null" 的元素
data.remove("null");

data 的内容为：

{"one","two","four","five","seven"}

成员函数 remove_if() 传入一个一元断言作为参数。一元断言接受一个和元素同类型的参数或引用，返回一个布尔值。断言返回 true 的所有元素都会被移除。

list<string> data {"one","two","null","four","five","null","seven"};
// 移除所有为 "null" 的元素
data.remove_if([](string str){
    return str == "null";
});

这里的参数是一个 lambda 表达式，但也可以是一个函数对象。

成员函数 unique() 可以移除连续的重复元素，只留下其中的第一个。

list<string> data {"one","null","null","four","four","four","seven"};
data.unique();

data 的内容为：

{"one","null","four","seven"}

注意是连续的重复元素，如果是这样的

list<string> data {"one","null","null","four","null","four","four","seven"};
data.unique();

data 的内容为：

{"one","null","four", "null", "four","seven"}

因为它并不是去重，而是去重连续的重复元素，保留第一个。
如果想去重也是可以的，一种方法是先排序，后使用 unique()。

list<string> data {"one","null","null","four","null","four","four","seven"};
data.sort();
data.unique();

data 的内容为：

{"four","null","one","seven"}

unique() 的功能是很强大的，重载的 unique() 函数接受一个二元断言作为参数，有着更灵活的功能，有兴趣的可以查阅其他资料，这里就不展开了。