C++——list

🕗 发布于 2024-10-10 22:31 c++ 开发语言

前言

一、接口

二、迭代器

前言

list，其实就是我们C语言数据结构学过的带头双向循环链表，每一个节点都有指向前一个和后一个节点的指针，除头节点外都存储数据。

list的接口与string和vector的接口很类似，因此博客不再过多演示。

由于物理结构的差异（内存存储位置不连续），与string和vector不同，list的模拟实现中不能再使用原生指针作为迭代器进行封装，因此本博客的重心会放在list迭代器的实现。

一、接口

大体上的接口我们在前面的vector和list就已经很熟悉了，由于list的本身特性，库里面增添了remove和sort的接口， remove是删除所有等于value的元素，remove_if是删除所有符合条件的元素，这个判断是否符合条件是需要传仿函数或者函数指针过去的。

仿函数实际是一个类实例化出的对象，通过运算符重载达到的类似函数调用的效果，这个以后会具体写代码来讲解实现，这里给出文档的示例，了解一下即可

另外值得一提的是，由于物理空间上的限制，list的sort效率并不高，我们对list进行排序的时候，也可以考虑先用迭代器构造将其数据转到相应的vector里，再用迭代器构造出一个list存储排序后的数据。

二、迭代器

由于容器物理空间分布的不同，容器的迭代器可以大致分为三种类型：单向，双向和随机迭代器。

它们之间是继承的关系，继承简单来说就是子类在继承父类原有内容基础上增添了新的功能。

单向迭代器：只能++，不能--

双向迭代器：只能++和--，不能+和-

随机迭代器：支持+和-，以及+=，++，-=，--等各种操作

由于list物理结构的原因，它的迭代器只支持++和--，也就是双向迭代器，可以利用对list进行遍历等等操作。

实际上，如果非要支持+和-，也不是不行，但是时间复杂度会是O（N），所以就放弃了这种方式，如果我们需要跳跃多个节点，可以利用while循环让迭代器++或者--。

三、模拟实现

1.基本框架

list，带头双向链表，实现它自然需要结点（存储当前结点数据以及前后结点位置）和迭代器（具体实现后面会细说），把两者封装起来成list，list的私有成员即为头节点指针和_size，我们每次插入和删除数据都对size进行++或--操作，方便记录结点个数。

namespace muss
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;

};

    template<class T>
    struct list_iterator
    {

    };

    template<class T>
    class list
    {
    public:

private:
Node* _head;
size_t _size;
};
}

这是最基本的框架，我们后面会对其进行完善

2.迭代器处理

对于迭代器的实现，我们为了让其能实现++，--的遍历操作，我们让封装起来的迭代器储存对应结点的地址，这样方便我们通过它的两个指针来找到前后两个结点。通过运算符重载，实现它的遍历操作，也就是可以实现++和--。

一个容器的迭代器一般都需要实现两个版本，const和非const，然而我们对其分别进行实现，会发现一个问题，除了一些成员函数的返回值外，其它的部分，这两个迭代器的实现几乎一模一样，这样就出现了很多代码相同但没有很好复用的情况，处理这种情况，库里面是这样做的：

库里面模板传了两个额外的参数作为了返回值，传什么样的模板参数就决定了会实例化除出一个怎样的迭代器版本。其实两种方式生成的迭代器效果是一样的，这是通过模板实现代码复用的一种手段。

3.迭代器失效问题

list的迭代器失效主要是因为结点的删除导致其对应位置迭代器的失效，由于结点的增加并不会改变其它结点的地址等，所以结点的增加并不会带来迭代器失效的问题。

可以看到，为了支持连续删除，erase会把删除元素的下一个结点的迭代器返回，我们可以利用这个返回值进行连续删除。

namespace muss
{
    template<class T>
    class list
    {
    public:
iterator erase(iterator pos)
{
assert(pos != end());

node* prev = pos._node->_prev;
node* next = pos._node->_next;

prev->_next = next;
next->_prev = prev;

delete pos._node;

--_size;

return next;
}
private:
Node* _head;
size_t _size;
};
}

4.模拟实现整体代码

list.h

