Container Types in C++ (1)

20 Feb 2018 Languages C/C++

This post compares the differences between built-in array, linked list and several STL (Standard Template Library) containers (array, vector, list, stack, queue, map). Some examples for their basic usage are included as well.

Comparison

Type Dynamic* Mutation** Indexed access Multi-dimension Introduced by
built-in array ✘ ✘ ✓ ✓ C
linked list ✘ ✓ ✘ ✓ C
vector ✓ ✓ ✓ ✓ C++98
array ✘ ✘ ✓ ✓ C++11
list ✘ ✓ ✘ ✘ C++98
stack ✘ ✓ ✘ ✘ C++98
queue ✘ ✓ ✘ ✘ C++98
map ✘ ✓ ✓ ✘ C++98

Note:

  • * Dynamic refers to deciding the size dynamically upon declaration, see new and delete in C++ for dynamic memory management;
  • ** Mutation refers to changing the size during run-time, which also means using heap for storage.

Discussion

array and list are just like the STL container versions of built-in array and linked list. So in the table, they get similar features checked or unchecked. While the difference lies in the STL supports, that array and list have methods required by STL, such as iterator, size(), empty(), swap(). More detailed description in the Appendix G of the book “C++ Primer Plus (6th edition)”.

vector does not have counterpart in original C. It is very flexible, that it can add/drop elements at any position as linked list, as well as access by index as built-in array. While it has to be stored in the heap, so not as efficient as built-in array or array.

stack and queue are two containers derived from data structures. They have push() and pop(), which operate elements in LIFO and FIFO manner respectively.

map is another powerful container usually implemented as red-black tree for quick look up with key.

Examples

  • built-in array
  • linked list
  • vector
  • array
  • list
  • stack
  • queue
  • map

Credits