当前位置：首页 > news >正文

list的模拟实现

news 来源：原创 2025/9/11 0:24:28

一、构造和扩容机制

二、普通迭代器

三、const迭代器

四、tip

有了前面vetcor的基础呢，我们在学习和使用list上就更加的方便快捷，浅显易懂了，所以相似的部分我就不做过多的言语阐述了，在使用方面呢，大家可以学习我之前看的c++网站，和vector和string的使用都是差不多的，重点要放在list的迭代器部分

一、构造和扩容机制

	template <class T>class list{typedef list_node<T> Node;public:void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void push_back(const T&val){Node* tail = _head->_prev;Node* newnode = new Node(val);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;

空初始化的时候我们也需要构造，所以缺省值我们给一个匿名对象进行初始化，这个我们在vector的模拟实现里面有重点说到

template <class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data=T()):_data(data),_next(nullptr),_prev(nullptr){}
};

二、普通迭代器

void listtest1()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}
}

这里我们还没有实现迭代器

这是一个带头双向循环链表，我们结合迭代器来看，由于它是一个结构体，我们解引用并不能得到它的数据，++it也不能得到向后走，！=也判断不了end（），因为里面存在着数据和前后指针，这时候我们就要运算符重载和封装这里

这里我们为什么不用class来写那个list_node 呢因为你写class就要把它定义成友元，而这里我们是要把这个类的权限全部开放所以我们定义成struct

template <class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> self;Node* _node;list_iterator(Node* node):_node(node){ }self& operator++(){_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator!=(const self&s){return _node != s._node;}};

我们来阐述一下这里的行为，我们封装了一个Node，实例化了一个对象，写出构造函数，++让里面的指针++返回这个Node的下一个位置的引用，下面也是类似，就是指针完成不了的事情我们通过间接的方式来让类完成

typedef list_iterator<T> iterator;
iterator begin()
{return _head->_next;
}
iterator end()
{return _head;
}

这里begin和end返回指着可以的原因是单参数的构造支持隐式类型的转换

这里重要的就是封装，封装屏蔽了底层差异和实现细节，提供统一访问修改遍历方式

这算是一种模拟指针的行为

我们简化了这里的接口，list_iterator封装了链表节点的指针，通过重载一系列运算符，用户可以像指针一样遍历链表，而不必关心节点如何连接

这里我们先封装一个简单的

先把其他的架子实现出来

首先是删除

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;return iterator(next);
}

删除这里会涉及迭代器失效的问题，有关于迭代器失效可以看一下我vector里面有详细的写，总而言之就是这里pos的位置删除了，而你的迭代器没有进行及时的更新，所以我们这里让迭代器指向下一个位置

iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

一般来说这里的insert不会发生迭代器失效，但是库里面有写，而且可以和上面统一一下

这样子我们的头插头删尾插尾删就可以复用这里的

void push_back(const T&val)
{insert(end(), val);}
void push_front(const T& val)
{insert(begin(), val);
}
void pop_back(const T& val)
{erase(end(), val);
}
void pop_front(const T& val)
{erase(begin(), val);
}

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

这个时候我们上面的删除迭代器就派上用场了，删除完我们返回下一个迭代器位置就行了

我们的析构就可以套用这个clear了

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

接下来我们来实现一下拷贝构造

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

这里不用const原因是因为e不是const对象，等下我们实现了const迭代器就可以实现了

再让我们实现一下赋值

首先是传统写法

	//lt3=lt1//list<T>& operator=(list<T>& l)//{//	if (this != &l)//	{//		clear();//		for (auto e : lt)//		{//			push_back(e);//		}//	}//}

现代写法

void swap(list<T>& l)
{std::swap(_head, l._head);
}
list<T>& operator=(list<T>& l)
{swap(l);return *this;
}

交换头节点的指针就可以了

为了不让有的人去获取这个链表的size时时间复杂度是o(n)，我们添加一个szie在private那里，在初始化那里给上0，insert那里++，erase那里--就好了

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

我们再来看一下后置++

self operator++(int)
{self tmp(*this);_node = _node->_next;return tmp;
}

self operator--(int)
{self tmp(*this);_node = _node->_prev;return tmp;
}

bool operator==(const self& s)
{return _node == s._node;
}

迭代器是不需要实现析构函数的，因为它不需要把那个节点给带走，你可以访问节点，但是不能带走不属于它的节点

为了支持自定义类型的实例化访问我们还需要实现->

T* operator->()
{return &_node->_data;
}

三、const迭代器

template <class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator<T> self;Node* _node;list_const_iterator(Node* node):_node(node){}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;}const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};

typedef list_const_iterator<T> const_iterator;
const_iterator begin() const
{return _head->_next;
}
const_iterator end() const
{return _head;
}

void print_list(const list<int>& l)
{list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}
}

这个const_iterator不是const iterator的类型，指针本身可以被修改，但是指针指向的内容不能被修改

那我们这里写成两个能不能复用一下搞成一个呢，我们看一下库里面的

同一个类模板，实例化参数不同，就是完全不同的类型

	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){}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;}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;}};

typedef list_iterator<T,T&,T*> iterator;
typedef list_iterator<T,const T&,const T*> const_iterator;

我们定义了两个类，我们也不知道这是什么类，留给后面来定义，只知道Ref相当于&类型的，Ptr代表*类型的，

Ref & operator*()
{return _node->_data;
}
Ptr* operator->()
{return &_node->_data;
}

比如说当我们实例化int的时候，普通对象先传给T&，再把T&传给Ref，Ref就可以实例化出来这个类进行使用，定义了一个const对象就实例化出来一个const的类出来，看似是一个类，在当你实例化普通和const对象的时候其实是两个类

四、tip

template<class T>
void print_list(const list<T>& l)
{list<T>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}for (auto e : l){cout << e << " ";}cout << endl;
}
void listtest3()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);print_list(l);
}

这段代码我们会发现编译不通过

template<typename T>
void print_list(const list<T>& l)
{typename list<T>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}for (auto e : l){cout << e << " ";}cout << endl;
}

改成这样就可以了，因为你list里面是模板，模板又没有实例化，编译器不敢去类里面找，去里面找也没有实例化，其次是你const_iterator是静态成员变量还是内嵌类型不知道，编译器分不清，前面加一个typename就是告诉编译器这里是一个类型，等list<t>实例化，再去实例化类型里面去找

那我们这个print如果想针对所有容器怎么办

	template<typename Container>void print_container(const Container& l){typename Container::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}for (auto e : l){cout << e << " ";}cout << endl;}void listtest3(){vector<string> v;v.push_back("11111111111");v.push_back("11111111111");v.push_back("11111111111");v.push_back("11111111111");print_container(v);}}

和上面是一样的玩法，把实例化这个类型传给了container

模板实现了泛型编程，把我们本来干的活交给了编译器

好了list就到这里结束了，接下来是栈和队列，写的不好的地方欢迎大家指出

一、构造和扩容机制

二、普通迭代器

三、const迭代器

四、tip

相关文章：