文章目录
- list的使用
- 几种构造函数
- list的实现
- 1.节点类的定义
- 1.1节点类的构造函数
- 2.正向迭代器实现
- 2.1operator*重载
- 2.2operator->重载
- 2.3operator++重载
- 2.4operator--
- 2.5operator==和operator！=
- 3.反向迭代器实现
- 3.1operator*重载
- 3.2operator->重载
- 3.3operator++重载
- 3.4operator--重载
- 3.5operator!=和operator==重载
- 3.6反向迭代器的全部代码
- 4.list的成员函数
- 4.1构造函数
- 4.2assign函数
- 4.3指定位置的插入
- 4.4指定位置的删除
- 4.5首插尾插和首删尾删
- 4.6交换函数
- 4.7resize函数
- 4.8clear函数
- 4.9迭代器的封装
- 全部代码
- 总结
list的使用
几种构造函数
无参默认构造函数
list<int> l1;
有参构造（使用val对list初始化n个对象）
list<int> l1(10, 1);
迭代器区间构造
list<int> l1(10, 1);
list<int> l2(l1.begin(), l1.end());
拷贝构造
list<int> l1(10, 1);
list<int> l2(l1);
还有一些老生常谈的迭代器和尾插，还有插入之类的使用我们就不用讲了，相信大家经过之前的vector和string的学习已经基本掌握使用了，但是在list中还多了一个接口，就是首插和首删，因为我们知道，在vector中我们要进行首插或者首删的代价是很大的，因为首插或者首删我们就要把整个数组移动，时间复杂度是线性的，但是对于list来说首插或者首删的代价是常数级的，因为我们库中的list使用的是带头的双向链表，所以我们可以以常数的时间复杂度进行任何位置的插入或者删除，虽然我说的list很好，但是list还有一个致命的缺陷，就是访问，对于list的访问来说，你要访问一个位置必须从头开始遍历，最大的时间复杂度是线性的，但是对于vector的访问来说，就是常数级的，所以list有好处也有不足的地方。
接下来我们来讲讲如何实现一个list
我们对链表肯定也是相当的熟悉，双向链表的结构就是两个指针，一个存放数据的成员，一个指针指向的是前一个节点，另一个指针指向的是下一个节点，我们来看看底层：
很显然底层是封装了的，底层的实现也是通过两个指针进行实现的，所以我们接下来实现也通过指针进行实现，并且先定义一个专门存放节点的结构体。
list的实现
1.节点类的定义
根据我们上面说的，我们先创建一个类来存放节点，由于我们要访问这个类的成员，所以干脆我们直接把这个类写成结构体，因为在C++中结构体默认是public。
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
};
上面就是我们定义的一个结构体，忘了说了，在这之前别忘了用一个命名空间将其隔离开，避免和库里的冲突了。
1.1节点类的构造函数
list_node(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _data(val)
{
}
参数部分就不需要解释了，用一个值来构造一个节点，后面的T()是临时对象，前面的const&延长了它的生命周期。
2.正向迭代器实现
对于迭代器的实现可和vector的实现不一样了，对于vector来说，有vector的空间是连续的，所以迭代器可以直接用指针书写，但是对于list来说空间根本不是连续的，我们对迭代器的要求是++就可以找到下一个节点的迭代器，然后–就可以找到上一个节点的迭代器，对于*我们就可以取到这个节点对应的值，所以这里很容易想到运算符重载，我们可以将这里的迭代器封装成一个类，然后对这个类进行封装
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> node;
typedef list_iterator<T, Ref, Ptr> self;
node* _node;
};
为了增加可读性我们将迭代器重命名为self。
注意：这里Ref表示引用是否需要加const，这里的Ptr表示的是指针是否需要加const
2.1operator*重载
Ref operator*()const
{
return _node->_data;
}
返回节点返回的值，注意 这里Ref代表的是引用
2.2operator->重载
Ptr operator->()const
{
return &operator*();
}
operator->返回的是节点对应的值的指针，因为节点有可能是内置类型，所以我嗯呢重载这个运算符，所以我们需要重载这个运算符来访问他的成员
2.3operator++重载
前置++
self& operator++()//传递引用防止拷贝构造
{
_node = _node->_next;
return *this;
}
先将节点指向下一个节点，然后返回下一个节点的迭代器
后置++
self operator++(int)
{
self tmp(*this);
++*this;
return tmp;
}
这里我们先创建一个临时的迭代器用this初始化然后对this进行++，注意，这里的++复用前面的的前置++，然后返回创建的临时的的迭代器的拷贝。注意这里返回值没有用引用，因为这里tmp出去之后要销毁，所以传递的是拷贝。
2.4operator–
//前置--
self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
self operator--(int)
{
self tmp(*this);
--*this;
return tmp;
}
2.5operator==和operator！=
bool operator==(const self& s)const
{
return _node == s._node;
}
bool operator!=(const self& s)const
{
return _node != s._node;
}
注意：这里我们还需要一个构造函数可以构造一个迭代器的函数
list_iterator(node* n) :_node(n) {}
用当前节点来构造一个迭代器
3.反向迭代器实现
基于正向迭代器实现的反向迭代器
这里反向迭代器器中只需要一个成员变量就是正向迭代器，我们只需要用正向迭代器中的运算符重载来封装反向迭代器的运算符重载。
template<class iterator, class Ref, class Ptr>
struct list_reverse_iterator
{
typedef list_reverse_iterator<iterator, Ref, Ptr> self;
iterator _cur;
};
注意：这里的模版参数还是和上面正向迭代器中的一样。。
3.1operator*重载
Ref operator*()const
{
//由于我们的成员变量是正向迭代器，但是我们的反向迭代器是从最后一个开始遍历的
iterator tmp = _cur;
--tmp;
return *tmp;//这里应该返回的是iterator重载的*
}
3.2operator->重载
Ptr operator->()const
{
return &operator*();
}
返回的是当前的指针
3.3operator++重载
前置++
self& operator++()
{
--_cur;
return *this;
}
注意：这里cur用的是正向迭代器中的前置–，反向迭代器的++是–向前访问
后置++
self operator++(int)
{
iterator tmp(_cur);
--*this;
return tmp;
}
后置++和上面正向迭代器的后置++类似
3.4operator–重载
//反向迭代器的--是++
self& operator--()
{
++_cur;
return *this;
}
self operator--(int)
{
iterator tmp(_cur);
++*this;//这里的--是复用上面的运算符重载
return tmp;
}
3.5operator!=和operator==重载
bool operator!=(const self& s)const
{
//这里可以直接复用正向迭代器已经实现的！=操作
return _cur != s._cur;
}
bool operator==(const self& s)const
{
return _cur == s._cur;
}
3.6反向迭代器的全部代码
template<class iterator, class Ref, class Ptr>
struct list_reverse_iterator
{
typedef list_reverse_iterator<iterator, Ref, Ptr> self;
list_reverse_iterator(iterator it) :_cur(it) {}
//重载反向迭代器的运算符
Ref operator*()const
{
//由于我们的成员变量是正向迭代器，但是我们的反向迭代器是从最后一个开始遍历的
iterator tmp = _cur;
--tmp;
return *tmp;//这里应该返回的是iterator重载的*
}
Ptr operator->()const
{
return &operator*();
}
//反向迭代器的++是--
self& operator++()
{
--_cur;
return *this;
}
self operator++(int)
{
iterator tmp(_cur);
--*this;
return tmp;
}
//反向迭代器的--是++
self& operator--()
{
++_cur;
return *this;
}
self operator--(int)
{
iterator tmp(_cur);
++*this;//这里的--是复用上面的运算符重载
return tmp;
}
bool operator!=(const self& s)const
{
//这里可以直接复用正向迭代器已经实现的！=操作
return _cur != s._cur;
}
bool operator==(const self& s)const
{
return _cur == s._cur;
}
iterator _cur;
};
4.list的成员函数
首先list的成员变量只需要一个节点类就可以，接下来我们来定义一个list。
//list的成员变量
node* _head;
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
由于我们每次初始化都要创建一个头节点，所以这里我们 直接封装成一个函数这样我们写构造函数的时候，就不用手动创建哨兵位的头结点了，可以直接调用函数。
4.1构造函数
4.1.1无参构造
list()
{
empty_init();
}
对于无参构造我们可以直接调用创建头结点的函数
4.1.2有参构造（用val初始化n个节点）
list(size_t n, const T& val = T())
{
empty_init();
for (size_t i = 0;i < n;i++)
{
push_back(val);
}
}
list(int n, const T& val = T())
{
empty_init();
for (int i = 0;;i < n;i++)
{
push_back(val);
}
}
4.1.3有参的迭代区间构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}
4.1.4拷贝构造函数和析构函数
list(const list<T>& x)
{
empty_init();
for (auto e : x)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
对于析构函数我们首先调用clear把所有除哨兵位的头结点外的节点全部给清理掉，然后再手动将头结点释放掉。
4.1.5赋值拷贝函数
list<T>& operator= (list<T> x)
{
swap(x);//这里调用的是自己实现的swap
return *this;
}
这是一种比较现代的写法，我们 传递的是拷贝构造，临时对象然后将这个临时对象和我们需要赋值拷贝的对象进行交换，由于这个是临时对象所以出了作用域就会销毁，这样我们的目的也达到了。
接下来我们来讲一种比较传统的写法，比较传统的写法：
list<T>& operator= (list<T> x)
{
assign(x.begin(),x.end());
return *this;
}
我们先用assign的迭代区间版进行拷贝，然后直接返回*this。
4.2assign函数
template <class InputIterator>
void assign(InputIterator first, InputIterator last)
{
//先删除所有节点，只剩下一个哨兵位节点
clear();
while (first != last)
{
push_back(*first);
first++;
}
}
void assign(size_t n, const T& val = T())
{
clear();
for (size_t i = 0;i < n;i++)
{
push_back(val);
}
}
void assign(int n, const T& val = T())
{
clear();
for (int i = 0;i < n;i++)
{
push_back(val);
}
}
注意迭代区间版本的assign函数需要重新定义一个模版，因为不妨有string或者其他的自定义类型的迭代器需要传递，如果我们传递就是当前类的迭代器，那么就只能传递当前类的迭代器，这样就一棒子打死了。
4.3指定位置的插入
注意：指定位置的删除返回的是迭代器，插入节点的迭代器，，这里我们来考虑一下会不会出现迭代器失效的情况，我们插入一个新节点，是我们重新开辟的节点，返回的也是重新开辟的节点的迭代器，所以这里不存在迭代器失效的问题。
对于插入来说，这里我们只需要记录pos位置的前一个节点，然后再pos和pos位置的前一个节点直接插入新的节点就可以了。
iterator insert(iterator pos, const T& val = T())
{
//插入新的值，应该创建一个新的节点
node* cur = pos._node;
node* newnode = new node(val);
node* prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
//这里返回的是构造函数
//用newnode重新构造了一个迭代器
return iterator(newnode);
}
4.4指定位置的删除
首先我们来讨论一下删除会不会出现迭代器失效的情况，这里很容易可以看出会出现迭代器失效的情况，因为我们删除的是当前节点，pos位置很明显已经被删除来了，成为了一个野的迭代器，所以这里为了防止迭代器失效的情况，我们直接返回下一个节点的迭代器就可以了
iterator erase(iterator pos)
{
assert(pos != end());
node* next = pos._node->_next;
node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
return iterator(next);
}
4.5首插尾插和首删尾删
这里可以直接复用上面写好的指定位置的插入和删除
void push_back(const T& val = T())
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val = T())
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
4.6交换函数
void swap(list<T>& x)
{
std::swap(_head, x._head);
}
4.7resize函数
对于resize函数，当n小于实际的size的时候我们需要尾删节点，当大于实际的size的时候我们需要尾插节点，用给定的指定的值
void resize(size_t n, T val = T())
{
size_t sz = size();
while (n < sz)
{
pop_back();
sz--;
}
while (n > sz)
{
push_back(val);
sz++;
}
}
4.8clear函数
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
4.9迭代器的封装
//封装两个正向迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<const T, const T&, const T*> const_iterator;
//封装两个反向迭代器
typedef list_reverse_iterator<T, T&, T*> reverse_iterator;
typedef list_reverse_iterator<const T, const T&, const T*> const_reverse_iterator;
iterator begin()
{
//因为是双向带头的链表，又因为是左闭右开，所以应该用head指向下一个，传递给begin
return iterator(_head->_next);
}
iterator end()
{
//左闭右开的缘故，所以这里传递的是head，因为实际访问不到head
return iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}
全部代码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace lyrics
{
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
list_node(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _data(val)
{
}
};
//这里封装一个类，用来控制list的迭代器
template<class T, class Ref, class Ptr>
//Ref表示引用是否const
//Ptr表示指针是否const
struct list_iterator
{
typedef list_node<T> node;
typedef list_iterator<T, Ref, Ptr> self;
node* _node;
//构造函数
list_iterator(node* n) :_node(n) {}
//重载迭代器的基本操作
//operator*用来访问迭代器对应的当前的数据
//返回值应该是引用，我们的引用用的是Ref
Ref operator*()const
{
return _node->_data;
}
//重载一个operator->防止list对应的是自定义类型的时候需要访问自定义类型的数据
Ptr operator->()const
{
return &operator*();
}
//重载一个++操作，因为在迭代器遍历的时候需要用到++这个操作对迭代器进行移动
//前置++
self& operator++()//传递引用防止拷贝构造
{
_node = _node->_next;
return *this;
}
//后置++
self operator++(int)
{
self tmp(*this);
++*this;
return tmp;
}
//前置--
self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
self operator--(int)
{
self tmp(*this);
--*this;
return tmp;
}
//除了上面的操作还需要一个！=和==因为我们要判断是否迭代器多久停止
bool operator==(const self& s)const
{
return _node == s._node;
}
bool operator!=(const self& s)const
{
return _node != s._node;
}
};
//上面封装了正向迭代器接下来封装反向迭代器
template<class iterator, class Ref, class Ptr>
struct list_reverse_iterator
{
typedef list_reverse_iterator<iterator, Ref, Ptr> self;
list_reverse_iterator(iterator it) :_cur(it) {}
//重载反向迭代器的运算符
Ref operator*()const
{
//由于我们的成员变量是正向迭代器，但是我们的反向迭代器是从最后一个开始遍历的
iterator tmp = _cur;
--tmp;
return *tmp;//这里应该返回的是iterator重载的*
}
Ptr operator->()const
{
return &operator*();
}
//反向迭代器的++是--
self& operator++()
{
--_cur;
return *this;
}
self operator++(int)
{
iterator tmp(_cur);
--*this;
return tmp;
}
//反向迭代器的--是++
self& operator--()
{
++_cur;
return *this;
}
self operator--(int)
{
iterator tmp(_cur);
++*this;//这里的--是复用上面的运算符重载
return tmp;
}
bool operator!=(const self& s)const
{
//这里可以直接复用正向迭代器已经实现的！=操作
return _cur != s._cur;
}
bool operator==(const self& s)const
{
return _cur == s._cur;
}
iterator _cur;
};
template<class T>
class list
{
typedef list_node<T> node;
public:
//封装两个正向迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<const T, const T&, const T*> const_iterator;
//封装两个反向迭代器
typedef list_reverse_iterator<T, T&, T*> reverse_iterator;
typedef list_reverse_iterator<const T, const T&, const T*> const_reverse_iterator;
iterator begin()
{
//因为是双向带头的链表，又因为是左闭右开，所以应该用head指向下一个，传递给begin
return iterator(_head->_next);
}
iterator end()
{
//左闭右开的缘故，所以这里传递的是head，因为实际访问不到head
return iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}
list()
{
empty_init();
}
list(size_t n, const T& val = T())
{
empty_init();
for (size_t i = 0;i < n;i++)
{
push_back(val);
}
}
list(int n, const T& val = T())
{
empty_init();
for (int i = 0;;i < n;i++)
{
push_back(val);
}
}
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}
list(const list<T>& x)
{
empty_init();
for (auto e : x)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
list<T>& operator= (list<T> x)
{
swap(x);//这里调用的是自己实现的swap
return *this;
}
bool empty() const
{
return _head->_next == _head;
}
size_t size() const
{
size_t count = 0;
for (auto e : *this)
{
count++;
}
return count;
}
template <class InputIterator>
void assign(InputIterator first, InputIterator last)
{
//先删除所有节点，只剩下一个哨兵位节点
clear();
while (first != last)
{
push_back(*first);
first++;
}
}
void assign(size_t n, const T& val = T())
{
clear();
for (size_t i = 0;i < n;i++)
{
push_back(val);
}
}
void assign(int n, const T& val = T())
{
clear();
for (int i = 0;i < n;i++)
{
push_back(val);
}
}
iterator insert(iterator pos, const T& val = T())
{
//插入新的值，应该创建一个新的节点
node* cur = pos._node;
node* newnode = new node(val);
node* prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
//这里返回的是构造函数
//用newnode重新构造了一个迭代器
return iterator(newnode);
}
iterator erase(iterator pos)
{
assert(pos != end());
node* next = pos._node->_next;
node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
return iterator(next);
}
void push_back(const T& val = T())
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val = T())
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void swap(list<T>& x)
{
std::swap(_head, x._head);
}
void resize(size_t n, T val = T())
{
size_t sz = size();
while (n < sz)
{
pop_back();
sz--;
}
while (n > sz)
{
push_back(val);
sz++;
}
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
private:
node* _head;
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
};
}
总结
在本文中，我们深入探讨了C++中std::list的使用以及如何通过模拟实现基本的链表功能。我们详细介绍了std::list的常见操作，如元素的插入、删除、访问和遍历，并解释了这些操作在底层是如何实现的。通过模拟实现一个简单的链表，我们不仅加深了对链表结构的理解，也体验了STL容器背后的设计思想和实现细节。
理解std::list的使用不仅是掌握C++标准库的重要部分，更是提高数据结构和算法水平的基础。通过亲自实现链表，我们可以更好地理解计算机内存管理和指针操作，这对于编写高效的C++程序至关重要。希望这篇文章能够帮助你更好地理解和运用std::list，并在实际编程中灵活运用。感谢你的阅读，期待你在C++编程之路上不断进步！
