個人主頁：仍有未知等待探索-CSDN博客

專題分欄：C++

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 歡迎來指教！

目錄

一、標準庫中的list

1、了解

2、常用接口說明

a.常見的構造函數

?b.迭代器

c. Capacity?編輯

d.Element access

e.Modifiers

二、實現

1、框架?

a.節點

b.迭代器

c.鏈表

2、節點

3、迭代器?

?4、鏈表

三、反向迭代器

四、問題

1、迭代器中的箭頭操作符為什么返回的是地址？

---

一、標準庫中的list

1、了解

list：是一個雙向帶頭循環鏈表，不支持隨機訪問（即下標訪問），任意位置的插入刪除效率高。

2、常用接口說明

a.常見的構造函數

list的構造函數

構造函數	接口說明
list(size_t n, const T& val = t())	構造n個值為val的list
list()	構造空的list
list(const list& x)	拷貝構造
list(iterator first, iterator second)	用[first， second)構造list

?b.迭代器

迭代器可以看作是一個指向節點的指針。

（rbegin和rend是反向迭代器，rbegin是指向了鏈表的尾部，rend是指向了鏈表的頭部）

注意：

?begin，進行++操作是往后面走。

rbegin，進行++操作是往前面走。

c. Capacity

d.Element access

e.Modifiers

二、實現

?老規矩，我們還是先對結構進行分析。?

鏈表：除了一些對鏈表的基本操作之外，還需要有迭代器和節點。

1、框架?

#include <cstring>
#include <iostream>
using namespace std;// 開辟一個自己的命名空間
namespace my
{// 鏈表節點// 迭代器// 鏈表
}

a.節點

// 鏈表節點
template<class T>
struct ListNode
{ListNode<T>* _prev;ListNode<T>* _next;T val;// 缺省參數，如果沒有傳參的話，默認是T類型的無參構造// 這樣做是為了防止T是一個自定義類型ListNode(const T& e = T()):_prev(nullptr),_next(nullptr),val(e){}
};

b.迭代器

其實這樣的迭代器是不完整的，我們在后面會對其進行擴展。

template<class T>
struct NodeIterator
{// 對于節點和迭代器的重命名，方便書寫typedef ListNode<T> Node;// 節點	typedef NodeIterator<T> Self; // 迭代器Node* _node;// 迭代器是用節點的指針來進行構造的NodeIterator(Node* node):_node(node){}
};

c.鏈表

// 鏈表
// list是一個帶頭雙向循環鏈表
template<class T>
class list
{typedef ListNode<T> Node;// 節點
public:typedef NodeIterator<T, T&, T*> iterator;// 迭代器
private:Node* _head;// 鏈表的頭部size_t _size;// 鏈表的長度
};

2、節點

其實節點這部分沒有什么可以講解的。唯一一個要理解的就是這個（const T& e = T()）。

//const T& e = T()
// 首先T()是一個匿名對象的寫法
// 為什么我們需要用到一個匿名對象，而不是一個const T& e = 值？
// 1、我們不知道T是什么類型，不知道值可以設成一個什么類型的值
// 2、如果我們設置成一個內置類型，而T是一個自定義類型的話，類型不匹配
ListNode(const T& e = T()):_prev(nullptr),_next(nullptr),val(e){}

3、迭代器?

?我之前框架里所寫的就是老版本的迭代器。

新版本里面的迭代器主要添加了兩個新的模板變量（Ref，Ptr），引入的這兩個變量是對解引用和引用的重寫。

思考題：怎么寫const版本的迭代器呢？

答：新版本寫法的迭代器可以直接這么寫（以int為例）：

NodeIterator<int, const int&, const int*>

思考題：反向迭代器怎么實現的？

標準庫里面的begin()和end() 與 rbegin()和rend()采用的是對稱法。

