c++之List容器的模拟实现
注：最终代码以汇总的为准
1.前言
在之前的数据结构中，我们曾模拟实现过链表的数据结构，但是十分麻烦，全篇都暴露了链表的底层结构-----指针，但是从使用的角度，使用者并不关心你用的底层结构是啥，而且编写者也不愿意将所有的底层结构暴露出来，为此，在此文章中，我们将充分发挥c++的优势，将指针包装一下，变为迭代器
2.基本框架的实现
基本结构包括链表的创建，包括链表结点的创建，结点的初始化，以及对底层结构----指针的封装,还有一些基本操作，例如++，==，！=，还有解引用操作等。
我们将造链表的文件放在List.h文件中，等下在test.cpp文件中进行测试。
如下代码是基本的结构代码：（具体功能没实现）
#include <assert.h>
namespace rens
{
template<class T>
struct list_node //定义结点结构
{
list_node* <T> _next;
list_node* <T> _prev;
T _data;
list_node(const T& x=T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
}
template <class T>
struct list_iterator
{
typedef list_node<T> Node;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*() //模拟指针的解引用
{
return _node->_data; //返回的是数据，类型为T
}
T* operator->() //解引用的->,这个较为特殊
{
return &_node->_data;
}
list_iterator<T>& operator++()
{
_node = _node->_next;
return *this; //++操作返回的是下一个结点
}
bool operator!=(const list_iterator<T>& it)
{
return this->_node != it._node;
}
bool operator==(const list_node<T>& it)
{
return this->_node == it._node;
}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
private:
Node* _head;
size_t _size;
};但是，上述代码如果要是想遍历const对象是，由于我们的迭代器不是const迭代器，不能满足我们的需求，为此我们还要将上述代码cv一份，并改为const迭代器。
const迭代器代码如下：
template <class T>
struct const_list_iterator
{
typedef list_node<T> Node;
Node* _node;
const_list_iterator(Node* node)
:_node(node)
{}
const T& operator*() //模拟指针的解引用
{
return _node->_data; //返回的是数据，类型为T
}
const T* operator->() //解引用的->,这个较为特殊
{
return &_node->_data;
}
const_list_iterator<T>& operator++()
{
_node = _node->_next;
return *this; //++操作返回的是下一个结点
}
bool operator!=(const const_list_iterator<T>& it)
{
return this->_node != it._node;
}
bool operator==(const const_list_iterator<T>& it)
{
return this->_node == it._node;
}
};但是，通过对比（对比图如下），我们发现这两段代码重复度太大了，仅仅是返回类型的区别，这样写未免太浪费，所以我们将其改造一下！
改造想法：既然我们的类型就是有无const的区别，那我们不妨利用模板，对其进行改造，添加一个Ref,即reference,引用&以及Ptr,即pointer,指针
为了方便改造，我们将原来的list_iterator<T>给typedef一下，省的总改！
改造代码：
template <class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*() //模拟指针的解引用
{
return _node->_data; //返回的是数据，类型为T
}
Ptr operator->() //解引用的->,这个较为特殊
{
return &_node->_data;
}
self& operator++() //前置++,返回的是引用， this指向的对象不销毁。
{
_node = _node->_next;
return *this; //++操作返回的是下一个对象
}
self operator++(int) //后置++,返回的是一个临时对象，tmp出函数就销毁了
{
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 this->_node != it._node;
}
bool operator==(const self& it)
{
return this->_node == it._node;
}
};其余功能的实现：
template <class T>
class list
{
typedef list_node<T> Node;
public:
//typedef list_iterator<T> iterator;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
iterator it(_head->_next); //我们的链表是双向循环链表，_head可以理解为哨兵结点
return it;
}
iterator end()
{
return iterator(_head);
}
const_iterator begin()const //加上const关键字表示该函数不会修改类的任何成员变量，即它是一个常量成员函数
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(std::initializer_list<T> lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//lt2(lt1)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//lt1=lt3
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
size_t size()const
{
return _size;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* nextnode = cur->_next;
Node* prevnode = cur->_prev;
prevnode->_next = nextnode;
nextnode->_prev = prevnode;
delete cur;
--_size;
return iterator(nextnode);
}
private:
Node* _head;
size_t _size;
};
}3.代码的汇总及实现
这是List.h文件
#include <assert.h>
#include <initializer_list>
#include<iostream>
#include<algorithm>
namespace rens
{
template<class T>
struct list_node //定义结点结构
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
template <class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*() //模拟指针的解引用
{
return _node->_data; //返回的是数据，类型为T
}
Ptr operator->() //解引用的->,这个较为特殊
{
return &_node->_data;
}
self& operator++() //前置++,返回的是引用， this指向的对象不销毁。
{
_node = _node->_next;
return *this; //++操作返回的是下一个对象
}
self operator++(int) //后置++,返回的是一个临时对象，tmp出函数就销毁了
{
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 this->_node != it._node;
}
bool operator==(const self& it)
{
return this->_node == it._node;
}
};
//template <class T>
//struct list_iterator
//{
// typedef list_node<T> Node;
// Node* _node;
// list_iterator(Node* node)
// :_node(node)
// {}
//
// T& operator*() //模拟指针的解引用
// {
// return _node->_data; //返回的是数据，类型为T
// }
//
// T* operator->() //解引用的->,这个较为特殊
// {
// return &_node->_data;
// }
//
// list_iterator<T>& operator++()
// {
// _node = _node->_next;
// return *this; //++操作返回的是下一个结点
// }
//
// bool operator!=(const list_iterator<T>& it)
// {
// return this->_node != it._node;
// }
//
// bool operator==(const list_node<T>& it)
// {
// return this->_node == it._node;
// }
//};
//template <class T>
//struct const_list_iterator
//{
// typedef list_node<T> Node;
// Node* _node;
// const_list_iterator(Node* node)
// :_node(node)
// {}
//
// const T& operator*() //模拟指针的解引用
// {
// return _node->_data; //返回的是数据，类型为T
// }
//
// const T* operator->() //解引用的->,这个较为特殊
// {
// return &_node->_data;
// }
//
// const_list_iterator<T>& operator++()
// {
// _node = _node->_next;
// return *this; //++操作返回的是下一个结点
// }
//
// bool operator!=(const const_list_iterator<T>& it)
// {
// return this->_node != it._node;
// }
//
// bool operator==(const const_list_iterator<T>& it)
// {
// return this->_node == it._node;
// }
//};
template <class T>
class list
{
typedef list_node<T> Node;
public:
//typedef list_iterator<T> iterator;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
iterator it(_head->_next); //我们的链表是双向循环链表，_head可以理解为哨兵结点
return it;
}
iterator end()
{
return iterator(_head);
}
const_iterator begin()const //加上const关键字表示该函数不会修改类的任何成员变量，即它是一个常量成员函数
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(std::initializer_list<T> lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//lt2(lt1)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//lt1=lt3
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
size_t size()const
{
return _size;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* nextnode = cur->_next;
Node* prevnode = cur->_prev;
prevnode->_next = nextnode;
nextnode->_prev = prevnode;
delete cur;
--_size;
return iterator(nextnode);
}
private:
Node* _head;
size_t _size;
};
}这是test.cpp文件
#include"list.h"
using namespace std;
void test1()
{
rens::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
rens::list<int>::iterator it1 = lt1.begin();
while (it1 != lt1.end())
{
*it1 += 1;
cout << *it1 << " ";
++it1;
}
cout << endl;
}
void print(const rens::list<int>& lt)
{
// const迭代器本身可以修改，指向内容不能修改
rens::list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
struct A
{
A(int a1=1,int a2=1)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test2()
{
rens::list<A> lt2;
lt2.push_back({ 1,1 });
lt2.push_back({ 2,2 });
lt2.push_back({ 3,3 });
lt2.push_back({ 4,4 });
rens::list<A>::iterator it = lt2.begin();
while (it != lt2.end())
{
cout << it->_a1 << "," << it->_a2 << endl;
++it;
}
cout << endl;
rens::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
print(lt1);
}
void test3()
{
rens::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.push_front(5);
lt1.push_front(6);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.pop_back();
lt1.pop_back();
lt1.pop_front();
lt1.pop_front();
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.pop_back();
lt1.pop_back();
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
void test4()
{
rens::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
rens::list<int> lt2(lt1);
lt1.clear();
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
rens::list<int> lt3 = { 10,20,30,40 };
lt1 = lt3;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
//test1();
//test2();
//test3();
test4();
return 0;
}