【温故而知新】C和C++5:STL容器技术综述

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 容器类是可以包含其他对象的类。STL中提供的较为常用的容器类有向量、链表、队列、集合和图等,每一种容器类都是一个模板,可以包含各种类型的对象。这些容器可以分为序列式和关联式两大类。

容器类是可以包含其他对象的类。STL中提供的较为常用的容器类有向量、链表、队列、集合和图等,每一种容器类都是一个模板,可以包含各种类型的对象。这些容器可以分为序列式和关联式两大类。

序列式容器主要有:

1、vector:向量类,可以认为是一种容量可变的数组,可以提供对元素的随机访问,而且可以在序列尾部快速插入和删除数据,并且在需要的时候可以方便地改变容器的大小;

2、list:双向链表类,不支持随机访问的数组类,遍历链表的元素需要从某个端点开始向前或向后遍历;

3、queue:队列,实现先进先出的功能。使用deque和list实现。所有元素占用连续存储控件,但是不能提供随机存取;

4、stack:栈容器,实现先进后出功能。使用vector、list和deque实现;

5、deque:双端队列,实现数据的先进先出功能,可以随机访问;

6、priority_queue:按值排序的队列容器,使用vector和deque创建了排序队列,依照优先级决定下一个元素。

关联式容器的数据存储按照顺序进行,其余序列式容器不同的地方在于使用关键字查找元素,主要分类有:

1、set:集合,该容器中的关键字和数据是同一个值因此不能包含相同元素;由于各个元素经过了排序,因此不能直接修改其中的元素,只能删除后重新添加;

2、multiset:多重集合,同set类似,区别在于可以包含相同元素;

3、map:映射类,由一组键值对组成的集合,每一个键只能与一个特定的值相联系,且不能存在重复的键;

4、multimap:多重映射类,同map类似,区别在于可以存在重复的键;

5、hash table:散列表,通常可以用于大数据搜索。


一、向量容器vector:

向量容器vector是STL提供的最简单的容器之一,可以提供类似数组的随机访问功能,此外比数组更强大之处在于可以方便地动态调整容器的容量。由于vector的存储结构是顺序存储,因此虽然vector可以在任意位置增删数据,但是只有在末尾进行操作时效率最高。vector类定义在头文件<vector.h>中。

vector定义了两个最常用的成员:

size_type vector::capacity() const;//返回当前能容纳的最大成员的个数;
void vector::reserve(size_type n);//申请分配内存达到n;
其他成员可参照相关文档;


二、双端队列deque:

一种动态数组的形式,可以高效率地向两端增删数据,同时在需要时可以动态地调整大小。deque类定义在<deque.h>中。

deque类完全继承自其基类,没有添加派生成员,其所有的变量和方法定义在随机接入容器random access、前向插入序列front insertion sequence、反向插入序列back insertion sequence中。

与vector相比,deque除了可以方便地使用push_back()在末尾添加数据之外,也可以使用push_front()在头部添加数据。


三、链表list:

list实现了双向链表功能。由于list采用链式存储结构,因此不支持随机存取,但是其优点是在链表的任何位置插入和删除元素都非常迅速。list结构定义在<list.h>中。

list类主要继承自双向容器Reversible、前向插入序列front insertion sequence和反向插入序列back insertion sequence。此外还定义了多种自有方法,如splice/remove/unique/merge/reverse/sort等,具体可以查看官方文档。


以上三类是STL提供的基本容器,除此之外STL还在这些基本容器的基础上提供了stack、queue、priority_queue、slist等容器,分别实现了栈、队列、优先级队列和双向迭代链表等功能。其使用方法大同小异,具体可搜索官方文档。


四、关联式容器:

set、map等关联式容器相比于序列式应用稍少一些。从总的思想上来看,序列式容器可以认为是数组、链表等结构的扩展,倾向于以排列的形式组织数据;而关联式容器通常没有这种先后继的关系,更倾向于一种集合的形式,因此可以处理更加复杂的数据结构。具体各个类的方法可以参考官方文档。


ps:看到这里,感觉STL跟Objective-C中的Foundation Framework有些神似的感觉……



目录
相关文章
|
3月前
|
存储 容器
46.[HarmonyOS NEXT RelativeContainer案例三] 打造自适应容器:内容驱动的智能尺寸调整技术
在HarmonyOS NEXT的UI开发中,创建能够根据内容自动调整尺寸的容器是实现灵活布局的关键。RelativeContainer结合自适应尺寸设置,可以实现内容驱动的智能尺寸调整,使UI更加灵活且易于维护。本教程将详细讲解如何创建自适应尺寸的RelativeContainer,帮助你掌握这一实用技术。
127 5
|
6月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
173 2
|
1月前
|
Kubernetes Cloud Native 持续交付
Docker:轻量级容器化技术解析
Docker:轻量级容器化技术解析
|
1月前
|
运维 测试技术 Docker
Docker:轻量级容器化技术革命
Docker:轻量级容器化技术革命
|
6月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
333 73
|
5月前
|
弹性计算 Java Maven
从代码到容器:Cloud Native Buildpacks技术解析
Cloud Native Buildpacks(CNB)是一种标准化、云原生的容器镜像构建系统,旨在消除手动编写Dockerfile,提供可重复、安全且高效的构建流程。它通过分层策略生成符合OCI标准的镜像,实现应用与基础镜像解耦,并自动化依赖管理和更新。阿里云应用管理支持通过CNB技术一键部署应用至ECS,简化构建和运行流程。
|
6月前
|
存储 虚拟化 Docker
|
6月前
|
开发工具 虚拟化 git
自学软硬件第755 docker容器虚拟化技术youtube视频下载工具
docker容器虚拟化技术有什么用?怎么使用?TubeTube 项目使用youtube视频下载工具
|
7月前
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
6月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
272 3