// 迭代器
// 新版本
// 鏈表迭代器：模仿指針的行為
// Ref:引用，Ptr指針
template<class T, class Ref, class Ptr>
struct NodeIterator
{typedef ListNode<T> Node;// 節點	typedef NodeIterator<T, Ref, Ptr> Self; // 迭代器Node* _node;NodeIterator(Node* node):_node(node){}// 前置++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(_node);_node = _node->_prev;return tmp;}// 解引用Ref operator*(){return _node->val;}// -> Ptr operator->(){return &_node->val;}// ==bool operator==(const Self& s){return _node == s._node;}// !=bool operator!=(const Self& s){return !(*this == s); }
};老版本：缺點：無法實現const的迭代器鏈表迭代器：模仿指針的行為
//template<class T>
//struct NodeIterator
//{
//	typedef ListNode<T> Node;// 節點
//	typedef NodeIterator<T> Self; // 迭代器
//
//	Node* _node;
//
//	NodeIterator(Node* node)
//		:_node(node)
//	{}
//	// 前置++
//	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(_node);
//		_node = _node->_prev;
//		return tmp;
//	}
//	// 解引用
//	T& operator*()
//	{
//		return _node->val;
//	}
//	// ==
//	bool operator==(const Self& s)
//	{
//		return _node == s._node;
//	}
//	// !=
//	bool operator!=(const Self& s)
//	{
//		return !(*this == s); 
//	}
//
//	// -> 
//	T* operator->()
//	{
//		return &_node->val;
//	}
//};

// 反向迭代器
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp(_it);return *( -- tmp);}Ptr operator->(){//return &_it.operator->();return &(_it.operator*());}Self& operator++(){_it -- ;return *this;}Self& operator--(){_it ++;return *this;}bool operator!=(const Self& s){return _it != s._it;}
};

?4、鏈表

// 鏈表
template<class T>
class list
{typedef ListNode<T> Node;
public:typedef NodeIterator<T, T&, T*> iterator;typedef NodeIterator<T, const T&, const T*> const_iterator;// 構造函數list ():_size(0){_head = new Node;_head -> _next = _head;_head -> _prev = _head;}list (size_t n, const T& val = T()):_size(0){_head = new Node;_head -> _next = _head;_head -> _prev = _head;for (size_t i = 0; i < n; i ++ ){push_back(val);}}list (list<T>& x):_size(0){_head = new Node;_head -> _next = _head;_head -> _prev = _head;iterator it = x.begin();while (it != x.end()){push_back(*it);it ++ ;}}list (iterator first, iterator last):_size(0){_head = new Node;_head -> _next = _head;_head -> _prev = _head;iterator it = first;while (it != last){insert(end(), *it);it ++ ;}}~list(){clear();delete _head;_head = nullptr;}// 訪問// const版本的迭代器，迭代器的指向的內容不能被修改// 1、自己單獨實現一個const版本的迭代器// 2、將const和非const合成一個，通過模板參數進行控制const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}// list capacitybool empty(){return _size == 0;}size_t size(){return _size;}// list element accessT& front(){return *begin();}T& back(){return *end();}// list modifiers/*void push_back(const T& val){Node* tmp = new Node;tmp -> val = val;Node* tail = _head -> _prev;tmp->_next = tail->_next;tail->_next = tmp;tmp->_prev = tail;_head->_prev = tmp;_size ++ ;}*/void push_back(const T& val){insert(end(), val);}void push_front(const T& val){insert(begin(), val);}iterator insert (iterator position, const T& val){Node* tmp = new Node(val);tmp->_next = position._node;tmp->_prev = position._node->_prev;position._node->_prev->_next = tmp;position._node->_prev = tmp;_size ++ ;return iterator(tmp);}void pop_back(){erase( -- end());}void pop_front(){erase(begin());}iterator erase (iterator position){iterator tmp(position._node->_next);position._node->_prev->_next = position._node->_next;position._node->_next->_prev = position._node->_prev;delete position._node;_size -- ;return tmp;}void clear(){while (_size){erase(begin());}}void swap(list& l){std::swap(_head, l._head);std::swap(_size, l._size);}private:Node* _head;size_t _size;
};

三、反向迭代器

通過前面例子知道，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的實現可以借助正向迭代器，即：反向迭代器內部可以包含一個正向迭代器，對正向迭代器的接口進行包裝即可。

四、問題

1、迭代器中的箭頭操作符為什么返回的是地址？

?答：其實是編譯器省略了一個箭頭，例如：Iterator it；

正常的調用是：it.operator->()->val; 省略了一個箭頭是為了提高代碼的可讀性。