#pragma once
#include <assert.h>
namespace muss
{
template<typename T>
struct list_node
{
typedef list_node<T> node;
T _data;
node* _prev;
node* _next;

list_node(const T& data = T())
: _data(data)
, _prev(nullptr)
, _next(nullptr)
{}
};

// 模板参数:        T、                 T&、                T*
template<typename T, typename Ref, typename Ptr>
struct list_iterator
{
typedef list_node<T> node; // list节点 
typedef list_iterator<T, Ref, Ptr> Self; // 迭代器自身类型
node* _node; // 迭代器遍历的关键:存储节点地址

list_iterator(node* node)
:_node(node)
{}

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

// 详细情况在test5，迭代器的->做了特殊处理
Ptr operator->()
{
return &_node->_data;
}

// 前置++、--
Self& operator++()
{
_node = _node->_next;
return *this;
}

Self& operator--()
{
_node = _node->_prev;
return *this;
}

// 后置++、--
Self& operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}

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

bool operator==(const Self& it) const
{
return _node == it._node;
}

bool operator!=(const Self& it) const
{
return _node != it._node;
}
};


template<typename T>
class list
{
public:
typedef list_node<T> node;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
// 置空并初始化list
void empty_initialize()
{
_head = new node;
_head->_prev = _head->_next = _head;
_size = 0;
}
list()
{
empty_initialize();
}

// 支持初始化列表初始化
list(initializer_list<T> il)
{
empty_initialize();
for (auto& e : il)
{
push_back(e);
}
}

list(const list<T>& lt)
{
empty_initialize();
for (auto& e : lt)
{
push_back(e);
}
}

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

// 不能返回引用，因为是中间变量的引用，使不得
iterator begin()
{
// 返回头节点的下一个节点

// 最拉跨
//node* node = _head->_next;
//iterator ret(node);
//return ret;

// 匿名对象
//return iterator(_head->_next);

// 强制类型转化
return _head->_next;
}

iterator end()
{
return _head;
}

const_iterator begin() const
{
return _head->_next;
}

const_iterator end() const
{
return _head;
}

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

size_t size() const
{
return _size;
}


iterator insert(iterator it, const T& value = T())
{
node* newnode = new node(value);
node* prev = it._node->_prev;
node* next = it._node;
prev->_next = newnode;
newnode->_prev = prev;
next->_prev = newnode;
newnode->_next = next;
++_size;
return newnode;
}

void push_back(const T& value = T())
{
insert(end(), value);
}

void push_front(const T& value = T())
{
insert(begin(), value);
}

iterator erase(iterator pos)
{
assert(pos != end());

node* prev = pos._node->_prev;
node* next = pos._node->_next;

prev->_next = next;
next->_prev = prev;

delete pos._node;

--_size;

return next;
}

void pop_back()
{
erase(--end());
}

void pop_front()
{
erase(begin());
}

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

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

// l1 =  l2   
// 为什么能得到深拷贝：
// 传参的时候传值传参，调用自己写的拷贝构造深拷贝
// 这里lt和l2无关，交换后，释放lt也就是原来的l1，l1得到lt也就是l2的深拷贝
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}

private:
node* _head;
size_t _size;
};

template<class Container>
void print_container(const Container& con)
{
typename Container::const_iterator it = con.begin();
while (it != con.end())
{
cout << *it << " ";
++it;
}
cout << endl;


}

void list_test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(5);
lt.push_back(6);
lt.push_back(7);
lt.push_back(8);
lt.push_back(9);
lt.push_back(10);

print_container(lt);

lt.erase(lt.begin());
lt.erase(--lt.end());

list<int>::iterator ilt = lt.begin();
print_container(lt);
ilt++;
ilt++;
ilt++;
ilt++;
lt.erase(ilt);
print_container(lt);

lt.clear();
print_container(lt);

lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
print_container(lt);

lt.empty_initialize();
print_container(lt);

lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
print_container(lt);
}

void list_test2()
{
list<int> l1;
list<int> l2;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);

l2.push_back(8);
l2.push_back(8);
l2.push_back(8);
l2.push_back(8);
l2.push_back(8);
print_container(l1);
print_container(l2);

swap(l1, l2);
print_container(l1);
print_container(l2);

l2 = l1;
print_container(l1);
print_container(l2);
l1.push_back(123);
print_container(l1);
print_container(l2);
// 
}

void list_test3()
{
list<string> ls;
ls.push_back("abcdefg1");
ls.push_back("abcdefg2");
ls.push_back("abcdefg3");
ls.push_back("abcdefg4");
ls.push_back("abcdefg5");
ls.push_back("abcdefg6");

print_container(ls);
ls.push_front("haha");
print_container(ls);

ls.insert(++ls.begin(), "wohaoshuai");
print_container(ls);

ls.pop_back();
print_container(ls);

ls.pop_front();
print_container(ls);

ls.erase(++(++ls.begin()));
print_container(ls);


}

