STL——list模拟实现

一、模拟实现源码

#pragma oncenamespace sjx
{template <typename T>struct __list_node{__list_node<T>* _next;__list_node<T>* _prev;T _data;__list_node(const T& val = T()) :_data(val), _next(nullptr), _prev(nullptr){}};template <typename T, typename Ref, typename Ptr>struct __list_iterator{typedef __list_node<T> node;typedef __list_node<T>* node_pointer;typedef __list_iterator<T, Ref, Ptr> self;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;node_pointer _pnode;__list_iterator(const node_pointer& val = nullptr) :_pnode(val) {}__list_iterator(const iterator& it) :_pnode(it._pnode) {}Ref operator*(){return _pnode->_data;}Ptr operator->(){return &(_pnode->_data);}bool operator!=(const self& val) const{return _pnode != val._pnode;}bool operator==(const self& val) const{return _pnode == val._pnode;}self& operator++(){_pnode = _pnode->_next;return *this;}self operator++(int){self tmp(_pnode);_pnode = _pnode->_next;return tmp;}self& operator--(){_pnode = _pnode->_prev;return *this;}self operator--(int){self tmp(_pnode);_pnode = _pnode->_prev;return tmp;}};template <typename T>class list{public:typedef __list_node<T> node;typedef __list_node<T>* node_pointer;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;list(){empty_initialize();}template <typename InputIterator>list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}list(const list& other){empty_initialize();list<T> tmp(other.begin(), other.end());swap(tmp);}~list(){clear();delete _head;}list<T>& operator=(list<T> other){empty_initialize();swap(other);return *this;}// Element accessT& front(){assert(!empty());return _head->_next->_data;}const T& front() const{assert(!empty());return _head->_next->_data;}T& back(){assert(!empty());return _head->_prev->_data;}const T& back() const{assert(!empty());return _head->_prev->_data;}// Iteratorsiterator begin(){return _head->_next;}const_iterator begin() const{return _head->_next;}iterator end(){return _head;}const_iterator end() const{return _head;}// Capacitybool empty() const{return _head->_next == _head;}size_t size() const{size_t i = 0;node_pointer cur = _head->_next;while (cur != _head){++i;cur = cur->_next;}return i;}// Modifiersvoid clear(){node_pointer cur = _head->_next;while (cur != _head){node_pointer tmp = cur->_next;delete cur;cur = tmp;}_head->_next = _head;_head->_prev = _head;}iterator insert(const_iterator pos, const T& val){node_pointer cur = new node(val);node_pointer tail = pos._pnode;node_pointer head = tail->_prev;head->_next = cur;cur->_next = tail;tail->_prev = cur;cur->_prev = head;return cur;}iterator insert(const_iterator pos, size_t count, const T& val){for (size_t i = 0; i < count; ++i){pos = insert(pos, val);}return pos._pnode;}template <typename InputIterator>iterator insert(const_iterator pos, InputIterator first, InputIterator last){node_pointer head = pos._pnode;if (first != last){head = insert(pos, *first)._pnode;++first;}while (first != last){insert(pos, *first);++first;}return head;}iterator erase(const_iterator pos){node_pointer tmp = pos._pnode;if (pos != end()){node_pointer del = tmp;tmp = tmp->_next;del->_prev->_next = del->_next;del->_next->_prev = del->_prev;delete del;}return tmp;}iterator erase(const_iterator first, const_iterator last){while (first != last){first = erase(first);}return last._pnode;}void push_back(const T& val){node_pointer tmp = new node(val);node_pointer tail = _head->_prev;tail->_next = tmp;tmp->_next = _head;_head->_prev = tmp;tmp->_prev = tail;}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}void swap(list<T>& val){std::swap(_head, val._head);}protected:void empty_initialize(){_head = new node;_head->_next = _head;_head->_prev = _head;}private:node_pointer _head;};
}

二、重难点——迭代器实现

list的迭代器不同于vector，vector的迭代器用指针就可以实现大部分功能，但是list的迭代器要实现++，不再是单纯数值上的加减，而是要让迭代器指向当前结点的next。

因此，需要将list的迭代器封装成一个类__list_iterator。通过运算符重载，来改变迭代器运算的效果。

需要注意的是__list_iterator还有另外两个模板参数，Ref和Ptr。

对于const_iterator，它与普通的iterator的区别就是它里面的内容不允许被修改，但是本身依旧可以进行++或者--等操作，其区别之一就在于对迭代器的解引用，一个的返回值可以被修改，一个不可以，因此我们引入了一个模板参数Ref，对于普通的迭代器，它被设置为T&，而对于const迭代器，它被设置为const T&。

对于模板参数Ptr，需要应对以下情况：

#include <iostream>
#include <assert.h>
#include "my_list.h"
struct Data
{int _year;int _month;int _day;Data(int year = 2000, int month = 1, int day = 1):_year(year), _month(month), _day(day){}
};int main()
{// 如果存储的对象是自定义类型，且要访问其中的数据sjx::list<Data> l1;l1.push_back(Data());sjx::list<Data>::iterator it = l1.begin();// 使用 * 访问std::cout << (*it)._year << " " << (*it)._month << " " << (*it)._day << std::endl;// 使用 operator->std::cout << it.operator->()->_year << " " << it.operator->()->_month << " " << it.operator->()->_day << std::endl;// 为了可读性，一般我们省略了一个 ->std::cout << it->_year << " " << it->_month << " " << it->_day << std::endl;return 0;
}