c++ - 如何知道用于实现标准代码(例如 C++ STL)的确切数据结构和算法？

Question

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

Answer 1

I wanted to know how the stack is implemented in C++ STL, using array or linked-list, or something even more sophisticated.

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

How to know, the exact data structures and algorithms used to implement a standard piece of code, like in 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 结尾，并且对迭代器失效的要求不太严格，这允许实现对元素所在的小容器使用优化。存储在容器内存中，无需动态分配。