list 就是
链表，它是序列容器，允许在序列中的任何位置以
O
(
1
)
O(1)
O(1)的时间复杂度进行插入和删除操作，并能够双向迭代。
list 简单使用
list 和 vector 的使用很相似，共同之处这里不多演示，我们主要介绍 list 的独特之处。
使用前要包含头文件 <list>
遍历
list 不同于 vector 和 string，它不支持下标遍历。
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for (list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
{
cout << *it << ' ';
}
cout << endl;
for (auto e : lt)
{
cout << e << ' ';
}
cout << endl;
for (list<int>::reverse_iterator rit = lt.rbegin(); rit != lt.rend(); ++rit)
{
cout << *rit << ' ';
}
cout << endl;
}
头插头删
void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_front(10);
lt.push_front(20);
lt.push_front(30);
for (list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
{
cout << *it << ' ';
}
cout << endl;
}
排序
list 有 sort 成员函数
void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_front(10);
lt.push_front(20);
lt.push_front(30);
lt.sort();
for (list<int>::iterator it = lt.begin(); it != lt.end(); ++it)
{
cout << *it << ' ';
}
cout << endl;
}
因为 <algorithm> 库里的 sort 只支持传入随机访问迭代器，但是 list 只有双向访问迭代器，库里的 sort 不支持。
我们知道库里的 sort 原理是快速排序，需要支持随机访问，而链表不支持随机访问，所以只能用自己的排序方式，速度也比较慢。
关于 vector 使用库里的 sort 和 list 使用自己的成员函数 sort 排序的对比(一千万个数据，Release版本)：
void testOP()
{
srand(time(0));
const int N = 10000000;
vector<int> v;
list<int> lt;
for (int i = 0; i < N; ++i)
{
v.push_back(rand());
lt.push_back(v[i]);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt.sort();
int end2 = clock();
cout << "vector sort: " << end1 - begin1 << endl;
cout << "list sort: " << end2 - begin2 << endl;
}
所以对于数据量较大的情况，不建议使用链表排序。
把 list 的数据拷贝到 vector ，然后使用 vector 排序，排完再拷贝回 list 反倒更快些：
void testOP2()
{
srand(time(0));
const int N = 10000000;
list<int> lt1;
list<int> lt2;
vector<int> v;
v.reserve(N);
for (int i = 0; i < N; ++i)
{
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
for (auto e : lt1)
{
v.push_back(e);
}
sort(v.begin(), v.end());
int i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
lt2.sort();
int end2 = clock();
cout << "list+vector sort: " << end1 - begin1 << endl;
cout << "list sort: " << end2 - begin2 << endl;
}
去重
list 提供了成员函数 unique 去重，
注意，它只能对连续的重复数据进行去重，所以使用前要先排序。
void test3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(1);
lt.push_back(4);
lt.push_back(5);
lt.push_back(1);
lt.push_back(4);
lt.push_back(8);
lt.sort();
lt.unique();
for (auto e : lt)
{
cout << e << ' ';
}
}
模拟实现
框架
template<class T>
struct List_node
{
List_node<T>* _next;
List_node<T>* _prev;
T _data;
};
template<class T>
class List
{
typedef List_node<T> Node;
public:
private:
Node* _head;
};
默认构造
list 是双向带头循环链表，构造时就得有个虚拟头结点。
List()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
List_node 构造函数：
List_node(const T& val = T())
: _next(nullptr)
, _prev(nullptr)
, _data(val)
{}
迭代器(重点)
为了方便迭代器的介绍，我们先把 push_back 实现出来：
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
list 迭代器不是原生指针，它的许多操作都需要我们自己重载。
所以需要我们额外写一个迭代器类模板。
-
迭代器类的成员变量是一个指向结点的指针。 -
迭代器会在 begin 和 end 函数用指针创建，所以需要有参的构造函数。 -
拷贝构造、赋值重载、析构函数都不需要我们自己实现，因为迭代器只负责访问容器，它本身只要浅拷贝足矣。 -
因为迭代器的使用类似指针，所以我们先实现解引用*，前置++，!= 三个运算符的重载。
- 解引用就是返回指针指向的结点的数据，注意传引用返回，以便修改数据。
- 前置
++即将指针指向下一个结点，然后返回迭代器本身。 != 就是比较两个迭代器对象里的 _node 指向的结点是否不同。
template<class T>
struct __List_iterator
{
typedef List_node<T> Node;
typedef __List_iterator<T> self;
Node* _node;
__List_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
};
接下来我们就可以实现 List 里的 begin 和 end 了：
typedef 要放在 public: 下，以便类外使用。begin 返回指向第一个结点的迭代器 ，用 _head->_next 指针构造一个即可。end 返回指向最后一个结点的迭代器，其实就是虚拟头结点 _head
typedef __List_iterator<T> iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
👆：直接 return 指针也可以，因为单参数的构造函数支持隐式类型转换。
如此我们就完成了一个简易的迭代器类，可以支持迭代器遍历：
void test1()
{
List<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
for (List<int>::iterator it = lt.begin(); it != lt.end(); ++it)
{
cout << *it << ' ';
}
cout << endl;
}
接下来完善迭代器类：
后置++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
前置-- 后置–
因为咱们list 迭代器是支持双向迭代，所以也要实现 --
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
==
bool operator==(const self& it)
{
return _node == it._node;
}
->
-> 的重载很怪异，它其实是一个单操作数的运算符。
它的实现如下：
T* operator->()
{
return &_node->_data;
}
List 内存储一个自定义类型 AA 的对象，然后打印其内部成员变量 a 的值：
struct AA
{
AA(int x = 0)
:a(x)
{}
int a;
};
void test2()
{
List<AA> lt;
AA a(3);
lt.push_back(a);
List<AA>::iterator it = lt.begin();
cout << it->a << endl;
}
it-> 返回了一个 AA* 类型的指针，它需要再 -> 才能取出 a。这个过程其实是编译器替我们做了，相当于it->->a
const 迭代器
常规思路是，复制刚写好的这个迭代器类模板，改模板名，并把 * 和 -> 重载的返回类型前加上 const。但是这样写重复代码过多，不合适。
最好的方式就是直接加两个模板参数，Ref 表示引用，Ptr表示指针，具体是什么引用，什么指针，在 List 类中 typedef 时传入：
template<class T, class Ref, class Ptr>
struct __List_iterator
{
typedef List_node<T> Node;
typedef __List_iterator<T, Ref, Ptr> self;
Node* _node;
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
};
template<class T>
class List
{
typedef List_node<T> Node;
public:
typedef __List_iterator<T, T&, T*> iterator;
typedef __List_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
};
修改
insert：
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
👆：和 vector 不同，list 迭代器使用 insert 并不会出现失效的问题，因为 list 不用挪动数据，不用异地扩容，也就不会出现野指针。
erase：
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
👆：erase 明显会发生迭代器失效，pos 指向的结点被删除后 pos 变成了野指针迭代器。解决方法很简单，使用时注意接收 erase 的返回值。
push_back 和 push_front 复用 insert，pop_back 和 pop_front 复用 erase：
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
clear 复用 erase：
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
析构
~List()
{
clear();
delete _head;
_head = nullptr;
}
拷贝构造、赋值重载
传统写法
老老实实地创建虚拟头结点，然后一个一个插入：
List(const List<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
for (auto e : lt)
{
push_back(e);
}
}
现代写法(迭代器构造、swap)
思路和以前一样，先写个有参构造和 swap：
为了提高复用性，创建虚拟头结点的代码封装成一个函数 empty_init：
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
template <class InputIterator>
List(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(List<T>& lt)
{
std::swap(_head, lt._head);
}
List(const List<T>& lt)
{
empty_init();
List<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
赋值重载：
List<T>& operator=(List<T> lt)
{
swap(lt);
return *this;
}
完整代码
#pragma once
#include <iostream>
#include <cassert>
using namespace std;
template<class T>
struct List_node
{
List_node<T>* _next;
List_node<T>* _prev;
T _data;
List_node(const T& val = T())
: _next(nullptr)
, _prev(nullptr)
, _data(val)
{}
};
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;
}
Ptr operator->()
{
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
template<class T>
class List
{
typedef List_node<T> Node;
public:
typedef __List_iterator<T, T&, T*> iterator;
typedef __List_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
List()
{
empty_init();
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
template <class InputIterator>
List(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(List<T>& lt)
{
std::swap(_head, lt._head);
}
List(const List<T>& lt)
{
empty_init();
List<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
List<T>& operator=(List<T> lt)
{
swap(lt);
return *this;
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
Node* _head;
};
|