目录
1.学习list iterator之前我们要知道iterator的区分
一.核心特性
1.双向循环链表结构
每个节点包含前驱和后继指针
2.头文件：#include <list>
3.时间复杂度
任意位置插入/删除：O(1)
随机访问：O(n)
排序：O(n log n)
4.内存特性
非连续内存存储
每个元素需要额外存储两个指针（前驱+后继）
内存占用 ≈ sizeof(T)2 + 2指针大小
二.构造函数
int main() { list<T> lst1; // 空链表 list<T> lst2(n); // n个默认初始化元素 list<T> lst3(n, value); // n个value副本 list<T> lst4(begin, end);// 迭代器范围构造 list<T> lst5(init_list); // 初始化列表 C++11 list<T> lst6(lst4); // 拷贝构造 }
三.list iterator的使用
1.学习list iterator之前我们要知道iterator的区分
功能上区分：
iterator 普通迭代器 reverse_iterator 反向迭代器 const_iterator 只读迭代器 const_reverse_iterator 只读反向迭代器 性质上区分：
名称 代表容器 支持操作 单向迭代器（ForwardIterator） Forward_list(单链表)，unordered_map ++ 双向迭代器（BidirectionalIterator） list(链表)，map，set ++/-- 随机迭代器（RandomAccessIterator） vector，string，deque ++/--/+/- 通过底层结构决定可以实现哪些算法
比如算法库里的sort要求使用随机迭代器，list就无法使用这个算法
对于算法库里的reverse和find可以正常使用
可以得知，功能是向上兼容得
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点
2.begin()+end()
返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
3. rbegin()+rend()
返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); auto it = lt.rbegin(); while (it != lt.rend()) { cout << *it << " "; //4 3 2 1 ++it; } cout << endl;
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
四.list关键接口
1.empty()
检测list是否为空，是返回true，否则返回false
list<int> lt; cout<<lt.empty()<<endl; //1 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); cout << lt.empty(); //0
2. size()
返回list中有效节点的个数
list<int> lt; cout<<lt.size()<<endl; //0 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); cout << lt.size(); //4
3.front()
返回list的第一个节点中值的引用
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); cout << lt.front(); //1
4. back()
返回list的最后一个节点中值的引用
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); cout << lt.back(); //4
5.push_front()
在list首元素前插入值为val的元素
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_front(5); //5 1 2 3 4
6. pop_front()
删除list中第一个元素
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.pop_front(); //2 3 4
7.push_back()
在list尾部插入值为val的元素
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); //1 2 3 4 5
8. pop_back()
删除list中最后一个元素
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.pop_back(); //1 2 3
9.insert ()
在list position 位置中插入值为val的元素
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); std::list<int>::iterator it; it=lt.begin(); int k = 3; while (k--) { ++it; } lt.insert(it, 30); 1 2 3 30 4
10.erase()
删除list position位置的元素
list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); std::list<int>::iterator it; it=lt.begin(); int k = 2; while (k--) { ++it; } lt.erase(it); //1 2 4
11.swap()
交换两个list中的元素
std::list<int> first(3, 100); // 100 100 100 std::list<int> second(5, 200); // 200 200 200 200 200 first.swap(second); // 200 200 200 200 200
12.clear()
清空list中的有效元素
std::list<int> mylist; mylist.push_back(1101); //1101 mylist.clear(); mylist.push_back(2202); //2202 return 0;
五.list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为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);
}
}六.模拟实现list
1.List.h
#pragma once // 防止头文件重复包含
#include<assert.h> // 断言检查
// 实现双向链表及相关迭代器
class bit
{
// 链表节点结构体模板
template<class T>
struct list_node
{
T _data; // 节点存储的数据
list_node<T>* _next; // 后继指针
list_node<T>* _prev; // 前驱指针
// 节点构造函数（默认构造空对象）
list_node(const T& data = T())
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{
}
};
// 链表迭代器结构体模板（支持普通/const迭代器）
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node; // 节点类型重命名
typedef list_iterator<T, Ref, Ptr> self; // 迭代器自身类型
Node* _node; // 迭代器当前指向的节点
list_iterator(Node* node) :_node(node)
{}
// 解引用操作符（返回数据引用）
Ref operator*()
{
return _node->_data;
}
// 成员访问操作符（返回数据指针）
// 使得 it->member 等价于 (&it->)_data->member
Ptr operator->()
{
return &_node->_data;
}
// 前置++（移动到下一节点）
self& operator++() {
_node = _node->_next;
return *this;
}
// 前置--（移动到前一节点）
self& operator--() {
_node = _node->_prev;
return *this;
}
// 后置++（需要返回临时对象）
self operator++(int) {
self tmp(*this);
_node = _node->_next;
return tmp;
}
// 后置--（同上）
self operator--(int) {
self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 比较操作符重载
bool operator!=(const self& s) const
{
return _node != s._node;
}
bool operator==(const self& s) const
{
return _node == s._node;
}
};
// 链表类模板
template <class T>
class list
{
typedef list_node<T> Node; // 节点类型简写
public:
/*typedef list_iterator<T> iterator;
typedef list_const_iterator<T> const_iterator;*/ //两个代码相似度太高，所以通过增加模板参数实现
// 迭代器类型定义（通过模板参数实现const重载）
typedef list_iterator<T, T&, T*> iterator; // 普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator; // const迭代器
// 获取起始迭代器（指向第一个有效节点）
iterator begin()
{
return _head->_next;
}
// 获取结束迭代器（哨兵节点）
iterator end()
{
return _head;
}
// const版本迭代器
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
// 初始化哨兵节点（构建空链表）
void empty_init() {
_head = new Node; // 申请头节点
_head->_next = _head; // 初始状态自环
_head->_prev = _head;
_size = 0; // 大小置零
}
// 默认构造函数
list()
{
empty_init();
}
// 初始化列表构造（支持花括号初始化）
list(std::initializer_list<T> il) {
empty_init();
for (auto& e : il) { // 遍历列表插入元素
push_back(e);
}
}
// 拷贝构造函数（深拷贝）
list(const list<T>& lt) {
empty_init();
for (auto& e : lt) { // 遍历插入每个元素
push_back(e);
}
}
// 赋值运算符（拷贝交换惯用法）
list<T>& operator=(list<T> lt) {
swap(lt); // 交换资源
return *this;
}
// 析构函数（清理节点）
~list() {
clear(); // 删除所有数据节点
delete _head; // 释放哨兵节点
_head = nullptr;
}
// 清空链表（保留哨兵节点）
void clear() {
auto it = begin();
while (it != end()) { // 逐个删除节点
it = erase(it);
}
}
// 交换两个链表内容
void swap(list<T>& lt) {
std::swap(_head, lt._head); // 交换头指针
std::swap(_size, lt._size); // 交换大小
}
// 尾插（复用insert实现）
void push_back(const T& x)
{
//Node* newnode = new Node(x);
//Node* tail = _head->_prev;
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->prev = newnode;
insert(end(), x); //直接调用insert
}
// 头插
void push_front(const T& x)
{
insert(begin(), x);
}
// 在pos位置前插入新节点
iterator insert(iterator pos, const T& x) {
Node* cur = pos._node; // 当前节点
Node* prev = cur->_prev; // 前驱节点
Node* newnode = new Node(x); // 创建新节点
// 调整指针链接
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size; // 更新大小
return newnode; // 返回新节点位置
}
// 尾删
void pop_back()
{
erase(--end());
}
// 头删
void pop_front()
{
erase(begin());
}
// 删除pos位置节点（注意：原代码此处返回类型应为iterator）
iterator erase(iterator pos) {
assert(pos != end()); // 不能删除哨兵节点
Node* prev = pos._node->_prev; // 前驱节点
Node* next = pos._node->_next; // 后继节点
// 调整链接关系
prev->_next = next;
next->_prev = prev;
delete pos._node; // 释放节点
--_size; // 更新大小
return next; // 返回下一位置的迭代器
}
// 获取元素数量
size_t size() const
{
return _size;
}
// 判断是否为空
bool empty() const
{
return _size == 0;
}
private:
Node* _head; // 哨兵头节点
size_t _size; // 元素个数
};
};
// 打印容器内容（泛型模板）
template<class Container>
void print_container(const Container& con) {
// 使用const迭代器遍历（保证内容不被修改）
// const iterator -> 迭代器本身不能修改
// const_iterator -> 指向内容不能修改
typename Container::const_iterator it = con.begin(); // typename指明依赖类型
//auto it = con.begin();或者使用auto
while (it != con.end()) {
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
// 范围for遍历（C++11特性）
for (auto e : con) {
std::cout << e << " ";
}
std::cout << std::endl;
}2.test.cpp
#include <iostream>
#include <list>
#include<algorithm>
using namespace std;
#include"list.h"
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
/*it = lt.begin();
lt.erase(it + 3);*/
// 不支持，要求随机迭代器
//sort(lt.begin(), lt.end());
string s("dadawdfadsa");
cout << s << endl;
sort(s.begin(), s.end());
cout << s << endl;
}
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);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
auto it = lt.begin();
int k = 3;
while (k--)
{
++it;
}
lt.insert(it, 30);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
int x = 0;
cin >> x;
it = find(lt.begin(), lt.end(), x);
if (it != lt.end())
{
lt.erase(it);
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list4()
{
// 直接构造
list<int> lt0({ 1,2,3,4,5,6 });
// 隐式类型转换
list<int> lt1 = { 1,2,3,4,5,6,7,8 };
const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };
print_container(lt1);
}
int main()
{
//test_list3();
//test_list4();
test_list1();
}
七.list与vector的对比
| vector | list | |
| 底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更 低 |
任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
学到C++11时需要补充一些新的接口。