C++ – what is underlying data structure of STL list, vector and set

clistsetstlvector

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?

Best Answer

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).