一、 list的介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
二、list的模拟实现
1、list的节点
template<class T> struct list_node { T _data; list_node<T>* _prev; list_node<T>* _next; list_node(const T& x = T()) :_data(x) , _next(nullptr) , _prev(nullptr) {} };
2、list 的迭代器
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) {} self& operator++() { _node = _node->_next; return *this; } self& operator--() { _node = _node->_prev; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } };
3、list
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->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } list(list<T>& lt) { empty_init(); for (auto e : lt) { push_back(e); } } list<T>& operator=(list<T> lt) { swap(lt); return *this; } void swap(list<T> lt) { std::swap(_size, lt._size); std::swap(_head, lt._head); } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* newnode = new Node(x); Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return iterator(newnode); } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; prev->_next = next; next->_prev = prev; --_size; } size_t size() { return _size; } void clear() { iterator it = begin(); while (it != end) { it = erase(it); } } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void push_back() { erase(end()); } void pop_back() { erase(begin()); } private: Node* _head; size_t _size; };
4、打印
template<typename Container> void print_container(const Container& con) { typename Container::const_iterator it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; } cout << endl; } void test_list() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); print_container(lt); list<string> lt1; lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); print_container(lt1); vector<string> v; v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); print_container(v); } } int main() { bit::test_list(); return 0; }
5、完整代码
#include<iostream> #include<string> #include<vector> using namespace std; namespace bit { template<class T> struct list_node { T _data; list_node<T>* _prev; list_node<T>* _next; list_node(const T& x = T()) :_data(x) , _next(nullptr) , _prev(nullptr) {} }; 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) {} self& operator++() { _node = _node->_next; return *this; } self& operator--() { _node = _node->_prev; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._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->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } list(list<T>& lt) { empty_init(); for (auto e : lt) { push_back(e); } } list<T>& operator=(list<T> lt) { swap(lt); return *this; } void swap(list<T> lt) { std::swap(_size, lt._size); std::swap(_head, lt._head); } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* newnode = new Node(x); Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return iterator(newnode); } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; prev->_next = next; next->_prev = prev; --_size; } size_t size() { return _size; } void clear() { iterator it = begin(); while (it != end) { it = erase(it); } } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void push_back() { erase(end()); } void pop_back() { erase(begin()); } private: Node* _head; size_t _size; }; template<typename Container> void print_container(const Container& con) { typename Container::const_iterator it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; } cout << endl; } void test_list() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); print_container(lt); list<string> lt1; lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); lt1.push_back("1111111111111"); print_container(lt1); vector<string> v; v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); print_container(v); } } int main() { bit::test_list(); return 0; }
