C++ STL容器之list的使用及复现

list

1. 序列式容器

vector、list、deque、forward_list(C++11 )等STL容器，其底层为线性序列的数据结构，里面存储的是元素本身，这样的容器被统称为序列式容器。

2. list容器

list 是用双向带哨兵位头节点的循环链表实现的。list 通过类模板来满足不同类型的数据，在使用时必须显示实例化调用。

3. list的成员函数

3.1 list的成员函数的介绍

函数声明	功能介绍
list< T > l()	构造一个空的list
list< T > l(n,val)	构造一个内容为n个val的list
list< T > l (l1.iterator1(),l1.iterator2())	构造一个从l1的iterator1到iterator2的list
list< T >l(l1)	拷贝构造一个l1的list

2. list的迭代器

函数名	功能介绍
begin和end	begin:首元素的位置；end：下一个元素的位置
rbegin和rend	c指const，cbegin和cend指向的内容不能修改
cbegin和cend	反向迭代器，rbegin从end开始，rend从begin开始，其++和–的方向相反
crbegin和crend	与前一个功能相同，但指向的内容不能修改

3.list的容量与元素访问

函数名	函数声明	功能介绍
size	size_type size() const	返回list中有效元素个数
front	reference front() const_reference front() const	返回list第一个元素的引用。
back	reference back() const_reference back() const	返回list最后一个元素的引用。

4.list容器的修改

函数名	函数声明	功能介绍
size	size_type size() const	返回list中有效元素个数
front	reference front() const_reference front() const	返回list第一个元素的引用。
back	reference back() const_reference back() const	返回list最后一个元素的引用。

4. list容器的重构

4.1 list迭代器的问题

迭代器的构造函数问题：

迭代器需要一个构造函数来初始化迭代器的状态，但迭代器不需要写拷贝构造，因为迭代器指向的节点不属于迭代器的类。

list迭代器的多参数特点：

在重载 list 的迭代器时，需要考虑普通迭代器的重载和 const 迭代器的重载。但如果只使用一个模板参数，就需要把普通迭代器的整段代码都拷贝下来单独做一份 const 迭代器的类，造成代码的冗余。（因为函数重载必须返回值相同，cons t修饰不算是重载，所以只能多做一个类）

stl中的list容器使用了多个模板参数来规避这个问题：

template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// *it//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr 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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};

迭代器使用多个模板解决 const，本质相当于写了一个类模板，编译器生成了两个类。

list迭代器的比较：

注意 operator== 和 operator！= 不是用 list 的值进行比较的，因为 list 中可以有多个相同的值，在迭代器遍历时会出现问题。实际它们的比较是通过地址来比较的，这样能确保在遍历的时候不会出问题。

4.2 begin和end

begin和end的const问题：

begin() 和 end() 使用在 const 对象上时，不能直接对其进行 const 修饰。原因是对迭代器加 const 修饰，不能修改的是迭代器，但我们的目的是让迭代器指向的内容不能被修改，所以迭代器有 iterator 和 const_iterator 两个版本。

template<class T>
class list
{typedef ListNode<T> Node;
public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<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;}
}

begin和end的匿名对象问题：

在重构 list 的迭代器时候，begin() 和 end() 的实现原理是匿名对象，而匿名对象会调用对象的拷贝构造：

template<class T>
class list
{typedef ListNode<T> Node;
public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);//也可以返回有名对象//iterator it(_head->next);//return it;}iterator end(){return iterator(_head);}}

甚至，可以把 iterator() 也省略掉，原理是单参数的构造函数支持隐式类型转换：

template<class T>
class list
{typedef ListNode<T> Node;
public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}}

4.3 operator->的重载

list容器对 operator-> 进行了重载，它的重构代码是：

Ptr operator->()
{return &_node->_data;
}

在实际使用时，编译器为提高代码的可读性，还对其进行了优化：

list<A>::iterator it = lt.begin();
while (it != lt.end())
{//*it += 10;//cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;++it;
}

在 it->_a1 这段代码中，它的底层是 it.operator->()->_a1，按理它的调用应该是 it->->_a1，但编译器将第二个箭头拿掉，使得代码整体更好读。

4.4 完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace mylist
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_pPre(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}//ListIterator(const Self& l)//{};Ref& operator*(){return _pNode->_val;}Ptr operator->(){return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self temp(*this);_pNode = _pNode->_pPre;return temp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;};//list类template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i =0 ; i < n; i++){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();Iterator it = first;while (it != last){push_back(*it);++it;}}list(const list<T>& l){CreateHead();const_iterator it = l.begin();while (it != l.end()){push_back(*it);++it;}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;_size = 0;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _size == 0;}// List AccessT& front(){return *(_pHead->_pNext);}const T& front()const{return *(_pHead->_pNext);}T& back(){return *(_pHead->_pPre);}const T& back()const{return *(_pHead->_pPre);}// List Modifyvoid push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){Node* cur = pos._pNode;Node* newnode = new Node(val);newnode->_pNext = cur;newnode->_pPre = cur->_pPre;cur->_pPre->_pNext = newnode;cur->_pPre = newnode;_size++;return iterator(newnode);}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){Node* cur = pos._pNode;Node* prev = cur->_pPre;Node* next = cur->_pNext;prev->_pNext = next;next->_pPre = prev;delete cur;_size--;return iterator(next);}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node;_pHead->_val = 0;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}PNode _pHead;size_t _size=0;};
};