C++STL——list

C++教学总目次

  
1、list简介

list是带头双向循环链表，也是模板类，使用时要指明类型，包含于头文件<list>
由于list是双向循环链表，在任意位置的插入删除的效率非常高，都是O(1)，以是list提供了头插头删和尾插尾删的接口。
2、构造函数

第一个就是默认构造函数，第二个支持用n个val来初始化链表，第三个支持迭代器区间初始化，最后一个就是拷贝构造函数了。使用如下：

1. string s = "hello world";
2. list<int> lt1;                        // 默认构造函数
3. list<int> lt2(10, 1);        // 创建10个结点赋值为1
4. list<int> lt3(lt2.begin(), lt2.end()); // 同类型迭代器区间初始化
5. list<char> lt4(s.begin(), s.end());    // 使用string的迭代器区间初始化
6. list<int> lt5(lt2);     // 拷贝构造

复制代码

3、迭代器

list的迭代器使用方法同vector和string。以是只要学会一种类型的迭代器使用，其他类型迭代器都会使用了。
但是list的迭代器和vector、string的迭代器有所差别。
algorithm库中有三个常用的函数：reverse、sort、find。先来看看这三个函数：

观察这三个函数，你会发现他们的模板参数取名是差别的。
实际上这三个函数并不是任何容器的迭代器都可以使用的，他们是有区别的。
迭代器有三种类型：单向迭代器、双向迭代器、随机迭代器。

从这三个函数的模板参数命名也可以看出来，find传单向迭代器就可以使用，sort必要传随机迭代器，reverse必要传双向迭代器。
基于list底层的性质，list只能是双向迭代器，以是不能使用sort对list进行排序，由于sort必要随机迭代器。
而像vertor和string底层都是指针，可以对指针++/–/+/-,以是它们的迭代器都是随机迭代器，上面三个函数都可以使用。
下面遍历list：

1. list<int> lt;
2. lt.push_back(1);
3. lt.push_back(2);
4. lt.push_back(3);
5. lt.push_back(4);
6. lt.push_back(5);
7. // 使用迭代器遍历list
8. list<int>::iterator it = lt.begin();
9. while (it != lt.end())
10. {
11.         cout << *it << " ";
12.         ++it;
13. }
14. cout << endl;
16. // 使用范围for遍历list——底层还是迭代器
17. for (auto e : lt)
18. {
19.         cout << e << " ";
20. }
21. cout << endl;

复制代码

---

4、访问和容量函数

empty判断链表是否为空。
size返回链表中结点个数。
max_size表示链表可以存储的最多结点——差别平台下差别，没什么意义
front返回链表头结点元素
back返回链表尾结点元素
5、修改类函数

1、assign函数就是把链表中全部结点清空，然后重新初始化。

1. list<int> lt;
2. lt.push_back(1);
3. lt.push_back(2);
4. lt.push_back(3);
5. lt.push_back(4);
6. lt.push_back(5);
7. list<int> lt2(10, 1);
8. lt2.assign(lt.begin(), lt.end());
9. lt2.assign(10, 2);

复制代码

2、push_front是头插，pop_front是头删，push_back是尾插，pop_back是尾删。
3、insert函数：支持在某个位置插入一个数据、支持在某个位置插入n个数据、支持在某个位置插入一段迭代器区间。

insert的使用这里就不先容了，详情可以看之前的string和vector，string和vector会用这里肯定也会用。现在来思索一下list的迭代器insert之后会失效吗？

观察这段代码，it指向3，当调用insert之后，在3的前面插入了10，然后再对it所指向的元素做修改，之后打印输出我们发现3确实被改成100了。以是list这里insert之后迭代器并不会失效，由于这里插入是new一个结点然后进行前后毗连。而之前vector那边可能会发生扩容，扩容后迭代器就失效了。
insert的返回值是插入新元素的迭代器。
4、erase函数：支持删除某个位置的元素、支持删除一段迭代器区间

