【STL源码剖析】总结笔记(2):容器(containers)概览

2023-10-18 14:20

本文主要是介绍【STL源码剖析】总结笔记(2):容器(containers)概览,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

00 写在前面

容器(containers)是STL的重要组成部分之一,也是非常值得我们深入研究的部分。各种vector、map、set的使用极大地提高了我们解决问题的效率。

每个容器内部都有着其独特的实现方式以及一些需要我们了解的要点,这些会是文章中的侧重点。

01 容器的结构与分类


概述

容器大致分为序列式容器(Sequence),关联式容器(Associative)和无序容器(Unordered),无序容器也可以归为关联式容器内。

在这里插入图片描述


分类


序列式容器(Sequence)
  1. array:数组,是一种固定大小的结构,静态空间,配置后大小就不能改变。
  2. vector:动态数组,单向开口的线性连续空间,可动态配置空间,原理是每次扩容时二倍增长,再将原空间数据拷贝到新空间中。
  3. deque:是一种双向开口的线性连续空间,可在头和尾进行插入和删除操作。
  4. list:链表结构,不是线性连续空间,使用指针寻址,这里指的是双向链表。
  5. forward-list:单向链表
  6. stack/queue:栈和队列,底层都是使用双向开口的deque包装后实现的。

关联式容器(Associative)
  1. set/multiset:以红黑树为基础的结构,可以存放key。对于set来说key不可以重复,multiset的key可以重复。
  2. map/multimap:以红黑树为基础的结构,可以存放key和value,对于map来说key不可以重复,multimap的key可以重复。
  3. unordered set/multiset:以哈希表为基础的结构,可以存放key。对于set来说key不可以重复,multiset的key可以重复。
  4. unordered map/multimap:以哈希表为基础的结构,可以存放key和value,对于map来说key不可以重复,multimap的key可以重复。

对比关系:

集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
std::set红黑树有序O(logn)O(logn)
std::multiset红黑树有序O(logn)O(logn)
std::unordered_set哈希表无序O(1)O(1)
映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
std::map红黑树key有序key不可重复key不可修改O(logn)O(logn)
std::multimap红黑树key有序key可重复key不可修改O(logn)O(logn)
std::unordered_map哈希表key无序key不可重复key不可修改O(1)O(1)

02 容器间的关系

先来看一张关系图:

在这里插入图片描述

这里的缩进显示代表着基层与衍生层的关系,而衍生不是继承,而是复合。

比如heap和priority里面有vector作为基层。set、map有红黑树作为基层。

也有一些非标准的容器在里面,比如slist,hash开头的等等。在C++ 11中slist改名为forward-list,hash开头的全部改为unordered开头。

注:这里的sizeof()埋一个小伏笔,后面会有具体大小的对比。另外GNU4.9有很多设计变得复杂了,比如使用了很多继承,但实际功能区别不大。


03 总结

在了解了容器的大致内容之后,我们可以从最熟悉的vector入手来看看内部的实现细节。

而在其他容器中也会有很多值得学习的地方,比如list中会体现出迭代器(iterators)设计的精妙之处,在set和map中会体现红黑树的实现等等,后续单独总结。

这篇关于【STL源码剖析】总结笔记(2):容器(containers)概览的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/233109

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》:本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整(可选)重新构建和运行总结Tomcat容器替

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque