C++ List 容器详解：结构与常用操作

2.2 构造并初始化 n 个 value

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> l2(10, 1);
    for (auto& ele : l2) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

2.3 使用迭代器区间构造初始化

这个构造函数会将一个迭代器区间的值用来初始化我们的 list，这个迭代器不要求和 list 迭代器一样，也可以使用其他类型的迭代器，只要求里面数据的类型一样就可以了。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> l2(10, 7);
    list<int> l3(l2.begin(),l2.end());
    for (auto& ele : l3) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

使用 string 类型的迭代器来初始化一个 list 容器，如下所示：

#include<iostream>
using namespace std;
#include<list>
#include<string>
int main() {
    string s1("abcdefg");
    list<char> l3(s1.begin(), s1.end());
    for (auto& ele : l3) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

我们这里虽然是 list 容器，但是使用的是 string 类型的迭代器进行初始化的。

2.4 拷贝构造

拷贝构造是使用一个已经初始化好的 list 来创建另外一个 list。如下所示：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<double> ld(5, 1.5);
    list<double> ld2(ld);
    for (auto& ele : ld2) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

2.5 使用大括号构造初始化

这个构造函数是 C++11 后来新加的，使用大括号初始化，函数原型如下：

C++11 增加了一个类型，将花括号括起来的内容成为 initializer_list，如下所示：

底层逻辑是在栈区开一个数组，这个 il 对象里面有两个指针，一个指针指向数组的开始位置，一个指针指向数组的结束位置，所以这个对象的大小是 8 字节（32 位）。

使用大括号初始化代码如下：

int main() {
    list<int> mylist({ 1,2,3,4,5,6,7});
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

list mylist({ 1,2,3,4,5,6,7});也可以将这一行写出这样：

list mylist={ 1,2,3,4,5,6,7}; 这样写的话就是隐式类型转换。

三、List 的迭代器

迭代器属于其对应容器的类域，所以我们在声明 list 迭代器时，需要指定类域。

与 string 类似，vector 也有八种迭代器，如下所示：

最常用的就是前面两个:begin() 和 end()

begin() 返回的是第一个元素的迭代器；

end() 返回的是最后一个元素的下一个位置的迭代器；

注意： list 容器的迭代器不再是原生指针了，不能再支持 + 和 - 了。 迭代器从功能上划分，可以分为 iterator;reverse_iterator;const_iterator;const_reverse_iterator; 迭代器从性质上划分可以分为：单向迭代器:forward_list/unordered_map... 能够支持 ++ 双向迭代器:list/map/set... 能够支持 ++，-- 随机迭代器:vector/string/deque... 能够支持 ++，--，+，- 迭代器的性质是由底层的结构决定的。 像 vector、string 之类的，它们的底层是连续的物理空间，所以他们的迭代器就能够支持 + 和 -。 如何看一个容器的迭代器是具有什么性质的呢？ 可以在 list 文档 里面的 Member types 里面看到 list 迭代器的类型，如下所示： bidirectional iterator 表示的就是双向迭代器的意思。 同样的，我们也可以在 vector 文档 里面的 Member types 里面看到 vector 迭代器的类型，如下所示： random access iterator 表示的就是随机迭代器的意思。 我们也可以在 unordered_map 文档 里面查看 unordered_map 迭代器的类型，如下所示： forward iterator 表示的就是单向迭代器的意思。 这个迭代器性质可以决定可以使用哪些算法。 我们可以查看 algorithm 里面的 sort 函数，函数原型如下所示： 虽然算法库里面的 sort 是一个模板，传任意类型迭代器都可以，可以根据模板来推导类型，但是真的能传任意类型的迭代器嘛？sort函数原型的参数给了暗示，要想去使用算法库里面的 sort 排序，这个迭代器类型必须是 RandomAccessIterator，也就是随机迭代器。如果传过来的参数不是随机迭代器，就会报错，这是因为 sort 算法使用的排序是快排，快排里面需要三数取中等，它需要支持 +，-，[] 等随机访问的。所以 list 容器里面自己支持了一个 sort 算法。 我们再查看 algorithm 里面的 reverse 函数，函数原型如下所示： reverse 函数需要传入双向迭代器，所以 list 和 vector 等都可以使用这个函数来进行翻转。但是 forward_list 就不能使用这个函数来进行翻转，因为 reverse 函数内部需要用到 --。 我们可以理解为随机迭代器和双向迭代器都是一种特殊的单项迭代器，随机迭代器是一种特殊的双向迭代器。它们之间有一种特殊的继承关系，如下所示： 我们在上面没有讲过 input 类型的迭代器，我们可以查看 algorithm 里面的 find 函数，函数原型如下： 这个函数要求参数是 InputIterator 类型的迭代器， InputIterator 类型的迭代器是个什么迭代器？ C++ 里面引出了两个不存在的迭代器，没有实体对应的迭代器，input 和 output 迭代器。有些算法里面的参数迭代器类型是 InputIterator，InputIterator 指的是可以传入任意类型的迭代器。 为什么 find 里面需要传入 InputIterator 类型的迭代器呢？ 因为 find 函数里面之后对迭代器进行 ++ 操作，所以什么类型的迭代器都可以传。

所以我们想要使用一些算法的时候，需要查看这个容器的迭代器到底支不支持这种算法。如果某种算法不支持这种迭代器，就会报错。

四、List 容器的遍历

因为 List 容器不支持 [] 来访问元素，所以 list 容器的遍历方式就只有迭代器和范围 for 了

4.1 迭代器方式遍历

代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    mylist1.push_back(10);
    mylist1.push_back(20);
    mylist1.push_back(30);
    mylist1.push_back(50);
    mylist1.push_back(60);
    mylist1.push_back(70);
    list<int>::iterator it = mylist1.begin();
    while (it != mylist1.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    return 0;
}

运行如下所示：

4.2 范围 for 遍历

代码如下所示：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    mylist1.push_back(1);
    mylist1.push_back(2);
    mylist1.push_back(3);
    mylist1.push_back(5);
    mylist1.push_back(6);
    mylist1.push_back(7);
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行如下所示：

五、List 容量的函数

list 中的节点在内存中是离散存放的，没有像 vector 和 string 这么多的容量函数。插入数据也不需要扩容，只需要 new 一个节点来存放数据和前后节点的指针就可以了，list 有以下三个容量函数

5.1 size() 函数

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls(10, 1);
    cout << ls.size() << endl;
    return 0;
}

5.2 empty() 函数

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls1(10, 1);
    list<int> ls2;
    cout << ls1.empty() << endl;
    cout << ls2.empty() << endl;
    return 0;
}

