C++ ─── List的模拟实现
目录
一， List的模拟实现
List 是一个双向循环链表,由于List的节点不连续，不能用节点指针直接作为迭代器，因此我们要对结点指针封装，来实现迭代器的作用。
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前 移动，所以需要重载，如果是forward_list就不需要重载--
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
二，代码实现
#pragma once
#include<assert.h>
#include<iostream>
#include <initializer_list>
#include<algorithm>
using namespace std;
namespace BMH
{
template<class T>
struct ListNode
{
typedef ListNode<T> Node;
Node* _prev;
Node* _next;
T _data;
ListNode(const T& data = T())
:_prev(nullptr)
, _next(nullptr)
, _data(data)
{}
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
//正向迭代器
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
// Ref 和 Ptr 类型需要重定义下，实现反向迭代器时需要用到
public:
typedef Ref Ref;
typedef Ptr Ptr;
Node* _node;
ListIterator(Node* node =nullptr)
:_node(node)
{}
//++it
Self& operator++()
{
_node = _node->_next;
return *this;//++it 返回自己（迭代器）
}
//--it
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//it++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
//it--
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//
// 具有指针类似行为
//*it 返回值
Ref operator*()
{
return _node->_data;;
}
//it-> 返回指针
Ptr operator->()
{
return &(_node->_data);
}
//
//
// 迭代器支持比较
bool operator == (const Self& it)
{
return _node == it._node;
}
bool operator != (const Self& it)
{
return _node != it._node;
}
};
template<class T>
class List
{
public:
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
///
//初始化创建头结点
void empty_init()
{
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
}
//构造函数
List()
{
empty_init();
}
List(int n, const T& value = T())
{
empty_init();
for (int i = 0; i < n; ++i)
push_back(value);
}
//用下面拷贝构造函数来实现构造函数，拷贝构造函数是构造函数的一种。
//List<int> lt2(lt1)
//List(const List<T>& lt)
//{
//empty_init();
//for (const auto& e : lt)
//{
//Push_Back(e);
//}
//}
//List<int> lt1 ={1,2,3,4}
List(initializer_list<T> il)//不用引用的原因：il本身是两个指针，拷贝代价小
{
empty_init();
for (const auto& e : il)
{
Push_Back(e);
}
}
template<class Inputiterator >
List(Inputiterator p1, Inputiterator p2)
{
empty_init();
while (p1 != p2)
{
Push_Back(*p1);
++p1;
}
}
//拷贝构造
//lt2(lt1)
List(const List<T>& lt)
{
empty_init();
for (const auto& e : lt)
{
Push_Back(e);
}
}
//赋值重载
//lt1=lt2
List<T>& operator=(List<T> lt)
{
swap(_head, lt._head);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);//用erase时会发生迭代器失效
}
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
///
//迭代器
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* tail = _head->_prev;
Node* newnode = new Node(x);
newnode->_prev = tail;
tail->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;
}
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& data )
{
Node* cur = pos._node;//pos是迭代器，找到其中的节点地址即可
Node* newnode = new Node(data);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur-> _prev= newnode;
return iterator(newnode);
}
//有迭代器失效,返回删除节点下一个的迭代器
iterator erase(iterator pos)
{
assert(pos!= (*this).end());//防止将
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
Node* _head;
};三、list和vector的区别
1、任意位置插入删除时：list可以随意插入删除，但是vector任意位置的插入删除效率低，需要挪动元素，尤其是插入时有时候需要异地扩容，就需要开辟新空间，拷贝元素，释放旧空间，效率很低
2、访问元素时：vector支持随机访问，但是list不支持随机访问
3、迭代器的使用上：vector可以使用原生指针，但是list需要对原生指针进行封装
4、空间利用上：vector使用的是一个连续的空间，空间利用率高，而list使用的是零碎的空间，空间利用率低
这个博客如果对你有帮助，给博主一个免费的点赞就是最大的帮助❤
欢迎各位点赞，收藏和关注哦❤
如果有疑问或有不同见解，欢迎在评论区留言哦❤
后续我会一直分享双一流211西北大学软工（C，数据结构，C++，Linux，MySQL）的学习干货以及重要代码的分享
原文地址：https://blog.csdn.net/m0_73751295/article/details/141831633
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！