C++ ─── List的模拟实现

一码归—码 2024-09-08 12:35:01 阅读 85

目录

​编辑

一, List的模拟实现

二,代码实现

三、list和vector的区别


一, List的模拟实现

     List 是一个双向循环链表,由于List的节点不连续,不能用节点指针直接作为迭代器,因此我们要对结点指针封装,来实现迭代器的作用。

迭代器有两种实现方式,具体应根据容器底层数据结构实现:

        1. 原生态指针,比如:vector

        2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:

        1. 指针可以解引用,迭代器的类中必须重载operator*()

        2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()

        3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)

至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前 移动,所以需要重载,如果是forward_list就不需要重载--

        4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

二,代码实现

<code>#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)的学习干货以及重要代码的分享



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。