本篇是關(guān)于vector和list的模擬實現(xiàn)中，關(guān)于迭代器模塊的更進(jìn)一步理解，以及在前文的基礎(chǔ)上增加對于反向迭代器的實現(xiàn)和庫函數(shù)的對比等
本篇是寫于前面模擬實現(xiàn)的一段時間后，重新回頭看迭代器的實現(xiàn)，尤其是在模板角度對list中迭代器封裝的部分進(jìn)行解析，希望可以對迭代器的封裝實現(xiàn)有更深層次的理解，同時將與庫內(nèi)的實現(xiàn)做對比進(jìn)行優(yōu)化處理
list和vector的迭代器對比
list和vector的迭代器實現(xiàn)是不一樣的，在vector中的迭代器就是一個原生指針，因此在實現(xiàn)的時候也就是用的原生指針即可，但是對于list來說不能這樣，list的迭代器中例如++和--這樣的操作，是不能和vector中的原生指針一樣直接去實現(xiàn)的，而是需要用next或者是prior來模擬這個過程，還有例如*和->這樣的訪問數(shù)據(jù)的模式，因此在list的迭代器實現(xiàn)中是使用了封裝來進(jìn)行實現(xiàn)的
STL中有六大組件，其中迭代器算其中一個，那么也就意味著迭代器具有通用的功能，例如下面的代碼，在使用構(gòu)造函數(shù)時可以使用迭代器進(jìn)行構(gòu)造，而這個構(gòu)造的過程使用的迭代器對于各種容器來說都是通用的：
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
vector<int> v1{ 1,2,3,4,5,3,2,2 };
vector<int> v2(v1.begin(), v1.end());
list<int> l1(v1.begin(), v1.end());
return 0;
}
那么就意味著，在實現(xiàn)迭代器的過程中也是就可以根據(jù)迭代器來進(jìn)行不同容器間的構(gòu)造
list的實現(xiàn)過程
首先，在list的實現(xiàn)過程中要有下面幾個部分組成：list中包含的節(jié)點，list的迭代器訪問，list的節(jié)點之間的關(guān)系
那么首先就是list中節(jié)點的定義，用到了模板，現(xiàn)在再對該部分進(jìn)行解析，其實就是在創(chuàng)建的時候可以根據(jù)需要的內(nèi)容開辟出對應(yīng)的節(jié)點類型
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};
有了節(jié)點信息，就可以對list做一些基礎(chǔ)的操作，例如頭插頭刪，尾插尾刪等操作，但對于insert和erase這些操作還不能夠?qū)崿F(xiàn)，因此就要實現(xiàn)迭代器模塊的內(nèi)容
不管是對于vector還是list，迭代器的本質(zhì)就是用一個原生指針去進(jìn)行訪問等等，但是list和vector不同的是，list的存儲地址并不是連續(xù)的，因此在訪問的過程中就需要對迭代器進(jìn)行一定程度的封裝，例如在++或者--的操作符上可以進(jìn)行一些體現(xiàn)，因此list迭代器的實現(xiàn)是需要進(jìn)行單獨的封裝的
// 定義正向迭代器
template <class T, class Ref, class Ptr>
class __list_iterator
{
public:
typedef list_node<T> Node;
typedef __list_iterator<T, T&, T*> self;
__list_iterator(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(*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;
}
Node* _node;
};
上面的片段對list進(jìn)行了一些封裝，實現(xiàn)了它的一些基礎(chǔ)功能，從代碼中也能看出來，迭代器的本質(zhì)確確實實就是指針，用指針來進(jìn)行一系列的操作，對下面這幾個片段單獨進(jìn)行解析：
Ptr operator->()
{
return &_node->_data;
}
這是對于迭代器中解引用的運算符重載，這里使用的是&_node->_data的寫法，看似很怪，但是實際上這里的函數(shù)調(diào)用過程應(yīng)該是這樣
也就是說，這里對于->進(jìn)行運算符重載后，還需要進(jìn)行解引用，這個運算符重載函數(shù)返回的是一個指針，而這個指針還要繼續(xù)進(jìn)行解引用才能得到用戶想要得到的值，編譯器在這里進(jìn)行了特殊處理，兩個->使得可讀性下降，因此將兩個->進(jìn)行了一定程度的合并，只需要一個->就可以實現(xiàn)解引用的目的
其次是對模板的使用部分
template <class T, class Ref, class Ptr>
typedef list_node<T> Node;
typedef __list_iterator<T, T&, T*> self;
這里在最開始定義的時候，就定義了數(shù)據(jù)類型，引用和指針三種模板參數(shù)，借助這個參數(shù)就可以用模板將復(fù)雜的內(nèi)容實現(xiàn)簡單化，只需要一份代碼，模板就可以直接實例化出用戶在調(diào)用的時候需要的代碼，在進(jìn)行封裝const迭代器的時候，只需要提供的參數(shù)改為const版本就可以實現(xiàn)目的，很便捷
這樣就實現(xiàn)了正向迭代器的普通版本，而對于const迭代器的版本也只需要進(jìn)行不同的模板參數(shù)就可以實例化出const版本的迭代器
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
有了迭代器，在實現(xiàn)鏈表的各種函數(shù)功能就更加方便，例如可以實現(xiàn)erase和insert的操作，實現(xiàn)了這兩個函數(shù)，在進(jìn)行頭插頭刪，尾插尾刪的時候就更加方便，只需要進(jìn)行原地的調(diào)用即可
// Modifiers
void push_front(const T& val)
{
//Node* newnode = new Node;
//newnode->_data = val;
//newnode->_next = _head->_next;
//_head->_next->_prev = newnode;
//_head->_next = newnode;
//newnode->_prev = _head;
//_size++;
insert(begin(), val);
}
void pop_front()
{
//Node* delnode = _head->_next;
//_head->_next = _head->_next->_next;
//_head->_next->_prev = _head;
//delete delnode;
//delnode = nullptr;
//_size--;
erase(begin());
}
void push_back(const T& val)
{
//Node* newnode = new Node;
//newnode->_data = val;
//newnode->_prev = _head->_prev;
//_head->_prev->_next = newnode;
//newnode->_next = _head;
//_head->_prev = newnode;
//_size++;
insert(end(), val);
}
void pop_back()
{
//Node* delnode = _head->_prev;
//delnode->_prev->_next = _head;
//_head->_prev = delnode->_prev;
//delete delnode;
//delnode = nullptr;
//_size--;
erase(--end());
}
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
_size++;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
delete cur;
cur = nullptr;
_size--;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
那么上面是對前面已經(jīng)有過的內(nèi)容進(jìn)行的重新溫故，但是上面的代碼其實是沒有實現(xiàn)反向迭代器的，而在STL的庫中，反向迭代器的定義和正向迭代器其實并不相同，它是直接借助正向迭代器對反向迭代器進(jìn)行適配，有些類似于用vector，list或者deque對棧和隊列進(jìn)行的適配，也體現(xiàn)了封裝和代碼復(fù)用
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
ReverseIterator(Iterator it)
:_it(it)
{}
Self& operator++()
{
--_it;
return *this;
}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return _it.operator->();
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
private:
Iterator _it;
};
上面的代碼就是對于反向迭代器的封裝，從中可以看出反向迭代器是使用了正向迭代器的，并且在它的基礎(chǔ)上進(jìn)行的修改，因此這個反向迭代器是可以適配于vector也可以適配于list的文章來源：http://www.zghlxwxcb.cn/news/detail-726757.html
整體來說，對于反向迭代器就是用正向迭代器進(jìn)行適配出來的，體現(xiàn)了模板的好處文章來源地址http://www.zghlxwxcb.cn/news/detail-726757.html
完整代碼
#pragma once
namespace mylist
{
// 定義節(jié)點內(nèi)容
template <class T>
struct list_node
{
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
T _data;
list_node<T>* _next;
list_node<T>* _prev;
};
// 定義正向迭代器
template <class T, class Ref, class Ptr>
class __list_iterator
{
public:
typedef list_node<T> Node;
typedef __list_iterator<T, T&, T*> self;
__list_iterator(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(*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;
}
Node* _node;
};
// 定義反向迭代器
template<class Iterator, class Ref, class Ptr>
class reverse_iterator
{
typedef reverse_iterator<Iterator, Ref, Ptr> self;
public:
reverse_iterator(Iterator it)
:_it(it)
{}
self& operator++()
{
_it--;
return *this;
}
self& operator++(int)
{
self tmp(*this);
_it--;
return tmp;
}
self& operator--()
{
_it++;
return *this;
}
self& operator--(int)
{
self tmp(*this);
_it++;
return tmp;
}
Ref operator*()
{
Iterator cur = _it;
return *(--cur);
}
Ptr operator->()
{
return &(operator*());
}
bool operator !=(const self& s)
{
return _it != s._it;
}
bool operator ==(const self& s)
{
return _it == s._it;
}
Iterator _it;
};
// 定義鏈表
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;
typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
//typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
// Constructor
list()
{
empty_init();
}
list(const list<T>& lt)
{
for (auto x : lt)
{
push_back(x);
}
}
list(iterator begin, iterator end)
{
empty_init();
while (begin != end)
{
push_back(begin._node->_data);
begin++;
}
}
//list(reverse_iterator rbegin, reverse_iterator rend)
//{
// empty_init();
// while (rbegin != rend)
// {
// push_back(rbegin._node->_data);
// rbegin++;
// }
//}
// Destructor
~list()
{
clear();
delete _head;
_head = nullptr;
}
// Operator=
list<T>& operator=(const list<T>& lt)
{
swap(lt);
return *this;
}
// Iterators
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);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//const_reverse_iterator rbegin() const
//{
// return const_reverse_iterator(end());
//}
//const_reverse_iterator rend() const
//{
// return const_reverse_iterator(begin());
//}
// Capacity
bool empty()
{
return _size == 0;
}
size_t size()
{
return _size;
}
// Element access
T& front()
{
return begin()._node->_data;
}
T& back()
{
return (--end())._node->_data;
}
// Modifiers
void push_front(const T& val)
{
//Node* newnode = new Node;
//newnode->_data = val;
//newnode->_next = _head->_next;
//_head->_next->_prev = newnode;
//_head->_next = newnode;
//newnode->_prev = _head;
//_size++;
insert(begin(), val);
}
void pop_front()
{
//Node* delnode = _head->_next;
//_head->_next = _head->_next->_next;
//_head->_next->_prev = _head;
//delete delnode;
//delnode = nullptr;
//_size--;
erase(begin());
}
void push_back(const T& val)
{
//Node* newnode = new Node;
//newnode->_data = val;
//newnode->_prev = _head->_prev;
//_head->_prev->_next = newnode;
//newnode->_next = _head;
//_head->_prev = newnode;
//_size++;
insert(end(), val);
}
void pop_back()
{
//Node* delnode = _head->_prev;
//delnode->_prev->_next = _head;
//_head->_prev = delnode->_prev;
//delete delnode;
//delnode = nullptr;
//_size--;
erase(--end());
}
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
_size++;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
delete cur;
cur = nullptr;
_size--;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
void swap(const list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
void clear()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* next = cur->_next;
delete(cur);
cur = next;
}
_head->_next = _head;
_head->_prev = _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_head->_data = T();
_size = 0;
}
void Print()
{
Node* cur = _head->_next;
while (cur != _head)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "null" << endl;
}
private:
Node* _head;
size_t _size;
};
void test_iterator()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
cout << "iterator constructor:";
list<int> lt1(lt.begin(), lt.end());
lt1.Print();
cout << "front():" << lt.front() << endl;
cout << "back():" << lt.back() << endl;
mylist::__list_iterator<int, int&, int*> it = lt.begin();
while (it != lt.end())
{
std::cout << *it << " ";
it++;
}
cout << endl;
}
void test_clear()
{
list<int> lt1;
cout << "push_back:" << endl;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.Print();
lt1.clear();
lt1.push_back(5);
lt1.push_back(6);
lt1.push_back(7);
lt1.push_back(8);
lt1.Print();
}
void test_push_pop()
{
list<int> lt1;
cout << "push_back:" << endl;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.Print();
cout << "pop_back:" << endl;
lt1.pop_back();
lt1.Print();
list<int> lt2;
cout << "push_front:" << endl;
lt2.push_front(1);
lt2.push_front(2);
lt2.push_front(3);
lt2.push_front(4);
lt2.Print();
cout << "pop_front:" << endl;
lt2.pop_front();
lt2.Print();
}
void test_reverse_iterator()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
cout << "iterator constructor:";
//list<int> lt1(lt.rbegin(), lt.rend());
//lt1.Print();
cout << "front():" << lt.front() << endl;
cout << "back():" << lt.back() << endl;
mylist::list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
std::cout << *rit << " ";
rit++;
}
cout << endl;
}
void test()
{
test_reverse_iterator();
//test_push_pop();
//test_clear();
}
}
到了這里，關(guān)于C++：關(guān)于模擬實現(xiàn)vector和list中迭代器模塊的理解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
