【C++ 学习 ⑬】- 详解 list 容器

目录

一、list 容器的基本介绍

二、list 容器的成员函数

2.1 - 迭代器

2.2 - 修改操作

三、list 的模拟实现

3.1 - list.h

3.2 - 详解 list 容器的迭代器

3.2 - test.cpp

 

一、list 容器的基本介绍

list 容器以类模板 list<T>（T 为存储元素的类型）的形式定义在 <list> 头文件中，并位于 std 命名空间中。

template < class T, class Alloc = allocator<T> > class list;    

list 是序列容器，允许在序列内的任意位置高效地插入和删除元素（时间复杂度是 O(1) 常数阶），其迭代器类型为双向迭代器（bidirectional iterator）。

list 容器的底层是以双向链表的形式实现的。

list 容器与 forward_list 容器非常相似，最主要的区别在于 forward_list 容器的底层是以单链表的形式实现的，其迭代器类型为前向迭代器（forward iterator）。

与其他标准序列容器（array、vector 和 deque）相比，list 容器在序列内已经获得迭代器的任意位置进行插入、删除元素时通常表现得更好。

与其他序列容器相比，list 容器和 forward_list 容器的最大缺点是不支持任意位置的随机访问，例如：要访问 list 中的第 6 个元素，必须从已知位置（比如头部或尾部）迭代到该位置，这需要线性阶的时间复杂度的开销。

二、list 容器的成员函数

2.1 - 迭代器

begin：

      iterator begin();
const_iterator begin() const;

end:

      iterator end();
const_iterator end() const;

rbegin：

      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

rend：

      reverse_iterator rend();
const_reverse_iterator rend() const;

示例：

#include <iostream>
#include <list>
using namespace std;
​
int main()
{
    list<int> l;
    l.push_back(0);
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
​
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
    }
    // 0 1 2 3 4
    cout << endl;
​
    for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit)
    {
        cout << *rit << " ";
    }
    // 4 3 2 1 0
    cout << endl;
    return 0;
}

 

2.2 - 修改操作

push_front：

void push_front(const value_type& val);

注意：value_type 等价于 T。

pop_front：

void pop_front();

push_back：

void push_back(const value_type& val);

pop_back：

void pop_back();

insert：

// C++ 98
single element (1) iterator insert(iterator position, const value_type& val);
          fill (2)     void insert(iterator position, size_type n, const value_type& val);
         range (3) template <class InputIterator>
                       void insert(iterator position, InputIterator first, InputIterator last);

相较于 vector，执行 list 的 insert 操作不会产生迭代器失效的问题。

示例一：

#include <iostream>
#include <list>
using namespace std;
​
int main()
{
    list<int> l;
    l.push_back(0);
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
​
    // 要求：在第三个元素前面插入元素 100
    // l.insert(l.begin() + 2, 100);  // error
    // 因为 list 对应的迭代器类型为双向迭代器，所以不支持加法操作，即没有重载该运算符
​
    // 解决方案：
    list<int>::iterator it = l.begin();
    for (size_t i = 0; i < 2; ++i)
    {
        ++it;
    }
    l.insert(it, 100);
​
    for (auto e : l)
    {
        cout << e << " ";
    }
    // 0 1 100 2 3 4
    cout << endl;
    return 0;
}

erase：

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

因为节点被删除后，空间释放了，所以执行完 list 的 erase 操作，迭代器就失效了，而解决方案依然是通过返回值对迭代器进行重新赋值。

示例二：

#include <iostream>
#include <list>
using namespace std;
​
int main()
{
    list<int> l;
    l.push_back(0);
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
​
    // 删除 list 中所有值为偶数的元素
    list<int>::iterator it = l.begin();
    while (it != l.end())
    {
        if (*it % 2 == 0)
            it = l.erase(it);  // 直接写 l.erase(it); 会报错
        else
            ++it;
    }
​
    for (auto e : l)
    {
        cout << e << " ";
    }
    // 1 3
    cout << endl;
    return 0;
}

三、list 的模拟实现

3.1 - list.h

