C++（list的简单实现，着重点是迭代器）

🕗 发布于 2024-09-23 06:44 c++ list 开发语言

本文适合能自主实现双向链表增删的有功底的人，如果不会的话可以看我以前使用c实现的双向链表。

C++中list是双向链表，forword_list才是单链表

1.节点（list_node）

2.链表的成员函数的实现

3.iterator迭代器

4.const_iterator 迭代器

5.合并iterator和const_iterator

1.节点（list_node）

template<class T>
struct list_node
{
list_node(const T& val = T())
:_val(val)//这里是初始化
{
_next = _prev = this;//使指针指向自己
//_val = val;//为什么不在写？因为这里赋值，因为模板参数可能是T = const int等，const不支持修改
}
list_node<T>* _next;
list_node<T>* _prev;
T _val;
};

初始化列表是初始化，而代码块中的代码是赋值。const类型的数据一旦初始化后，就不能在修改其值。

2.链表的成员函数的实现

这里就是链表的增删问题了这里就不讲了，直接给代码。

template<class T>
class list
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
    public:
        //构造
list()
{
_phead = new Node(-1);
}
        //拷贝构造
list(const list<T>& l)
{
PNode pcur = l._phead->_next;
while (pcur != l._phead)
{
push_back(pcur->_val);
}
}


        //深拷贝实现的复制
list<T>& operator=(const list<T>& l)
{
PNode pcur = l._phead->_next;
while (pcur != l._phead)
{
push_back(pcur->_val);
}
return *this;
}
        //现代写法
        list<T>& operator=(list<T> l)
        {
            std::swap(_phead,l._phead);
            return *this;
        }

        //析构
~list()
{
delete(_phead);
}
        


iterator begin()
{
return _phead->_next;
}
iterator end()
{
return _phead;
}


size_t size()
{
PNode pcur = _phead->_next;
int cout = 0;
while (pcur != _phead)
{
count++;
pcur = pcur->_next;
}
return count;
}

bool empty()
{
return _phead->_next == _phead;
}

T& front()
{
return _phead->_next->_val;
}

T& back()
{
PNode pcur = _phead->_next;
while (pcur->_next != _phead)
{
pcur = pcur->_next;
}
return pcur->_val;
}


        //push,pop可以复用insert和erase
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode newnode = new Node(val);
newnode->_prev = pos.operator->()->_prev;
pos.operator->()->_prev->_next = newnode;
newnode->_next = pos.operator->();
pos.operator->()->_prev = newnode;

return newnode;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode del = pos.operator->();
PNode ret = del->_next;
del->_prev->_next = del->_next;
del->_next -> _prev = del->_prev;
delete del;
return ret;
}
void clear()
{
PNode* pcur = _phead;
PNode* next;
while (pcur != _phead)
{
next = pcur->_next;
delete pcur;
pcur = next;
}
}
        //交换的是资源
void swap(list<T>& l)
{
std::swap(_phead, l._phead);
}
        
private :
PNode _phead;//指向哨兵位
};

3.iterator迭代器

iterator迭代器的本质就是控制指向节点的指针的向前和向后移动。

template<class T>
class Iterator
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
typedef Iterator<T> Self;
public:
        //构造
Iterator(PNode ptr = nullptr)
{
_pnode = ptr;
}
        //没有析构函数，让编译器自动生成就可以了，因为没有资源需要释放
        //返回当前iterator指向的节点的_val值
T& operator*()
{
return _pnode->_val;
}
        
        //如果_val的类型是一个结构体的话可以使用这个，这个的意思就是访问_val的成员
        
T* operator->()
{
return &(_pnode->_val);
}
        //前置++
Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
        //后置++
Self operator++(int)
{
PNode tmp = _pnode;
_pnode = _pnode->_next;
return tmp;
}
Self& operator--()
{
_pnode = _pnode->_prev;
return* this;
}
Self operator--(int)
{
PNode* tmp = _pnode;
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _pnode != l._pnode;
}
bool operator==(const Self& l)
{
return _pnode == l._pnode;
}
private:
PNode _pnode;
};

这里将operator-> 的一些注意事项：

理解一下operator->()的本质，就是返回_val的首元素地址。

//假如T的类型是class A
class A
{

public:
    int a;
    int b;
}

//
list<A> ls = {{1,2}，{2,3}，{2,4}}}；
list<A>::iterator it = ls.begin();
it->a; //这句代码的实现就是  it.operator->()->a; 也就是先调用operator->()，再用其返回值加上下标引用操作符访问a，可以理解为operator->()返回的是结构体或类的等可以通过下标访问操作符访问其成员的指针

注意前置++，和后置++的区别

首先，前置++，是先++后使用，返回的是该iterator的引用。

后置++，是先使用后++，所以返回的是++之前的值，所以返回值，就是++前的iterator（不是引用）。

前置--，和后置--也是类似的道理。

4.const_iterator 迭代器

注意const_iterator与iterator的区别，不是再iterator前加一个const，注意cosnt和iterator之间有一个下划线连接；而两者的真正区别就是const_iterator不允许对iterator指向的节点的元素的值进行修改。

template<class T>
class Iterator
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
typedef Iterator<T> Self;
public:
        //构造
Iterator(PNode ptr = nullptr)
{
_pnode = ptr;
}
        //没有析构函数，让编译器自动生成就可以了，因为没有资源需要释放
        //返回当前iterator指向的节点的_val值
