4

任何在性能关键代码中使用过“deque”的人都可能已经注意到（至少在 VS2010 附带的 STL 中）块大小为 16 字节。这是 VS2010 附带的头文件的实际片段：

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 16 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

这不是新信息，请参阅关于 deque<T> 的额外间接以了解有关此 decl 导致性能问题的原因的更多详细信息。

我想在各种算法中使用双端队列，但如果我受限于这个实现，我就不会。绕过这个问题的最佳方法是什么？

1）使用另一个没有这个问题的容器。如果是这样，有人能指点我一个没有 GNU 许可证限制的吗？

2) 创建一个新的容器类来解决这个限制。这个新的容器类不会是 std 命名空间的一部分。

3) 编辑 'deque' 头文件中的 _DEQUESIZ 定义。IMO，我认为这是合法的，因为 _DEQUESIZ 的确切规范不是 STL 定义的双端队列概念的一部分。

4) 向 deque（和相关的迭代器类）添加一个额外的模板参数，以允许在编译时指定块大小。此参数将默认为 _DEQUESIZ 的当前定义。我几乎拒绝这个解决方案，因为现在我使用这个混蛋的 STL 的代码是不可移植的。

5) 游说大会更改 STL，这样我就可以愉快地使用 'deque' 而不会出现性能问题。IMO，这可能比当前的财政悬崖辩论更成功。顺便说一句，我是加拿大人，所以整个众议院 + 参议院 + 总统的繁文缛节令人困惑。

4

2 回答 2

0

不是真正的答案，但评论太长了：

如果您担心性能，我不建议您编写新的容器类。通常，STL 实现使用基于它们所针对的特定编译器的实现细节的不可移植优化，而您通常无法这样做。我曾经尝试自己重写一些非常简单的 STL 算法，执行速度大约是 STL 算法的一半。

更改_DEQUESIZ可能会在无法预料的地方导致性能问题，因为其他代码可能会针对原始值进行优化。再一次，当您为特定编译器编写代码时，您可以执行的那种不可移植的优化。不仅如此：您甚至可能会破坏一些取决于_DEQUESIZ.

总而言之，在我看来，只有您的选项 1 是可行的。不幸的是，我不知道有什么好的选择；这就是为什么我写这不是您问题的真正答案的原因。

于 2012-12-21T12:20:54.240 回答
0

我赞成1）。

标准库的 libc++ 实现是在一个非常自由的许可证下分发的，实际上足够自由，你可以调整它以适应它，如果你的编译器阻塞它（它是围绕 Clang 设计的，它更符合 C++11比 VS 2010 更清楚）。您只需要保留许可证。

于 2012-12-21T16:11:56.207 回答