【C++精华铺】12.STL list模拟实现

🕗 发布于 2024-07-16 13:38 c++ list 开发语言 stl

1.序言

STL (Standard Template Library)是C++标准库中的一个重要组件，提供了许多通用的数据结构和算法。其中，STL list是一种带头双向链表容器，可以存储任意类型的元素。

list的特点包括：

双向性：list中的元素可以根据需要在前向和后向方向上进行遍历和访问。

动态大小：list的大小可以根据需要动态增长和收缩，不像数组需要预先定义大小。

高效的插入和删除：在list中插入或删除元素的操作非常高效，时间复杂度为常数时间。

不支持随机访问：由于list的实现是基于链表的，所以不支持随机访问，只能通过遍历来访问指定位置的元素。

list提供了一系列的成员函数来操作元素，包括：

push_back()和push_front()：分别在list的尾部和头部插入一个元素。

pop_back()和pop_front()：分别删除list的尾部和头部的元素。

insert()：在指定位置插入一个或多个元素。

erase()：删除指定位置的一个或多个元素。

size()：返回list中元素的个数。

empty()：判断list是否为空。

值得注意的是，由于list是双向链表，所以在内存上的开销相对较大，而且无法通过下标直接访问元素。因此，在选择容器时需要根据实际需求进行权衡。

2.list整体结构

template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _Data;
list_node(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _Data(x)
{}
};

template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> iterator;     
node* _node; 
      //···········
};

template<class T>
class list
{
typedef list_node<T> node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
//······
private:
node* _head;

};

3.list迭代器

3.1 operator*()

operator*() 返回的是list某节点存储的数据，并且返回时要能修改数据，所以返回类型是T&（Ref：是个模板参数，兼顾 T& 和 const T &，用哪个传那个）。

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

3.2 operator->()

operator->() 用于取list存储的数据对象里面的属性，也是模拟指针的行为，返回数据对象的地址。

Ptr operator->()
{
return &_node->_Data;
}

需要注意的是如果我们使用这个 -> 的运算符重载，假设一迭代器对象 it ：it.operator->()->(某属性) 等价于 it->->(某属性) ，这里实际上有俩个 -> ,为了增加代码的可读性，这里进行了特殊处理，优化成了一个 -> ：it->(某属性) 。

3.3 operator++() 和 operator++(int)、operator--() 和 operator--(int)

operator++()（operator--()）是前置++（--），返回++（--）后的值，operator++(int)（operator--()）是后置++（--），返回++前的值（--）。

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

3.4 operator==() 和 operator!=()

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

3.5 迭代器完整代码

template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _Data;
list_node(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _Data(x)
{}
};

template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> iterator;
__list_iterator(node* n)
:_node(n)
{}
Ref operator*()
{
return _node->_Data;
}
Ptr operator->()
{
return &_node->_Data;
}

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

bool operator==(const iterator& it)
{
return _node == it._node;
}
bool operator!=(const iterator& it)
{
return _node != it._node;
}
node* _node; 
};

4.list接口

4.1构造函数

list()
{
_head = new node;
_head->_next = _head->_prev = _head;
}

~list()
{
while (end() != _head)
{
erase(end());
}
delete _head;
_head = nullptr;
}
template<class Iterator>
list(Iterator first, Iterator last)
{
_head = new node;
_head->_next = _head->_prev = _head;

while (first != last)
{
push_back(*first);
first++;
}
}

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

list(const list<T>& l)
{
_head = new node;
_head->_next = _head->_prev = _head;

list<T> tmp(l.begin(), l.end());
swap(tmp);
}

4.2 push_back() push_front() pop_back() pop_front()

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

node* newnode = new node(x);
newnode->_prev = tail;
newnode->_next = tail->_next;
tail->_next = newnode;
_head->_prev = newnode;
}

void push_front(const T& x)
{
node* head = _head->_next;

node* newnode = new node(x);
newnode->_prev = _head;
newnode->_next = head;
_head->_next = newnode;
head->_prev = newnode;

}
void pop_back()
{
node* tail = _head->_prev;

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

delete tail;
}
void pop_front()
{
node* head = _head->_next;

_head->_next = head->_next;
head->_next->_prev = _head;

delete head;
}

4.3迭代器

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

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

4.4 insert() 和 erase()

注意erase的迭代器失效，需要更新pos

void insert(iterator pos, const T& x)
{
node* cur = pos._node;
node* newnode = new node(x);

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

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;

return iterator(next);
}

5. list完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std; 
namespace zy
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _Data;
list_node(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _Data(x)
{}
};

