相关疑难解决方法(0)

在讨论算法的时间复杂度时,"恒定摊还时间"是什么意思？

我正在查看STL容器并试图弄清楚它们到底是什么(即使用的数据结构),并且deque阻止了我:我起初认为它是一个双链表,它允许从两端插入和删除恒定时间,但我对运营商[]在恒定时间内做出的承诺感到不安.在链表中,任意访问应该是O(n),对吗？

如果它是一个动态数组,它如何在恒定时间内添加元素？应该提到的是,可能会发生重新分配,并且O(1)是一个摊销成本,就像向量一样.

所以我想知道这个结构允许在恒定时间内任意访问,同时永远不需要移动到一个新的更大的地方.

显然;-)标准容器提供某种形式的保证.

什么类型的保证以及不同类型的容器之间究竟有什么区别？

从工作的SGI页(约STL)我想出了这一点:

Container Types:
================
Container:
    Forward Container
        Reverse Container
            Random Access Container
    Sequence
        Front Insert Sequence
        Back  Insert Sequence
    Associative Container
        Simple   Associative Container
        Pair     Associative Container
        Sorted   Associative Container
        Multiple Associative Container

Container Types mapped to Standard Containers
=============================================

std::vector:    Sequence    Back        Sequence                    Forward/Reverse/Random Container
std::deque:     Sequence    Front/Back  Sequence                    Forward/Reverse/Random Container
std::list:      Sequence    Front/Back  Sequence                    Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container       Forward Container
std::map:       Sorted/Pair/Unique      Associative Container       Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container …

由于几天前的这个问题,有一些事情一直困扰着我对于野外std::deque::push_back/push_front实际std::deque实施的复杂性要求.

上一个问题的结果是这些操作需要具有O(1)最差的案例复杂性.我确认这确实是这样的c++11:

从23.3.3.4 deque修饰符,参考insert,push/emplace前/后

复杂性:复杂性是插入元素数量的线性加上到双端队列开始和结束距离的较小者.在双端队列的开头或末尾插入单个元素总是需要恒定的时间并导致对T的构造函数的单个调用.

这与O(1)索引,通过operator[]等的复杂性要求相结合.

问题是实现并不严格满足这些要求.

在这两个方面msvc与gcc所述std::deque的实施是一个阻塞数据结构,由指针的动态阵列的至(固定大小)的块,其中每个块中存储有数量的数据元素.

在最坏的情况下,push_back/front etc可能需要一个额外的块将被分配(这是精-固定大小的分配是O(1)),但它也可以要求块指针的动态阵列被调整大小-这不是很好的,因为这是O(m)其中m是块数,在一天结束时O(n).

显然,这仍然是分摊的O(1)复杂性,因为通常m << n它在实践中会非常快.但似乎存在一致性问题？

作为进一步的点,我看不出你如何能设计一个数据结构,严格同时满足O(1)两个复杂性push_back/front etc和operator[].您可以拥有块指针的链接列表,但这并不能提供所需的operator[]行为.真的可以吗？

我可以想到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？

想知道为什么我的内存访问速度比我预期的慢一些,我终于想通了Visual C++实现deque确实有一个内置的额外间接层,破坏了我的内存局部性.

即它似乎持有一个数组T*,而不是一个数组T.

是否有另一个我可以使用VC++但没有这个"功能"的实现,或者是否有某种方式(虽然我认为不太可能)在这个实现中能够避免它？

我基本上都在寻找一个vector在前面也有O(1)推/弹的东西.
我想我可以自己实现它,但处理allocators等是一种痛苦,需要一段时间才能正确,所以我宁愿使用以前编写/测试的东西,如果可能的话.

假设我std::vector<foo>现在知道向量末尾的插入是摊销常数。这意味着它可以是 O(1) 或 O(n) （因为它获取一个新的内存块，将旧的内容复制到新的内存块中）。我的问题是，当将项目复制到较新的内存块（据说更大）时，是否会再次调用对象的复制构造函数？（第一次调用复制构造函数是使用push_back），在我的情况下，在调整向量大小时会再次调用 foo 的复制构造函数吗？我知道使用 std::deque 不会调用复制构造函数，因为它将对象的地址存储在堆上并将它们维护在向量类型数据结构中。C++98 和 C++11 中的行为是否相同

我在理解这个概念时遇到了一些困难。从这个线程here它指出

双端队列要求在前面或后面的任何插入都应保持对成员元素的任何引用有效。迭代器失效是可以的，但成员本身必须留在内存中的同一位置。

我对这个线程的印象是

指针实际上是一种迭代器。事实上，对于一些容器类型，对应的迭代器可以简单地实现为一个指针。

如果我们有一个指针和一个迭代器，它们都引用容器的相同元素，那么任何使一个无效的操作都会使另一个无效。

所以如果一个迭代器失效，那么引用也会失效。我的问题是这怎么可能。如果指向某个内存地址的迭代器无效，那么对该地址的引用如何有效？

更新：

我知道双端队列是由随机内存块实现的，这些内存块由独立的数据结构（例如动态数组）跟踪。但是，我很难理解迭代器如何无效但引用可能有效，因为迭代器本质上是数据结构内容的通用指针。这让我认为迭代器可能指向其他东西，而指针指向实际项目？考虑下面的向量图。

根据我在上图中对向量的理解，如果指针的内容发生变化，迭代器也会发生变化。deque 有什么不同。