C++模拟实现list
C++教学总目录
C++模拟实现list
- 1、成员变量
- 2、迭代器
- 3、insert函数
- 4、erase函数
- 5、pop_back、push_front、pop_front函数
- 6、size和clear函数
- 7、析构函数
- 8、拷贝构造函数
- 9、赋值运算符重载
- 完整代码（包含测试代码）
1、成员变量
先来看看SGI版本STL中list的实现方式：
成员变量就是一个结点的指针。但是我们实现的时候多加一个size来保存结点个数，因为如果计算结点个数需要遍历一遍链表，时间复杂度为O(N)，我们选择多提供一个size成员变量。
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _val(val)
{}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
list()
{
empty_init();
}
private:
Node* _head;
size_t _size;
};
我们仿照SGI版本的实现，为了方便写将结点类型重命名。
这里提供了一个empty_init函数是用来创建哨兵位的头节点的。当我们调用空的构造函数、带参的构造函数、拷贝构造函数等都需要先创建哨兵位的头节点，所以我们将这一步写在函数里面，后面调用empty_init即可。
2、迭代器
list的迭代器不同于vector和string。vector和string基于底层的性质，可以对其开辟空间的指针进行++/–，所以vector和string的迭代器就是原生指针。但是list的迭代器无法是结点的指针，因为list空间并不连续，指针++/–无法找到下一个/前一个结点。
我们先来看看SGI版本是如何实现的：
可以看到，list的迭代器是创建了自定义类型来实现的，再对自定义类型重载operator++/–，这样就可以实现迭代器的功能，同时要获取数据就重载operator*。
实现如下：
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_val;
}
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
__list_iterator<T> operator++(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
__list_iterator<T>& operator--()
{
_node = _node->_prev;
return *this;
}
__list_iterator<T> operator--(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const __list_iterator<T>& it) const
{
return _node != it._node;
}
bool operator==(const __list_iterator<T>& it) const
{
return _node == it._node;
}
};
然后在list类中对该结构体类型重命名，并实现begin和end。
typedef __list_iterator<T> iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
接着我们实现一个push_back函数，然后就可以跑起来测试一下我们写的迭代器了：
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
newnode->_prev = tail;
tail->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;
_size++;
}
下面对我们写的迭代器进行测试：
可以发现我们写的迭代器成功跑起来了。
下面提出几个注意点：
普通迭代器已经实现了，那么const迭代器呢？
思路一：
typedef const __list_iterator<T> const_iterator;
这样子行吗？
这样子是不行的，因为const修饰迭代器之后，迭代器内的成员变量是不能修改的，也就不能进行++/–了，所以这样写是不行了。
思路二：
template<class T>
struct __list_const_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->_val;
}
__list_const_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
__list_const_iterator<T> operator++(int)
{
__list_const_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
__list_const_iterator<T>& operator--()
{
_node = _node->_prev;
return *this;
}
__list_const_iterator<T> operator--(int)
{
__list_const_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const __list_const_iterator<T>& it) const
{
return _node != it._node;
}
bool operator==(const __list_const_iterator<T>& it) const
{
return _node == it._node;
}
};
typedef __list_const_iterator<T> const_iterator;
将普通迭代器拷贝一份，名字改为__list_const_iterator，operator*改为const T，这样也可以实现const迭代器，但是这么写太冗余了。
我们来看看库里是怎么写的：
添加了两个模板参数，这里我们先看Ref，Ref实际上就是类型的引用，如果是普通迭代器就是T&，如果是const迭代器就是const T&。通过不同的模板参数实例化出不同类。
我们再来看Ptr，Ptr实际上是T*/const T*，因为迭代器还重载了一个函数：operator->：
为什么重载这个函数呢？
当我们的T类型是自定义类型时：
struct A
{
int _a1;
int _a2;
A(int a1 = 0, int a2 = 0)
:_a1(a1), _a2(a2)
{}
};
int main()
{
zzy::list<A> lt;
lt.push_back(A(1, 1));
lt.push_back(A(2, 2));
lt.push_back(A(3, 3));
zzy::list<A>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_a1 << " " << it->_a2 << endl;
++it;
}
return 0;
}
这里重载operator->也是需要传模板参数控制，对于普通对象就是T*，对于const对象就是const T*。
那么综合上述，并且为了方便书写迭代器类型，我们对迭代器类型typedef为self，代码如下：
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->_val;
}
Ptr operator->()
{
return &(operator*());
}
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) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};
并且在list类中加上const迭代器：
typedef __list_iterator<T, const T&, const T*> const_iterator;
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
但是！！！！！这样写完还是不能调用const迭代器！！！！
zzy::list<A> lt;
lt.push_back(A(1, 1));
lt.push_back(A(2, 2));
lt.push_back(A(3, 3));
zzy::list<A>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_a1 << " " << it->_a2 << endl;
++it;
}
上面的代码中，我们虽然指明it是const迭代器，但是lt调用的begin函数还是普通迭代器的begin函数。
这是因为lt是普通对象，所以调用普通迭代器begin，如果lt是const对象，那就会调用const迭代器的begin。
而因为lt.begin的返回值是普通迭代器，而it是const迭代器，所以就变成了用普通迭代器构造const迭代器，而我们迭代器模板类中并没有写普通迭代器构造const迭代器的函数。所以无法从普通迭代器转换成const迭代器，因此无法使用const迭代器。
解决办法很简单，添加一个普通迭代器构造const迭代器就行。
typedef __list_iterator<T, T&, T*> iterator;
__list_iterator(const iterator& it)
:_node(it._node)
{}
添加这个函数之后：
1、当模板类实例化为const迭代器时，支持普通迭代器构造const迭代器。
2、当模板类实例化为普通迭代器时，本质上就是普通迭代器的拷贝构造函数。
所以说：在那么早以前，C++祖师爷能搞出这些东西，是多么的牛逼！！！！！！
3、insert函数
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return newnode;
}
insert函数实现在pos位置之前插入一个新结点，并返回新节点的迭代器。
4、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;
--_size;
return next;
}
5、pop_back、push_front、pop_front函数
这三个函数我们直接复用前面写好的insert和erase就行，前面写的push_back也可以复用insert。
void pop_back()
{
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
6、size和clear函数
size_t size() const { return _size; }
// 如果不提供_size成员变量，需要遍历链表求出节点个数。
size_t size() const
{
size_t sz = 0;
auto it = begin();
while (it != end())
{
++it;
++sz;
}
return sz;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
7、析构函数
复用clear函数：
~list()
{
clear();
delete _head;
_head = nullptr;
}
8、拷贝构造函数
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
push_back(e);
}
9、赋值运算符重载
这个我们使用现代写法，但是需要先实现一个swap函数用来交换list的值。
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
//list& operator=(list& lt) 也可以这么写，但是不推荐
list<T>& operator=(list<T>& lt)
{
swap(lt);
return *this;
}
可以看到上面的operator=重载的返回值和参数可以直接写为list，但是不推荐这么写。我们还是写成list<T>好一些。
完整代码（包含测试代码）
#pragma once
namespace zzy
{
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _val(val)
{}
};
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
typedef __list_iterator<T, T&, T*> iterator;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
__list_iterator(const iterator& it)
:_node(it._node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(operator*());
}
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) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
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 _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
list()
{
empty_init();
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
push_back(e);
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
//list& operator=(list& lt) 也可以这么写，但是不推荐
list<T>& operator=(list<T>& lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
size_t size() const { return _size; }
//size_t size() const
//{
// size_t sz = 0;
// auto it = begin();
// while (it != end())
// {
// ++it;
// ++sz;
// }
// return sz;
//}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
//newnode->_prev = tail;
//tail->_next = newnode;
//newnode->_next = _head;
//_head->_prev = newnode;
//_size++;
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return 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;
--_size;
return next;
}
private:
Node* _head;
size_t _size;
};
void Print(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//(*it) += 1;
cout << *it << " ";
++it;
}
cout << endl;
}
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;
Print(lt);
}
struct A
{
A(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
int _a1 = 0;
int _a2 = 0;
};
void test_list2()
{
list<A> lt;
lt.push_back(A(1, 1));
lt.push_back(A(2, 2));
lt.push_back(A(3, 3));
lt.push_back(A(4, 4));
list<A>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << (*it)._a1 << " " << (*it)._a2 << endl;
// 这里的it模拟的是自定义类型的指针，所以可以这样写
cout << it->_a1 << " " << it->_a2 << endl;
// 严格来说it->->_a1，这么写才是符合语法的
// 因为运算符重载要求可读性，编译器特殊处理，省略了一个->
it++;
}
cout << 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_front(5);
lt.push_front(6);
lt.push_front(7);
lt.push_front(8);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_front();
lt.pop_back();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.clear();
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << lt.size() << endl;
}
void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
list<int> lt1(lt);
list<int>::const_iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
list<int> lt2;
lt2.push_back(10);
lt2.push_back(20);
lt2.push_back(30);
lt2.push_back(40);
lt1 = lt2;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
}