通过比较list与vector在简单模拟实现时的不同进一步理解STL的底层

🕗 发布于 2024-10-19 03:30 c++ 开发语言 算法 数据结构 c语言

cplusplus.com/reference/list/list/?kw=list

当我们大致阅读完list的cplusplus网站的文档时，我们会发现它提供的接口大致上与我们的vector相同。当然的，在常用接口的简单实现上它们也大体相同，但是它们的构造函数与迭代器的实现却大有不同。(食用本文时建议与文末的模拟实现代码一起食用，效果更佳)

一，list与vector在构造函数上的不同

1.1成员封装的不同

我们在vector中，需要封装的成员只有我们顺序表的起始指针，有效元素的末尾指针，以及用来记录空间结束位置的指针：

如果我们在list中，便无法再这样封装，因为我们的list存放数据的内存并不连续，所以我们需要对链表的节点用额外的结构体封装，而在原本的list类里面我们封装的成员则是链表的头结点：

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

};
template<class T>
class list
{
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}
typedef list_node<T> Node;
private:
Node* _head;
};

1.2迭代器的封装的不同

在vector中，迭代器可以直接简单的设置为我们存储数据类型的对应指针。但是在list中，我们发现迭代器需要指向的是一个节点，有人说那我直接照搬vector不也OK。但是这时候就会有个问题，因为我们的节点相当于一个自定义类型，后面在进行调用的时候不可避免的会去调用它的构造函数，同时我们迭代器又会有许多的函数去使用，所以迭代器也需要额外的用一个类来封装。

template<class T, class Ref, class Ptr>
struct list_iterator//tip
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
};

TIPS:这里将迭代器与结点成员设置为公开是为了方便list类的调用，实际上我们在使用list时也无法直接调用这些成员，这也是对成员的保护方式。

二，list与vector在迭代器上的不同(重点)

2.1对迭代器的const修饰

在我们的vector中，由于我们的迭代器本身就是我们存储数据的类型的相应指针，所以我们可以通过直接加const的方式来实现我们的const_iterator。但是在list中，由于我们的迭代器是指向一个自定义类型的指针，而我们的自定义类型中存储数据。如果我们直接用const来修饰，会发现我们此时无法修改迭代器指向的结点，从而无法完成我们后续的遍历。如果我们要为const来再额外封装一个类，会使代码看上去非常冗余。

在stl的源码中有着这样的几行代码：

template <class T, class Ref, class Ptr>
struct __slist_iterator : public __slist_iterator_base
{
  typedef __slist_iterator<T, T&, T*>             iterator;
  typedef __slist_iterator<T, const T&, const T*> const_iterator;
  typedef __slist_iterator<T, Ref, Ptr>           self;

  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __slist_node<T> list_node;

我们发现，它的模板参数有三个。其实由于我们的目的是为了源结点中的值无法被改变，只需要我们在返回结点中的值时加上const修饰，而我们获取存储数据的方式无非两种，一种是对迭代器解引用(其中_node是当前迭代器指向的结点)：

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

或者通过->来获取：

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

所以我们只需要对T*与T&在模板实例化时用const修饰即可：

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

TIP:在迭代器的类型中我们又分为随机，双向和单向迭代器，从左向右为父级关系。在使用库中的sort时对list无法使用快排，因为他是双向迭代器，而vector之所以可以使用是因为他是随机迭代器。

2.2list反向迭代器的实现

通过上面的多个模板参数的引出，我们可以对反向的迭代器Reverse_iterator来封装进行封装：

template<class Iterator>
class ReverseListIterator
{
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态
成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
//
// 构造
ReverseListIterator(Iterator it) : _it(it) {}
//
// 具有指针类似行为
Ref operator*() {
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->() { return &(operator*()); }
//
// 迭代器支持移动
Self& operator++() {
--_it;
return *this;
}
Self operator++(int) {
Self temp(*this);
--_it;
return temp;
}
Self& operator--() {
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
//
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it != l._it;}
Iterator _it;
};

原理其实就是我们2.1中介绍到的，这里我们直接给出模拟实现代码。

三，list与vector其他方面不同的总结(不仅是模拟实现上)

附件：list的简单模拟实现代码(常用接口)

/
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <list>
using namespace std;

namespace ELY {

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

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

template<class T,class Ref,class Ptr>
struct list_iterator//tip
{
typedef list_node<T> Node;
typedef list_iterator<T,Ref,Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}

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

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->_prev;
return tmp;
}

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


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


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

};

template<class T>
class list
{
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
public:
typedef list_node<T> Node;
typedef list_iterator<T,T&,T*> iterator;//tip
typedef list_iterator<T,const T&,const T*> const_iterator;//tip
list()
{
empty_init();
}

list(const list<T>& list)
{
empty_init();
for (auto i : list)
{
push_back(i);
}
}

list<T>& operator=(list<T> list)
{
swap(list);
return *this;
}

list(size_t n, const T& val = T())
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}

iterator begin()
{
return iterator(_head->_next);
}

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

iterator end() 
{
return iterator(_head);
}

const_iterator end() const
{
return const_iterator(_head);
}


void push_back(const T& x = T())
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;

newnode->_next = _head;
newnode->_prev = tail;

tail->_next = newnode;
_head->_prev = newnode;
}