5.3 resize() 函数

resize 的函数原型如下：

1、当 n 大于 list 的 size 时，会在尾部插入 val，如果我们传入了 val，就插入我们传入的 val，如果没有传入，就调用 val 类型的默认构造函数。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls(10, 1);
    cout << "当前 list 的 size 是:" << ls.size() << endl;
    ls.resize(15, 4);
    cout << "现在 list 的 size 是:" << ls.size() << endl;
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

2、当 n 小于 list 的 size 时，会删除 list 中的元素。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls(10, 1);
    cout << "当前 list 的 size 是:" << ls.size() << endl;
    ls.resize(5);
    cout << "现在 list 的 size 是:" << ls.size() << endl;
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

六、List 的元素获取

因为 list 在内存中不是连续存放的，所以就不能通过方括号和 at 来进行访问，list 提供了 front 和 back 函数来访问 list 第一个元素和最后一个元素。

6.1 front() 函数

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);
    cout << ls.front() << endl;
    return 0;
}

6.2 back() 函数

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);
    cout << ls.back() << endl;
    return 0;
}

七、List 的增删查改

7.1 push_back() 函数

这个函数的作用是在 list 尾部插入一个元素，代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(10);
    ls.push_back(20);
    ls.push_back(30);
    ls.push_back(40);
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

7.2 pop_back() 函数

这个函数的作用是在 list 尾部删除一个元素，代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(10);
    ls.push_back(20);
    ls.push_back(30);
    ls.push_back(40);
    ls.pop_back();
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

7.3 push_front() 函数

这个函数的作用是在 list 头部插入一个元素，代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_front(10);
    ls.push_front(20);
    ls.push_front(30);
    ls.push_front(40);
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

7.4 pop_front() 函数

这个函数的作用是在 list 头部删除一个元素，代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);
    ls.pop_front();
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

7.5 insert() 函数