#pragma once
​
#include <iostream>
#include <assert.h>
​
namespace yzz
{
    template<class T>
    struct __list_node
    {
        __list_node<T>* _prev;
        __list_node<T>* _next;
        T _data;
​
        __list_node(const T& val = T())
            : _prev(0), _next(0), _data(val)
        { }
    };
​
​
    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T, Ref, Ptr> self;
        typedef __list_node<T> list_node;
        list_node* _pnode;  // 节点指针
​
        __list_iterator(list_node* p = 0)
            : _pnode(p)
        { }
​
        self& operator++()
        {
            _pnode = _pnode->_next;
            return *this;
        }
​
        self operator++(int)
        {
            self tmp(*this);
            _pnode = _pnode->_next;
            return tmp;
        }
​
        self& operator--()
        {
            _pnode = _pnode->_prev;
            return *this;
        }
​
        self operator--(int)
        {
            self tmp(*this);
            _pnode = _pnode->_prev;
            return tmp;
        }
​
        Ref operator*() const
        {
            return _pnode->_data;
        }
​
        Ptr operator->() const
        {
            return &_pnode->_data;
        }
​
        bool operator!=(const self& it) const
        {
            return _pnode != it._pnode;
        }
​
        bool operator==(const self& it) const
        {
            return _pnode == it._pnode;
        }
    };
​
​
    template<class T>
    class list
    {
    private:
        typedef __list_node<T> list_node;
​
        void empty_initialize()
        {
            _phead = new list_node;
            _phead->_prev = _phead;
            _phead->_next = _phead;
        }
​
    public:
        /*-------- 构造函数和析构函数 --------*/
        list()
        {
            empty_initialize();
        }
​
        list(const list<T>& l)  // 实现深拷贝
        {
            empty_initialize();
            for (auto& e : l)
            {
                push_back(e);
            }
        }
​
        ~list()
        {
            clear();
            delete _phead;
            _phead = 0;
        }
​
        /*-------- 赋值运算符重载 --------*/
        // 利用上面写好的拷贝构造函数实现深拷贝
        void swap(list<T>& l)
        {
            std::swap(_phead, l._phead);
        }
​
        list<T>& operator=(list<T> tmp)
        {
            swap(tmp);
            return *this;
        }
​
        /*-------- 迭代器 --------*/
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        
        iterator begin()
        {
            return _phead->_next;
            // 等价于：return iterator(_phead);
            // 返回的过程中发生了隐式类型转换
        }
​
        iterator end()
        {
            return _phead;
        }
​
        const_iterator begin() const
        {
            return _phead->_next;
            // 等价于：return const_iterator(_phead->_next);
        }
​
        const_iterator end() const
        {
            return _phead;
        }
​
        /*-------- 容量操作 --------*/
        size_t size() const
        {
            size_t sz = 0;
            list_node* cur = _phead->_next;
            while (cur != _phead)
            {
                ++sz;
                cur = cur->_next;
            }
            return sz;
        }
​
        bool empty() const
        {
            return _phead->_next == _phead;
        }
​
        /*-------- 修改操作 --------*/
        iterator insert(iterator pos, const T& val)
        {
            list_node* newnode = new list_node(val);
            newnode->_prev = pos._pnode->_prev;
            newnode->_next = pos._pnode;
​
            pos._pnode->_prev->_next = newnode;
            pos._pnode->_prev = newnode;
            return newnode;
        }
​
        void push_back(const T& val)
        {
            // 方法一：
            /*list_node* newnode = new list_node(val);
            newnode->_prev = _phead->_prev;
            newnode->_next = _phead;
​
            _phead->_prev->_next = newnode;
            _phead->_prev = newnode;*/
​
            // 方法二（直接复用）：
            insert(end(), val);
        }
​
        void push_front(const T& val)
        {
            // 方法一：
            /*list_node* newnode = new list_node(val);
            newnode->_prev = _phead;
            newnode->_next = _phead->_next;
​
            _phead->_next->_prev = newnode;
            _phead->_next = newnode;*/
​
            // 方法二（直接复用）：
            insert(begin(), val);
        }
​
        iterator erase(iterator pos)
        {
            assert(pos != end());  // 前提是 list 非空
            list_node* prev_pnode = pos._pnode->_prev;
            list_node* next_pnode = pos._pnode->_next;
            prev_pnode->_next = next_pnode;
            next_pnode->_prev = prev_pnode;
            delete pos._pnode;
            return iterator(next_pnode);
        }
​
        void pop_back()
        {
            erase(--end());
        }
​
        void pop_front()
        {
            erase(begin());
        }
​
        void clear()
        {
            list_node* cur = _phead->_next;
            while (cur != _phead)
            {
                list_node* tmp = cur;
                cur = cur->_next;
                delete tmp;
            }
            _phead->_prev = _phead->_next = _phead;
        }
​
    private:
        list_node* _phead;  // 头指针
    };
}

