STL列表、向量、集合的底层数据结构是什么？
STL列表、向量和集合的底层数据结构是什么？
我的解决方案：
- 向量：（动态分配）数组
- 列表：？
- set：堆（或所有叶节点尽可能位于左侧并将最小/最大元素放在顶部的二叉树）
对吗？
what is underlying data structure of STL list, vector and set ?
My solution:
- vector : (dynamic allocated) array
- list: ?
- set: heap (or a binary tree with all leaf nodes located as left as possible and keep min/max element on top)
Right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
根据评论，澄清一下，这些是最常见的选择，但根据所需的复杂性和其他因素，这些实现的支持可能会有所不同：
矢量 = 动态调整数组大小
列表 = 双向链表
设置 = 红/黑树（平衡二叉搜索树）
我认为您可能会混淆堆和 BST。堆被可视化为一棵树，但它实际上构建在可索引列表结构（例如数组或向量）之上。 C++ 通过 STL 中的算法头提供堆函数。 BST 更多的是基于键/值的结构，用于高效查找（这就是您通常想要的集合）。
Based on comments, to clarify, these are the most common choices, but based on desired complexity and other factors, the backing of these implementations may vary:
Vector = dynamically resizing array
List = Doubly Linked List
Set = Red/Black Tree (balanced Binary Search Tree)
I think you might possibly be mixing up Heaps and BSTs. A heap is visualized as a tree, but it's actually built on top of an indexable list structure (e.g. array or vector). C++ provides heap functions via the algorithm header in the STL . BSTs are more of a key/value based structure used for efficient lookup (which is what you generally want for a set).
该标准不保证使用什么数据结构，只有复杂性保证，因此实现可以选择满足它们的任何结构。
也就是说，
std::vector通常是一个动态数组，< code>std::list 可能是一个 双向链表 并且std::set通常是某种自平衡二叉树< /a>.The standard gives no guarantees on what data structures are used, there are only complexity guarantees, so the implementation can choose any structure that fulfills them.
That said,
std::vectoris usually a dynamic array,std::listis probably a doubly-linked list andstd::setis most often some kind of self-balancing binary tree.