insert() 函数原型如下：

insert 重载了三个版本：

• insert(iterator, value);
• insert(iterator, num, value);
• insert(iterator, iterator1, iterator2);

7.5.1 insert(iterator, value)

这个函数是往迭代器位置之前插入一个 value 元素。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    list<int>::iterator it = ls.begin();
    it++;
    ls.insert(it, 100); //在第二个位置之前插入 100
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    return 0;
}

7.5.2 insert(iterator, num, value)

这个函数是往迭代器位置之前插入 num 个 value 元素。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    list<int>::iterator it = ls.begin();
    it++;
    ls.insert(it, 5,100);//在第二个位置之前插入 5 个 100
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    return 0;
}

7.5.3 insert(iterator, iterator1, iterator2)

这个函数是往迭代器位置之前插入另外迭代器区间的元素。这个迭代器区间可以是其他类型的迭代器区间。

#include<iostream>
using namespace std;
#include<list>
#include<vector>
int main() {
    list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    list<int>::iterator it = ls.begin();
    it++;
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    //在第二个位置之前插入 vector 容器的数据
    ls.insert(it, v.begin(),v.end());
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    return 0;
}

因为 list 里面的元素在内存里面是离散存放的，所以我们插入数据不会导致迭代器失效。

7.6 erase() 函数

erase() 函数原型如下：

erase 重载了两个版本

• erase(iterator)
• erase(iterator1,iterator2)

返回值是删除元素的下一个迭代器。

7.6.1 erase(iterator)

这个函数是删除迭代器指向的元素

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(10);
    ls.push_back(20);
    ls.push_back(30);
    ls.push_back(40);
    list<int>::iterator it = ls.begin();
    it++; //删除第二个元素
    ls.erase(it);
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

7.6.2 erase(iterator1,iterator2)

这个函数是删除迭代器区间的元素。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls;
    ls.push_back(10);
    ls.push_back(20);
    ls.push_back(30);
    ls.push_back(40);
    ls.push_back(50);
    ls.push_back(60);
    list<int>::iterator it = ls.begin();
    it++;
    list<int>::iterator ite = ls.end();
    ite--; //删除 [it,ite) 之间的元素
    ls.erase(it,ite);
    for (auto& ele : ls) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

erase 会导致删除元素的迭代器失效，因为这个元素被删除了，但是不会影响其他的迭代器

7.7 swap() 函数

用来交换连个 list 容器。实际上是交换 list 的头节点的指针。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> ls1;
    ls1.push_back(1);
    ls1.push_back(2);
    ls1.push_back(3);
    ls1.push_back(4);
    list<int> ls2;
    ls2.push_back(10);
    ls2.push_back(20);
    ls2.push_back(30);
    ls2.push_back(40);
    cout << "交换前：" << endl;
    cout << "ls1:" << endl;
    for (auto& ele : ls1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "ls2:" << endl;
    for (auto& ele : ls2) {
        cout << ele << " ";
    }
    cout << endl;
    ls1.swap(ls2);
    cout << "交换后：" << endl;
    cout << "ls1:" << endl;
    for (auto& ele : ls1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "ls2:" << endl;
    for (auto& ele : ls2) {
        cout << ele << " ";
    }
    cout << endl;
}

7.8 clear() 函数

这个函数是清空 list 容器，但是头节点不会被删除。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> lt(5, 1);
    for (auto e : lt) {
        cout << e << " ";
    }
    cout << endl;
    lt.clear(); //清空容器
    for (auto e : lt) {
        cout << e << " ";
    }
    cout << endl; //(无数据)
    return 0;
}

7.9 assign() 函数

函数原型如下：

这个函数的作用是给 list 容器新的元素，将原来的元素给替换掉。它有两个重载版本

7.9.1 void assign(InputIterator first,InputIterator last)

这个重载版本是将 list 中的元素替换为这两个迭代器区间的元素，代码如下：

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
    vector<int> v;
    for (int i = 1; i < 10; i++) {
        v.push_back(i);
    }
    list<int> mylist1;
    mylist1.push_back(10);
    mylist1.push_back(20);
    mylist1.push_back(30);
    cout << "assign 之前："<<endl;
    cout << "mylist：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    mylist1.assign(v.begin(), v.end());
    cout << "assign 之后：" << endl;
    cout << "mylist：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下：会将 [v.begin() v.end()) 之间的元素拷贝到 list 容器