const T& operator*()
{
return _pnode->_val;
}
        
        //如果_val的类型是一个结构体的话可以使用这个，这个的意思就是访问_val的成员
        
const T* operator->()
{
return &(_pnode->_val);
}
        //前置++
const Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
        //后置++
const Self operator++(int)
{
PNode tmp = _pnode;
_pnode = _pnode->_next;
return tmp;
}
const Self& operator--()
{
_pnode = _pnode->_prev;
return* this;
}
const Self operator--(int)
{
PNode* tmp = _pnode;
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _pnode != l._pnode;
}
bool operator==(const Self& l)
{
return _pnode == l._pnode;
}
private:
PNode _pnode;
};

跟上面的iterator的实现差不多就是返回值需要用const修饰，毕竟不允许修改值嘛。

5.合并iterator和const_iterator

上面的两个迭代器的实现非常类似，所以能否通过一个模板来实现呢？

注意上面两个代码的异同

iterator    const_iterator
T           const T
T*          const T*
T&          const T&
//下面两个可以根据传入的T还是const T来相应的生成。
iterator<T>  const_iterator<const T> 
iterator<T>&     const_iterator<const T>&

所以只需要根据前三个参数，模板就可以知道生成iterator的模板还是const_iterator的模板。

template<class T,class Ref,class Ptr>
class Iterator
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
typedef Iterator<T, Ref, Ptr> Self;
public:
Iterator(PNode ptr = nullptr)
{
_pnode = ptr;
}

T& operator*()
{
return _pnode->_val;
}
PNode operator->()
{
return _pnode;
}

Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}

Self operator++(int)
{
PNode tmp = _pnode;
_pnode = _pnode->_next;
return tmp;
}
Self& operator--()
{
_pnode = _pnode->_prev;
return* this;
}
Self operator--(int)
{
PNode* tmp = _pnode;
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _pnode != l._pnode;
}
bool operator==(const Self& l)
{
return _pnode == l._pnode;
}
private:
list_node<T>* _pnode;
};

实例化时：

template<class T>
class list
{
public:
        typedef Iterator<T,T&,T*> iterator;//iteraotr迭代器
typedef Iterator<const T, const T&, const T*> const_iterator;//const_iterator迭代器
}

完整代码。

刷题记录: 用来调试刷题是写的代码 (gitee.com)

原文地址：https://blog.csdn.net/2402_82658387/article/details/142444037

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：设计模式实战——开发中常用到的单例模式
下一篇：MySQL调优--11--分批插入/更新数据 ---案例

百度搜索AI探索版多线程批量生成TXT原创文章软件-可生成3种类型文章
8、有8种标题模式可自由设置：1、关键词 2、百度搜索AI原创标题(以原创标题写文章) 3、关键词 + 百度搜索AI原创标题 4、关键词 + 下拉副标题 5、关键词 + 下拉副标题
阅读更多2024-11-16
批量更改表格数据不更新、不实时渲染、或则watch监听不到表格修改数据
第一种方法是监听的watch中添加deep:true，但是这种方法对我来说不管用，我需要监听某一列的数据，在批量更改后，统计数量，这时候，手动更改数据，他的监听并不能实时抓捕到。我这里的功能是，批量更
阅读更多2024-11-16
【大语言模型】ACL2024论文-10 CSCD-IME: 纠正拼音输入法产生的拼写错误
本文研究了中文拼写校正（CSC）任务，特别是针对拼音输入法（IME）产生的错误。作者首先介绍了一个包含40,000个标注句子的中文拼写校正数据集（CSCD-IME），这些句子来自新浪微博上的官方媒体帖
阅读更多2024-11-16
react 中 memo 模块作用
memo`是一个用于优化组件性能的高阶组件。
阅读更多2024-11-16
随笔content1
如果组件的具体类型无法获得，或者你并不关心组件的具体类型，那么可以使用 ComponentPublicInstance。当你将一个响应式对象的属性赋值或解构到一个本地变量时，访问或赋值该变量是非响应式
阅读更多2024-11-16
Java多线程底层设计思路
Java 的多线程设计比较全面和灵活，提供了多种方式来定义任务和管理线程，特别是通过Runnable和Callable接口，可以实现任务和线程的解耦，适应不同的应用场景。与 Python 和 C# 相
阅读更多2024-11-16
第七章利用CSS和多媒体美化页面
当设置为show时，就意味着当表格中某个单元格没有内容时，依然会显示该单元格的边框，这样可以保持表格的完整性和视觉上的连贯性，让用户在浏览表格时，能清晰地看到每个单元格的范围。而当参数为hide时，则
阅读更多2024-11-16
Cyberchef配合Wireshark提取并解析TCP/FTP流量数据包中的文件
通过cyberchef还原pcap数据包中TCP上层的文件内容，提升wireshark分析数据包的效率
阅读更多2024-11-16
redis
Redis 本质上是一个 Key-Value 类型的内存数据库，整个数据库加载在内存当中进行操作，定期通过异步操作把数据库数据 flush 到硬盘上进行保存。因为是纯内存操作， Redis 的性能
阅读更多2024-11-16
C++学习笔记之string容器、vector容器
vector可以动态扩展，动态扩展并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间。我们读过的书，说过的话，见过的山水，见到的人和事，最终都会变成我们脚下的的路。
阅读更多2024-11-16

C++（list的简单实现，着重点是迭代器）

1.节点（list_node）

2.链表的成员函数的实现

3.iterator迭代器

4.const_iterator 迭代器

5.合并iterator和const_iterator

相关文章