C++_STL之list篇

Ne0inhk

— 11 min read
C++_STL之list篇

一、list的介绍

  std::list是C++标准模板库(STL)中的一个双向链表容器。与vector和deque不同，list不支持随机访问，但它在任何位置插入和删除元素都非常高效。

1.基本特性

(1)双向链表结构：每个元素都包含指向前驱和后继的指针

(2)非连续存储：元素分散存储在内存中，通过指针连接

(3)时间复杂度：

        任意位置插入/删除：O(1)

        随机访问：O(n)

        遍历：O(n)

二、list常用操作

        我这里就通过调试来带大家看一下每个函数的效果。

1.创建和构造

        列举了一些list构造时的基础用法.

#include <iostream> #include <list> using namespace std; int main() { list<int> l1; // 空list list<int> l2(5); // 包含5个默认构造的元素(0) list<int> l3(5, 10); // 包含5个值为10的元素 list<int> l4 = { 1, 2, 3 }; // 初始化列表 list<int> l5(l4); // 拷贝构造 list<int> l6(l5.begin(), l5.end()); // 通过迭代器范围构造 return 0; }

        

2.迭代器

由于list不支持随机访问，只能通过迭代器或front/back方法访问元素：

list<int> l = { 1, 2, 3, 4, 5 }; cout << l.front()<<endl; // 第一个元素 (1) cout << l.back()<<endl; // 最后一个元素 (5) // 遍历list for (auto it = l.begin(); it != l.end(); ++it) { cout << *it << " "; } cout << endl; // C++11起可用范围for循环 for (int val : l) { cout << val << " "; } return 0;

 迭代器构造：

3.拷贝构造

4.clear()

        效果：清空链表中所有数据。

5.size()

        返回链表中节点的个数

6.push_back(const T& x)

        在链表尾部插入值为x的节点。

7.push_front(const T& x)

        在链表头部插入值为x的节点。

8.insert(iterator pos, const T& x)

        在第pos个位置插入值为x的节点。

9.pop_back()

        删除尾部元素

10.pop_front()

        删除头部元素

11.erase(iterator pos)

        删除第pos位置的元素

三、list的模拟实现

