文章目录：
🌏list介绍
1、list是一个序列式容器，可以允许在常数时间内对容器中的任意位置进行插入和删除的操作，且list是一个双向链表，该容器可以前后双向迭代。
2、list与forward_list非常相似：最主要的区别是forward_list是单向链表，只能向前迭代，让其更简单更高效。
3、list与其它标准序列容器(array、vector和deque)相比，list在任意位置进行插入和删除元素执行更高效。
4、与其它序列式容器相比，list和forward_list最大的缺陷是不支持随机访问容器中任意位置的元素。
🌏list结构
🌏list模拟实现
list基本框架
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace hy
{
//定义list的节点类
template<class T>
struct __list_node
{
T _data;
__list_node* _prev;
__list_node* _next;
__list_node(const T& data = T())
:_data(data)
,_prev(nullptr)
,_next(nullptr)
{}
};
template<class T>
class list
{
public:
typedef __list_node<T> node;
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head;
};
}
list的构造函数
1?? 空初始化list
2?? n个val值初始化list
3?? 用一段迭代器区间初始化链表
empty_list_init()
{
_head = new node(T()); //无法确定传入的参数类型，所以传匿名函数构造
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_list_init();
}
list(size_t n, const T& val = T())
{
empty_list_init();
for (size_t i = 0;i < n;++i)
push_back(val);
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_list_init();
while (first != last)
{
push_back(*first);
++first;
}
}
list的正向迭代器和反向迭代器
🌑迭代器的实现有两种方式，具体应该根据容器底层的数据结构实现：
- 原生态指针，如：vector
- 将原生态指针进行封装，因为迭代器的使用形式与指针相同，所以自定义类中需要实现以下方法：
1、指针可以解引用访问数据，因此迭代器类中需要重载operator*()
2、指针通过->访问其指向空间的成员，迭代器类中需要重载operator->()
3、指针需要依次向后（向前）移动，所以需重载operator++()与operator++(int),反向迭代器需重载operator–()与operator–(int)
5、需要比较是否相等，所以重载operator==()和operator!=()
反向迭代器用正向迭代器去适配
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 = nullptr)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
const T& operator*()const
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
}
//后置 ++it it.operator++(&it)
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//前置 it++ it.operator++(&it,0)
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& lt)const
{
return _node == lt._node;
}
bool operator==(const Self& lt)const
{
return _node != lt._node;
}
};
template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp(_it);
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator==(const Self& s)
{
return _it == s._it;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
};
拷贝构造和赋值运算符重载
🗺?写法一:
拷贝构造: 新链表申请头节点，遍历传入的链表，将其中的值依次尾插到新的链表。
赋值运算符重载: 检查是否自己给自己赋值，清理原有链表资源，遍历赋值的链表，将其中的值依次尾插到新的链表。
list(const list<T>& lt)
{
_head = new node(T());
_head->_prev = _head;
_head->_next = _head;
for (const auto& e : lt)
{
push_back(e);
}
}
list<T>& operator=(const list<T>& lt)
{
if (lt != &this)
{
clear();
for (const auto& e : lt)
{
push_back(e);
}
}
return *this;
}
🗺?写法二:
拷贝构造: 用传入的lt对象的[begin,end)区间构造一个tmp对象，将tmp和需要的对象交换。
赋值运算符重载: 函数的参数使用传值传参，传值传参拷贝了lt对象，将lt和需要赋值的交换。
void clear()
{
iterator it = begin();
while (it != end())
{
//erase删除一个后会返回下一个位置
it = erase(it);
}
}
list(const list<T>& lt)
{
list<T> tmp(lt.begin(), lt.end());
empty_list_init();
swap(tmp);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
list容量相关 size 、resize
🛩?resize: 若n大于原有效节点数量，我们只需要删除多余的节点，若n小于原有效节点数量，调用push_back 插入val值。注意：我们需要先保存原有节点的数量，因为我们进行插入或删除时链表的size会随着改变。
size_t size()const
{
size_t count = 0;
node* cur = _head->_next;
while (cur != _head)
{
++count;
cur = cur->_next;
}
return count;
}
void resize(size_t n, const T& val = T())
{
size_t oldSize = size();
if (n < oldSize)
{
//将有效元素减少到n
while (n < oldSize)
{
pop_back();
oldSize--;
}
}
else
{
while (n > oldSize)
{
push_back(val);
oldSize++;
}
}
}
list的插入和删除
//在pos位置插入值为val的节点
iterator insert(iterator pos, const T& val)
{
assert(pos._node);
node* newnode = new node(val);
node* cur = pos._node;
// 插入新的节点
newnode->_next = cur;
newnode->_prev = cur->_prev;
cur->_prev = newnode;
newnode->_prev->_next = newnode;
return iterator(newnode);
}
//删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
assert(pos._node);
assert(pos != end());
node* prev = pos._node->_prev;
node* next = pos._node->_next;
delete pos._node;
prev->_next = next;
next->_prev = prev;
return iterator(next);//返回删除节点的下一个位置
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
list元素的访问操作
T& front()
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
const T& front()const
{
return _head->_next->_data;
}
const T& back()const
{
return _head->_prev->_data;
}
🌏list模拟实现完整代码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace hy
{
//定义list的节点类
template<class T>
struct __list_node
{
T _data;
__list_node* _prev;
__list_node* _next;
__list_node(const T& data = T())
:_data(data)
,_prev(nullptr)
,_next(nullptr)
{}
};
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 = nullptr)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
const T& operator*()const
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
}
//后置 ++it it.operator++(&it)
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//前置 it++ it.operator++(&it,0)
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& lt)const
{
return _node == lt._node;
}
bool operator!=(const Self& lt)const
{
return _node != lt._node;
}
};
template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp(_it);
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator==(const Self& s)
{
return _it == s._it;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
};
template<class T>
class list
{
public:
typedef __list_node<T> node;
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
//反向迭代器适配支持
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
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(iterator(end()));
}
reverse_iterator rend()
{
return reverse_iterator(iterator(begin()));
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(iterator(end()));
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(iterator(begin()));
}
T& front()
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
const T& front()const
{
return _head->_next->_data;
}
const T& back()const
{
return _head->_prev->_data;
}
void empty_list_init()
{
_head = new node(T());//无法确定传入的参数类型，所以传匿名函数构造
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_list_init();
}
list(size_t n, const T& val = T())
{
empty_list_init();
for (size_t i = 0;i < n;++i)
push_back(val);
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_list_init();
while (first != last)
{
push_back(*first);
++first;
}
}
/*list(const list<T>& lt)
{
_head = new node(T());
_head->_prev = _head;
_head->_next = _head;
for (const auto& e : lt)
{
push_back(e);
}
}*/
/*
list<T>& operator=(const list<T>& lt)
{
if (lt != &this)
{
clear();
for (const auto& e : lt)
{
push_back(e);
}
}
return *this;
}*/
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
void clear()
{
iterator it = begin();
while (it != end())
{
//erase删除一个后会返回下一个位置
it = erase(it);
}
}
list(const list<T>& lt)
{
list<T> tmp(lt.begin(), lt.end());
empty_list_init();
swap(tmp);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
size_t size()const
{
size_t count = 0;
node* cur = _head->_next;
while (cur != _head)
{
++count;
cur = cur->_next;
}
return count;
}
void resize(size_t n, const T& val = T())
{
size_t oldSize = size();
if (n < oldSize)
{
//将有效元素减少到n
while (n < oldSize)
{
pop_back();
oldSize--;
}
}
else
{
while (n > oldSize)
{
push_back(val);
oldSize++;
}
}
}
//在pos位置插入值为val的节点
iterator insert(iterator pos, const T& val)
{
assert(pos._node);
node* newnode = new node(val);
node* cur = pos._node;
// 插入新的节点
newnode->_next = cur;
newnode->_prev = cur->_prev;
cur->_prev = newnode;
newnode->_prev->_next = newnode;
return iterator(newnode);
}
//删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
assert(pos._node);
assert(pos != end());
node* prev = pos._node->_prev;
node* next = pos._node->_next;
delete pos._node;
prev->_next = next;
next->_prev = prev;
return iterator(next);//返回删除节点的下一个位置
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void empty()
{
return begin() == end();
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head;
};
}