当前位置： 首页 > news >正文

学懂C++（四十五 ）：深入详解C++ STL 容器：从基础到进阶

news 来源：原创 2024/9/21 20:36:47

      

目录

1. 向量（Vector）

概念

特点

核心点

实现

适用场景

代码解析

2. 双端队列（Deque）

概念

特点

核心点

实现

适用场景

代码解析

3. 列表（List）

概念

特点

核心点

实现

适用场景

代码解析

4. 集合（Set）

概念

特点

核心点

实现

适用场景

代码解析

5. 映射（Map）

概念

特点

核心点

实现

适用场景

代码解析

6. 无序集合（Unordered Set）

概念

特点

核心点

实现

适用场景

代码解析

7. 无序映射（Unordered Map）

概念

特点

核心点

实现

适用场景

代码解析

8. 栈（Stack）

概念

特点

核心点

实现

适用场景

代码解析

9. 队列（Queue）

概念

特点

核心点

实现

适用场景

代码解析

10. 优先队列（Priority Queue）

概念

特点

核心点

实现

适用场景

代码解析

总结

          C++ 标准模板库（STL）是一个非常强大的工具集，提供了一组通用的类和函数，用于数据结构和算法的实现。STL 的核心组件包括容器（Containers）、迭代器（Iterators）和算法（Algorithms）。本文将深入探讨 STL 容器，全面讲解其概念、特点、核心点、实现、适用场景，并通过经典示例代码和详细解析，帮助开发者更好地理解和应用 STL 容器。

1. 向量（Vector）

概念

std::vector 是一个模板类，表示一个可以动态调整大小的数组。它可以高效地在末尾添加和删除元素，提供随机访问功能。

特点

  • 动态大小：可以自动调整大小。
  • 随机访问：支持常数时间的随机访问。
  • 连续内存：存储在连续的内存块中，兼容C风格数组。

核心点

  • 内存管理：使用动态数组管理内存，自动处理内存分配和释放。
  • 扩展策略：当容量不足时，通常会按一定比例（通常是2倍）扩展容量。

实现

#include <iostream>
#include <vector>void vectorExample()
{std::vector<int> vec;// 添加元素vec.push_back(1);vec.push_back(2);vec.push_back(3);// 随机访问std::cout << "Element at index 1: " << vec[1] << std::endl;// 迭代访问for(const auto& elem : vec){std::cout << elem << " ";}std::cout << std::endl;
}

适用场景

  • 需要动态调整大小的数组。
  • 需要高效随机访问的场景。

代码解析

  1. push_back：在向量末尾添加元素。
  2. 随机访问：使用下标操作符[]访问元素。
  3. 迭代访问：使用范围基于（range-based）for循环迭代访问元素。

2. 双端队列（Deque）

概念

std::deque 是一个双端队列，支持在两端高效地添加和删除元素。

特点

  • 双端操作：在两端添加和删除元素都很高效。
  • 随机访问：支持常数时间的随机访问。
  • 分段存储：内部实现为一组连续的内存块，提高内存管理效率。

核心点

  • 双端操作：push_front 和 push_back 方法用于在两端添加元素。
  • 内存管理：使用分段存储来优化内存管理。

实现

#include <iostream>
#include <deque>void dequeExample()
{std::deque<int> deq;// 在两端添加元素deq.push_back(1);deq.push_back(2);deq.push_front(0);// 随机访问std::cout << "Element at index 1: " << deq[1] << std::endl;// 迭代访问for(const auto& elem : deq){std::cout << elem << " ";}std::cout << std::endl;
}

适用场景

  • 需要在两端频繁添加和删除元素的场景。
  • 需要高效随机访问的场景。

代码解析

  1. push_front：在队列前端添加元素。
  2. push_back：在队列末尾添加元素。
  3. 随机访问：使用下标操作符[]访问元素。

3. 列表（List）

概念

std::list 是一个双向链表，支持在任意位置高效地插入和删除元素。

特点

  • 双向链表：每个元素包含指向前后元素的指针。
  • 高效插入和删除：在链表的任意位置插入和删除元素都很高效。
  • 顺序访问：不支持随机访问，只能顺序访问。

