c++编程14——STL（3）list

欢迎来到博主的专栏：c++编程
博主ID：代码小豪

文章目录

- list
- - 成员类型
  - 构造、析构、与赋值
  - iterator
  - 元素访问
  - 修改元素
  - list的操作

list

list的数据结构是一个链表，准确的说应该是一个双向链表。这是一个双向链表的节点结构：
在这里插入图片描述
list的使用方式和vector大差不差，区别主要还是体现在某些操作的效率方面，如下：

	list	vector
插入与删除	O(1)	O(N)
遍历	O(N)	O(N)
访问	O(N)	O(1)

总体而言，如果线性表需要大量的删除和插入，那么使用list会更加高效，如果只是单纯的存储数据，vector比list更好用，而且vector的空间还比list小。

OK，话不多说，开始看看list都有什么操作。

成员类型

由于STL中的容器都是模板类，因此数据的类型和常见的内置类型肯定不同，了解成员类型可以更好的读懂list的各个函数原型。

list的模板如下：

template < class T, class Alloc = allocator<T> > 
class list;

函数原型常见类型有：

类型	作用
value_type	模板当中的第一个类型，即T
reference	value_type类型的引用，即T&
pointer	value_type类型的指针，即T*
size_type	代表无符号整型
difference_type	代表有符号整型

希望大家能记住以上类型，因为接下来的list的函数原型经常会出现上述类型的参数。

构造、析构、与赋值

由于博主也不太会使allocator，因此介绍使用list的时候，参数一律使用alloc的缺省值。

default (1)	
explicit list (const allocator_type& alloc = allocator_type());
fill (2)	
explicit list (size_type n, const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type());
range (3)	
template <class InputIterator>
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());
copy (4)	
list (const list& x);

default构造：初始化时不传入任何参数，就能实例化出一个空链表。

	list<int> L1;//实例化一个容纳int变量的空链表
	list<float> L2;//实例化一个容纳int变量的空链表
	list<string>L3;//实例化一个容纳string对象的空链表

填充（fill）构造：构造一个n个值为val的对象的链表。

	list<int>L4(4, 2);//{2,2,2,2}
	list<float>L5(5, 3.14);//{ 3.14, 3.14, 3.14, 3.14, 3.14}
	list<string>L6(2, "hello world");
	//{"hello world","hello world"}

c++11标准还支持使用initializer_list初始化。

list (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());

这种初始化方式非常方便，非常好用。关于initializer_list的介绍可以去看看博主的c++杂谈系列。

使用方法大致如下：

	list<int>L7{ 1,2,3,4,5 };//{1,2,3,4,5}
	list<string>L8{ "haha","hehe","xixi"};//{"haha","hehe","xixi"}

是不是有点像给数组初始化时的用法，非常方便。

范围（range）构造

这种该构造是通过使用传入迭代器的方式，将迭代器内的元素传入list容器当中。

list<int>L7{ 1,2,3,4,5 };//{1,2,3,4,5}
list<string>L8{ "haha","hehe","xixi"};//{"haha","hehe","xixi"}
list<int>L9(L7.begin(), L7.end());//{1,2,3,4,5}
list<string>L9(L8.begin(), L8.end());//{"haha","hehe","xixi"}

当然了，这里的迭代器可以是与list<T>相同类型的迭代器。比如这种用法也是合理的。

	string str("hello world");
	list<char>L11(str.begin(), str.end());
	//{'h','e','l','l','o',' ','w','o','r','d'}

当然了，上面的说法是存在严重错误的，list<char>和string：：iterator的类型当然是不一样的，只是读起来顺口而已。实际上我想表达的是：list<char>容器的元素类型是char，而string::iterator指向的元素也是char类型。因此可以这样构造。

拷贝（copy）构造，构造一个与x一致的容器。

list<int>L12{ 1,2,3,4,5 };
list<int>L13(L12);//L13与L12一致

赋值运算符重载和拷贝构造的使用方法完全一致

 list& operator= (const list& x);

	list<int> list1{ 1,2,3,4 };
	list<int>list2;
	list2 = list1;//list2与list1一致

至于析构函数则没什么需要大家操作的地方了，当list超出作用域时，会自动调用list的析构函数。而且list析构函数还不需要传入参数

iterator

list的迭代器也是分为四种，分别是

（1）正向迭代器
（2）正向定值迭代器
（3）反向迭代器
（4）反向定值迭代器

STL的迭代器用法基本差不多，这里博主就不多演示怎么使用了，大家可以参考vector和string的迭代器用法。

list迭代器的不同之处在于，vector和string的迭代器都是随机迭代器（random access iterator），而list是双向迭代器（bidirectional iterator），随机迭代器可以支持++，–，以及加减算术的操作，而双向迭代器只能使用++或者–操作。

list<int>list1{ 1,2,3,4,5,6 };
list<int>::iterator it = list1.begin();
it + 1;//error，双向迭代器不支持算术加减
it++;//ok,双向迭代器支持自加自减

