list模拟实现（部分）
1.没有实现const迭代器。
#include<iostream>
using namespace std;
namespace test {
template<class T>
struct list_node {
T _val;
list_node<T> * _prev;
list_node<T> * _next;
list_node(const T& val = T())
:_val(val), _prev(nullptr), _next(nullptr) {}
};
template<class T>
struct __list_iterator {
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node) :_node(node) {}//
T& operator*() {
return this->_node->_val;
}
__list_iterator<T>& operator++() {
this->_node = this->_node->_next;
return *this;
}
__list_iterator<T> operator++(int) {
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const __list_iterator<T>& it) {
return this->_node != it._node;
}
bool operator==(const __list_iterator<T>& it) {
return this->_node == it._node;
}
};
template<class T>
class list {
public:
typedef __list_iterator<T> iterator;
list() {
//Node* p = new Node;//new Node()?
//p->_next = _head;
//p->_prev = _head;
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
iterator begin() {
return _head->_next;
}
iterator end() {
return _head;
}
~list() {}
void push_back(const T& val) {
Node* p = new Node(val);
Node* tail = _head->_prev;
tail->_next = p;
p->_prev = tail;
p->_next = _head;
_head->_prev = p;
}
void pop_back() {
Node* p = this->_head->_prev;
p->_prev->_next = _head;
_head->_prev = p->_prev;
delete p;
}
void insert(iterator pos, const T& val) {
Node* newnode = new Node(val);
Node* p = pos._node;//只能使用点而不能用->，原因如下
p->_prev->_next = newnode;
newnode->_prev = p->_prev;
p->_prev = newnode;
newnode->_next = p;
}
void erase(iterator pos) {
Node* p = pos._node;//. not -> 因为iterator没有重载后者
p->_prev->_next = p->_next;
p->_next->_prev = p->_prev;
delete p;
}
private:
typedef list_node<T> Node;//先写这个
Node* _head;//再写这个，否则_head类型不明确
};
void test() {
list<int> lt;
lt.push_back(2);
lt.push_back(5);
lt.push_back(72);
lt.push_back(585);
lt.push_back(575);
for (auto& e : lt) {
cout << e << " ";
}
cout << endl;
auto it = lt.begin();
lt.insert(++it,8989);
lt.erase(lt.begin());
lt.erase(++lt.begin());
list<int>::iterator itt = lt.begin();
while (itt != lt.end()) {
std::cout << *itt << " ";
++itt;
}
std::cout << std::endl;
}
}
int main() {
test::test();
}2.已经实现const迭代器但没有使用双模板参数来减少代码冗余。并附加详细注释。
#include<iostream>
using namespace std;
namespace test
{
template<class T>
struct list_node//list中的node，一个node包含一个值和两个指针。
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())//你提供了val我们就用你的，你没提供我就调用T();
:_next(nullptr)
, _prev(nullptr)
, _val(val)
{}
};
template<class T>
struct __list_iterator//我们对于迭代器做了封装（这就是容器，只暴露迭代器，你使用它来访问），因为他已经不再像vector<内置类型>那样（typedef T* iterator;list存储不连续且一个node包含三个部分）
{
typedef list_node<T> Node;//为了这个struct内好写，我们将节点类型typedef以下，方便下面实现类内成员函数
Node* _node;//迭代器内部只有一个成员即指向list的节点的指针_node;
__list_iterator(Node* node)//对于迭代器的初始化就是对于这个指针的初始化
:_node(node)
{}
T& operator*()//*it就是it.operator*()，拿到val，返回类型的引用，因为走出这个函数这个_node指向的_val还在
{
return _node->_val;
}
__list_iterator<T>& operator++()//前置++,++it的时候就是it.operator++()
{
_node = _node->_next;
return *this;
}
__list_iterator<T> operator++(int)//后置++，it++就是it.operator(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
//注意后置和前置++返回类型不同，返回的都还是迭代器，但是一个是引用。
//前置++： 为了实现链式操作，例如 ++it = 10;，需要返回一个左值，以便赋值。
//后置++： 为了返回自增前的值，需要创建一个临时对象来保存原来的值，然后返回这个临时对象的副本。
//前置++返回引用，可以支持链式操作，例如 ++it = 10;
// 如果后置++也返回引用，那么 it++ = 10; 的含义就会变得模糊，到底是给自增前的迭代器赋值，还是给自增后的迭代器赋值？
//所以前置++返回引用，方便我们修改，后置++返回一个副本，这个副本是自增前的值，方便我们再用以下，其实真实的已经改变了
bool operator!=(const __list_iterator<T>& it)//while(it!=lt.end())就是it.!=(lt.end()）
{
return _node != it._node;
}
bool operator==(const __list_iterator<T>& it)
{
return _node == it._node;
}
};
template<class T>//const的迭代器，指向的迭代器不能修改
struct __list_const_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()//const迭代器返回const引用即可：(*it)+=10;这种就不能用了，
//注意const不能加在最后边，因为那样就表明迭代器不能被修改了，即*this也就是调用这个函数的对象（迭代器）
//但是我们知道迭代器是要修改的，只是迭代器的指向不能修改，所以我们在返回类型这里添加const！！！
{
return _node->_val;
}
__list_const_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
__list_const_iterator<T> operator++(int)
{
__list_const_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const __list_const_iterator<T>& it)
{
return _node != it._node;
}
bool operator==(const __list_const_iterator<T>& it)
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;//list的节点我不希望任何人动.所以我private
//typedef的作用1：迭代器各个容器之间都用iterator这个名字，但因为我们都在命名空间std中，所以会冲突，
//所以使用了typedef来将__list_iterator<T>来重命名为iterator，这样我们自己可以使用这个名字，
//而且也防止我们直接定义一个名字叫做iterator的类造成的冲突问题
public:
typedef __list_iterator<T> iterator;//iterator是暴露给外部的接口，其他人可以使用它操作这个list，我public，并typedef方便使用
typedef __list_const_iterator<T> const_iterator;//注意const迭代器不是typedef const __list_iterator<T> iterator;后者迭代器不得修改了
//这样设计有点冗余，库中使用了多个模板参数
iterator begin()//这些下面都是list的对象也就是一个一个链表可以调用的函数，比如lt.begin() lt.end()
{
//return _head->_next;
return iterator(_head->_next);//因为单参数的构造函数具有隐式类型转换功能，所以也可以像上面写
//也可以写全，return this->_head->_next;
}
iterator end()
{
return _head;
//return iterator(_head);
}
const_iterator begin()const {
return const_iterator(_head->_next);
}
const_iterator end()const {
return (const_iterator)_head;
}
list()//缺省构造函数直接构造一个头结点即可
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
~list()
{
//...
}
void push_back(const T& x)
{
Node* tail = _head->_prev;//尾节点就是头结点的前置
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void pop_back() {
Node* p = this->_head->_prev;
p->_prev->_next = _head;
_head->_prev = p->_prev;
delete p;
}
void insert(iterator pos, const T& val) {
Node* newnode = new Node(val);
Node* p = pos._node;//只能使用点而不能用->，原因如下
p->_prev->_next = newnode;
newnode->_prev = p->_prev;
p->_prev = newnode;
newnode->_next = p;
}
void erase(iterator pos) {
Node* p = pos._node;//. not -> 因为iterator没有重载后者
p->_prev->_next = p->_next;
p->_next->_prev = p->_prev;
delete p;
}
private:
Node* _head;//一个list，最重要的成员就是头指针（一个指向node的指针）
};
void Print(const list<int>& lt) {
list<int>::const_iterator it = lt.begin();
//这里你再使用list<int>::iterator it = lt.begin();就不行了，因为我们const引用了lt，它调用了const的begin方法，
//const begin方法返回const的引用，你却将它赋给了非const的iterator，这是权限的放大
while (it != lt.end()) {
//同上，这里不能再对(*it)++;因为*it返回const引用，你不得对他自增
cout << *it << " ";
it++;
}
cout << endl;
}
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();//等号右侧是一个临时的迭代器对象，左侧是一个迭代器对象，所以底层调用了默认的拷贝构造（浅拷贝）
//迭代器对象不能有析构函数，不能迭代器析构时把list的node给析构了
//所以这两个对象都指向begin，但是析构两次没事（我们的析构是空的
while (it != lt.end())
{
(*it) += 1;
cout << *it << " ";
++it;
}
cout << endl;
lt.erase(lt.begin()++);
lt.insert(++lt.begin(), 852);
lt.insert(++lt.begin(), 852);
lt.insert(++lt.begin(), 852);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl << endl;
Print(lt);
}
}
int main() {
test::test_list1();
}
//由于上述代码存在冗余：const的迭代器和普通迭代器只是operator*这个函数的返回值不同，其他一样。所以我们可以考虑使用两个模板参数；3.两个模板参数来缩减代码：
#include<iostream>
using namespace std;
namespace test
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())
:_next(nullptr)
, _prev(nullptr)
, _val(val)
{}
};
template<class T,class Ref>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref> self;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T,T&> iterator;
typedef __list_iterator<T,const T&> const_iterator;
iterator begin()
{
//return _head->_next;
return iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin()const {
return const_iterator(_head->_next);
}
const_iterator end()const {
return (const_iterator)_head;
}
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
~list()
{
//...
}
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void pop_back() {
Node* p = this->_head->_prev;
p->_prev->_next = _head;
_head->_prev = p->_prev;
delete p;
}
void insert(iterator pos, const T& val) {
Node* newnode = new Node(val);
Node* p = pos._node;
p->_prev->_next = newnode;
newnode->_prev = p->_prev;
p->_prev = newnode;
newnode->_next = p;
}
void erase(iterator pos) {
Node* p = pos._node;
p->_prev->_next = p->_next;
p->_next->_prev = p->_prev;
delete p;
}
private:
Node* _head;
};
void Print(const list<int>& lt) {
list<int>::const_iterator it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
it++;
}
cout << endl;
}
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
(*it) += 1;
cout << *it << " ";
++it;
}
cout << endl;
lt.erase(lt.begin()++);
lt.insert(++lt.begin(), 852);
lt.insert(++lt.begin(), 852);
lt.insert(++lt.begin(), 852);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl << endl;
Print(lt);
}
}
int main() {
test::test_list1();
}
4.我们重载了->运算符，使得list更好支持自定义类型。此时我们使用了三个模板参数：
#include<iostream>
using namespace std;
namespace test
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())
:_next(nullptr)
, _prev(nullptr)
, _val(val)
{}
};
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->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
Ptr operator->() {
return &(this->_node)->_val;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._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 _head->_next;
return iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin()const {
return const_iterator(_head->_next);
}
const_iterator end()const {
return (const_iterator)_head;
}
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
~list()
{
//...
}
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void pop_back() {
Node* p = this->_head->_prev;
p->_prev->_next = _head;
_head->_prev = p->_prev;
delete p;
}
void insert(iterator pos, const T& val) {
Node* newnode = new Node(val);
Node* p = pos._node;
p->_prev->_next = newnode;
newnode->_prev = p->_prev;
p->_prev = newnode;
newnode->_next = p;
}
void erase(iterator pos) {
Node* p = pos._node;
p->_prev->_next = p->_next;
p->_next->_prev = p->_prev;
delete p;
}
private:
Node* _head;
};
struct A {
A(int a=0, int b=0) :_a(a), _b(b) {}
//这样写先当于没有默认构造函数了：A(int a, int b) :_a(a), _b(b) {}，但是list_node的构造函数中会用，所以我们给缺省值
int _a, _b;
};
void test() {
list<A> lt;
lt.push_back(A(1, 1));
lt.push_back(A(2, 2));
lt.push_back(A(3, 3));
lt.push_back(A(4, 4));
auto it = lt.begin();
while (it != lt.end()) {
cout << it->_a << " " << it->_b << endl;
//本质是cout<<it->->_a<<" "<<it->->_b<<endl;但为了重载函数的可读性，编译器做了优化
//it->返回对象的地址（const或非const），得到地址后再去利用“地址->内容”的方式访问_a和_b
++it;
}
}
}
int main() {
test::test();
}