C++学习笔记_16_list简单用法
文章目录
list介绍
- 列表是序列容器,允许在序列中的任何位置进行恒定时间的插入和擦除操作,以及双向迭代。
- 列表容器被实现为双向链表;双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置。排序在内部是通过与每个元素的关联来保持的,每个元素都链接到它前面的元素和它后面的元素。
- 它们与forward_list非常相似:主要区别在于forward_list对象是单链表,因此它们只能向前迭代,以换取更小和更高效。
- 与其他基本标准序列容器(数组、向量和deque)相比,列表通常在容器中已经获得迭代器的任何位置插入、提取和移动元素方面表现更好,因此在密集使用这些元素的算法(如排序算法)方面也是如此。
- 与其他序列容器相比,list和forward _ lists的主要缺点是它们无法通过位置直接访问元素;例如,要访问列表中的第六个元素,必须从一个已知的位置(如开始或结束)迭代到该位置,这需要线性时间。它们还会消耗一些额外的内存来保存与每个元素相关联的链接信息(这对于小型元素的大型列表来说可能是一个重要因素)
一、list使用
1.list构造函数
- list()
- list(size_type n, const value_type& val = value_type())
- list (const list& x)
- list (InputIterator first, InputIterator last)
代码示例:
所需头文件:
#include <iostream>
#include <list>
using namespace std;//这里用了命名空间
void test_list0()
{
list<int> lt1();
list<int> lt2(2, 3);
list<int> lt3(lt2);
list<int> lt4(lt3.begin(), lt3.end());
}
可以通过遍历检验:
迭代器:
list<int>::iterator it = lt4.begin();
while (it != lt4.end())
{
cout << *it << " ";
++it;
}
cout << endl;
范围for:
for (auto s : lt)
{
cout << s << " ";
}
cout << endl;
2.iterator的使用
将迭代器理解成一个指针,该指针指向list中的某个节点
函数声明:
begin,end:返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin,rend:返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin位置
用法如下:
//遍历方式1
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
3.capacity
empty:检测list是否为空,是返回true,否则返回false
size:返回list中有效节点的个数
4.element access
front:返回list的第一个节点中值的引用
back:返回list的最后一个节点中值的引用
5.modifiers
先将输出封装:
void printlist(list<int>& lt)
{
for (auto& s : lt)
{
cout << s << " ";
}
cout << endl;
}
push_back 在list尾部插入值为val的元素:
void test_list3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
printlist(lt);
}
push_front 在list首元素前插入值为val的元素
lt.push_front(5);
printlist(lt);
pop_front 删除list中第一个元素
lt.pop_front();
printlist(lt);
pop_back 删除list中最后一个元素
lt.pop_back();
printlist(lt);
insert 在list position 位置中插入值为val的元素
auto pos = ++lt.begin();//第二个节点
lt.insert(pos, 9);
printlist(lt);
erase 删除list position位置的元素
lt.erase(pos);
printlist(lt);
swap 交换两个list中的元素
int array[] = { 1,2,3 };
list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));
printlist(lt);
printlist(lt1);
lt1.swap(lt);
printlist(lt);
printlist(lt1);
clear 清空list中的有效元素
lt1.clear();
printlist(lt1);
测试结果如下:
二、迭代器失效
因为可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}