Ordered Associative Containers

A map is usually implemented as a red-black tree and is the choice when elements must be iterated over in order.

Programming

Why the Container You Pick Matters

When a program has to keep track of many elements, the container you choose quietly decides three things: how fast a lookup happens, what order you see elements in when you loop over them, and how the data is laid out in memory. Associative containers are the family that stores elements as key and value pairs, and std::map and std::unordered_map are the two members of that family this article compares.

The source treats the choice between these containers as a set of practical rules rather than abstract theory. The goal here is not to memorize those rules but to understand the reasoning behind each one, so that you can predict which container will behave the way your program needs.

What Each Container Promises

A container's behavior follows from the data structure underneath it. A map is usually implemented as a red-black tree, and the source says this is the choice when elements must be iterated over in order. An unordered_map is usually implemented as a hash table, and the source says it is the choice for fast lookup on large amounts of data.

Read the comparison as a pair of matched facts. The map column pairs its tree-based implementation with ordered iteration. The unordered_map column pairs its hash-table implementation with fast lookup on large data. Neither column claims the other's strength, so the decision comes down to which property your program needs more.

Which implementation and strength belongs to each container, and which requirement favors each one?

Tracing the Sorted Order of a map

Start with the behavior that the red-black tree implementation is chosen for: iteration in order. The tree diagram below shows four keys arranged so that a left-to-right reading of the tree yields them in sorted order. Each key sits in a node, and the order number under each node is the position it takes when the container is walked from its smallest key to its largest.

Where does each key sit in the tree, and why does visiting the nodes in order produce a sorted sequence?

The order numbers give the traversal sequence: Apple, Banana, Mango, Pear. That is alphabetical order, even though Mango was the root of the tree. The sorted sequence comes from the structure of the tree, not from the order in which the keys were inserted. This is the reason the source pairs the tree implementation with in-order iteration.

cpp

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> fruit_counts;
    fruit_counts["pear"] = 4;
    fruit_counts["apple"] = 9;
    fruit_counts["mango"] = 2;

    for (const auto& entry : fruit_counts) {
        std::cout << entry.first << " " << entry.second << "\n";
    }
}

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> fruit_counts;
    fruit_counts["pear"] = 4;
    fruit_counts["apple"] = 9;
    fruit_counts["mango"] = 2;

    for (const auto& entry : fruit_counts) {
        std::cout << entry.first << " " << entry.second << "\n";
    }
}

Output

apple 9
mango 2
pear 4

Notes on the code

The keys are inserted as pear, apple, mango.
The range-based for loop visits the entries in the map's stored order.

What do you think happens?

The keys were inserted as pear, apple, mango. In what order will the loop print them?

Insertion order: pear, apple, mango
Sorted order: apple, mango, pear
Unpredictable, because the order is not defined

Reveal answer

Answer:

apple, mango, pear

A map iterates in sorted key order, which comes from its tree structure. The insertion order does not control the output.

How a Hash Table Locates a Key

An unordered_map is usually a hash table, and the source chooses it for fast lookup on large amounts of data. A hash table works by taking a key, computing an index from it, and using that index to pick a bucket. The lookup then goes to that bucket rather than scanning through every stored element. The diagram below shows three keys being placed into buckets numbered 0 to 2.

How does each key get a bucket index, and how do two keys share one bucket?

In this picture, dog and owl are both hashed to bucket 2, so that bucket holds two entries that share the same index. Sharing a bucket is a normal part of how a hash table works. Bucket 1 has no key in this example, so it is empty. The point to take from the diagram is that a lookup starts from the key's bucket index, which is why the source associates this structure with fast lookup.

cpp

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> stock{{"cat", 7}, {"dog", 3}};
    std::cout << stock["dog"] << "\n";
}

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> stock{{"cat", 7}, {"dog", 3}};
    std::cout << stock["dog"] << "\n";
}

Output

Notes on the code

The brace list gives the initial key and value pairs.
Looking up dog computes its bucket and returns the stored value.

Choosing Between Ordered and Unordered

The source gives three guidelines for this decision. First, use unordered containers when you need fast lookup for large amounts of data. Second, use ordered associative containers such as map and set when you need to iterate over their elements in order. Third, use unordered containers for element types that have no natural order, meaning types for which no reasonable less-than comparison exists.

The ordering requirement comes first because it is the one hard constraint the source names. If the output must come out in order, an unordered container does not meet it, and the lookup and natural-order rules only decide between the options that remain. The source does not give a separate default for cases where none of these conditions applies, so these three rules should be treated as the decision basis rather than a complete procedure.

Parentheses Versus Braces When Creating Containers

Container creation uses two initializer forms, and the source gives each one a specific job. Parentheses are used when you supply a size. Braces are used when you supply a list of elements. The same pair of symbols can mean very different things depending on which form you use, so keeping this split in mind prevents a common class of mistakes.

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> sized(5);
    std::vector<int> listed{5};

    std::cout << sized.size() << " " << listed.size() << "\n";
    std::cout << listed[0] << "\n";
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> sized(5);
    std::vector<int> listed{5};

    std::cout << sized.size() << " " << listed.size() << "\n";
    std::cout << listed[0] << "\n";
}