iterator insert(iterator pos, const T& val)//tip
{
Node* newnode = new Node(val);
Node* cur = pos._node;

cur->_prev->_next = newnode;
newnode->_prev = cur->_prev;

cur->_prev = newnode;
newnode->_next = cur;
return iterator(newnode);
}

iterator push_front(const T& val)
{
return insert(begin(), val);
}

iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;

cur->_next->_prev = cur->_prev;
cur->_prev->_next = cur->_next;

pos = cur->_next;
delete cur;

return pos;
}

iterator pop_front()
{
return erase(begin());
}

iterator pop_back()
{
return erase(--end());
}

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

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

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

private:
Node* _head;
};
}
/
mylist.h

原文地址：https://blog.csdn.net/xiuwoaiailixiya/article/details/143061584

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

上一篇：【C++】unordered_set、unordered_map超详细封装过程，处理底层细节
下一篇：昨天今天明天-《分析模式》漫谈40

大数据研究实训室建设方案
大数据项目实训平台作为一个通用的项目实训管理系统，具有高度的灵活性和可扩展性，能够根据学校或机构的特定需求进行定制，内置大数据、云计算和人工智能等领域的实训实战课程资源。实训室将专注于培养学生在大数据
阅读更多2024-10-19
ollama上传本地模型到仓库
一定要添加ollama的密钥，不然上传的时候会报错登录上之后找到设置然后加入你电脑上的ollama的key。
阅读更多2024-10-19
通过PHP与API的结合，开启电商数据集成的新篇章
在数字化转型的浪潮中，电子商务数据的集成对于企业来说变得越来越重要。PHP，作为服务端脚本语言的佼佼者，为开发者提供了强大的工具和库来实现与电商API的无缝对接。通过掌握API调用，PHP开发者可以轻
阅读更多2024-10-19
Java爬虫：API接口数据爬取入门详解及示例代码
API接口数据爬取是Java爬虫技术的一个重要应用领域。通过使用Java的HTTP客户端库和数据解析库，我们可以高效地从API接口获取数据，并进行进一步的分析和应用。掌握这些技能，将使你在数据获取和处
阅读更多2024-10-19
VUE传递字符串显示二维码
1.安装插件npm install vue-qrcode2.使用<script setup lang="ts">import { ref } from
阅读更多2024-10-19
智能指针(3)
我们会发现如果使用的是普通的开辟在栈里面的成员变量或者静态的全局变量都是跟着智能指针走的，但是我们的引用计数计数的是一个空间被多少个智能指针管理着，所以这个计数是肯定要跟着被管理的空间走的，以上两种表
阅读更多2024-10-19
C#两个窗体之间传递参数
C#两个窗体之间传递参数
阅读更多2024-10-19
【C#】使用Visual Studio创建Windows Forms应用程序计算对角线之和
118 Pages（2）课后练习题
阅读更多2024-10-19
DFS算法经典题目： Leetcode 51.N皇后
题目详情如下这道题如果使用暴力解法的话，需要对N个皇后放在每个地方都进行枚举并判断是否可行，时间复杂度非常之高，肯定是过不了的，所以需要使用其他解法。根据题目可以知道每两个皇后之间的位置关系不能是在同
阅读更多2024-10-19
Mybatis多对一查询的配置及两种方法的使用示例对比以及Mybatis一对多查询两种方法使用示例及对比
同多对一的查询一样，mapper.xml配置中使用子查询嵌套的方法在SQL执行的时候会进行多次查询，最终查询次数和取得的行数成正比增加。City(id=0, cityname=北京, areaList
阅读更多2024-10-19