// =
void list_test4()
{
list<int> l1 = { 1,2,3,4,5 };
list<int> l2 = { 5,6,7 };
print_container(l1);
print_container(l2);
l1 = l2;
print_container(l1);
print_container(l2);
l2.push_back(15);
print_container(l1);
print_container(l2);
}

struct AA
{
int a1 = 1;
int a2 = 2;
};

// ->
void list_test5()
{
list<int> l1 = { 1,2,3,4,5 };
auto it = l1.begin();
//cout << it->
// 不能这样，下面那个存struct的地址，struct里面有元素，所以才能访问
// 而这里存int的地址，内没有元素，不能访问


list<AA> lsa;
lsa.push_back(AA());
lsa.push_back(AA());
lsa.push_back(AA());
lsa.push_back(AA());
auto ita = lsa.begin();

//Ptr operator->()
//{
//return &node->_data;
//}

// 其实是两个箭头，为了可读性而特殊处理了
cout << ita->a1 << " " << ita->a2 << endl;
cout << ita.operator->()->a1 << " " << ita.operator->()->a2 << endl;
}

void list_test6()
{
list<int> l1 = { 1,2,3,4,5 };
auto it = l1.begin();
++it;
auto ret = l1.insert(it, 7);
cout << *ret << endl;
}
}

test.cpp

#include<iostream>
#include<list>
using namespace std;

#include"List.h"

int main()
{

muss::list_test2();

return 0;
}

此博客完结~~~~~

原文地址：https://blog.csdn.net/2301_79830926/article/details/142796536

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

上一篇：LCD -
下一篇：2024年最新详解项目管理系统：让你从小白到高手的蜕变

Vivado - 在硬件中调试 Serial I/O (IBERT)
本文分享在 ZCU102 和 ZCU106 板卡上使用 IBERT Ultrascale GTY进行眼图测量的示例。
阅读更多2024-10-12
Spring Boot课程答疑：技术问题快速解答
在整个系统测试中，根据需求文档和设计文档，逐一对功能进行检测并写好测试用例，有效避免残片缺陷，因为产品出现缺陷不仅影响功能，而且可以导致数据的不准确，导致产品质量的降低，经过测试，才能使得产品的稳定性
阅读更多2024-10-12
Java后端面试----某团一面
mysql主要有有三种日志文件分别为：binlog,undolog,redolog三类binlog又称为归档日志（二进制日志），主要是对数据库的中的数据进行数据备份，崩溃恢复，数据复制等操作，binl
阅读更多2024-10-12
STM32F103C8T6 - 定时器
PSC、CNT和自动重装载寄存器构成了最基本的计时电路（时基单元），基本定时器只能选择内部时钟，所以时基单元直接连接到了内部时钟输入CK_INT。RCC的TIMxCLK一般都是系统的主频72MHz。时
阅读更多2024-10-12
java抽象类和接口-cnblog
在解决实际问题时,一般将父类作为抽象类，子类继承父类，并且实例化对象在一个类中，只要有有一个方法是抽象的，类就是抽象的抽象类被继承后需要实现所有的抽象方法，抽象类的关键词是abstract。
阅读更多2024-10-12
Mysql(八) --- 视图
前面我们学习了索引，这次我们来学习视图视图是一个虚拟的表，它是基于一个或多个基本表或其他视图的查询结果集。视图本身不存储数据，而是通过执行查询来动态生成数据。用户可以像操作普通表一样使用视图进行查询、
阅读更多2024-10-12
根据请求错误的状态码判断代理配置问题
使用雷池社区版配置代理的时候可以能会有很多的问题，配置代理可能回遇到不同的问题，这时候需要查看状态码
阅读更多2024-10-12
数据结构：单链表OJ题
相交链表、环形链表、链表随机复制（深拷贝）
阅读更多2024-10-12
yolo5快速上手训练数据集
names配置，就是lables中的类。根目录新建datasets目录。
阅读更多2024-10-12
【忆】Window 下可以ping，但是无法telnet ubuntu服务器端口
1、添加端口8096。
阅读更多2024-10-12

C++——list

前言

一、接口

二、迭代器

三、模拟实现

1.基本框架

2.迭代器处理

3.迭代器失效问题

4.模拟实现整体代码

list.h

test.cpp

相关文章