核心点

  • 链表结构：使用双向链表实现，保证高效的插入和删除操作。
  • 迭代器：提供双向迭代器，支持前向和后向遍历。

实现

#include <iostream>
#include <list>void listExample()
{std::list<int> lst;// 添加元素lst.push_back(1);lst.push_back(2);lst.push_front(0);// 迭代访问for(const auto& elem : lst){std::cout << elem << " ";}std::cout << std::endl;// 插入和删除元素auto it = lst.begin();++it;lst.insert(it, 10);lst.erase(it);
}

适用场景

  • 需要在任意位置频繁插入和删除元素的场景。
  • 需要顺序访问的场景。

代码解析

  1. push_front：在链表前端添加元素。
  2. push_back：在链表末尾添加元素。
  3. insert和erase：在链表的任意位置插入和删除元素。
  4. 迭代访问：使用范围基于（range-based）for循环迭代访问元素。

4. 集合（Set）

概念

std::set 是一个有序集合，存储唯一的元素并自动对元素进行排序。

特点

  • 有序：元素自动排序。
  • 唯一性：集合中的元素是唯一的。
  • 高效查找：支持对元素的高效查找。

核心点

  • 有序集合：使用红黑树实现，保证元素的有序性和查找效率。
  • 唯一性：自动去重，保证元素的唯一性。

实现

#include <iostream>
#include <set>void setExample()
{std::set<int> s;// 添加元素s.insert(3);s.insert(1);s.insert(2);s.insert(2); // 重复元素插入无效// 迭代访问for(const auto& elem : s){std::cout << elem << " ";}std::cout << std::endl;// 查找元素auto it = s.find(2);if(it != s.end()){std::cout << "Element found: " << *it << std::endl;}else{std::cout << "Element not found" << std::endl;}
}

适用场景

  • 需要存储唯一且有序的元素集合。
  • 需要高效查找元素的场景。

代码解析

  1. insert：在集合中添加元素，自动去重。
  2. find：在集合中查找元素。
  3. 迭代访问：使用范围基于（range-based）for循环迭代访问元素。

5. 映射（Map）

概念

std::map 是一个有序映射，存储键值对，并根据键对元素进行排序。

特点

  • 有序：键值对自动排序。
  • 键唯一：每个键在映射中是唯一的。
  • 高效查找：支持对键的高效查找。

核心点

  • 有序映射：使用红黑树实现，保证键值对的有序性和查找效率。
  • 唯一键：自动去重，保证键的唯一性。

实现

#include <iostream>
#include <map>void mapExample()
{std::map<int, std::string> m;// 添加键值对m[1] = "one";m[2] = "two";m[3] = "three";// 迭代访问for(const auto& pair : m){std::cout << pair.first << ": " << pair.second << std::endl;}// 查找键值对auto it = m.find(2);if(it != m.end()){std::cout << "Element found: " << it->first << ": " << it->second << std::endl;}else{std::cout << "Element not found" << std::endl;}
}

适用场景

  • 需要存储键值对并根据键进行排序的场景。
  • 需要高效查找键的场景。

代码解析

  1. operator[]：在映射中添加或访问键值对。
  2. find：在映射中查找键。
  3. 迭代访问：使用范围基于（range-based）for循环迭代访问键值对。

6. 无序集合（Unordered Set）

概念

std::unordered_set 是一个无序集合，存储唯一的元素并使用哈希表进行管理。

特点

  • 无序：元素没有特定顺序。
  • 唯一性：集合中的元素是唯一的。
  • 高效查找：使用哈希表实现，对元素进行高效查找。

核心点

  • 无序集合：使用哈希表实现，保证元素的唯一性和查找效率。
  • 唯一性：自动去重，保证元素的唯一性。

实现

#include <iostream>
#include <unordered_set>void unorderedSetExample()
{std::unordered_set<int> us;// 添加元素us.insert(3);us.insert(1);us.insert(2);us.insert(2); // 重复元素插入无效// 迭代访问for(const auto& elem : us){std::cout << elem << " ";}std::cout << std::endl;// 查找元素auto it = us.find(2);if(it != us.end()){std::cout << "Element found: " << *it << std::endl;}else{std::cout << "Element not found" << std::endl;}
}

