C++模拟实现list

C++教学总目录

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 oncenamespace 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;}
}