什么是STL列表,向量和集合的基础数据结构？

Question

我的解决方案

对？

Answer 1

根据评论,澄清,这些是最常见的选择,但基于所需的复杂性和其他因素,这些实现的支持可能会有所不同:

Vector =动态调整数组大小

Set = 红/黑树(平衡二进制搜索树)

我想你可能会混淆堆和BST.堆可视化为树,但它实际上构建在可索引列表结构(例如数组或向量)之上.C++通过STL中的算法头提供堆函数.BST更多是用于高效查找的基于键/值的结构(这是您通常想要的一组).

列表是一个双向链表 (4认同)
@ user1002288 - `std :: set`有订购要求.C++ 11的`std :: unordered_set`没有.[双向链表](http://en.wikipedia.org/wiki/Linked_list)是一组节点,它们引用之前和之后的节点(或"NULL"). (3认同)

Answer 2

该标准不保证使用什么数据结构,只有复杂性保证,因此实现可以选择任何满足它们的结构.

也就是说,std::vector通常是一个动态数组,std::list可能是一个双向链表,std::set通常是某种自平衡二叉树.