适用场景

  • 需要存储唯一且无序的元素集合。
  • 需要高效查找元素的场景。

代码解析

  1. insert：在集合中添加元素，自动去重。
  2. find：在集合中查找元素。
  3. 迭代访问：使用范围基于（range-based）for循环迭代访问元素。

7. 无序映射（Unordered Map）

概念

std::unordered_map 是一个无序映射，存储键值对，并使用哈希表进行管理。

特点

  • 无序：键值对没有特定顺序。
  • 键唯一：每个键在映射中是唯一的。
  • 高效查找：使用哈希表实现，对键进行高效查找。

核心点

  • 无序映射：使用哈希表实现，保证键的唯一性和查找效率。
  • 唯一键：自动去重，保证键的唯一性。

实现

#include <iostream>
#include <unordered_map>void unorderedMapExample()
{std::unordered_map<int, std::string> um;// 添加键值对um[1] = "one";um[2] = "two";um[3] = "three";// 迭代访问for(const auto& pair : um){std::cout << pair.first << ": " << pair.second << std::endl;}// 查找键值对auto it = um.find(2);if(it != um.end()){std::cout << "Element found: " << it->first << ": " << it->second << std::endl;}else{std::cout << "Element not found" << std::endl;}
}

适用场景

  • 需要存储键值对并使用哈希表进行管理的场景。
  • 需要高效查找键的场景。

代码解析

  1. operator[]：在映射中添加或访问键值对。
  2. find：在映射中查找键。
  3. 迭代访问：使用范围基于（range-based）for循环迭代访问键值对。

8. 栈（Stack）

概念

std::stack 是一个适配器容器，提供后进先出（LIFO）的数据结构。

特点

  • LIFO：后进先出顺序。
  • 适配器容器：通常基于 std::deque 或 std::vector 实现。

核心点

  • LIFO 数据结构：提供 push、pop 和 top 方法。
  • 适配器模式：基于其他容器实现。

实现

#include <iostream>
#include <stack>void stackExample()
{std::stack<int> st;// 添加元素st.push(1);st.push(2);st.push(3);// 访问栈顶元素std::cout << "Top element: " << st.top() << std::endl;// 移除栈顶元素st.pop();std::cout << "Top element after pop: " << st.top() << std::endl;
}

适用场景

  • 需要后进先出（LIFO）数据结构的场景，如递归调用、表达式求值等。

代码解析

  1. push：在栈顶添加元素。
  2. pop：移除栈顶元素。
  3. top：访问栈顶元素。

9. 队列（Queue）

概念

std::queue 是一个适配器容器，提供先进先出（FIFO）的数据结构。

特点

  • FIFO：先进先出顺序。
  • 适配器容器：通常基于 std::deque 实现。

核心点

  • FIFO 数据结构：提供 push、pop 和 front 方法。
  • 适配器模式：基于其他容器实现。

实现

#include <iostream>
#include <queue>void queueExample()
{std::queue<int> q;// 添加元素q.push(1);q.push(2);q.push(3);// 访问队首元素std::cout << "Front element: " << q.front() << std::endl;// 移除队首元素q.pop();std::cout << "Front element after pop: " << q.front() << std::endl;
}

适用场景

  • 需要先进先出（FIFO）数据结构的场景，如任务调度、消息队列等。

代码解析

  1. push：在队列末尾添加元素。
  2. pop：移除队首元素。
  3. front：访问队首元素。

10. 优先队列（Priority Queue）

概念

std::priority_queue 是一个适配器容器，提供按优先级排序的队列。

特点

  • 优先级排序：元素按照优先级排序。
  • 适配器容器：通常基于 std::vector 和堆算法实现。

核心点

  • 优先级数据结构：提供 push、pop 和 top 方法。
  • 适配器模式：基于其他容器和算法实现。

实现

