list
四、模拟实现
1、list.h
#pragma once
#include <iostream>
namespace little_monster
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};
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* n)
:_node(n)
{}
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
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;
}
};
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;
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 Init_empty()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
Init_empty();
}
list(const list<T>& lt)
{
Init_empty();
for (auto e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<int>& operator=(list<int> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
_size = 0;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
--_size;
return iterator(next);
}
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size;
};
}
（1）关于整个list的搭建
①节点
节点是一个struct封装的类，由数据、指向前一个位置的指针、指向后一个位置的指针、构造函数共同构成，创建的是一个独立的节点，初始化指针都为空
②迭代器
迭代器是一个struct封装的类，由构造函数、自增自减、解引用、判断相等接口构成，其中Ptr接受指针，Ref接受引用
其中operator* 和operator->之前没有见过，operator* 很简单，返回的是该节点的值data，也就是解引用的作用，然后operator->为了增加代码的可读性，其实是省略了一个->，当A->_data时，其实是A.operator->()->_data，然后这里的A.operator->()返回的是A的指针，然后通过间接访问符->访问_data
其中，有关于迭代器的类型
在list中，迭代器的三个模版参数分别为T、T&、T*，也就是说这个迭代器有该类型，该类型的引用和该类型的指针三个模版参数，这里就是将有关于迭代器的功能全部封装在里边，因为在以前的学习中，包括string和vector，它们的迭代器都是原生态指针，这里对于迭代器的要求更加复杂，因为对于string和vector来说，它们的存储空间是连续的，而list是不连续的
③接口
接口就是常规的接口，包括构造、拷贝构造、析构、增删查改函数，增删查改的接口直接复用的insert和erase，对于构造函数和拷贝构造函数我们封装了一个Init_empty函数，用来生成头结点
（2）自定义类型实例化
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
int _a1;
int _a2;
};
void test3()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
auto it = lt.begin();
while (it != lt.end())
{
std::cout << (*it)._a1<<" "<<(*it)._a2 << std::endl;
std::cout << it->_a1 << " " << it->_a2 << std::endl;
std::cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << std::endl;
++it;
}
std::cout << std::endl;
}
如果是自定义类型的话，访问其中的元素就需要访问操作符来进行访问，这里有三种方式进行访问，都是通过被封装的迭代器进行的
2、test.cpp
（1）test1
测试尾插构造以及拷贝构造
void test1()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
list<int> lt2(lt1);
for (auto e : lt1)
{
std::cout << e << " ";
}
std::cout << std::endl;
for (auto e : lt2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
（2）test2
void test2()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
lt1.insert(++lt1.begin(), 6);
lt1.insert(--lt1.end(), 7);
for (auto e : lt1)
{
std::cout << e << " ";
}
std::cout << std::endl;
lt1.erase(++lt1.begin());
lt1.erase(--lt1.end());
for (auto e : lt1)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
这里解释一下，insert是插入指定位置前面一个元素，也就是说6插入到了2前面，7插入到了5前面
erase是删除指定位置的元素，也就是第二个元素以及头结点前一个元素分别是6和5
五、额外小知识
有关于内置类型也会调用构造函数这件事
void test4()
{
int* p = new int;
*p = 1;
//int* p = new int(1);
//上面和这句结果是相同的，过程不同，一个是在构造后进行赋值，一个是初始化列表赋初值
AA* ptr = new AA;
ptr->_a1 = 1;
}
前面的文章提到过这件事，因为它套用了模版，模版当然也要兼容内置类型，所以内置类型在构造时可以使用类似自定义类型构造的形式，这样也会类似于调用模版函数
今日分享到这里~
