文章索引

前言模拟实现list1. ListNode节点类2. list的迭代器封装3. 反向迭代器4. list类的模拟实现测试代码

list的反向迭代器总结

前言

通过模拟实现可以让我们更加深刻的理解C++底层STL的实现逻辑, 本篇就对list的底层进行模拟实现.

博客主页: 酷酷学!!! 点击关注 共同进步!!!

正文开始

模拟实现list

要模拟实现list, 必须要熟悉list的底层结构以及其接口的含义, 通过上一篇的学习, 这些内容基本掌握之后, 现在我们来模拟实现list.

1. ListNode节点类

<code>#pragma once

#include<iostream>

using namespace std;

#include<assert.h>

namespace my

{ -- -->

//list的节点类

template<class T>

struct ListNode

{

ListNode(const T& val = T())

: _prev(nullptr)

, _next(nullptr)

, _val(val)

{ }

ListNode<T>* _prev;

ListNode<T>* _next;

T _val;

};

2. list的迭代器封装

list的迭代器

迭代器有两种实现方式, 具体应根据容器底层数据结构的实现:

1.原生态指针, 比如:vector

2.将原生态指针进行封装, 因迭代器使用形式与指针完全相同,

因此在自定义的类中必须实现以下方法:

1.指针可以解引用,迭代器的类中必须重载operator*()

2.指针可以通过->访问其所指空间成员,迭代器类中必须重载operator->()

3.指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)

至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,

双向链表可以向前或者向后移动,所以需要重载,如果是forward_list就不需要重载--

4.迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

template<class T,class Ref,class Ptr>

class ListIterator

{

typedef ListNode<T> Node;

typedef ListIterator<T, Ref, Ptr> Self;

//Ref 和 Ptr类型需要重新定义下,实现反向迭代器时需要用到

public:

typedef Ref Ref;

typedef Ptr Ptr;

//构造

ListIterator(Node* node = nullptr)

: _node(node)

{ }

//具有指针类似行为

Ref operator*()

{

return _node->_val;

}

Ptr operator->()

{

return &(operator*());

}

//迭代器支持移动

Self& operator++()

{

_node = _node->_next;

return *this;

}

Self operator++(int)

{

Self temp(*this);

_node = _node->_next;

return temp;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

Self operator--(int)

{

Self temp(*this);

_node = _node->_prev;

return temp;

}

//迭代器支持比较

bool operator!=(const Self& l) const

{

return _node != l._node;

}

bool operator==(const Self & l) const

{

return _node == l._node;

}

Node* _node;

};

3. 反向迭代器

//反向迭代器,迭代器复用

template<class Iterator>

class ReverseListIterator

{

//注意:此处typename的作用是明确的告诉编译器,Ref是Iterator类中的一个类型,

//而不是静态成员变量,否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员

//变量,因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的

public:

typedef typename Iterator::Ref Ref;

typedef typename Iterator::Ptr Ptr;

typedef ReverseListIterator<Iterator> Self;

//构造

ReverseListIterator(Iterator it)

: _it(it)

{ }

//具有指针类似行为

Ref operator*()

{

Iterator temp(_it);

--temp;

return *temp;

}

Ptr operator->()

{

return &(operator*());

}

//迭代器支持移动

Self& operator++()

{

--_it;

return *this;

}

Self& operator++(int)

{

Self temp(*this);

--_it;

return *this;

}

Self& operator--()

{

++_it;

return *this;

}

Self& operator--(int)

{

Self temp(*this);

++_it;

return temp;

}

//迭代器支持比较

bool operator!=(const Self& l) const

{

return _it != l._it;

}

bool operator==(const Self& l) const

{

return _it == l._it;

}

Iterator _it;

};

4. list类的模拟实现

template<class T>

class list

{

typedef ListNode<T> Node;

public:

//正向迭代器

typedef ListIterator<T, T&, T*> iterator;

typedef ListIterator<T, const T&, T*> const_iterator;

//反向迭代器

typedef ReverseListIterator<iterator> reverse_iterator;

typedef ReverseListIterator<const_iterator> const_reverse_iterator;

//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();

while (first != last)

{

push_back(*first);

++first;

}

}

list(const list<T>& l)

{

CreateHead();

//用l中的元素构造临时的temp,然后与当前对象交换

list<T> temp(l.begin(), l.end());

this->swap(temp);

}

list<T>& operator=(list<T> l)

{

this->swap(l);

return *this;

}

~list()

{

clear();

delete _head;

_head = nullptr;

}

//list的迭代器

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());

}

//List的容器相关

size_t size() const

{

Node* cur = _head->_next;

size_t count = 0;

while (cur != _head)

{

++count;

cur = cur->_next;

}

return count;

}

bool empty() const

{

return _head->_next = _head;

}

void resize(size_t newsize, const T* data = T())

{

size_t oldsize = size();

if (newsize <= oldsize)

{

//将有效元素减少到newsize

while (newsize < oldsize)

{

pop_back();

--oldsize;

}

}

else

{

while (oldsize < newsize)

{

push_back(data);

++oldsize;

}

}

}

//list的元素访问操作

//注意:List不支持operator[]

T& front()

{

return _head->_next->_val;

}

