阅读量:0
目录
1.List
List是连续的容器，而vector是非连续的容器，即list将元素存储在连续的存储器中，而vector存储在不连续的存储器中。
向量（vector）中间的插入和删除是非常昂贵的，因为它需要大量的时间来移动所有的元素。链表克服了这个问题，它是使用list容器实现的。
List支持双向，并为插入和删除操作提供了一种有效的方法。
在列表中遍历速度很慢，因为列表元素是按顺序访问的，而vector支持随机访问。
2.list 模拟实现
2.1基本框架
list_node来实现每个节点，list_iterator和list_const_iterator是两个不同版本的迭代器一个是普通迭代器一个是const类型的迭代器，名字上也有所区分，list本身就有迭代器的效果，这个是为了模拟这个，重载了一些基本运算符，而list是统一管理节点，具有增删查改等效果
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <cassert> #include <algorithm> // For std::reverse using namespace std; namespace List { // 节点类 template<class T> class list_node { public: T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& data = T()) : _data(data) , _next(nullptr) , _prev(nullptr) {} }; //list迭代器 template<class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> Self; Node* _node; list_iterator(Node* node) : _node(node) { } }; //const版本迭代器 template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; Node* _node; // 修正: list_const_iterator 的构造函数应该接受 Node* 类型 list_const_iterator(Node* node) : _node(node) { } }; //实现list template<class T> class list { typedef list_node<T> Node; public: typedef list_iterator<T> iterator; typedef list_const_iterator<T> const_iterator; list() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } ~list() { while (!empty()) { pop_front(); } delete _head; } private: Node* _head; size_t _size; }; } 2.2 list_node
定义节点
template<class T> class list_node { public: T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& data = T()) : _data(data) , _next(nullptr) , _prev(nullptr) {} };2.3 list
维护节点
//实现list template<class T> class list { typedef list_node<T> Node; public: typedef list_iterator<T> iterator; typedef list_const_iterator<T> const_iterator; list() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } ~list() { while (!empty()) { pop_front(); } delete _head; } private: Node* _head; size_t _size; }; 2.3.1 默认构造
//默认构造 list() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } 2.3.2 析构函数
//析构函数 ~list() { while (!empty()) { pop_front(); } delete _head; }2.3.3 begin（）
开始位置的迭代器
//begin（） iterator begin() { return iterator(_head->_next); } //const const_iterator begin() const { return const_iterator(_head->_next); } 2.3.4 end（）
结尾位置的迭代器
//普通版 iterator end() { return iterator(_head); } //const版 const_iterator end() const { return const_iterator(_head); } 2.3.5 size（）
数据个数
size_t size() const { return _size; } 2.3.6 empty（）
判空
bool empty() const { return _size == 0; } 2.3.7 insert（）
指定位置插入
void insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); //prev newnode cur newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; ++_size; } 2.3.8 push_back()
尾插
void push_back(const T& x) { insert(end(), x); } 2.3.9 push_front（）
头插
void push_front(const T& x) { insert(begin(), x); } 2.3.10 erase （）
指定位置删除
void erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; --_size; } 2.3.11 pop_back()
尾删
void pop_back() { erase(--end()); } 2.3.12 pop_front()
头删
void pop_front() { erase(begin()); }2.3.13 list完整代码
template<class T> class list { typedef list_node<T> Node; public: typedef list_iterator<T> iterator; typedef list_const_iterator<T> const_iterator; list() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } size_t size() const { return _size; } bool empty() const { return _size == 0; } void insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); //prev newnode cur newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; ++_size; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; --_size; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } ~list() { while (!empty()) { pop_front(); } delete _head; } private: Node* _head; size_t _size; };2.4 list_iterator
为了支持list迭代器效果而模拟实现了一个迭代器
template<class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> Self; Node* _node; list_iterator(Node* node) : _node(node) { } };2.4.1 - >
// 修正: 返回指向 _data 的指针，而不是引用 T* operator->() { return &_node->_data; } 2.4.2 *
T& operator*() { return _node->_data; } 2.4.3 前置++
Self& operator++() { _node = _node->_next; return *this; } 2.4.4 后置++
Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } 2.4.5 前置--
Self& operator--() { _node = _node->_prev; return *this; } 2.4.6 后置 --
Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } 2.4.7 ！=
bool operator!=(const Self& x) const { return _node != x._node; } 2.4.8 list_iterator完整代码
template<class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> Self; Node* _node; list_iterator(Node* node) : _node(node) { } // 修正: 返回指向 _data 的指针，而不是引用 T* operator->() { return &_node->_data; } T& operator*() { return _node->_data; } 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& x) const { return _node != x._node; } };2.5 list_const_iterator
list_const_iterator和list_iterator实现原理一致，只是有些成员函数被const修饰，typedef了const
template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; Node* _node; // 修正: list_const_iterator 的构造函数应该接受 Node* 类型 list_const_iterator(Node* node) : _node(node) { } // 修正: 返回指向 _data 的 const 指针，而不是引用 const T* operator->() const { return &_node->_data; } const T& operator*() const { return _node->_data; } 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& x) const { return _node != x._node; } }; 3.整个实现完整代码
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <cassert> #include <algorithm> // For std::reverse using namespace std; namespace List { // 节点类 template<class T> class list_node { public: T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& data = T()) : _data(data) , _next(nullptr) , _prev(nullptr) {} }; template<class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> Self; Node* _node; list_iterator(Node* node) : _node(node) { } // 修正: 返回指向 _data 的指针，而不是引用 T* operator->() { return &_node->_data; } T& operator*() { return _node->_data; } 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& x) const { return _node != x._node; } }; template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; Node* _node; // 修正: list_const_iterator 的构造函数应该接受 Node* 类型 list_const_iterator(Node* node) : _node(node) { } // 修正: 返回指向 _data 的 const 指针，而不是引用 const T* operator->() const { return &_node->_data; } const T& operator*() const { return _node->_data; } 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& x) const { return _node != x._node; } }; template<class T> class list { typedef list_node<T> Node; public: typedef list_iterator<T> iterator; typedef list_const_iterator<T> const_iterator; list() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } size_t size() const { return _size; } bool empty() const { return _size == 0; } void insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); //prev newnode cur newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; ++_size; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; --_size; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } ~list() { while (!empty()) { pop_front(); } delete _head; } private: Node* _head; size_t _size; }; void test1() { list<int> lt; lt.push_back(1); lt.push_back(2); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } } 