C++第二十三弹---深入理解STL中list的使用

✨个人主页：熬夜学编程的小林

💗系列专栏：【C语言详解】【数据结构详解】【C++详解】

1、list的介绍

2、list的使用

2.1、构造函数

2.2、赋值操作符重载

2.3、迭代器使用

2.4、容量操作

2.5、元素访问

2.6、修改操作

2.7、其他操作

总结

1、list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_lis非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list 通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

因此list的本质就是双向循环链表。

2、list的使用

2.1、构造函数

1. Default constructor (构造一个没有元素的空容器。)

explicit list (const allocator_type& alloc = allocator_type());

2. Fill constructor (构造了一个含有 n 个元素的容器，每个元素都是 val 的副本。 )

explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());

3. Range constructor (使用两个迭代器 first 和 last，这两个迭代器指定了一个序列的范围，来构造一个容器。这个范围包括从 first 到 last 之间的所有元素，但不包括 last 指向的元素。)

template <class InputIterator>  
list (InputIterator first, InputIterator last,const allocator_type& alloc =allocator_type());

4. Copy constructor (构造一个容器，其中包含 x 中每个元素的副本，顺序相同。)

list (const list& x);

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

代码演示：

//构造函数
void test_list1()
{//1.默认构造list<int> lt1;//2.填充构造list<int> lt2(10, 1);//3.范围构造(迭代器区间构造)vector<int> v = { 1,3,5,6,7,8,9 };list<int> lt3(v.begin(), v.end());//4.拷贝构造list<int> lt4(lt3);}

我们可以通过打断点的方式查看 list 中元素。
测试结果：

2.2、赋值操作符重载

1. copy (将新内容分配给容器，替换其当前内容，并相应地修改其大小。 )

list& operator= (const list& x);

代码演示：

void test_list2()
{list<int> lt1(10, 1);list<int> lt2 = lt1;
}

测试结果：

2.3、迭代器使用

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

此处迭代器指向的位置与vector容器一样，直接演示代码！！！

代码演示：

void test_list3()
{vector<int> v = { 1,2,3,4,5,6,7,8,9 };list<int> lt(v.begin(), v.end());//迭代器区间构造list<int>::iterator it = lt.begin();//获取指向第一个元素迭代器while (it != lt.end())//正向打印链表{cout << *it << " ";//解引用当前位置的值，类似指针解引用it++;//it向后走}cout << endl;auto rit = lt.rbegin();//类型可以直接还用autowhile (rit != lt.rend())//反向打印链表{cout << *rit << " ";rit++;}cout << endl;
}

测试结果：

2.4、容量操作

empty (判断容器是否为空。)
size (获取容器元素个数。)

代码演示：

void test_list4()
{vector<int> v{ 1,3,5,7,9 };list<int> lt(v.begin(), v.end());cout << "size() = " << lt.size() << endl;cout << "empty() = " << lt.empty() << endl;
}

测试结果：

【注意】
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

2.5、元素访问

front (获取第一个元素。 )
back (获取最后一个元素。)

代码演示：

void test_list5()
{vector<int> v{ 2,4,6,8,10 };list<int> lt(v.begin(), v.end());cout << "front() = " << lt.front() << endl;cout << "back() = " << lt.back() << endl;
}

测试结果：

2.6、修改操作

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素

push_back (在末尾添加元素。) :
pop_back (删除最后一个元素。) :

代码演示：

void test_list6()
{list<int> lt;lt.push_back(1);//尾插lt.push_back(2);lt.push_back(3);lt.push_front(10);//头插lt.push_front(20);lt.push_front(30);
}

测试结果：

push_front (在开头添加元素。)
pop_front (删除第一个元素。)

代码演示：

void test_list7()
{list<int> lt = { 1,2,3,4,5,6,7 };for (auto x : lt){cout << x << " ";}cout << endl;lt.pop_back();//尾删lt.pop_front();//头删for (auto x : lt){cout << x << " ";}
}

测试结果：

insert (在pos位置前插入元素。)
erase (删除pos位置元素。)

代码演示：

void test_list8()
{list<int> lt = { 1,2,3,4,5 };//iterator insert(iterator pos, const T& val);//在pos位置前插入vallt.insert(lt.begin(), 100);//在第一个位置前插入100for (auto x : lt){cout << x << " ";}cout << endl;//iterator erase (iterator pos);//删除pos位置的值lt.erase(lt.begin());//删除第一个位置的值for (auto x : lt){cout << x << " ";}cout << endl;
}

测试结果：

2.7、其他操作

splice

转移链表元素到另一个链表。

代码演示：

void test_list9()
{list<int> lt;list<int> lt1(1,10);lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto x : lt1){cout << x << " ";}cout << endl;//将lt链表的元素转移到lt1的第一个位置，转移的是结点lt1.splice(lt1.begin(), lt);for (auto x : lt1){cout << x << " ";}cout << endl;//lt链表的元素全部转移到lt1中，因此打印为空for (auto x : lt){cout << x << " ";}cout << endl;
}

测试结果：

remove()

删除等于val值的元素。

unique()

从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素。

代码演示：

void test_list10()
{list<int> lt = { 1,2,3,4,5 };for (auto x : lt){cout << x << " ";}cout << endl;lt.remove(1);//删除等于1的所有元素for (auto x : lt){cout << x << " ";}cout << endl;//从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素。lt.unique();for (auto x : lt){cout << x << " ";}cout << endl;
}

测试结果：

sort()

对列表的元素进行排序，可以接受一个比较函数。

代码演示：

bool Com(int x, int y)
{return x > y;//降序
}void test_list11()
{list<int> lt = { 1,2,3,3,8,9 };for (auto x : lt){cout << x << " ";}cout << endl;lt.sort(Com);//使用Com排序方法排序，降序for (auto x : lt){cout << x << " ";}cout << endl;
}

测试结果：

reverse()

将链表元素进行逆序。

代码演示：

void test_list12()
{list<int> lt = { 1,2,3,3,8,9 };for (auto x : lt){cout << x << " ";}cout << endl;lt.reverse();//将链表逆序for (auto x : lt){cout << x << " ";}cout << endl;
}

测试结果：