淘宝网站的建设内容网站下载免费软件

---

前言

C++模拟实现list：list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍

---

一、list

list本质上是一个双向带头循环链表。
实现list类，需要节点类（clase list_node）、迭代器（class __list_iterator）;
节点类（clase list_node）： 定义每个节点的结构；
迭代器（class __list_iterator）： 使用节点的指针封装出一个类，可以使用运算符重载的形式更好的访问链表；

二、list类的初始化和尾插

namespace hhb
{// 节点template <class T>struct list_node{list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val){}list_node<T>* _next;list_node<T>* _prev;T _val;};// 链表template<class T> class list{typedef list_node<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){Node* newNode = new Node(x);Node* tail = _head->_prev;newNode->_next = _head;newNode->_prev = tail;tail->_next = newNode;_head->_prev = newNode;}private:Node* _head;};
}

三、list的迭代器的基本实现

• 使用链表节点的指针封装出一个类，是list链表的访问可以向vector一样使用++等操作访问
• vector和list的使用，虽然在形式上一样，但是他们的底层是不一样的
• （*）vector迭代器是对指针的解引用
• （*）list迭代器是调用operator（解引用操作符）函数重载，本质是不一样的

对于const迭代器，是operator（*）和 operator(->)的运算符重载函数的返回值不一样，因此需要增加两个模板参数

• 即： （T& 和 T*）

// 迭代器
template <class T, class Ref, class Ptr>
struct __list_iterator
{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;
public:__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}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;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}Node* _node;
};

• operator->运算符重载编译器会进行优化， 如下：

struct A
{
public:A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}int _a1;int _a2;
};
void test_list02()
{hhb::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));lt.push_back(A(5, 5));hhb::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;cout << it->_a1 << " " << it->_a2 << " " << endl;// 此处编译器进行了优化， it->返回的是T* 也就是 A*， 如果要访问A的成员// 按道理来讲，应该是 (it->)->_a1 / (it->)->_a2 来进行访问++it;}cout << endl;}

四、list的完整实现

• list需要有size()的接口，所以需要对链表节点个数进行计数，增加一个成员变量_size.
• 实现insert()和erase()接口后，push_back()和push_front()、pop_back()和pop_front()接口都可以复用接口。
• clear()只清除（不包含哨兵位的头节点）数据，不销毁链表
• 析构函数调用clear（）后，释放_head节点（哨兵位的头节点）
• 拷贝构造函数在拷贝之前，一定要先自己初始化（创建哨兵位的头节点）
• 赋值（=）运算符重载使用现代写法，拷贝构造加交换函数加自动调用析构函数。

	// 链表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;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void emptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>& lt){emptyInit();for (auto e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T> operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}void push_back(const T& x){//Node* newNode = new Node(x);//Node* tail = _head->_prev;//newNode->_next = _head;//newNode->_prev = tail;//tail->_next = newNode;//_head->_prev = newNode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pos_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;++_size;return newNode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;--_size;return next;}//size_t size()//{//	int sz = 0;//	iterator it = begin();//	while (it != end())//	{//		sz++;//		++it;//	}//	//	return sz;//}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}

五、测试

• 测试push_back, pop_back可以顺便测试insert, erase函数, 所以不单独测试insert和erase函数

void test_list03()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pos_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}

• 测试拷贝构造和赋值运算符重载

void test_list04()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;hhb::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;hhb::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}

六、整个list类

// list.h
#pragma once#include <assert.h>
namespace hhb
{// 节点template <class T>struct list_node{list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val){}list_node<T>* _next;list_node<T>* _prev;T _val;};// 迭代器template <class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;public:__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}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;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}Node* _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;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void emptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>& lt){emptyInit();for (auto e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T> operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}void push_back(const T& x){//Node* newNode = new Node(x);//Node* tail = _head->_prev;//newNode->_next = _head;//newNode->_prev = tail;//tail->_next = newNode;//_head->_prev = newNode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pos_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;++_size;return newNode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;--_size;return next;}//size_t size()//{//	int sz = 0;//	iterator it = begin();//	while (it != end())//	{//		sz++;//		++it;//	}//	//	return sz;//}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}

• 整个测试

#define  _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <list>
using namespace std;
#include "list.h"void print1(const hhb::list<int>& lt)
{hhb::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}void test_list01()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);hhb::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;print1(lt);
}struct A
{
public:A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}int _a1;int _a2;
};void test_list02()
{hhb::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));lt.push_back(A(5, 5));hhb::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;cout << it->_a1 << " " << it->_a2 << " " << endl;// 此处编译器进行了优化， it->返回的是T* 也就是 A*， 如果要访问A的成员// 按道理来讲，应该是 (it->)->_a1 / (it->)->_a2 来进行访问++it;}cout << endl;}void test_list03()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pos_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}void test_list04()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;hhb::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;hhb::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}int main()
{//test_list01();test_list02();//test_list03();//test_list04();return 0;
}

---

总结

C++模拟实现list：list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