#include <iostream>
#include <queue>
#include <vector>void priorityQueueExample()
{std::priority_queue<int, std::vector<int>> pq;// 添加元素pq.push(1);pq.push(3);pq.push(2);// 访问最高优先级元素std::cout << "Top element: " << pq.top() << std::endl;// 移除最高优先级元素pq.pop();std::cout << "Top element after pop: " << pq.top() << std::endl;
}

适用场景

  • 需要按优先级处理元素的场景，如任务调度、A*算法等。

代码解析

  1. push：在优先队列中添加元素。
  2. pop：移除最高优先级元素。
  3. top：访问最高优先级元素。

总结

        本文详细介绍了 C++ STL 各种常用容器，包括向量（Vector）、双端队列（Deque）、列表（List）、集合（Set）、映射（Map）、无序集合（Unordered Set）、无序映射（Unordered Map）、栈（Stack）、队列（Queue）和优先队列（Priority Queue）。每种容器的概念、特点、核心点、实现方法、适用场景以及经典示例代码和详细解析都进行了深入讲解。

        通过对这些容器的学习和应用，开发者可以更好地应对软件开发中的复杂问题，提高代码的质量和开发效率，充分发挥

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 深度学习——分布式训练
  • Webpack中的 HTTP 压缩
  • c语言个人笔记
  • netty编程之实现HTTP服务
  • 采用java或者python获取视频流的方法
  • 【功能实现】axios实现动态数据
  • 【卡码网C++基础课 13.链表的基础操作1】
  • 婚恋交友系统该如何制作成品系统？
  • Spring Boot 全局异常@ControllerAdvice和@RestControllerAdvice的区别
  • C#入门（15）while循环和do—while循环
  • SpringMVC核心机制环境搭建
  • 协议汇总 TCP、UDP、Http、Socket、Web Scoket、Web Service、WCF、API
  • ruoyi-app前端在缓存中添加nick_name和user_id属性值
  • GeoStudio2024：地质工程的瑰宝下载安装介绍
  • std::vector的reserve(), resize()和shrink_to_fit()
  • ----------
  • 【css3】浏览器内核及其兼容性
  • 2018一半小结一波
  • Java｜序列化异常StreamCorruptedException的解决方法
  • Javascript编码规范
  • Nacos系列：Nacos的Java SDK使用
  • node和express搭建代理服务器（源码）
  • React 快速上手 - 07 前端路由 react-router
  • WePY 在小程序性能调优上做出的探究
  • 阿里云应用高可用服务公测发布
  • 二维平面内的碰撞检测【一】
  • 前端工程化（Gulp、Webpack）-webpack
  • 实现简单的正则表达式引擎
  • 实战｜智能家居行业移动应用性能分析
  • 用Canvas画一棵二叉树
  • 《天龙八部3D》Unity技术方案揭秘
  • UI设计初学者应该如何入门？
  • 昨天1024程序员节，我故意写了个死循环~
  • ​必胜客礼品卡回收多少钱，回收平台哪家好
  • ![CDATA[ ]] 是什么东东
  • #define、const、typedef的差别
  • #QT(QCharts绘制曲线)
  • #stm32驱动外设模块总结w5500模块
  • #微信小程序（布局、渲染层基础知识）
  • （175）FPGA门控时钟技术
  • （3）(3.5) 遥测无线电区域条例
  • （每日一问）基础知识：堆与栈的区别
  • （三） prometheus + grafana + alertmanager 配置Redis监控
  • （三）SvelteKit教程：layout 文件
  • （十）Flink Table API 和 SQL 基本概念
  • (数位dp) 算法竞赛入门到进阶 书本题集
  • （学习日记）2024.01.19
  • （转）eclipse内存溢出设置 -Xms212m -Xmx804m -XX:PermSize=250M -XX:MaxPermSize=356m
  • （转）我也是一只ＩＴ小小鸟
  • （状压dp）uva 10817 Headmaster's Headache
  • *setTimeout实现text输入在用户停顿时才调用事件！*
  • .MSSQLSERVER 导入导出 命令集－－堪称经典，值得借鉴！
  • .NET Core 版本不支持的问题
  • .NET CORE使用Redis分布式锁续命(续期)问题
  • @cacheable 是否缓存成功_Spring Cache缓存注解