The three types of containers in C++

I have to confess, I have grown tired of using the same container type in my game engine. Thus, I opened a C++ book and looked for other type of containers. If you don't know what a container is, a container manages a collection of objects. I have learned that C++ contains three types of containers:

  • Sequential Containers
  • Associative Containers
  • Unordered Containers

Out of the listed above, the sequential container is the type of container you may have used the most. Arrays and vectors belong to this type of container. 

Let me teach you what makes each container type different.

Sequential Containers

These type of containers are ordered-collections in which each element has a position. The position depends on the time and place of insertion. If you append four objects to the end of a vector, these objects will appear in the  exact order as you inserted them. The STL provides five sequence container classes:

  • vectors
  • deque
  • arrays
  • lists
  • forward_list

Associative Containers

These are sorted-collections in which the position of an element depends on its value. The value of the elements determine the position of the elements in the container. The order of insertion doesn't matter. The STL contains four associative container classes:

  • set
  • multiset
  • map
  • multimap

Unordered (associative) Containers

These are unordered-collections in which the position of an element doesn't matter. Neither does the order of insertion nor the value of the element. Only their existence in the container matters. If you put four elements in to a collection, their order is undefined and might change over time. The STL container contains four unordered container classes:

  • unordered_set
  • unordered_multiset
  • unordered_map
  • unordered_multimap

The implementation of each type of container differs. For example: 

  • Sequence containers are usually implemented as arrays or linked-lists.
  • Associative containers  are usually implemented as binary trees.
  • Unordered containers are usually implemented as hash tables.

There you have it. The three types of containers found in the STL are sequential, associative and unordered.

Hope this helps.

PS. Sign up to my newsletter and get development tips.

Harold Serrano

Computer Graphics Enthusiast. Currently developing a 3D Game Engine.