1.基础元素
struct list_node
{list_node* _next;list_node* _prev;T _data;list_node(const T& x): _next(nullptr), _prev(nullptr), _data(x){}
};
list链表,基本要素就是链表的一个小块,这个小块自己带着的数据以及指向前后位置的指针组成。初始化时,赋值指定,指向就为nullptr即可
2.迭代器
1.普通和const迭代器实现
由于实现的迭代器分别是普通迭代器和const迭代器,分开写的话代码重复度过高,所以我们需要套用模板
template<class T,class Ref,class Ptr>
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode->_data;}Ptr operator->(){return &_pnode->_data;}Self& operator++(){_pnode = _pnode->_next;return *this;}Self operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}Self& operator--(){_pnode = _pnode->_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}
};
需要介绍一下为什么这样写
首先我们实现的无论哪种迭代器都是一样的操作,差别就是const的不能修改值嘛,也就意味着迭代器函数传出的参数是const修饰的,所以差别在传出的表示。不过,那么我们就可以用模板直接替代传出变量的位置。
基本实现参数有三类
普通的迭代器表示:<T,T*,T&>
const的迭代器表示:<const T,const T*,const T&>
我们清楚,其实这三种切换就行,那么我们直接将这三种的模板套用,<class T,class Ref,class Ptr>。
那么在list的结构体实现中,我们就可以套用模板实现普通和const的迭代器
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
2.正迭代器实现和反向迭代器实现
对比正迭代器,反向的无非就是倒着走,那么它的函数是和正迭代器实现相反,不过都是一个list中的不同功能迭代器。所以实现代码分离就可以了。
先给出我们list结构体的外壳,为了方便求总数不需要遍历,我们用空间换时间。
template<class T>
class list
{
private:node* _head;size_t _size;
};
我们将普通迭代器和const迭代器模板展开,然后将反向迭代器展开,对于我们而言反向迭代器就是把函数变一下而已。
typedef list_node<T> node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;typedef ReverIterator<iterator, const T&, const T*> reverse_iterator;
typedef ReverIterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const
{return const_iterator(_head->_next);
}const_iterator end() const
{return const_iterator(_head);
}iterator begin()
{return iterator(_head->_next);
}iterator end()
{return iterator(_head);
}reverse_iterator rbegin()
{return reverse_iterator(end());
}reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rbegin() const
{return reverse_iterator(end());
}const_reverse_iterator rend() const
{return reverse_iterator(begin());
}
3.拷贝构造和赋值拷贝
void empty_initialize()
{_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;
}list()
{empty_initialize();
}template <class InputIterator>
list(InputIterator first, InputIterator last)
{empty_initialize();while (first != last){push_back(*first);++first;}
}void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}list(const list<T>& lt)
{empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);
}list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}
4.全部实现代码
namespace MY
{template<class T>struct list_node{list_node* _next;list_node* _prev;T _data;list_node(const T& x): _next(nullptr), _prev(nullptr), _data(x){}};template<class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode->_data;}Ptr operator->(){return &_pnode->_data;}Self& operator++(){_pnode = _pnode->_next;return *this;}Self operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}Self& operator--(){_pnode = _pnode->_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}};/*template<class T>struct __list_const_iterator{typedef list_node<T> node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T& operator*(){return _pnode->_data;}__list_const_iterator<T>& operator++(){_pnode = _pnode->_next;return *this;}__list_const_iterator<T>& operator--(){_pnode = _pnode->_prev;return *this;}bool operator!=(const __list_const_iterator<T>& it){return _pnode != it._pnode;}};*/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;//typedef __list_const_iterator<T> const_iterator;typedef ReverIterator<iterator, const T&, const T*> reverse_iterator;typedef ReverIterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return reverse_iterator(end());}const_reverse_iterator rend() const{return reverse_iterator(begin());}void empty_initialize(){_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_initialize();}/*list(const list<T>& lt){empty_initialize();for (const auto& e : lt){push_back(e);}}*/template <class InputIterator>list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}void swap(list<T>& lt)//void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(const list<T>& lt)//list(const list& lt){empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);}/*list<T>& operator=(const list<T>& lt){if (this != <){clear();for (const auto& e : lt){push_back(e);}}return *this;}*/list<T>& operator=(list<T> lt)//list& operator=(list lt){swap(lt);return *this;}size_t size() const{return _size;}bool empty() const{return _size == 0;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}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;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};
}
5.list和vector的比较
vector | list | |
底层结构 | 动态顺序表,一段连续空间 | 带头结点的双向循环链表 |
随机访问 | 支持随机访问,访问某个元素效率O(1) | 不支持随机访问,访问某个元素 效率O(N) |
插入和删除 | 任意位置插入和删除效率低,需要搬移元素,时间复杂 度为O(N),插入时有可能需要增容 | 任意位置插入和删除效率高,不 需要搬移元素,时间复杂度为 O(1) |
空间利用率 | 缓存利用率高 | 空间利用率低, 缓存利用率低 |
迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装,即前一个后一个位置都要知道 |
迭代器失效 | 在插入元素时,要给所有的迭代器重新赋值,因为插入 元素有可能会导致重新扩容,致使原来迭代器失效,删除时,当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效, 删除元素时,只会导致当前迭代 器失效,其他迭代器不受影响 |
使用场景 | 需要高效存储,支持随机访问,不关心插入删除效率 | 大量插入和删除操作,不关心随机访问 |