template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> iterator;
__list_iterator(node* n)
:_node(n)
{}
Ref operator*()
{
return _node->_Data;
}
Ptr operator->()
{
return &_node->_Data;
}

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

bool operator==(const iterator& it)
{
return _node == it._node;
}
bool operator!=(const iterator& it)
{
return _node != it._node;
}
node* _node; 
};


template<class T>
class list
{
typedef list_node<T> node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

list()
{
_head = new node;
_head->_next = _head->_prev = _head;
}

~list()
{
while (end() != _head)
{
erase(end());
}
delete _head;
_head = nullptr;
}
template<class Iterator>
list(Iterator first, Iterator last)
{
_head = new node;
_head->_next = _head->_prev = _head;

while (first != last)
{
push_back(*first);
first++;
}
}

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

list(const list<T>& l)
{
_head = new node;
_head->_next = _head->_prev = _head;

list<T> tmp(l.begin(), l.end());
swap(tmp);
}

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

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

node* newnode = new node(x);
newnode->_prev = tail;
newnode->_next = tail->_next;
tail->_next = newnode;
_head->_prev = newnode;
}

void push_front(const T& x)
{
node* head = _head->_next;

node* newnode = new node(x);
newnode->_prev = _head;
newnode->_next = head;
_head->_next = newnode;
head->_prev = newnode;

}
void pop_back()
{
node* tail = _head->_prev;

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

delete tail;
}
void pop_front()
{
node* head = _head->_next;

_head->_next = head->_next;
head->_next->_prev = _head;

delete head;
}

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

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

void insert(iterator pos, const T& x)
{
node* cur = pos._node;
node* newnode = new node(x);

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

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;

return iterator(next);
}
private:
node* _head;

};
}

原文地址：https://blog.csdn.net/qq_64293926/article/details/140388034

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

上一篇：安卓学习中遇到的问题【bug】
下一篇：ensp综合实验

【C++】list 类深度解析：探索双向链表的奇妙世界
本文深度解析了 C++ 标准库中的 list 类。首先阐述学习 list 类的原因，其具有高效插入删除操作优势，如双向链表结构使插入删除只需调指针，时间复杂度常数级；内存管理灵活，节点分散存储避免内存
阅读更多2024-11-16
常用List工具类（取交集、并集等等）
【代码】常用List工具类（取交集、并集等等）
阅读更多2024-11-16
宝塔面板从 Nginx 切换到 Caddy：详细教程
宝塔面板从 Nginx 切换到 Caddy
阅读更多2024-11-16
计算机网络中的数据包传输机制详解
数据包是网络通信的基本单位，它包含了控制信息（如源地址、目的地址等）和用户数据（即有效载荷）。根据不同的网络协议，数据包的结构会有所不同。数据包的传输机制是计算机网络的核心内容之一，它涉及到数据的封装
阅读更多2024-11-16
LinkedList 源码分析
仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n)。底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现。是一
阅读更多2024-11-16
【泛型 Plus】Kotlin 的加强版类型推断：@BuilderInference
视频先行下面是视频内容的脚本文案原稿分享。小剧场面试官：「既然协程和泛型你都熟悉，flow() 函数是怎么实现类型推断的有了解过吗？」求职者：「嗯……」求职者：「嗯……在Kotlin协程中，flow
阅读更多2024-11-16
20.UE5UI预构造，开始菜单
如果我们直接再画布上设计我们的按钮，我们需要为每一个按钮进行编辑，复用性太差，能不能在其他的UI蓝图中编辑好，随后就好像其他元素（文本，button）一样，直接放入到我们的画布中？为了在复用时，可以自
阅读更多2024-11-16
支持向量机SVM——基于分类问题的监督学习算法
支持向量机SVM是一种常用于分类问题的监督学习算法。文章主要从基础公式角度讲解它的基本原理，涉及线性和非线性情况。
阅读更多2024-11-16
鸿蒙生态下的安全隐私保护：打造用户信任的应用体验
作为开发者，在享受鸿蒙生态系统带来的广阔市场机遇的同时，也面临着保障用户数据安全和隐私保护的重要责任。同时，开发者需要向用户提供清晰的信息收集和使用的说明，让用户了解自己的数据如何被使用。总的来说，在
阅读更多2024-11-16
基本数据类型：Kotlin、Dart (Flutter)、Java 和 C++ 的比较
本文比较了 Kotlin、Dart (Flutter)、Java 和 C++ 中的基本数据类型，并探讨了有符号和无符号整数的区别。文章还详细解释了二进制补码的计算方式和其在计算机系统中的应用。理解这些
阅读更多2024-11-16