我可以想到C++中的三个操作可以在某种意义上描述为具有"恒定"的复杂性.我已经看到了一些关于这意味着什么的辩论(*),在我看来,我们可以说"所有这些操作都是不变的,但有些操作比其他操作更稳定":-)
(编辑2:如果你已经认为你已经知道了答案,那么请先阅读一些关于这个问题的辩论,然后再过早说:C++中的数据结构究竟是什么？很多人都有很高的分数,他们正在争论"常数"意味着什么.我的问题并不像你想象的那么明显!)
(编辑:我不需要什么复杂性"意味着我要一个明确的答案,或许与C++标准报价的底漆,它告诉我们究竟是什么被认为是恒定的.处理器蜱,真实世界的时间,或其他什么？在其他线程上,有些人认为时间与C++标准所要求的完全无关.)
标准中的这些复杂性保证是否适用于运行的运行时？或者他们只是指定所包含对象可能发生的(最大)份数/移动次数？什么'摊销'是什么意思？
1.给定(非空)vector<int> v,以下在运行时显然是常量:
swap(v.front(), v.back());
(虽然一个学究者可能会指出它取决于数据是在缓存中还是换出来的等等!).
2.给定一个list<int> l,做一个push_back很简单.正好分配了一个新项目,并且链接列表中的一些指针被洗牌.每个push_front涉及一个分配,总是具有相同的内存量,因此这显然是相当"恒定"的.但是,当然,进行分配的时间可能非常多变.内存管理可能需要花费大量时间才能找到合适的空闲内存.
3.但是,做一个push_back上vector<int>更是不可预知的.大多数情况下,它会非常快,但它会不时地为所有数据重新分配空间并将每个元素复制到新位置.因此,它在运行时方面的可预测性不如单个list::push_front,但它仍然被称为常量(摊销).平均而言,向向量添加大量数据将带来与添加量无关的复杂性,这就是为什么它被称为"摊销常数"时间.(我对吗？)
最后,我要求int避免使用其他类型的复杂性.例如,a vector< vector<int> >可能稍微复杂一点,因为向量(向量)的每个元素可能具有不同的大小,例如,交换两个元素并不像上面的情况1那样恒定.但理想情况下,我们可以回答所有人vector<T>,而不仅仅是T=int.
(*)有关辩论的一个例子,请参阅对这些答案的评论:究竟什么数据结构是C++中的deques？