Output

5 1
5

Notes on the code

The parentheses ask for a vector with five elements, each set to its default value of zero.
The braces create a vector whose single element is the number 5.

The two lines look almost identical, yet they produce different containers. The parenthesized form gives a count, and the braced form gives content. The lesson generalizes: before writing a container declaration, decide whether you are giving the container a size or giving it the elements themselves.

Passing and Returning Containers

Once a container exists, it often moves between functions. The source gives a direct guideline for this: pass a container by reference, and return a container by value. Passing by reference means the function receives the caller's container itself rather than a separate parameter, so the function works on the same container the caller holds. Returning by value means the function hands the container back as its result, and the caller receives it as the function's output.

Before

void add_entry(std::map<std::string, int>& counts) {
    counts["kiwi"] = 1;
}

int main() {
    std::map<std::string, int> counts;
    add_entry(counts);
}

The function takes the container by reference, so the change to counts is visible to the caller.

After

std::map<std::string, int> make_counts() {
    std::map<std::string, int> counts;
    counts["kiwi"] = 1;
    return counts;
}

int main() {
    std::map<std::string, int> counts = make_counts();
}

The function builds a container and returns it by value, so the caller receives the result as the function's output.

The two arrows in this guideline point in different directions. The input travels into the function by reference, and the result travels back out by value. Reading the two directions separately makes the guideline easier to remember: inputs travel by reference, and results travel back by value.

Best practice

Prefer compact, contiguous data structures. The source warns that a list is relatively expensive to traverse. When a container will be walked through repeatedly, a structure whose elements sit close together is a stronger default than one whose elements are scattered and costly to step through. Ask whether the structure is compact and contiguous, and whether you will traverse it often enough for traversal cost to matter.

Mistakes Beginners Make With Containers

Common mistake
Choosing unordered_map because it sounds faster, even when the output must be sorted
What it looks like
A report must list customer names alphabetically, but the program stores them in an unordered_map and prints them in loop order.
Why it fails
The source says an unordered container does not satisfy an ordering requirement, and iteration order is not something to depend on.
Do this instead
Use map when iteration must be in order, and keep unordered_map for fast lookup where order does not matter.
Common mistake
Using map for everything because it is ordered
What it looks like
A program needs fast lookup across a very large set of records and order is never used, yet it still uses map.
Why it fails
The source pairs unordered_map with fast lookup on large amounts of data, and it does not make ordering the default requirement.
Do this instead
Start from the requirement. If order is needed, use map. If fast lookup on large data is the priority and order is not needed, use unordered_map.
Common mistake
Writing parentheses where braces were intended
What it looks like
Writing std::vector<int> v(5) when the intent was a vector containing the single value 5.
Why it fails
Parentheses supply a size, so the result has five zero-valued elements instead of one element.
Do this instead
Use braces when supplying a list of elements, and parentheses when supplying a size.
Common mistake
Copying a container into a function parameter when the function only needs to read or change the caller's container, which the source's by-reference guideline avoids

Applying the Guidelines to a Requirement

MEDIUM

A program stores two million product records keyed by SKU. It must look up a product quickly by SKU, and the order of the records does not matter. Which container should it use, and why? Then describe a second requirement, a leaderboard that must print scores from highest to lowest, and say which container fits.

Hints

Identify the one hard constraint first: does the output have to come out in order?
The source associates unordered_map with fast lookup on large amounts of data.
For the leaderboard, the source associates map with iteration in order.

Your attempt (not saved)

EASY

Write a declaration that creates a std::vector<double> holding exactly three elements, each set to 2.5, using the initializer form that matches a list of elements.

Hints

A list of values uses the brace form.
Braces list three separate values, so the result has three elements.

Your attempt (not saved)

Key Takeaways Recap

1
A map is usually a red-black tree and is the choice when elements must be iterated over in order.
2
An unordered_map is usually a hash table and is the choice for fast lookup on large amounts of data.
3
Pass containers by reference, return them by value, use parentheses for sizes and braces for lists, and prefer compact contiguous structures.

At a glance

A map is usually implemented as a red-black tree, so it is the choice when elements must be iterated over in order.
An unordered_map is usually implemented as a hash table, so it is the choice for fast lookup on large amounts of data.
If output must come out in order, use map or set, because an unordered container does not satisfy that requirement.
Use parentheses to supply a size and braces to supply a list of elements.
Pass containers by reference and return them by value, and prefer compact, contiguous structures when traversal cost matters.

More concepts starting with O

Why the Container You Pick Matters

What Each Container Promises

Tracing the Sorted Order of a map

How a Hash Table Locates a Key

Choosing Between Ordered and Unordered

Parentheses Versus Braces When Creating Containers

Passing and Returning Containers

Mistakes Beginners Make With Containers

Applying the Guidelines to a Requirement

Key Takeaways Recap

At a glance

Related Topics