我一直在阅读 gcc 13537 错误报告 关于 std::deque push_back、push_front 操作，以及它们如何真正摊销 O(1)，而不仅仅是 O(1)。
讨论的结论是双端队列的指针重新分配映射（即 O(n)）未考虑 push_back/push_front 的复杂性，因为 [container.requirements.general]/2:
说明了本条款中的所有复杂性要求 仅就包含对象的操作次数而言。
因为移动指针不是对双端队列包含的对象的操作。
所以这让我思考，为什么相同的逻辑不适用于 std::unoredered_map::rehash？
在最坏的情况下，unoredered_map 的所有元素都可以具有相同的哈希值，因此它们最终会出现在同一个桶中。对于每个元素，我们需要将其附加到同一个桶中，这很可能实现为单链表。如果我们将元素附加到列表的末尾，我们需要遍历它的所有元素，所以我们有 n O(n) 插入，总共 O(n^2)。但是遍历列表不应该涉及对 unoredered_map 元素的任何操作，所以应用上面的逻辑，插入应该是 O(1)，整个事情应该是 O(n)
这真的很令人困惑，看起来双端队列的复杂性应该被摊销，或者 rehash 应该是 O(n) 最坏的情况，或者也许我只是没弄对？
编辑：阅读评论后，现在我看不出有任何理由在插入时遍历桶，这个 O(n^2) 最坏的情况变得更加混乱
按照标准的规定，插入操作会导致 std::unordered_set / std::unordered_map 容器的 rehash，所以所有的元素都必须重新插入到表中：这会导致 O(N) 的成本.这不取决于是否重新分配了底层动态大小的指针数组，而是取决于必须再次执行插入操作以将新存储桶分配给所有元素中的每一个的成本。
对 std::deque 容器的推送操作也是如此：它总是 O(1)。不考虑底层动态大小指针数组的可能重新分配。
这对我来说很有意义，因为标准没有明确定义这种底层指针数组的存在。