list的结构不像vector和string
vector和string其储存数据的空间是连续的，list储存数据的空间是随机的。
vector和string的迭代器本质上是指针，其可以支持++ – *等操作。
为了让list也可以支持类似指针的行为，所以对list的迭代器进行了封装
先看string的迭代器：
string的迭代器本质上是字符指针，const迭代器同理为const指针
要注意在string构造函数时要多开辟一个空间存放’ \0’
#include<iostream>
using namespace std;
namespace My
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
return _src;
}
iterator end()
{
return _src + size;
}
const_iterator begin()const
{
return _src;
}
const_iterator end()const
{
return _src + size;
}
string(const char*src="")
:_src(new char[strlen(src)+1])
{//多开辟一个空间存放'\0'
strcpy(_src, src);
size = strlen(_src);
capacity = size;
}
~string()
{
delete[]_src;
_src = nullptr;
size = 0;
capacity = 0;
}
private:
char*_src;//指向字符串
int size;//字符串的大小
int capacity;//字符串的容量
};
}
在利用迭代器遍历string
int main()
{
My::string s1 = "abcde";
My::string::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : s1)
{
cout << e << " ";
}
}
vector的迭代器
#include<iostream>
using namespace std;
namespace My
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;//const迭代器
vector()
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
~vector()
{
if (_start != nullptr)
{
delete[]_start;
}
_start = _finish = _endofstorage = 0;
}
//迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
void reserve(int n)
{
if (n > capcity())
{
T* tmp = new T[n];
int sz = size();
if (_start)//原数据不是空,需要拷贝数据
{
memcpy(tmp, _start,sz*sizeof(T));//这里不考虑自定义类型。
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
int capcity()
{
return _endofstorage - _start;
}
int size()
{
return _finish - _start;
}
void push_back(const T&e)
{
if (_finish == _endofstorage)
{
int newcapcity = capcity() == 0 ? 5 : 2 * capcity();
reserve(newcapcity);//增容
}
*_finish = e;
_finish++;
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
//vector的大小为_finish-_start;
//vector的容量为_endofstorage-_start
};
}
int main()
{
My::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
My::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v1)
{
cout << e << " ";
}
}
list的迭代器因为其储存方式不连续需要对迭代器进行封装
首先list结构的基本形式为
#include<iostream>
using namespace std;
namespace My
{
template<class T>
struct _List_Node//链表节点
{
T _val;
struct _List_Node*_next;
struct _List_Node*_prev;
_List_Node(const T&val = T())
:_val(val), _next(nullptr), _prev(nullptr)
{}
};
template <class T>
class list
{
public:
typedef _List_Node<T> node;
list()//构造函数
{
_head = new node;//调用模板函数的默认构造函数
_head->_next = _head;//双向带头链表
_head->_prev = _head;
}
private:
node*_head;
};
}
在此基础上，我们定义迭代器类：
有两种情况，一种为普通迭代器，另一种为const修饰的迭代器，我们这里使用模板来实例化两个迭代器
template<class T,class Ref>
struct List_iterator//迭代器类
{
};
template <class T>
class list
{
public:
typedef _List_Node<T> node;
typedef List_iterator<T, T&> iterator;
typedef List_iterator<T, const T&> const_iterator;
list()//构造函数
{
_head = new node;//调用模板函数的默认构造函数
_head->_next = _head;//双向带头链表
_head->_prev = _head;
}
private:
node*_head;
};
list迭代器++相当于走向list的下一个节点， *是指通过节点指针来访问该节点的值等等
#include<iostream>
using namespace std;
namespace My
{
template<class T>
struct _List_Node//链表节点
{
T _val;
struct _List_Node*_next;
struct _List_Node*_prev;
_List_Node(const T&val = T())
:_val(val), _next(nullptr), _prev(nullptr)
{}
};
template<class T,class Ref>
struct List_iterator//迭代器类
{
typedef _List_Node<T> node;
typedef List_iterator<T, Ref> Self;
node* _pnode;
List_iterator(node*pnode)
:_pnode(pnode)
{}
Ref& operator * ()//const对象Ref为const &，非const对象返回&
{
return _pnode->_val;
}
bool operator !=(const Self&s)const //不修改
{
return _pnode != s._pnode;//判断两个节点的地址是否相同
}
Self& operator ++()//前置++
{
_pnode = _pnode->_next;
return *this;
}
Self operator++(int)//后置++
{
Self tmp = *this;//构造函数
_pnode = _pnode->_next;
return tmp;
}
Self& operator --()//前置--
{
_pnode = _pnode->_prev;
return *this;
}
Self operator --(int)//后置--
{
Self tmp = *this;
_pnode = _pnode->_prev;
return tmp;
}
};
template <class T>
class list
{
public:
typedef _List_Node<T> node;
typedef List_iterator<T, T&> iterator;
typedef List_iterator<T, const T&> const_iterator;
list()//构造函数
{
_head = new node;//调用模板函数的默认构造函数
_head->_next = _head;//双向带头链表
_head->_prev = _head;
}
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);
}
void push_back(const T&x)
{
node* NewNode = new node(x);
node*tail = _head->_prev;
tail->_next = NewNode;
_head->_prev = NewNode;
NewNode->_prev = tail;
NewNode->_next = _head;
}
private:
node*_head;
};
}
const迭代器Ref为const T&这样通过模板，相当于构造了两个迭代器。
int main()
{
My::list<int>v1;
v1.push_back(1);
v1.push_back(2);
My::list<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v1)
{
cout << e << " ";
}
return 0;
}