7.9.2 void assign(size_type n,const value_type& val)

这个重载版本是将 list 中的元素替换为 n 个 val，代码如下：

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
    list<int> mylist1;
    mylist1.push_back(10);
    mylist1.push_back(20);
    mylist1.push_back(30);
    cout << "assign 之前：" << endl;
    cout << "mylist：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    mylist1.assign(10,33);
    cout << "assign 之后：" << endl;
    cout << "mylist：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下：会将 list 中的元素替换为 10 个 33

7.10 emplace_back() 函数

这个函数和 push_back() 函数具有一样的功能，只不过这个函数的功能更加强大。从日常的角度，使用 emplace_back() 函数或者使用 push_back() 函数是一样的。emplace_back() 函数在部分的场景会更加高效一点。所以后续的一些标准都推荐使用 emplace 系列。

日常使用如下所示：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> lt;
    lt.push_back(21);
    lt.emplace_back(22);
    lt.emplace_back(23);
    lt.emplace_back(24);
    for (auto& ele : lt) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

高效的场景如下所示：现在我们理解这么用就可以，emplace_back() 函数涉及到很多没有学过的知识。只了解用法，不关心底层细节。

#include<iostream>
using namespace std;
#include<list>
struct A {
public:
    A(int a1 = 1,int a2=1) :_a1(a1), _a2(a2) {}
    int _a1;
    int _a2;
};
int main() {
    list<A> lta;
    A aa1(1, 1);
    lta.push_back(aa1);
    lta.push_back(A(2,2)); //lta.push_back(2, 2);//不支持这样写
    lta.emplace_back(aa1);
    lta.emplace_back(A(2, 2)); //emplace_back() 支持直接传入构造 A 对象的参数
    lta.emplace_back(3,3);//支持这样写
    for (auto& ele : lta) {
        cout << ele._a1 <<":"<< ele._a2<<endl;
    }
    cout << endl;
    return 0;
}

八、List 常见的操作函数

8.1 remove() 函数

函数原型如下：

这个函数的作用是删除 list 中节点值等于 val 的节点。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist;
    mylist.push_back(10);
    mylist.push_back(20);
    mylist.push_back(30);
    mylist.push_back(40);
    mylist.push_back(10);
    mylist.push_back(10);
    cout << "删除前：" << endl;
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    cout << endl;
    mylist.remove(10); //删除节点中值为 10 的节点
    cout << "删除后：" << endl;
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

8.2 remove_if() 函数

函数原型如下：

这个函数的作用是删除 list 中满足这个条件的节点，这个函数的参数是一个仿函数，学到后面就理解了。

#include<iostream>
using namespace std;
#include<list>
bool single_digit(const int value) {
    return value<10;
}
int main() {
    list<int> mylist;
    mylist.push_back(11);
    mylist.push_back(2);
    mylist.push_back(32);
    mylist.push_back(4);
    mylist.push_back(14);
    mylist.push_back(1);
    mylist.push_back(8);
    cout << "删除前：" << endl;
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    cout << endl;
    mylist.remove_if(single_digit);//删除小于 10 的数
    cout << "删除后：" << endl;
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

8.3 unique() 函数

这个函数的作用是删除 list 中连续的重复值，使用这个函数删除重复值需要 list 是有序的，如果不是有序的，就只能删除相邻的重复值，后面不相邻的重复值就不会删除。

以下是无序的例子：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist;
    mylist.push_back(1);
    mylist.push_back(1);
    mylist.push_back(2);
    mylist.push_back(2);
    mylist.push_back(1);
    mylist.push_back(1);
    mylist.push_back(2);
    mylist.push_back(1);
    mylist.unique();
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    return 0;
}

以下是有序的例子：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist;
    mylist.push_back(1);
    mylist.push_back(1);
    mylist.push_back(2);
    mylist.push_back(2);
    mylist.push_back(1);
    mylist.push_back(1);
    mylist.push_back(2);
    mylist.push_back(1);
    mylist.sort();
    mylist.unique();
    for (auto& ele : mylist) {
        cout << ele << " ";
    }
    return 0;
}

8.4 merge() 函数