3.2 - 详解 list 容器的迭代器

我们可以通过循序渐进的方式来了解 list 容器的迭代器：

  1. 首先，不能使用原生态指针直接作为 list 容器的正向迭代器，即：

    typedef list_node* iterator;

    否则当正向迭代器进行 ++/-- 操作时，无法让它指向下一个或上一个节点，并且进行解引用 * 操作时，无法直接获得节点的值，所以需要对原生态指针进行封装，然后对这些操作符进行重载，即：

    typedef __list_iterator<T> iterator;

  2. 其次，不能按以下方式直接定义 list 容器的常量正向迭代器，即：

    typedef const __list_iterator<T> const_iterator;

    否则常量正向迭代器就无法进行 ++/-- 操作，因为 const 类对象只能去调用 const 成员函数，并且 operator* 的返回值类型为 T&，即仍然可以在外部修改 list 容器。

    可以重新定义一个常量正向迭代器 __list_const_iterator，但需要修改的地方仅仅是 operatr* 的返回值，即将其修改为 const T&，显然这样的解决方案会造成代码的冗余，所以在 __list_iterator 类模板中增加一个类型参数 Ref，将 operator* 的返回值修改为 Ref，即：

    typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;

  3. 最后，在重载 -> 操作符时，对于正向迭代器，返回值类型应该是 T*，对于常量正向迭代器，返回值类型应该是 const T*，所以再增加一个类型参数 Ptr，将 operator-> 的返回值类型修改为 Ptr，即：

    typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

3.2 - test.cpp

#include "list.h"
#include <iostream>
using namespace std;
​
void Print1(const yzz::list<int>& l)
{
    yzz::list<int>::const_iterator cit = l.begin();
    while (cit != l.end())
    {
        cout << *cit << " ";
        ++cit;
    }
    cout << endl;
}
​
void test_list1()
{
    yzz::list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);
    cout << l1.size() << endl;  // 4
    yzz::list<int> l2(l1);
    for (yzz::list<int>::iterator it = l2.begin(); it != l2.end(); ++it)
    {
        cout << *it << " ";
    }
    // 1 2 3 4
    cout << endl;
​
    l1.push_front(10);
    l1.push_front(20);
    l1.push_front(30);
    l1.push_front(40);
    cout << l1.size() << endl;  // 8
    yzz::list<int> l3;
    l3 = l1;
    for (auto& e : l3)
    {
        cout << e << " ";
    }
    // 40 30 20 10 1 2 3 4
    cout << endl;
​
    l1.pop_back();
    l1.pop_back();
    l1.pop_front();
    l1.pop_front();
    cout << l1.size() << endl;  // 4
    Print1(l1);
    // 20 10 1 2
