C++ · Intermediate level

Intermediate level · Module 3: The Standard Template Library · Lesson 1 of 3

Choosing Containers

Compare vector, map, set, unordered_map and unordered_set by ordering, uniqueness and lookup speed.

In this lesson you will

  • Describe the main STL containers and their trade-offs
  • Use map and unordered_map for key–value data

Key concepts

std::vectorstd::map vs std::unordered_mapstd::setlookup complexity

The lesson

std::vector is the default container: contiguous memory, fast iteration and fast push_back. std::map keeps keys sorted and finds them in logarithmic time; std::unordered_map finds keys in constant time on average but has no order. Sets are the same structures storing keys only.

map[key] creates a default value when the key is missing, which is convenient for counting but surprising when you only meant to look something up. Use find or contains (C++20) to check without inserting.

Choose by what you need: order (map/set), fastest lookup (unordered_map/set), sequence and iteration (vector). When unsure, start with vector and measure.

Step by step

  1. Store product prices in a std::map and print them in key order.
  2. Switch to std::unordered_map and observe the order change.
  3. Use contains to check for a product without inserting it.
  4. Collect distinct suppliers with a std::set.

Practice activity

Write a phone book that stores names and numbers in a map, supports lookup and lists entries alphabetically.

Expected result: Lookups for existing and missing names behave correctly, and the list is alphabetical.

Check your understanding

  1. Which container keeps keys sorted?

    Show answer

    std::map (and std::set).

  2. What happens when you read map[key] for a missing key?

    Show answer

    A default value is inserted for that key.

Taught live by an instructor — online or in person. Free course lessons are for self-study and do not lead to a certificate — see registration options.