【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

相关文章

如何将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

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要