​
    l1.clear();
    cout << l1.size() << endl;  // 0
    cout << l1.empty() << endl;  // 1
}
​
struct Point
{
    int _x;
    int _y;
​
    Point(int x = 0, int y = 0)
        : _x(x), _y(y)
    { }
};
​
void Print2(const yzz::list<Point>& l)
{
    yzz::list<Point>::const_iterator cit = l.begin();
    while (cit != l.end())
    {
        // 方法一：
        // cout << "(" << (*cit)._x << ", " << (*cit)._y << ")" << " ";
        
        // 方法二：
        cout << "(" << cit->_x << ", " << cit->_y << ")" << " ";
        // 注意：operator-> 是单参数，所以本应该是 cit->->_i 和 cit->->_j，
        // 但为了可读性，编译器做了优化，即省去一个 ->
        ++cit;
    }
    cout << endl;
}
​
void test_list2()
{
    yzz::list<Point> l;
    l.push_back(Point(1, 1));
    l.push_back(Point(2, 2));
    l.push_back(Point(3, 3));
    l.push_back(Point(4, 4));
    Print2(l);
    // (1, 1) (2, 2) (3, 3) (4, 4)
}
​
int main()
{
    // test_list1();
    test_list2();
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/72674.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

计算机网络 网络层 路由 路由信息协议RIP

计算机网络 网络层 路由 路由信息协议RIP

阅读更多...
RabbitMQ工作流程详解

RabbitMQ工作流程详解

1 生产者发送消息的流程 (1)生产者连接RabbitMQ&#xff0c;建立TCP连接(Connection)&#xff0c;开启信道(Channel) (2)生产者声明一个Exchange (交换器)&#xff0c;并设置相关属性&#xff0c;比如交换器类型、是否持久化等 (3)生产者声明一个队列井设置相关属性&#xf…
阅读更多...
计算机网络 网络层 IPv4数据报

计算机网络 网络层 IPv4数据报

阅读更多...
IoTDB 1.x 开启外部访问

IoTDB 1.x 开启外部访问

对于部署的IoTDB数据库&#xff0c;如果需要局域网内其他设备进行访问的处理。 1、防火墙开放端口 无论windows还是liunx都需要你将6667默认的端口加入防火墙中&#xff0c;否则肯定是无法访问端口 2、修改配置文件 对conf/iotdb-datanode.properties文件中的 修改为本机的…
阅读更多...
接口测试实战，Jmeter正则提取响应数据-详细整理，一篇打通...

接口测试实战，Jmeter正则提取响应数据-详细整理，一篇打通...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在测试时&#xf…
阅读更多...
最新AI创作系统ChatGPT程序源码+详细搭建部署教程+微信公众号版+H5源码/支持GPT4.0+GPT联网提问/支持ai绘画+MJ以图生图+思维导图生成！

最新AI创作系统ChatGPT程序源码+详细搭建部署教程+微信公众号版+H5源码/支持GPT4.0+GPT联网提问/支持ai绘画+MJ以图生图+思维导图生成！

使用Nestjs和Vue3框架技术&#xff0c;持续集成AI能力到系统&#xff01; 新增 MJ 官方图片重新生成指令功能同步官方 Vary 指令 单张图片对比加强 Vary(Strong) | Vary(Subtle)同步官方 Zoom 指令 单张图片无限缩放 Zoom out 2x | Zoom out 1.5x新增GPT联网提问功能、手机号注…
阅读更多...
静态网页和动态网页区别

静态网页和动态网页区别

1&#xff0c;静态网页和动态网页有何区别 1) 更新和维护 静态网页内容一经发布到网站服务器上&#xff0c;无论是否有用户访问&#xff0c;这些网页内容都是保存在网站服务器上的。如果要修改网页的内容&#xff0c;就必须修改其源文件&#xff0c;然后重新上传到服务器上。…
阅读更多...
【C语言】每日一题（错误的集合）

【C语言】每日一题（错误的集合）

最近在牛客、力扣上做题&#xff0c;花费海量时间&#xff0c;苦不堪言&#xff0c;有时绞尽脑汁也想不出&#xff0c;痛定思痛&#xff0c;每日记录写的比较困难的题。 错误的集合 题目如上图所示 题主乍看之下觉得很简单&#xff0c;再看例子&#xff0c;不就是一个有序数组…
阅读更多...
线性回归学习总结

线性回归学习总结

一 、引文 1 回归分析 回归是统计学上用来分析数据的方法&#xff0c;以了解两个或多个变量之前的关系。通常是建立被解释变量Y和解释变量X之间关系的模型。回归分析的最早形式是最小二乘法。 勒让德和高斯都将该方法应用于从天文观测中确定关于太阳的物体的轨道&#xff08;…
阅读更多...
adb 通过wifi连接手机

adb 通过wifi连接手机

adb 通过wifi连接手机 1. 电脑通过USB线连接手机2. 手机开启USB调试模式&#xff0c;开启手机开发者模式3.手机开启USB调试模式 更多设置-》开发者选项-》USB调试4.点击Wi-Fi 高级设置&#xff0c;可以查看到手机Wi-Fi的IP地址&#xff0c;此IP地址adb命令后面的ip地址&#xf…
阅读更多...
百度云盘发展历程与影响

百度云盘发展历程与影响

摘要&#xff1a; 百度云盘作为中国领先的云存储与共享服务提供商&#xff0c;自其创立至今经历了多个阶段的发展与变革。本论文通过对百度云盘的历史回顾与分析&#xff0c;探讨了其在技术、商业模式、用户体验以及对社会的影响等方面的演变。同时&#xff0c;还分析了在竞争激…
阅读更多...
横向移动-域控提权

横向移动-域控提权

横向移动-域控提权 CVE-2021-42287 由于Active Directory没有对域中计算机和服务器账号进行验证&#xff0c;经过身份验证的攻击者利用该漏洞绕过完全限制&#xff0c;可将域中普通用户权限提升为域管理员权限并执行任意代码。 利用条件 前提条件&#xff1a;一个域内普通账…
阅读更多...
计算机基础概论

计算机基础概论

一、计算机的组成 1.计算机组成的五大部件 &#xff08;1&#xff09;运算器&#xff1a;也叫算术逻辑单元&#xff0c;完成对数据的各种常规运算&#xff0c;如加减乘除&#xff0c;也包括逻辑运算&#xff0c;位移&#xff0c;比较等。 &#xff08;2&#xff09;控制器&a…
阅读更多...
计算机网络-物理层（一）物理层的概念与传输媒体

计算机网络-物理层（一）物理层的概念与传输媒体

计算机网络-物理层&#xff08;一&#xff09;物理层的概念与传输媒体 物理层相关概念 物理层的作用用来解决在各种传输媒体上传输比特0和1的问题&#xff0c;进而为数据链路层提供透明(看不见)传输比特流的服务物理层为数据链路层屏蔽了各种传输媒体的差异&#xff0c;使数据…
阅读更多...
图像的镜像变换之c++实现（qt + 不调包）

图像的镜像变换之c++实现（qt + 不调包）

1.基本原理 1.水平镜像变化 设图像的宽度为width&#xff0c;则水平镜像变化的映射关系如下&#xff1a; 2.垂直镜像变化 设图像的宽度为height&#xff0c;则垂直镜像变化的映射关系如下&#xff1a; 2.代码实现&#xff08;代码是我以前自学图像处理时写的&#xff0c;代码很…
阅读更多...
Kotlin和Java互操作时的可空性

Kotlin和Java互操作时的可空性

注&#xff1a;文中demo的kt版本是1.7.10 一、kotlin语言中的可空性设计 在Java语言中的NPE&#xff08;NullPointerException&#xff09;可以说非常常见&#xff0c;而且诟病已久。 kotlin做为后起之秀&#xff0c;在空指针的问题上进行了升级&#xff0c;即&#xff1…
阅读更多...
Linux_5_Shell脚本编程

Linux_5_Shell脚本编程

目录 1 基础1.1 程序组成1.2 程序编程风格1.3 编程语言1.4 编程逻辑处理方式 2 shell 脚本语言的基本结构2.1 shell脚本的用途2.2 shell脚本基本结构2.3 创建shell脚本过程2.4 脚本注释规范2.5 第一个脚本2.6 脚本调试2.7 变量2.7.1 变量2.7.2 变量类型2.7.3 编程语言分类2.7.4…
阅读更多...
popen/pclose 函数

popen/pclose 函数

函数作用 如果说system在一定程度上是execl的优化版&#xff0c;那么popen就一定程度上是system的优化版&#xff0c;使用popen不仅可以运行代码&#xff0c;还可以获取运行的输出结果&#xff08;但是system和exec族函数还是非常重要的&#xff0c;也有自己的特定应用场景&am…
阅读更多...
python_day19_正则表达式

python_day19_正则表达式

正则表达式re模块 导包 import res "python java c c python2 python python3"match 从头匹配 res re.match("python", s) res_2 re.match("python2", s) print("res:", res) print(res.span()) print(res.group()) print("…
阅读更多...
Docker安装nacos v2.1.1

Docker安装nacos v2.1.1

目录 前言安装nacos安装步骤1&#xff1a;准备1. 安装docker2. 搜索可以使用的镜像。3. 选择合适的redis镜像。3. 也可从docker hub上搜索镜像。 安装步骤2&#xff1a;拉取镜像拉取镜像查看已拉取的镜像 安装步骤3&#xff1a;创建容器创建容器方式1&#xff1a;快速创建容器创…
阅读更多...
最新文章

Copyright @ 2022~2023