erase之后迭代器会失效吗？答案肯定是会失效，由于指向的那个结点空间被开释了，以是迭代器失效。以是erase返回值是删除元素的下个位置。
5、swap函数就是互换两个list的值，雷同前面vector和string。clear就是清除全部数据。resize也是类型vector的，开空间+初始化。

---

6、操纵类函数

1、reverse函数就是逆置，这里其实可以直接使用算法库的reverse函数逆置，没必要在list中再实现reverse函数。
2、sort函数是用来给list中数据排序的，由于算法库中的sort函数得是随机迭代器才气使用，而list是双向迭代器，以是不能使用算法库中的sort函数，因此在list类实现了sort函数，这个函数使用的是归并排序。但是这个函数的效率非常低，如果在数据量比力大的情况下，我们可以把数据拷贝到vector中存储，然后使用算法库中的sort快排，再把数据拷回list中，如许的效率更高。

3、merge函数用来合并两个链表：

使用如下：

1. std::list<double> first, second;
3. first.push_back(3.1);
4. first.push_back(2.2);
5. first.push_back(2.9);
7. second.push_back(3.7);
8. second.push_back(7.1);
9. second.push_back(1.4);
10. first.sort();
11. second.sort();
12. first.merge(second);
13. cout << "first:";
14. for (const auto& e : first)
15. {
16.         cout << e << " ";
17. }
18. cout << endl;
19. cout << "second:";
20. for (const auto& e : second)
21. {
22.         cout << e << " ";
23. }
24. cout << endl;

复制代码

调用了merge之后，将second中的全部结点合并到first链表中，second中就没有结点了。固然merge函数的使用前提是两个链表都有序。
4、unique函数用来去重：如果链表中有多个雷同的数据，可以使用unique来去重

使用unique的前提也是链表必须有序。
5、remove_if是给一个函数，然后把满足条件的值全部去掉。

使用如下：

这里我们实现了一个test函数，当x<10时返回true。我们在调用remove_if时将函数地点传过去，当满足条件时——返回true时就将元素删掉。以是小于10的元素全部被去除了。
6、remove函数很简单，就是把你所给的值的元素删掉。

7、splice函数是拼接（更形象来说时转移）：支持在某个位置拼接list、支持在某个位置拼接list对象的某个结点、支持在某个位置拼接list的一段迭代器区间

使用如下：

1. #include <iostream>
2. #include <vector>
3. #include <string>
4. #include <list>
6. using namespace std;
9. int main()
10. {
11.         list<int> mylist1, mylist2;
12.         list<int>::iterator it;
13.         for (int i = 1; i <= 4; ++i)
14.                 mylist1.push_back(i);      // mylist1: 1 2 3 4
16.         for (int i = 1; i <= 3; ++i)
17.                 mylist2.push_back(i * 10);   // mylist2: 10 20 30
19.         for (auto e : mylist1)
20.         {
21.                 cout << e << " ";
22.         }
23.         cout << endl;
25.         for (auto e : mylist2)
26.         {
27.                 cout << e << " ";
28.         }
29.         cout << endl << endl;
30.         it = mylist1.begin();
31.         it++;
33.         // 全部转移到mylist1
34.         mylist1.splice(it, mylist2);
35.        
36.         for (auto e : mylist1)
37.         {
38.                 cout << e << " ";
39.         }
40.         cout << endl;
42.         for (auto e : mylist2)
43.         {
44.                 cout << e << " ";
45.         }
46.         cout << endl;
48.         return 0;
49. }

复制代码

上面的代码将mylist2中的全部结点转移到了mylist1中第一个结点的后面。
把上面调用splice的语句换成：

1. // 部分转移
2. mylist1.splice(it, mylist2, ++mylist2.begin());

复制代码

现在就变成了将mylist2中第二个结点转移到mylist1的第一个结点后面。
我们再把代码换成：

1. mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());

复制代码

现在是把mylist1中第一个结点后面的全部结点转移到mylist1的第一个结点前面。
必要注意的是：使用splice进行转移时，可以对同一个list进行转移，但是要保证区间不能重叠，如果区间重叠就会出问题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。