这个函数的作用是合并两个有序列表，形成一个大的有序 list。这个函数会将参数的那个 list 的元素给移动到调用这个函数的 list。所以会导致一个 list 元素清空。代码如下所示：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    mylist1.push_back(1);
    mylist1.push_back(3);
    mylist1.push_back(5);
    list<int> mylist2;
    mylist2.push_back(2);
    mylist2.push_back(4);
    mylist2.push_back(6);
    cout << "合并前" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    mylist1.merge(mylist2);
    cout << "合并后" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下：

会将 mylist 给移到 mylist1 里面，所以 mylist2 为空。

8.5 sort() 函数

这个函数的作用是将 list 排序，默认是从小到大排序，可以加上仿函数来从大到小来排序。

8.5.1 sort() 函数的使用

不使用仿函数代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    mylist1.push_back(11);
    mylist1.push_back(3);
    mylist1.push_back(52);
    mylist1.push_back(77);
    mylist1.push_back(45);
    mylist1.push_back(1);
    mylist1.push_back(45);
    cout << "排序前：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    mylist1.sort();
    cout << "排序后：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下所示：

使用仿函数代码如下：

仿函数是一个特殊的类，自带了 less 和 greater 的类。less ls;greater gt;

从小到大排序就用 ls，从大到小就用 gt；

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    mylist1.push_back(11);
    mylist1.push_back(3);
    mylist1.push_back(52);
    mylist1.push_back(77);
    mylist1.push_back(45);
    mylist1.push_back(1);
    mylist1.push_back(45);
    cout << "排序前：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    greater<int> gt;
    mylist1.sort(gt);
    cout << "排序后：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下：

但是我们使用 sort 之前还需要再实例化一个对象，是不是太复杂了呢？我们可以直接传入一个匿名对象，如下所示：

mylist1.sort(greater());

8.5.2 sort() 函数的效率问题

我们 list 容器里面自己实现了一个 sort 函数，为什么算法库里面有还需要自己来实现呢？上面迭代器部分讲过：算法库里面的 sort 函数需要传入随机迭代器，而 list 容器的迭代器是双向迭代器。

此外，list 容器中的 sort 函数效率非常低，数据量少可以用它排序，数据量多了尽量不要用它来排序。数据量多的时候，我们可以将 list 容器里面的数据拷贝一份给 vector，让 vector 来排序，排序完成之后再拷贝给 list，虽然上面需要三步，但是这三步花费的时间是要比直接给 list 排序花费的时间少的。我们写一段代码来测试一下：测试要使用 release 情况下测试，debug 没有参考价值（debug 会打很多调试信息，所以没有参考价值）。

代码 1：测试算法库中的 sort 和 list 容器自带的 sort 的性能：给一百万的数据

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
    srand(time(0));
    const int N = 1000000;
    list<int> lt1;
    vector<int> v;
    v.reserve(N);
    for (int i = 0; i < N; i++) {
        auto e = rand() + i;
        lt1.push_back(e);
        v.push_back(e);
    }
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();
    int begin2 = clock();
    lt1.sort();
    int end2 = clock();
    cout << "vector sort:" << end1 - begin1 << endl;
    cout << "list sort:" << end2 - begin2 << endl;
    return 0;
}

运行结果如下：

list 和 vector 在相同的数据情况下，vector 排序要比 list 排序快的多。

代码二：测试将 list 数据拷贝给 vector，排序然后再拷贝回来的时间与直接使用 list 排序的时间相比

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
    srand(time(0));
    const int N = 1000000;
    list<int> lt1;
    list<int> lt2;
    for (int i = 0; i < N; i++) {
        auto e = rand() + i;
        lt1.push_back(e);
        lt2.push_back(e);
    }
    int begin1 = clock(); //拷贝到 vector
    vector<int> v(lt1.begin(), lt1.end());
    //排序
    sort(v.begin(), v.end());
    //拷贝回 lt1
    lt1.assign(v.begin(), v.end());
    int end1 = clock();
    int begin2 = clock();
    lt2.sort();
    int end2 = clock();
    cout << "list->vector->list sort:" << end1 - begin1 << endl;
    cout << "list sort:" << end2 - begin2 << endl;
    return 0;
}

运行结果如下：

我们将 list 容器里面的数据拷贝一份给 vector，让 vector 来排序，排序完成之后再拷贝给 list 这个所花费的时间还没有直接给 list 排序花费的时间多。

