c++ - 大小的时间复杂度是多少?
问题描述
我正在研究不同 STL 容器的各种操作的复杂性。通过这个网站上的另一个问题,我找到了这张图表。
我注意到这张图表中缺少的一项操作是尺寸操作。我想如果知道 .begin 和 .end 的复杂性,也可以计算大小的复杂性。但这些也不见了。
我找到了一个类似于我在这个问题中寻找的答案,但这个答案是针对 Java 的,所以它不涵盖所有 STL 容器,它只定义了一些给定数据类型的大 O 大小。
有谁知道各种容器的 .size 操作的复杂性,或者有人可以给我一个指针,告诉我在哪里可以找到这些复杂性。任何帮助将不胜感激。
此外,如果我的问题措辞错误和/或离题。不要犹豫,建议编辑。
解决方案
从 C++11 开始,size
成员函数的复杂度对于所有标准容器都是不变的。
std::forward_list
这是单链表数据结构的一种实现,不提供size
成员函数。可以使用迭代器在线性时间内计算大小。
除了标准的 C++ 容器之外,所有数据结构都可以通过单独存储的大小变量进行扩充,以实现这种恒定的复杂性,但代价是插入和删除操作的恒定开销很小。Array 的特殊之处在于它不需要任何额外的开销,假设迭代器到 end 被存储。
推荐阅读
- c# - ASP.NET Core + Angular 静态路由
- python - django.core.exceptions.AppRegistryNotReady:模型尚未加载。Django 3.1.4
- c++ - c++编译/执行MakeFiles
- image - 减少颤动中前导和标题之间的空间
- java - 无法获取代理详细信息
- python-3.x - Discord.py 没有运行 Visual Studio 代码
- assembly - 如何在 ARM Cortex-M3 上旋转和移位 64 位整数?
- cordova - Apache Cordova:检测到更改时如何在开发期间自动重新加载应用程序?
- mysql - Spring Boot 2 - MySQL 数据源
- javascript - 如何使用带有 html 的 express-handlebars?