const T& front() const

{

return _head->_next->_val;

}

T& back()

{

return _head->_prev->_val;

}

const T& back() const

{

return _head->_prev->_val;

}

//list的插入和删除

void 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* pNewNode = new Node(val);

Node* pCur = pos._node;

//先将新节点插入

pNewNode->_prev = pCur->_prev;

pNewNode->_next = pCur;

pNewNode->_prev->_next = pNewNode;

pCur->_prev = pNewNode;

return iterator(pNewNode);

}

//删除pos位置的节点,返回该节点的下一个位置

iterator erase(iterator pos)

{

//找到待删除的节点

Node* pDel = pos._node;

Node* pRet = pDel->_next;

//将该节点从链表中拆下来并删除

pDel->_prev->_next = pDel->_next;

pDel->_next->_prev = pDel->_prev;

delete pDel;

return iterator(pRet);

}

void clear()

{

Node* cur = _head->_next;

//采用头删除删除

while (cur != _head)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_head->_next = _head->_prev = _head;

}

void swap(my::list<T>& l)

{

std::swap(_head, l._head);

}

private:

void CreateHead()

{

_head = new Node;

_head->_prev = _head;

_head->_next = _head;

}

Node* _head;

};

}

测试代码

对构造函数进行测试

//对模拟实现的list进行测试

//正向打印链表

template<class T>

void PrintList(const my::list<T>& l)

{

auto it = l.begin();

while (it != l.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

//测试list的构造

void Testmylist1()

{

my::list<int> l1;

my::list<int> l2(10, 5);

PrintList(l2);

int array[] = { 1,2,3,4,5,6,7,8,9,0 };

my::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));

PrintList(l3);

my::list<int> l4(l3);

PrintList(l4);

l1 = l4;

PrintList(l1);

}

对头/尾插入删除进行测试

<code>//PushBack()/PopBack()/PushFront()/PopFront()

void Testmylist2()

{ -- -->

//测试pushBack和PopBack

my::list<int> l;

l.push_back(1);

l.push_back(2);

l.push_back(3);

PrintList(l);

l.pop_back();

l.pop_back();

PrintList(l);

l.pop_back();

cout << l.size() << endl;

//测试pushFront与popFront

l.push_front(1);

l.push_front(2);

l.push_front(3);

PrintList(l);

l.pop_front();

l.pop_front();

PrintList(l);

l.pop_front();

cout << l.size() << endl;

}

测试指定位置插入删除

<code>//测试insert和erase

void Testmylist3()

{ -- -->

int array[] = { 1,2,3,4,5 };

my::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

auto pos = l.begin();

l.insert(l.begin(), 0);

PrintList(l);

++pos;

l.insert(pos, 2);

PrintList(l);

l.erase(l.begin());

l.erase(pos);

PrintList(l);

//pos指向的节点已经被删除,pos迭代器失效

cout << *pos << endl;

auto it = l.begin();

while (it != l.end())

{

it = l.erase(it);

}

cout << l.size() << endl;

}

测试反向迭代器

<code>//测试反向迭代器

void Testmylist4()

{ -- -->

int array[] = { 1,2,3,4,5 };

my::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

auto rit = l.rbegin();

while (rit != l.rend())

{

cout << *rit << " ";

++rit;

}

cout << endl;

const my::list<int> cl(l);

auto crit = l.rbegin();

while (crit != l.rend())

{

cout << *crit <<" ";

++crit;

}

cout << endl;

}

list的反向迭代器

我们知道, 反向迭代器的++就是正向迭代器的- -, 反向迭代器的- -就是正向迭代器的++, 因此反向迭代器的实现可以借助正向迭代器, 即: 返现迭代器内部可以包含一个正向迭代器, 对正向迭代器的接口进行包装即可.

<code>//反向迭代器,迭代器复用

template<class Iterator>

class ReverseListIterator

{ -- -->

//注意:此处typename的作用是明确的告诉编译器,Ref是Iterator类中的一个类型,

//而不是静态成员变量,否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员

//变量,因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的

public:

typedef typename Iterator::Ref Ref;

typedef typename Iterator::Ptr Ptr;

typedef ReverseListIterator<Iterator> Self;

//构造

ReverseListIterator(Iterator it)

: _it(it)

{ }

//具有指针类似行为

Ref operator*()

{

Iterator temp(_it);

--temp;

return *temp;

}

Ptr operator->()

{

return &(operator*());

}

//迭代器支持移动

Self& operator++()

{

--_it;

return *this;

}

Self& operator++(int)

{

Self temp(*this);

--_it;

return *this;

}

Self& operator--()

{

++_it;

return *this;

}

Self& operator--(int)

{

Self temp(*this);

++_it;

return temp;

}

//迭代器支持比较

bool operator!=(const Self& l) const

{

return _it != l._it;

}

bool operator==(const Self& l) const

{

return _it == l._it;

}

Iterator _it;

};

完

总结

通过以上的实现，可以模拟出一个类似于list的数据结构，并且可以对其中的元素进行添加、删除、查找、等操作。这样就可以在不使用C++内置的list时，使用自己实现的List类来进行相同的操作。

感谢您的点赞与收藏!!!