list的特性及使用

1、list的介绍

1.list是序列容器，允许在序列的任何位置进行时间复杂度为o(1)的插入和删除操作，并且由双向迭代器。

2.list的底层是双链表，双链表不是物理上连续的储存空间，而是不同的地址空间通过next和prev指针连接成顺序表。

3.list相较于其他的顺序序列容器（deque，vector），主要缺点是不能通过下标进行访问元素，要访问元素只能通过迭代器的方式顺序访问。

如下草图所示

2、list成员说明

3、list对象的构造

list对象的构造可以通过花括号，初始化列表，圆括号，以及复制拷贝其他list对象的方式。

default (1)	explicit list (const allocator_type& alloc = allocator_type());
fill (2)	explicit list (size_type n); list (size_type n, const value_type& val, 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); list (const list& x, const allocator_type& alloc);
move (5)	list (list&& x); list (list&& x, const allocator_type& alloc);
initializer list (6)	list (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

4、list元素访问

1、front()返回list容器的首元素的引用

2、back()返回list容器的尾元素的引用

int main()
{
	list <int> l1{ 1,2,3,4,5,6,7,8 };

	cout << l1.front() << endl;
	cout << l1.back() << endl;

	return 0;
}

5、迭代器

参见cplusplus官网的迭代器声明

begin()为正向迭代器的头，end为正向迭代器的尾，方向由list容器的第一个元素到最后一个元素移动，rbegin()为反向迭代器的头，rend为反向迭代器的尾，方向由list容器的最后一个元素到第一个元素。

#include<iostream>
#include<list>
using namespace std;
int main()
{
	list <int> l1{ 1,2,3,4,5,6,7,8 };
	list<int>::iterator it1 = l1.begin();
	list<int>::reverse_iterator it3 = l1.rbegin();
	list<int>::iterator it2 = l1.end();
	list<int>::reverse_iterator it4 = l1.rend();
	for (; it1 != it2; it1++)
	{
		cout << *it1 << " ";
	}
	cout << endl;
	for (; it3 != it4; it3++)
	{
		cout << *it3 << " ";
	}
	cout << endl;
	return 0;
}

6、容器

1、empty()

判断容器是否为空，即检查迭代器begin()和end()是否相等，相等则为空，返回真，不想等则不为空，返回假；

int main()
{
   list<int> l1 = { 1,2,3,4,5,6,7 };
   bool flag = l1.empty();
   if (!flag)
   {
       cout << "不为空" << endl;
   }

else{

cout<<"为空"<<endl;}
return 0;
}

2、size()

返回容器的元素个数

3、max_size()

返回根据系统或者库实现限制的容器可保有的元素最大数量，即对于最大容器的容量

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

int main()
{
	list<int> l1 = { 1,2,3,4,5,6,7 };
	cout << l1.empty() << endl;
	cout << l1.size() << endl;
	cout << l1.max_size()<< endl;
	return 0;
}

7、修改器增删查改等功能

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 的交换

8、vector与list对比，优缺点比较

区别	vector	list
底层实现	连续储存空间容器，内存动态开辟，在堆上分配空间	动态双向链表，在堆上
空间利用率	不造成内存碎片，空间利用率高	节点不连续，存储空间在物理上不连续，密度小，空间利用率低
访问元素方式	迭代器，下标，随机访问	只能迭代器
插入和删除	插入元素push_back() ,时间复杂度为o(1), 删除元素pop_back(),时间复杂度为o(1); 在非尾部插入元素“insert(iterator pos,value_type val);时间复杂度o(n); erase(iterator pos):时间复杂度为o(n); resize();开辟空间，储存数据； reverse():开辟空间，不储存数据	插入：o(1).需要开辟空间； push_back (x), erase(),时间复杂度：o(n）
迭代器	连续的储存空间，支持随即迭代器，迭代器越界会发生检查	内存空间不连续，不支持随机访问，只能顺序访问，双向迭代器越界检查，