list 用法与模拟

list 用法

list

list 模拟

#pragma once
#include <assert.h>
namespace sjy
{//链表节点template <typename T>struct __list_node{__list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_val(val){}/*成员变量*/__list_node<T>* _prev;__list_node<T>* _next;T _val;};//迭代器template <typename T, typename Ref, typename Ptr>struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}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& other) const{return _node != other._node;}bool operator==(const self& other) const{return _node == other._node;}/*成员变量*/Node* _node;};//list容器template <typename 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;}//默认成员函数相关list():_size(0){_head = new Node;_head->_prev = _head;_head->_next = _head;}~list(){clear();delete _head;}list(const list<T>& other):_size(0){_head = new Node;_head->_prev = _head;_head->_next = _head;iterator it = other.begin();while (it != other.end()){push_back(*it);++it;}}list<T>& operator=(list<T> other){swap(other);return *this;}//添加相关void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = _tail;newnode->_next = _head;_head->_prev = newnode;_size++;}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* posptr = pos._node;Node* posptrprev = posptr->_prev;posptrprev->_next = newnode;newnode->_prev = posptrprev;newnode->_next = posptr;posptr->_prev = newnode;_size++;return newnode;}//删除相关void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos != end());Node* posptr = pos._node;++pos;Node* posptrprev = posptr->_prev;Node* posptrnext = posptr->_next;posptrprev->_next = posptrnext;posptrnext->_prev = posptrprev;delete posptr;_size--;return pos;}//其他size_t size(){return _size;}void swap(list<T>& other){std::swap(_head, other._head);std::swap(_size, other._size);}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}private:Node* _head;size_t _size;};
}