1.构造函数

        首先我们可以通过STL库学习一下list的基本实现方法，然后自己根据SLTL库中的代码模拟实现一个list。

        通过库中代码，我们需要先实现出list底层节点的模板以及迭代器所需要的模板，然后在构造函数。代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include <assert.h> namespace lwf { //创建模板结构体 template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _val; list_node(const T& val = T()) :_next(nullptr) , _prev(nullptr) , _val(val) {} }; //创建模板结构体 template<class T, class Ref, class Ptr> struct _list_iterator { typedef list_node<T> Node; typedef _list_iterator<T, Ref, Ptr> self; Node* _node; _list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& it) { return _node != it._node; } bool operator==(const self& it) { return _node == it._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; void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; } list() { empty_init(); } list(const list<T>& It) { empty_init(); for (auto& e : It) { push_back(e); } } private: Node* _head; size_t _size; }; }

2.迭代器

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

3.拷贝构造

        拷贝构造的实现就是将原有的list变量拷贝给被拷贝对象深拷贝。

 list(const list<T>& It) { empty_init(); for (auto& e : It) { push_back(e); } } void swap(list<T> It) { std::swap(_head, It._head); std::swap(_size, It._size); } list<T>& operator=(list<T> It) //list& operator=(list<T> It) 这样写也可以 { swap(It); return *this; }

4.clear()

        通过迭代器来将list中元素逐个删除

 void clear() { iterator it=begin(); while (it != end()) { it = erase(it); } _size = 0; }

5.size()

        返回内部元素_size（_size一直是在统计list中元素的个数）即可。

 size_t size() { return _size; }

6.insert(iterator pos, const T& x)

        首先需要创建一个新节点，然后通过双链表结构的思路将节点插入所需要插入的位置，双链表在前面的博客中有实现过，需要的可自行查看。。

 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; cur->_prev = newnode; newnode->_next = cur; ++_size; //解决迭代器失效问题 return newnode; }

7.push_back(const T& x)

        在list尾部插入x，此时我们这里可以巧妙的运用上面的insert(iterator pos, const T& x)函数来实现。

 void push_back(const T& x) { /*Node* tail = _head->_prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); }

8.push_front(const T& x)

        在list头部插入x，此时我们这里也可以巧妙的运用上面的insert(iterator pos, const T& x)函数来实现。

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

9.erase(iterator pos)

        删除list中pos位置的元素，这里的思路其实同双链表的删除操作一样，前面的博客中有实现过，需要的可自行查看。

 iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; //解决迭代器失效问题 return next; }

10.pop_back()

         删除list的尾部，此时我们这里也可以巧妙的运用上面的erase(iterator pos)函数来实现。

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

11.pop_front()

         删除list的头部，此时我们这里也可以巧妙的运用上面的erase(iterator pos)函数来实现。

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

12.析构函数

        这里我们可以直接调动clear()函数来清除链表中的节点，然后释放private中的_head节点即可。

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

四、实现的整体代码。

        这里是自我实现的所有代码的集合，需要的可自行拿取。

#pragma once #include<iostream> using namespace std; #include <assert.h> namespace lwf { template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _val; list_node(const T& val = T()) :_next(nullptr) , _prev(nullptr) , _val(val) {} }; template<class T,class Ref,class Ptr> struct _list_iterator { typedef list_node<T> Node; typedef _list_iterator<T, Ref, Ptr> self; Node* _node; _list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& it) { return _node != it._node; } bool operator==(const self& it) { return _node == it._node; } }; /*template<class T> struct _list_const_iterator { typedef list_node<T> Node; Node* _node; _list_const_iterator(Node* node) :_node(node) {} const T& operator*() { return _node->val; } _list_const_iterator<T>& operator++() { _node = _node->_next; return *this; } _list_const_iterator<T> operator++(int) { _list_const_iterator<T> tmp(*this); _node = _node->_next; return tmp; } bool operator!=(const _list_const_iterator<T>& it)const { return _node != it._node; } bool operator==(const _list_const_iterator<T>& it)const { return _node == it._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; iterator begin() { //return iterator(_head->next); return _head->_next; } iterator end() { return _head; } const_iterator begin()const { //return iterator(_head->next); return _head->_next; } const_iterator end()const { return _head; } void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; } list() { empty_init(); } list(const list<T>& It) { empty_init(); for (auto& e : It) { push_back(e); } } void swap(list<T> It) { std::swap(_head, It._head); std::swap(_size, It._size); } list<T>& operator=(list<T> It) //list& operator=(list<T> It) 这样写也可以 { swap(It); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it=begin(); while (it != end()) { it = erase(it); } _size = 0; } size_t size() { return _size; } void push_back(const T& x) { /*Node* tail = _head->_prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; cur->_prev = newnode; newnode->_next = cur; ++_size; //解决迭代器失效问题 return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; //解决迭代器失效问题 return next; } private: Node* _head; size_t _size; }; void Test_1() { list<int> It; It.push_back(1); It.push_back(2); It.push_back(3); It.push_back(4); It.push_front(5); It.push_front(6); It.push_front(7); It.push_front(8); for (auto& e : It) { cout << e << " "; } cout << endl; It.pop_back(); It.pop_front(); for (auto& e : It) { cout << e << " "; } cout << endl; } void Test_2() { list<int> It; It.push_back(1); It.push_back(2); It.push_back(3); It.push_back(4); It.push_front(5); It.push_front(6); It.push_front(7); It.push_front(8); for (auto& e : It) { cout << e << " "; } cout << endl; It.pop_back(); It.pop_front(); for (auto& e : It) { cout << e << " "; } cout << endl; It.clear(); It.push_front(50); It.push_front(60); It.push_front(70); It.push_front(80); for (auto& e : It) { cout << e << " "; } cout << endl; cout << It.size() << endl; } void Test_3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; list<int> lt1(lt); for (auto e : lt1) { cout << e << " "; } cout << endl; list<int> lt2; lt2.push_back(10); lt2.push_back(20); lt2.push_back(30); lt2.push_back(40); for (auto e : lt2) { cout << e << " "; } cout << endl; lt1 = lt2; for (auto e : lt1) { cout << e << " "; } cout << endl; } }

五、感言

       家人们创作不易，在这里感谢各位大佬和友友们的支持，如果各位有所收获，不介意的话给我点个赞再走吧，感谢大家！

Read more

Java Web 桂林旅游景点导游平台系统源码-SpringBoot2+Vue3+MyBatis-Plus+MySQL8.0【含文档】

Java Web 桂林旅游景点导游平台系统源码-SpringBoot2+Vue3+MyBatis-Plus+MySQL8.0【含文档】

系统架构设计### 摘要 随着信息技术的快速发展，智慧旅游逐渐成为提升旅游体验的重要方向。桂林作为中国著名的旅游城市，拥有丰富的自然景观和人文资源，但传统的旅游信息服务模式存在信息分散、更新滞后、用户体验不佳等问题。游客在规划行程时往往需要从多个平台获取信息，效率较低。因此，开发一个集景点介绍、路线规划、用户评价等功能于一体的智能化导游平台具有重要的现实意义。该平台旨在通过技术手段整合桂林旅游资源，为游客提供一站式服务，提升旅游体验的便捷性和个性化。关键词：智慧旅游、桂林、导游平台、资源整合、用户体验。 本系统采用前后端分离架构，后端基于SpringBoot2框架搭建，结合MyBatis-Plus实现高效的数据操作，数据库选用MySQL8.0以支持高并发访问。前端使用Vue3框架开发，利用其响应式特性提升用户交互体验。系统功能涵盖景点信息展示、用户评论管理、路线推荐、订单管理等模块，并通过JWT实现安全的用户认证。系统设计注重可扩展性和可维护性，采用RESTful API规范进行接口设计，确保前后端高效协作。关键词：SpringBoot2、Vue3、MyBatis-Plus、MyS

By Ne0inhk
低代码平台后端引擎：元数据驱动架构、插件化内核与 Java 扩展机制

低代码平台后端引擎：元数据驱动架构、插件化内核与 Java 扩展机制

文章目录 * 🎯 低代码平台后端引擎：元数据驱动架构、插件化内核与 Java 扩展机制 * 📊📋 第一章：引言——低代码后端的物理本质：从硬编码到元数据驱动 * 🧬🧩 1.1 静态架构的“编译时”枷锁 * 🛡️⚖️ 1.2 元数据驱动（Metadata-Driven）的逻辑重构 * 🌍📈 第二章：数据建模内核——动态表单引擎与多态存储设计 * 🧬🧩 2.1 存储模型的物理博弈：EAV vs. JSONB vs. 动态 DDL * 🛡️⚖️ 2.2 数据绑定（Data Binding）的运行时映射 * 🔄🎯 第三章：精密工程——基于 Java 的动态数据处理引擎实现 * 🧬🧩 3.1 泛型执行器（Generic Executor）的设计 * 💻🚀 代码实战：

By Ne0inhk
Java 数据结构与算法：时间空间复杂度 从入门到实战全解

Java 数据结构与算法：时间空间复杂度 从入门到实战全解

🏠个人主页：黎雁 🎬作者简介：C/C++/JAVA后端开发学习者 ❄️个人专栏：C语言、数据结构（C语言）、EasyX、JAVA、数据结构与算法（JAVA）、游戏、规划、程序人生 ✨ 从来绝巘须孤往，万里同尘即玉京 文章目录 * Java 数据结构与算法：时间空间复杂度 从入门到实战全解 🚀 * 📝 文章摘要 * 🧠 前置知识回顾 * 一、数据结构与算法基础认知 📚 * 1. 什么是数据结构？ * 2. 数据库 ≠ 数据结构（一定要分清） * 3. 数据结构与算法的关系 * 4. 最实用的学习路线（直接照做） * 二、算法复杂度：评价算法好坏的唯一标准 ⚖️ * 1. 两个核心概念 * ① 时间复杂度 ⏱️ * ② 空间复杂度 📦 * ③ 时间 vs 空间：怎么取舍？

By Ne0inhk
秋天的第一个项目，飞算JavaAI一小时拿下~

秋天的第一个项目，飞算JavaAI一小时拿下~

个人主页-爱因斯晨 目录 飞算JavaAI介绍 功能简介 安装流程 功能实测与案例分析 智能引导 理解需求 接口设计 表结构设计 处理逻辑接口 源码生成 SQL chat 工具箱 智能对话 总结   我们在写项目时常常会因为需求条件的繁琐来为难，但是我们有了飞算JavaAI大大提高了编码效率，他与其余的AI相比最大的优点就是，即使你不懂代码，也能靠指令需求生成整个项目。#飞算JavaAI炫技赛 #AI开发 飞算介绍 飞算Java AI 是飞算数智科技自主研发的一系列人工智能产品，以互联网科技、大数据等技术为基础，为企业和开发者提供服务。其中，飞算 JavaAI 将人工智能与 Java 技术融合，可实现从需求分析、软件设计到工程代码生成的全流程智能引导，支持文本 / 语音输入需求，能自动生成接口、表结构和代码逻辑，还可一键生成源码及完整工程并优化代码。 飞算JavaAI官网直达 功能简介 飞算平台提供了多个功能模块： * 工程级深度理解：包括技术规范、开发模式等。

By Ne0inhk