这意味着我们可以通过一下两种方式遍历list1.

list<int>list1{ 1,2,3,4,5,6 };
list<int>::iterator it = list1.begin();

while (it != list1.end())
{
	cout << *it;
	it++;
}

for (auto& e : list1)
{
	cout << e;
}

元素访问

list不支持使用下标访问符（[]）访问容器内的元素了。实际上，list一共就提供了两个函数，一个front，一个back。用来访问第一个或者最后一个元素。

reference front();
const_reference front() const;
reference back();
const_reference back() const;

list1.front() = 7;//第一个元素1修改成7
list1.back() = 1;//最后一个元素修改成1

修改元素

大家看看list关于修改元素的函数结口，是不是感觉很熟悉
在这里插入图片描述
可以发现list和vector关于修改元素的函数接口简直是如出一辙、

这是因为Victor，string，list都是线性表的结构，因此对元素的修改操作的效果都是一致的，区别只在于涉及的算法不同，这里我打算将算法放在list的模拟实现当中讲解，或者也可以去看博主的C语言数据结构关于双链表的博客。

list的操作

list和vector虽然在逻辑上是一致的，但是在内存结构上却完全不同了，因此list可执行的操作和vector是不同的。

在这里插入图片描述

remove——移除所有值为val的节点

void remove (const value_type& val);

unique——去掉链表中所有的重复元素。（链表需有序）

	list<int>list2{ 5,6,3,2,1,1,5 };
	list2.sort();//排序
	list2.unique();
	//list2={1,2，3,5，6}

sort——排序

(1)	
  void sort();
(2)	
template <class Compare>
  void sort (Compare comp);

默认情况下会将链表排成升序，如果想要将链表排成降序，就需要用到仿函数（像函数一样使用的类）。

	list<int>list2{ 5,6,3,2,1,1,5 };
	list2.sort();//升序
	for (auto& e : list2)
	{
		cout << e << ' ';
	}
	cout << endl;
	list2.sort(greater<int>());
	//降序，这个greater是一个仿函数模板，博主不做说明
	for (auto& e : list2)
	{
		cout << e << ' ';
	}

reverse——逆置链表

void reverse();

reverse可以让链表中的所有元素的顺序颠倒过来。

merge——合并链表

(1)	
  void merge (list& x);
(2)	
template <class Compare>
  void merge (list& x, Compare comp);

(1)
list容器将与x合并，merge会将x的所有成员都转移到list容器当中。（x会变成一个空链表，而list则会变大）。合并的两个链表必须拥有相同的顺序（升序，不能是逆序）。合并后的链表也会呈升序

list<int>list4{6,5,5,3,5};
	list<int>list5{ 7,9,3,4,2 };
	list4.sort();//list4排成升序
	list5.sort();//list5排成升序
	list4.merge(list5);//将list5和list4合并
	for (auto& e : list4)
	{
		cout << e << ' ';//{2，3,3，4,5，5，5，6,7，9}
	}

(2)
如果我们想要让合并后的链表是逆序的，那就将待合并的链表排成逆序，再传入仿函数comp，可以让合并后的链表呈逆序。

list<int>list4{6,5,5,3,5};
	list<int>list5{ 7,9,3,4,2 };
	list4.sort(greater<int>());//排成逆序
	list5.sort(greater<int>());//排成逆序
	list4.merge(list5,greater<int>());//合并成逆序
	for (auto& e : list4)
	{
		cout << e << ' ';//{9,7,6,5,5,5,4,3,3,2}
	}

splice——粘接（感觉像是剪切）

entire list (1)	
void splice (iterator position, list& x);
single element (2)	
void splice (iterator position, list& x, iterator i);
element range (3)	
void splice (iterator position, list& x, iterator first, iterator last);

splice重载了三个版本，每个版本都有不一样的效果

第一版：全部粘接，将x的全部元素粘接到list容器的迭代器指向的位置。x会变成一个空链表。

	list<int>list1{ 1,2,3,4 };
	list<int>list2{ 10,20,30,40 };
	list1.splice(list1.begin(), list2);
	for (auto& e : list1)
	{
		cout << e << ' '; //{10, 20, 30, 40, 1, 2, 3, 4};
	}

第二版，单元素粘接，将x中的迭代器i指向的元素粘接到容器position指向的位置。

	list<int>list1{ 1,2,3,4 };
	list<int>list2{ 10,20,30,40 };
	list1.splice(list1.begin(), list2,list2.begin());
	for (auto& e : list1)
	{
		cout << e << ' '; //{10,1, 2, 3, 4};
	}

第三版，迭代区间粘接。将x中[first，last）区间内的所有元素都粘接到list容器的position位置上。

	list<int>list1{ 1,2,3,4 };
	list<int>list2{ 10,20,30,40 };
	list1.splice(++list1.begin(), list2,++list2.begin(),--list2.end());
	for (auto& e : list1)
	{
		cout << e << ' '; //{1,20,30 2, 3, 4};
	}