C++的STL简介（四）

目录

1.List

2.list 模拟实现

2.1基本框架

2.2 list_node

2.3 list

2.3.1 默认构造

2.3.2 析构函数

2.3.3 begin（）

2.3.4 end（）

2.3.5 size（）

2.3.6 empty（）

2.3.7 insert（）

2.3.8 push_back()

2.3.9 push_front（）

2.3.10 erase （）

2.3.11 pop_back()

2.3.12 pop_front()

2.4 list_iterator

2.4.1 - >

2.4.2 *

2.4.3 前置++

2.4.4 后置++

2.4.5 前置--

2.4.6 后置 --

2.4.7 ！=

2.4.8 list_iterator完整代码

2.5 list_const_iterator

3.整个实现完整代码

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::reverseusing 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){ }};
//实现listtemplate<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

维护节点

//实现listtemplate<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 curnewnode->_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 curnewnode->_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::reverseusing 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 curnewnode->_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;}
}