问题标签 [stddeque]

所以我正在编写一个图遍历例程，我希望能够通过选择 FIFO 或 LIFO 邻居遍历策略将其转换为深度优先或广度优先遍历。在实践中，这意味着我需要在std::deque和std::vector（或堆栈）上抽象“入队”和“出队”操作。

这可以通过为这些容器专门设置几个模板函数来轻松完成。但是，我想知道：在 STL 中是否有一种规范的方法来实现这一点？看起来我可以使用back_insert_iterator“入队”，但我没有找到front_remove_iterator“出队”。我错过了什么吗？

为什么将元素推送到所有现有迭代器的一端std::deque都会使所有现有迭代器无效（尽管所有引用仍然有效）？

我知道双端队列是作为数组数组实现的，并且在任一端推送一个元素不会导致现有元素的任何重新分配。这就是为什么引用仍然有效。但是迭代器也应该如此。

我也知道双端队列的迭代器是RandomAccessIterator类型的，并且这个迭代器应该支持一些操作，比如加/减一个常数、++、--等。

我不明白的是RandomAccessIterator应该支持哪些操作，而std::deque.

我按照三规则实现了一个类，但我遇到了崩溃。经过调试，我得出的结论是，在复制构造函数第 51 行中，由于双端队列的某些内部逻辑，指针 oQueue 不为 NULL，因此构造函数尝试删除内存并失败。

然后我在某处读到我不应该在复制构造函数中检查 oQueue 的 NULLness，因为它可能没有在构造函数中初始化。由于默认构造函数，不应该始终将 oQueue 初始化为 NULL 吗？

我有一个管理地图的 A 类。

当我在我的地图中添加很多元素时，我想通过删除第一次插入的元素来定期清理它。

当我尝试从双端队列中弹出元素时，以下代码有时会崩溃：

上面的代码有意义吗？如果是，错误可能在哪里？如果没有，我怎样才能定期清理地图？

我想使用push_front或push_back取决于用户输入。是否可以将其包含在函数参数中，然后编写一个函数以节省内存？

我需要能够将一个 std::queue 的内容添加（附加）到另一个，最好以与使用 std::deque::insert 大致相同的方式，但使用 std::vector？我宁愿继续使用 std::vectors，而不是进行重大重写来实现 std::deques。

与我之前在同一个项目中的一些帖子一样，我的流动性有限，因为我必须使用一些遗留代码。大部分限制与速度有关。尽管如此，这个论坛的成员还是提出了一些优雅而独特的解决方案；我希望能找到另一个。

显然不会编译，因为 ccc 类型 std::queue 不支持插入

一些重要的注意事项：永远不会有正在使用的容器（队列、双端队列等）需要 FIFO 以外的任何东西的情况。此外，该处理处理的队列量在每秒 80,000 到 100,000 个元素的范围内，通常非常小，有时非常大。

std::deque将元素存储在固定大小的“桶”（数组）中。不同的编译器使用不同的桶大小：

• MSVC：16 字节或元素大小（如果更大）
• GCC：512 字节或元素大小（如果更大）
• 铛：element_size < 256 ? 4096 : element_size * 16

对于 MSVC（尤其是）和 GCC，如果双端队列元素大小大于硬编码大小，在大多数情况下std::deque会变成一个复杂的性能损失。std::list

在我看来，Clang 做得更好，无论双端队列元素的大小如何，存储桶都至少有 16 个元素。尽管 4096 字节的最小桶大小在某些情况下对于小元素可能不是最佳的。

为什么没有std::deque额外的存储桶大小模板参数，默认值是供应商认为合理的？这不会破坏向后兼容性，但会允许性能优化。

我正在寻找一种技术来检测是否可以推送/插入/等。std::deque 的其他元素。它应该为我进行动态内存分配，但是当我的内存已满时会发生什么？通过使用 malloc() 我会收到一个 Nullpointer 但是在使用 std::deque 时如何检测内存不足的情况？

据我了解 std::deque 的 push_back() 复制我输入的数据。因此，当我引用动态数据（例如动态字节数组或 std::vector）时，它只复制对它的引用. 现在我尝试了解是否必须在 std::deque 的 pop_back() 之前删除/释放动态分配的数据？给出了 C++11。希望有人可以帮助我！下面我将我的两个场景作为代码示例：

情景一：

场景二：

这是我在 HackerRank 上研究此问题的解决方案时遇到的问题。它基本上归结为以下内容：给定一个数组 A 和一个整数 K，问题要求您找到大小为 K 的 A 的每个连续子数组的最大值。还有一些额外的东西（对于每个测试用例，这个问题发生 T次，并且必须从输入中读取才能获得 A)，但这就是它的要点。

该站点会检查您的答案是否足够有效，即使您的代码最终产生了正确的输出，提交也可能由于超时而失败。现在，当您第一次进入代码区域时，有一些预定义的代码供您使用：

一切都很好，该网站已经为您的利益处理了输入，并为您指明了模块化方法。您所要做的实际上是解决连续子数组问题；我使用以下函数完成了它，它通过了所有测试用例：

然而，回想起来，我认为我可以（稍微？）做得更好。对于每个测试用例，main 中的输入处理循环 n 次以填充数组 arr，然后 printKMax 也依次循环 n 次以创建和滑动移动窗口。我想我可以将它们组合成一个循环，我想这应该更有效。我用下面的代码做到了，这和以前基本相同，但是将 printKMax 合并到了 main.js 中。这次我将省略评论。

然而，这一次，除了最简单的测试用例之外，代码都失败了，在每种情况下，由于时间限制。

我知道在实践中模块化是好的，但在这一点上，我的兴趣比其他任何事情都更“学术”。关于实际程序，我是否缺少某些东西，或者这与我不知道的幕后运行方式有关？

编辑：正如 PaulMcKenzie 所建议的，我使用 g++ 来运行程序的两个版本，使用失败的测试用例之一作为输入。两者都运行良好并产生了相同的输出，但一个printKMax运行了 3.97 秒，而一个没有运行了 5.44 秒。大约需要 37% 的时间。