8.6 reverse() 函数

这个函数的作用是翻转 list 里面中的元素。

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    mylist1.push_back(111);
    mylist1.push_back(222);
    mylist1.push_back(333);
    mylist1.push_back(444);
    mylist1.push_back(555);
    mylist1.push_back(666);
    mylist1.push_back(777);
    cout << "翻转前：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    mylist1.reverse();
    cout << "翻转后：" << endl;
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行如下所示：

8.7 splice() 函数

splice 函数原型如下：

8.7.1 void splice(iterator position,list& x)

将容器 x 中的所有元素转移到 position 这个位置之前。代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    list<int> mylist2;
    for (int i = 1; i <= 4; i++) {
        mylist1.push_back(i); //mylist1: 1 2 3 4
    }
    for (int i = 1; i <= 3; i++) {
        mylist2.push_back(i*10); //mylist2: 10 20 30
    }
    cout << "splice() 之前" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    list<int>::iterator it = mylist1.begin();
    it++; //it 指向 mylist1 容器的第二个元素
    mylist1.splice(it, mylist2); //转移容器 mylist2 中的元素到 it 位置之前
    cout << "splice() 之后" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下：

8.7.2 void splice(iterator position,list& x,iterator i)

将容器 x 中从迭代器 i 的元素转移到 position 这个位置之前。代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    list<int> mylist2;
    for (int i = 1; i <= 4; i++) {
        mylist1.push_back(i); //mylist1: 1 2 3 4
    }
    for (int i = 1; i <= 3; i++) {
        mylist2.push_back(i * 10); //mylist2: 10 20 30
    }
    cout << "splice() 之前" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    list<int>::iterator it = mylist1.begin();
    it++; //it 指向 2
    list<int>::iterator itbegin = mylist2.begin();
    itbegin++; //itbegin 指向 20
    mylist1.splice(it, mylist2,itbegin); //会将 mylist2 中的 20 元素转移到 2 这个元素之前
    cout << "splice() 之后" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下所示：

8.7.3 void splice(iterator position,list& x,iterator first,iterator last)

将容器 x 中从迭代器 first 开始到迭代器 last 之间的元素转移到 position 这个位置之前。代码如下：

#include<iostream>
using namespace std;
#include<list>
int main() {
    list<int> mylist1;
    list<int> mylist2;
    for (int i = 1; i <= 4; i++) {
        mylist1.push_back(i); //mylist1: 1 2 3 4
    }
    for (int i = 1; i <= 7; i++) {
        mylist2.push_back(i * 10); //mylist2: 10 20 30 40 50 60 70
    }
    cout << "splice() 之前" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    list<int>::iterator it = mylist1.begin();
    it++; //it 指向 2
    it++; //it 指向 3
    list<int>::iterator itbegin = mylist2.begin();
    itbegin++; //itbegin 指向 20
    list<int>::iterator itend = mylist2.end();
    itend--; //itend 指向 70
    mylist1.splice(it, mylist2, itbegin,itend); //会将 mylist2 迭代器 [itbegin,itend) 之间的元素转移到 3 这个元素之前
    cout << "splice() 之后" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    cout << "mylist2:";
    for (auto& ele : mylist2) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下所示：

有时我们会将 list 容器 [1,2,3,4,5,6,7,8,9] 中的 6 移到开始位置，我们就可以使用 splice，如果不使用 splice，我们就需要 delete6 这个节点，然后再 new 一个节点，效率低下，所以我们就可以使用 splice 函数。代码如下所示：我们输入哪一个数字，就会把哪一个元素放到第一个位置。

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
int main() {
    list<int> mylist1;
    for (int i = 1; i <= 9; i++) {
        mylist1.push_back(i);
    }
    int x;
    cin >> x;
    cout << "splice() 之前" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    auto posx = find(mylist1.begin(), mylist1.end(),x);
    if (posx != mylist1.end()) {
        mylist1.splice(mylist1.begin(), mylist1, posx);
    }
    cout << "splice() 之后" << endl;
    cout << "mylist1:";
    for (auto& ele : mylist1) {
        cout << ele << " ";
    }
    cout << endl;
    return 0;
}

运行结果如下所示：

九、list 和 vector 的比较