一.list的基本结构
在模拟实现list之前，我们来梳理一下list的基本结构。
list是一个带头、双向、循环的链表。
所以对list的模拟实现，我们可以先封装一个List_Node结构体结点，然后再在list类中去存放头结点的指针来实现。
//链表结点
template<class T>
struct __List_Node
{
//构造函数
__List_Node(const T& val = T())
:_val(val)
,_prev(nullptr)
,_next(nullptr)
{}
//成员变量
T _val;
__List_Node<T>* _prev;
__List_Node<T>* _next;
};
//list类
template<class T>
class list
{
typedef __List_Node<T> Node;
public:
private:
Node* _head;//指向链表头结点的指针
};二.list的基本雏形
在模拟实现list的成员函数前，我们先来大致把list的雏形写出来。
对于一个list来说，最基本的用法是：插入数据、遍历链表。
插入数据没什么太多的说法，然而遍历比较重要，对于list的遍历，通常的做法都是去使用迭代器来遍历，所以我们先大致把list的雏形实现出来。
尾插数据
对于list的尾插，不太难，就是去生成一个新结点，然后把新结点链接到尾部即可。
//尾插
void push_back(const T& val)
{
Node* newnode = new Node(val);//开辟一个新结点
//开始将新结点链接到尾部
Node* tail = _head->_prev;//先找到尾结点
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}遍历链表
在实现遍历链表之前，我们先来回顾下一string和vector的迭代器遍历。
string::iterator it=str.begin();
while(it!=str.end())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
对于string和vector的遍历，我们可以看到，想要获取it迭代器的val，直接*it即可，因为string和vector的迭代器就是一个指针指向某个位置的下标，所以可以用*来解引用获取val，但是list不可以这样做，因为list的迭代器是一个指向结点的指针，直接解引用不能得到val，而是得到_val、_prev、_next。
同时string和vector的迭代器++操作也是真的将迭代器移到下一个位置，而list迭代器++是移到下一个结点处。
接下来在看一个代码来解释，将list的迭代器又++换成+1时，会报错，那是因为list的迭代器类中没有这个运算符的重载。
所以对于list的迭代器实现，我们可以封装一个iterator类来实现，在类中重载++和*。
list的迭代器实现
//封装迭代器
template<class T>
struct __list_iterator
{
typedef __List_Node<T> Node;
typedef __list_iterator<T> iterator
//构造函数
iterator(Node* val)
:_node(val)
{}
//重载*
T& operator*()
{
return _node->_val;
}
//重载++
iterator operator++()
{
_node = _node->_next;
return *this;
}
//重载!=
bool operator!=(const iterator& it)
{
if (this->_node != it._node)
return true;
else
return false;
}
//成员变量
Node* _node;//是一个指针结点的指针
};
//list类
template<class T>
class list
{
public:
typedef __List_Node<T> Node;
typedef __list_iterator<T> iterator;
public:
//非const正向begin迭代器
iterator begin()
{
iterator it(_head->_next);
return it;
}
//非const正向end迭代器
iterator end()
{
iterator it(_head);
return it;
}
private:
Node* _head;
};
做到这里，我list的基本雏形就已经实现了，接下来在一个个的实现剩下的函数即可。
三.正向Iterators的实现
在这里我们先来实现一下正向非const和const迭代器，反向迭代器暂时不讲解。
非const与const的正向迭代器
这两个迭代器前一个比较好实现，后一个就稍微没那么简单，要用到模板。
非const正向迭代器
对于非const的正向迭代器来说，比较简单，正向begin迭代器指向第一个元素，end迭代器指向_head即可。
//非const正向begin
iterator begin()
{
iterator it(_head->_next);
return it;
}
//非const正向end
iterator end()
{
iterator it(_head);
return it;
}
const正向迭代器
但对于const的正向迭代来说，就稍微没那么简单了，对于const的迭代器，我们先要去构建一个const类型的迭代器，然后将这个迭代器返回即可，那么应该如何设计呢，我们可以使用模板来实现。
给非const的迭代器传一个<T,T&,T*>的模板。
而const的迭代器传一个<T,const T&,const T*>的模板。
这样我们在构造非const迭代器的时候传<T,T&,T*>模板。
在构造const迭代器的时候传<T,const T&,const T*>模板。
//封装迭代器
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef __List_Node<T> Node;
typedef __list_iterator<T, Ref, Ptr> iterator;
//构造函数
__list_iterator(Node* val)
:_node(val)
{}
//重载*
Ref operator*()
{
return _node->_val;
}
//重载前置++
iterator& operator++()
{
_node = _node->_next;
return *this;
}
//重载后置++
iterator operator++(int)
{
iterator tmp(*this);
_node = _node->_next;
return tmp;
}
//重载前置--
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
//重载后置--
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载!=
bool operator!=(const iterator& it)
{
if (this->_node != it._node)
return true;
else
return false;
}
//成员变量
Node* _node;//是一个指针结点的指针
};
//list类
template<class T>
class list
{
public:
typedef __List_Node<T> Node;
typedef __list_iterator<T, T&, T*> iterator;//正向非const迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator;//正向const迭代器
public:
//const正向begin
const_iterator begin() const
{
const_iterator it(_head->_next);
return it;
}
//const正向end
const_iterator end() const
{
const_iterator it(_head);
return it;
}
private:
Node* _head;
};四.Member functions的模拟实现
构造函数
构造函数最主要有两个，一个是普通的无参构造函数，一个是拷贝构造函数。
无参构造函数
无参构造函数我们直接给一个头结点就好了
//构造函数
list()
:_head(new Node)
{
_head->_next = _head;
_head->_prev = _head;
}
拷贝构造函数
拷贝构造函数我们可以去遍历被拷贝的list，在遍历的途中将数据一个一个的尾插到新list中
//拷贝构造函数
list(const list<T>& l)
:_head(new Node)
{
_head->_next = _head;
_head->_prev = _head;
list<T>::const_iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
++it;
}
}析构函数
在实现析构函数之前，我们可以先把clear函数实现一下，再在析构函数中复用clear，这写起来更加方便。
clear函数
这个函数的功能是，将头结点除外的所有结点删除 。
//clear函数
void clear()
{
Node* move = _head->_next;
while (move != _head)//依次遍历每一个结点，并将结点释放
{
Node* moveNext = move->_next;
delete move;
move = moveNext;
}
_head->_next = _head;//保留头指针
_head->_prev = _head;
}析构函数
先将头结点外的所有结点删除，再删除头节点。
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}赋值=重载
list<int> l1;
list<int> l2;
l2=l1;
赋值=重载的实现，我们可以先用l1拷贝构造一个临时的list，再用这个临时的list去与l2做交换。
//交换函数，用于交换两个list
void Swap(list<T>& l)
{
swap(_head, l._head);
}
//赋值=重载
list<T>& operator=(const list<T>& l)
{
if (this != &l)
{
list<T> tmp(l);//先拷贝构造一个临时list
Swap(tmp);//用临时的list与*this交换
}
return *this;
}五.Capacity的模拟实现
在这些接口中，最常用的就前两个，我们来把这两个实现一下。
size函数
//求链表的大小
size_t size() const
{
size_t count = 0;
const_iterator cit = begin();
while (cit != end())
{
count++;
cit++;
}
return count;
}
empty函数
//判断链表是否为空
bool empty() const
{
if (size() == 0)
return true;
else
return false;
}六.Element access的模拟实现
这个部分有两个函数：front获取第一个元素的引用，back获取最后一个元素的引用。
front与back函数
//front函数
T& front()
{
assert(size());//断言list是否没有数据
return *(begin());
}
const T& front() const
{
assert(size());//断言list是否没有数据
return *(begin());
}
//back函数
T& back()
{
assert(size());
return *(--end());
}
const T& back() const
{
assert(size());
return *(--end());
}七. Modifiers的模拟实现
在这一部分中，我们来把常用的实现一下。
insert函数
//insert函数
iterator insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);//开辟一个新结点
Node* posNext = pos._node->_next;//找到pos的下一个结点
pos._node->_next = newnode;
newnode->_prev = pos._node;
newnode->_next = posNext;
posNext->_prev = newnode;
return iterator(newnode);
}erase函数
//erase函数
iterator erase(iterator pos)
{
assert(pos != end());//要删除的结点不能是_head
Node* posPrev = pos._node->_prev;
Node* posNext = pos._node->_next;
posPrev->_next = posNext;
posNext->_prev = posPrev;
delete pos._node;
return iterator(posNext);
}push_back、push_front、pop_back、pop_front函数
对于这四个函数来说，我们可以直接复用上面的insert和erase。
//尾插
void push_back(const T& val)
{
insert(--end(), val);
}
//尾删
void pop_back()
{
assert(size());
erase(--end());
}
//头插
void push_front(const T& val)
{
insert(end(), val);
}
//头删
void pop_front()
{
assert(size());
erase(begin());
}resize函数
这个函数是调整list的数据个数。
//resize函数
void resize(const size_t& n, const T& val = T())
{
if (n > size())//如果要调整的n大于list的大小，则一个个尾插
{
size_t tmp=n-size();
while (tmp--)
{
push_back(val);
}
}
else if (n < size())//如果要调整的n小于list的大小，则将一个个尾删
{
size_t tmp = size() - n;
while (tmp--)
{
pop_back();
}
}
}八.所以源代码
list.h
namespace list_blog
{
//链表结点
template<class T>
struct __List_Node
{
//构造函数
__List_Node(const T& val = T())
:_val(val)
,_prev(nullptr)
,_next(nullptr)
{}
//成员变量
T _val;
__List_Node<T>* _prev;
__List_Node<T>* _next;
};
//封装正向迭代器
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef __List_Node<T> Node;
typedef __list_iterator<T, Ref, Ptr> iterator;
typedef Ref Ref;
typedef Ptr Ptr;
//构造函数
__list_iterator(Node* val)
:_node(val)
{}
//重载*
Ref operator*() const
{
return _node->_val;
}
//重载前置++
iterator& operator++()
{
_node = _node->_next;
return *this;
}
//重载后置++
iterator operator++(int)
{
iterator tmp(*this);
_node = _node->_next;
return tmp;
}
//重载前置--
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
//重载后置--
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载!=
bool operator!=(const iterator& it)
{
if (this->_node != it._node)
return true;
else
return false;
}
//成员变量
Node* _node;//是一个指针结点的指针
};
//list类
template<class T>
class list
{
public:
typedef __List_Node<T> Node;
typedef __list_iterator<T, T&, T*> iterator;//正向非const迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator;//正向const迭代器
public:
//非const正向begin
iterator begin()
{
iterator it(_head->_next);
return it;
}
//非const正向end
iterator end()
{
iterator it(_head);
return it;
}
//const正向begin
const_iterator begin() const
{
const_iterator it(_head->_next);
return it;
}
//const正向end
const_iterator end() const
{
const_iterator it(_head);
return it;
}
//构造函数
list()
:_head(new Node)
{
_head->_next = _head;
_head->_prev = _head;
}
//拷贝构造函数
list(const list<T>& l)
:_head(new Node)
{
_head->_next = _head;
_head->_prev = _head;
list<T>::const_iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
++it;
}
}
//clear函数
void clear()
{
Node* move = _head->_next;
while (move != _head)//依次遍历每一个结点，并将结点释放
{
Node* moveNext = move->_next;
delete move;
move = moveNext;
}
_head->_next = _head;//保留头指针
_head->_prev = _head;
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
//交换函数，用于交换两个list
void Swap(list<T>& l)
{
swap(_head, l._head);
}
//赋值=重载
list<T>& operator=(const list<T>& l)
{
if (this != &l)
{
list<T> tmp(l);
Swap(tmp);
}
return *this;
}
//求链表的大小
size_t size() const
{
size_t count = 0;
const_iterator cit = begin();
while (cit != end())
{
count++;
cit++;
}
return count;
}
//判断链表是否为空
bool empty() const
{
if (size() == 0)
return true;
else
return false;
}
//front函数
T& front()
{
assert(size());//断言list是否没有数据
return *(begin());
}
const T& front() const
{
assert(size());//断言list是否没有数据
return *(begin());
}
//back函数
T& back()
{
assert(size());
return *(--end());
}
const T& back() const
{
assert(size());
return *(--end());
}
//insert函数
iterator insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);//开辟一个新结点
Node* posNext = pos._node->_next;//找到pos的下一个结点
pos._node->_next = newnode;
newnode->_prev = pos._node;
newnode->_next = posNext;
posNext->_prev = newnode;
return iterator(newnode);
}
//erase函数
iterator erase(iterator pos)
{
assert(pos != end());//要删除的结点不能是_head
Node* posPrev = pos._node->_prev;
Node* posNext = pos._node->_next;
posPrev->_next = posNext;
posNext->_prev = posPrev;
delete pos._node;
return iterator(posNext);
}
//尾插
void push_back(const T& val)
{
//Node* newnode = new Node(val);//开辟一个新结点
开始将新结点链接到尾部
//Node* tail = _head->_prev;//先找到尾结点
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(--end(), val);
}
//尾删
void pop_back()
{
assert(size());
erase(--end());
}
//头插
void push_front(const T& val)
{
insert(end(), val);
}
//头删
void pop_front()
{
assert(size());
erase(begin());
}
//resize函数
void resize(const size_t& n, const T& val = T())
{
if (n > size())
{
size_t tmp=n-size();
while (tmp--)
{
push_back(val);
}
}
else if (n < size())
{
size_t tmp = size() - n;
while (tmp--)
{
pop_back();
}
}
}
private:
Node* _head;
};
//测试正向迭代器
void Test1()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
const list<int> l2(l1);
list<int>::const_iterator cit = l2.begin();
while (cit != l2.end())
{
cout << *cit << " ";
cit++;
}
cout << endl;
}
//测试赋值=重载
void Test2()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
list<int> l2;
l1 = l2;
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
//测试size和empty
void Test3()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
cout << l1.size() << endl;
cout << l1.empty() << endl;
}
//测试front和back函数
void Test4()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
cout << l1.front() << endl;
cout << l1.back() << endl;
}
//测试insert和erase
void Test5()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
list<int>::iterator it = l1.begin();
it++;
it++;
l1.insert(it, 10);
it = l1.begin();
it++;
l1.erase(it);
it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
//测试头插、头删、尾插、尾删
void Test6()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.pop_back();
l1.pop_back();
l1.push_front(0);
l1.push_front(-1);
l1.push_front(-2);
l1.pop_front();
l1.pop_front();
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
//测试resize
void Test7()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);
l1.resize(10);
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
}test.c
#include"list.h"
int main()
{
list_blog::Test1();
list_blog::Test2();
list_blog::Test3();
list_blog::Test4();
list_blog::Test5();
list_blog::Test6();
list_blog::Test7();
return 0;
}