C++学习之路，从0到精通的征途：List类的模拟实现

目录

一.list的介绍

二.list的接口实现

1.结点

2.list结构

3.迭代器 

（1）begin

（2）end

 4.修改

（1）insert

（2）push_back

（3）push_front

（4）erase

（5）pop_back

（6）pop_front

（7）swap

（8）clear 

5.默认成员函数

（1）构造函数

（2）拷贝构造函数

（3）赋值重载

（4）析构函数

三.代码总览

list.h

test.cpp

---

 

一.list的介绍

源文档

二.list的接口实现

1.结点

template<class T>
struct list_node
{list_node* _prev;list_node* _next;T _data;// 由于数据类型由模板参数决定，所以缺省值给匿名对象list_node(const T& x = T()):_prev(nullptr),_next(nullptr),_data(x){}
};

        用一个结构体来封装结点，我们手动写默认构造函数以便在申请结点时调用。

2.list结构

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;
private:// 哨兵位Node* _head;// 有效数据个数size_t _size = 0;
};

3.迭代器 

        list的迭代器与之前的string和vector不同，由于list的数据存储空间并不是连续的，所以我们无法再继续用原生指针来实现迭代器类型，++，解引用等操作并不能实现想要达到的目的，所以我们需要重载这些操作符，并将迭代器封装成一个新的类。

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){}// 比较指向的结点是否相同bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}// Ref来控制iterator与const_iterator// Ref->T& -- iterator;// Ref->const T& -- const_iterator;// 获取结点存储的数据Ref operator*(){return _node->_data;}// 使迭代器指向下一个结点Self& operator++(){_node = _node->_next;return *this;}// 后置++Self operator++(int){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;}// 为了可读性进行特殊处理 it->->_a1 被优化为 it->_a1// Ptr来控制iterator与const_iterator// Ptr->T* -- iterator// Ptr->const T* -- const_iteratorPtr operator->(){return &_node->_data;}
};

（1）begin

iterator begin()
{return iterator(_head->_next);
}

const_iterator begin() const
{return const_iterator(_head->_next);
}

（2）end

iterator end()
{// 返回尾结点的下一个结点，也就是哨兵位return iterator(_head);
}

const_iterator begin() const
{return const_iterator(_head->_next);
}

 4.修改

（1）insert

void insert(iterator pos, const T& x)
{// 申请新结点的空间，调用构造Node* newnode = new Node(x);// 断开旧连接，连接新结点Node* cur = pos._node;Node* prev = cur->_prev;// prev newnode curnewnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;++_size;
}

（2）push_back

void push_back(const T& x)
{//Node* newnode = new Node(x);//Node* tail = _head->_prev;tail newnode _head//newnode->_prev = tail;//newnode->_next = _head;//tail->_next = newnode;//_head->_prev = newnode;insert(end(), x);
}

（3）push_front

void push_front(const T& x)
{insert(begin(), x);
}

（4）erase

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;//return iterator(next);// 为防止迭代器失效，返回删除后的下一个结点的迭代器// 单参数构造函数支持隐式转换return next;
}

        为防止erase后，pos依然指向被delete的结点从而导致迭代器失效，erase返回指向下一个结点的迭代器。 

（5）pop_back

void pop_back()
{erase(--end());
}

（6）pop_front

void pop_front()
{erase(begin());
}

（7）swap

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}

        交换哨兵位即可交换两个list。

（8）clear 

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

        除了哨兵位，其他结点逐个erase。 

5.默认成员函数

（1）构造函数

空list申请哨兵位：empty_init

// 空list申请哨兵位
void empty_init()
{_head = new Node;_head->_prev = _head;_head->_next = _head;
}// 无参数构造
list()
{//_head = new Node;//_head->_prev = _head;//_head->_next = _head;empty_init();
}// initializer_list构造
list(std::initializer_list<T> il)
{empty_init();for (auto& e : il){push_back(e);}
}

（2）拷贝构造函数

list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}

        先申请哨兵位，再逐个尾插即可。

（3）赋值重载

list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

（4）析构函数

~list()
{clear();delete _head;_head = nullptr;
}

三.代码总览

list.h

#include<iostream>
#include<initializer_list>namespace my_list
{template<class T>struct list_node{list_node* _prev;list_node* _next;T _data;// 由于数据类型由模板参数决定，所以缺省值给匿名对象list_node(const T& x = T()):_prev(nullptr),_next(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){}// 比较指向的结点是否相同bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}// Ref来控制iterator与const_iterator// Ref->T& -- iterator;// Ref->const T& -- const_iterator;// 获取结点存储的数据Ref operator*(){return _node->_data;}// 使迭代器指向下一个结点Self& operator++(){_node = _node->_next;return *this;}// 后置++Self operator++(int){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;}// 为了可读性进行特殊处理 it->->_a1 被优化为 it->_a1// Ptr来控制iterator与const_iterator// Ptr->T* -- iterator// Ptr->const T* -- const_iteratorPtr operator->(){return &_node->_data;}};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;// 空list申请哨兵位void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}// 无参数构造list(){//_head = new Node;//_head->_prev = _head;//_head->_next = _head;empty_init();}// initializer_list构造list(std::initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2 = lt1list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size(){return _size;}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 newnode _head//newnode->_prev = tail;//newnode->_next = _head;//tail->_next = newnode;//_head->_prev = newnode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){// 申请新结点的空间，调用构造Node* newnode = new Node(x);// 断开旧连接，连接新结点Node* cur = pos._node;Node* prev = cur->_prev;// prev newnode curnewnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;++_size;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;//return iterator(next);// 为防止迭代器失效，返回删除后的下一个结点的迭代器// 单参数构造函数支持隐式转换return next;}private:// 哨兵位Node* _head;// 有效数据个数size_t _size = 0;};
}

test.cpp

#include"list.h"
using namespace std;namespace my_list
{void test_list1(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it = lt1.begin();while (it != lt1.end()){*it += 10;cout << *it << " ";++it;}cout << endl;lt1.push_back(1);lt1.push_back(2);lt1.push_front(3);lt1.push_front(4);for (auto& e : lt1){cout << e << " ";}cout << endl;lt1.pop_back();lt1.pop_front();for (auto& e : lt1){cout << e << " ";}cout << endl;cout << lt1.size() << endl;}void test_list2(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_front(3);lt1.push_front(4);for (auto& e : lt1){cout << e << " ";}cout << endl;list<int> lt2(lt1);for (auto& e : lt1){cout << e << " ";}cout << endl;list<int> lt3;lt3 = lt1;for (auto& e : lt1){cout << e << " ";}}struct AA{int _a1;int _a2;AA(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){}};void test_list3(){list<int> lt1 = { 1,2,3,4 };for (auto& e : lt1){cout << e << " ";}cout << endl;list<AA> lt2 = { {1,1},{2,2},{3,3},{4,4} };list<AA>::iterator it = lt2.begin();while (it != lt2.end()){//cout << (*it)._a1 << ":" << (*it)._a2 << endl;//cout << it->->_a1 << ":" << it->->_a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;++it;}list<AA>::iterator lit = lt2.begin();while (lit != lt2.end()){cout << lit.operator->()->_a1 << ":" << lit.operator->()->_a2 << endl;++lit;}}
}int main()
{my_list::test_list3();return 0;
}