如何知道用于实现标准代码段的确切数据结构和算法，例如在 C++ STL 中？

Question

我想知道堆栈是如何在 C++ STL 中实现的，使用数组或链表，或者更复杂的东西。另外我怎么知道，任何代码的任何标准片段是如何实现的？我已经尝试使用谷歌搜索和编写自定义代码来获得一个想法，但它非常耗时，有时 3rd 方网站不会透露任何有用的信息。

Answer 1

我想知道堆栈是如何在 C++ STL 中实现的，使用数组或链表，或者更复杂的东西。

std::stack是一个容器适配器。它使用您提供的容器类型作为模板参数。默认情况下，它使用std::deque.

如何知道用于实现标准代码段的确切数据结构和算法，例如在 C++ STL 中？

通过阅读源代码或文档（如果有）。如果两者都不可用，那么您可以询问向您出售实施的供应商。如果这也不是一个选项，您可以尝试逆向工程（假设您这样做是合法的），但此选项既不简单也不快速。

尽管标准没有明确指定用于实现标准容器的数据结构，但它们的要求非常严格，以至于实现选择的自由度很小。在实践中：

• std::list 用双链表实现
• std::forward_list .. 单向链表
• std::vector .. 呈指数增长的动态数组
• std::array .. 毫不奇怪，有一个数组
• std::deque .. 使用分段数组
• 有序关联容器是平衡搜索树
• 无序关联容器是带有链式存储桶的哈希表。
• std::queue和std::stack是容器适配器，按原样使用底层序列容器。
• std::priority_queue 是一个容器适配器，它在参数序列容器的顶部构建一个隐式二进制堆。
• std::basic_string 类似于 vector，除了它以 null 结尾，并且对迭代器的无效要求不那么严格，这允许实现对小容器使用优化，其中元素存储在容器内存中而无需动态分配。