Grouping with maps of lists

Why this matters

Most real data comes as a flat list of records. A list of orders has one row per order, with a city on each row. Often you need the opposite view: all the orders for Pune together, all the orders for Delhi together, and so on. Turning the flat list into one group per key is called grouping.

Grouping shows up in many places. A shop groups sales by day. A school groups students by class. A log file groups errors by the server that wrote them. The steps are always the same: look at a record, find its key, and add the record to the group for that key. The data structure that holds the groups is a map from each key to a list of records.

This lesson builds that structure step by step. It covers the C++ version with std::map and std::vector, the Java version with Map and List, and the C++ std::multimap, which is a different way to hold the same groups. It also covers the mistakes that cause crashes or quietly wrong results. Every sample was compiled and run with g++ 15.2 and OpenJDK 25, and the output shown below comes from those runs.

Two terms are used throughout. A map is a collection of pairs, where each pair has a key and a value, and you look up a value by its key. A key is the label you search by, such as a city name. In this lesson the value is a list of orders.

The problem: one value per key is not enough

Suppose you write each order into a map with the city as the key. A map keeps one value per key. Writing a second order for Pune with byCity[city] = order would replace the first Pune order, so you would lose it. The map has the right keys, but it cannot hold more than one order under each key.

The fix is to make the value a list. Then each key holds a list of every record that has that key. Each time a record arrives, you find its key and append the record to that list.

Step 1: a map from city to a list of orders

Here is a complete C++ program. It has five orders, and it groups them by city. Compile it with g++ -std=c++20 -Wall.

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
struct Order {
    int id;
    std::string city;
    double total;
};
 
int main() {
    std::vector<Order> orders = {
        {1, "Pune", 250.0},
        {2, "Delhi", 120.5},
        {3, "Pune", 75.0},
        {4, "Mumbai", 300.0},
        {5, "Delhi", 99.9},
    };
 
    std::map<std::string, std::vector<Order>> byCity;
    for (const Order& o : orders) {
        byCity[o.city].push_back(o);
    }
 
    for (const auto& [city, group] : byCity) {
        std::cout << city << ":";
        for (const Order& o : group) {
            std::cout << " #" << o.id;
        }
        std::cout << '\n';
    }
    std::cout << "groups: " << byCity.size() << '\n';
}

The program prints this.

Delhi: #2 #5
Mumbai: #4
Pune: #1 #3
groups: 3

The type std::map<std::string, std::vector<Order>> reads as "a map from a string to a vector of orders". The key is the city name. The value is the list of orders for that city.

The loop line byCity[o.city].push_back(o); does the grouping in one line. The square brackets look up the key o.city. If the key is not in the map yet, the map creates a new entry with an empty vector as its value. The call push_back then adds the order to the end of that vector. The first time Pune appears, the map creates the Pune entry, and the second time, it reuses it.

The map sorts its keys. That is why Delhi prints before Mumbai and Pune. A std::map always stores keys in sorted order, so the output order is predictable.

The final loop uses a structured binding, const auto& [city, group]. This reads each map entry into two names, city for the key and group for the vector. The binding uses a reference, written with &, so the vector is not copied on each loop step.

Step 2: how the list gets created

The line byCity[o.city] deserves a closer look, because it does two jobs. It finds the entry for a key, and if the key is missing, it inserts that key with a default value. For a vector, the default value is an empty vector. The following program makes this visible.

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
int main() {
    std::map<std::string, std::vector<int>> byCity;
    byCity["Pune"].push_back(1);
 
    std::cout << "size before lookup: " << byCity.size() << '\n';
    if (byCity["Goa"].empty()) {
        std::cout << "Goa has no orders\n";
    }
    std::cout << "size after lookup: " << byCity.size() << '\n';
}

The output is this.

size before lookup: 1
Goa has no orders
size after lookup: 2

The check byCity["Goa"].empty() looked like a read, but it added a Goa entry to the map. The map now has two keys instead of one. If you only wanted to check whether a key exists, use count or contains, which do not insert anything. Exercise 5 shows this.

Step 3: the Java version

Java uses a Map whose values are List objects. The method computeIfAbsent does the same job as the C++ square brackets. It looks up the key. If the key has no value yet, it runs a small function that creates a new list and stores it.

import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.TreeMap;
 
public class GroupDemo {
    record Order(int id, String city, double total) {}
 
    public static void main(String[] args) {
        List<Order> orders = List.of(
            new Order(1, "Pune", 250.0),
            new Order(2, "Delhi", 120.5),
            new Order(3, "Pune", 75.0),
            new Order(4, "Mumbai", 300.0),
            new Order(5, "Delhi", 99.9)
        );
 
        Map<String, List<Order>> byCity = new TreeMap<>();
        for (Order o : orders) {
            byCity.computeIfAbsent(o.city(), k -> new ArrayList<>()).add(o);
        }
 
        System.out.println(byCity);
        System.out.println(byCity.get("Pune").size());
    }
}

The program prints this.

{Delhi=[Order[id=2, city=Delhi, total=120.5], Order[id=5, city=Delhi, total=99.9]], Mumbai=[Order[id=4, city=Mumbai, total=300.0]], Pune=[Order[id=1, city=Pune, total=250.0], Order[id=3, city=Pune, total=75.0]]}
2

The record Order line declares a small class that holds three fields and has toString built in, which is why each order prints in that form. The TreeMap is Java's sorted map, like std::map in C++. A HashMap would work for the grouping, but its keys come out in no sorted order.

The lambda k -> new ArrayList<>() is the function that runs only when the key is missing. The word k is the key, and the function ignores it. The call returns the list for the key, whether it was just created or was already there, and add(o) appends the order to it.

Step 4: working with each group

Once the records are grouped, a common next step is to compute something for each group. This example adds up the total of each city's orders and finds the largest order in each group. It uses the same map from Step 1, and it adds a loop inside the group loop.

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
 
struct Order {
    int id;
    std::string city;
    double total;
};
 
int main() {
    std::vector<Order> orders = {
        {1, "Pune", 250.0},
        {2, "Delhi", 120.5},
        {3, "Pune", 75.0},
        {4, "Mumbai", 300.0},
        {5, "Delhi", 99.9},
    };
 
    std::map<std::string, std::vector<Order>> byCity;
    for (const Order& o : orders) {
        byCity[o.city].push_back(o);
    }
 
    for (const auto& [city, group] : byCity) {
        double sum = 0.0;
        for (const Order& o : group) {
            sum += o.total;
        }
        auto biggest = std::max_element(group.begin(), group.end(),
            [](const Order& a, const Order& b) { return a.total < b.total; });
        std::cout << city << ": " << group.size() << " orders, total " << sum
                  << ", largest #" << biggest->id << '\n';
    }
}

The output is this.

Delhi: 2 orders, total 220.4, largest #2
Mumbai: 1 orders, total 300, largest #4
Pune: 2 orders, total 325, largest #1

The inner loop adds the totals of one group. The call to std::max_element finds the order with the largest total in that group. Its third argument is a small function, a lambda, that says how two orders are compared. A lambda is a function written inline, with the square brackets [] at its start. The call returns an iterator, and biggest->id reads the id of the order it points at.

The output says 1 orders for Mumbai. This program does not handle the singular word, so it prints the same form for one order. Printing the correct word would take one more if statement, which is left out here to keep the example short.

The steps repeat for any grouped data: group first, then loop over each group and compute what you need. The group is already together, so no search is needed inside the loop.

Checking that every record landed in a group

A grouping program can run without any error and still give a wrong answer. The most common cause is a key that looks the same to a person but is different to the computer. The map compares keys exactly, letter by letter and capital by capital, so Pune and pune are two different keys.

Suppose one of the orders was typed with a lowercase city name. The program below adds that order to the input and groups the data again.

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
struct Order {
    int id;
    std::string city;
    double total;
};
 
int main() {
    std::vector<Order> orders = {
        {1, "Pune", 250.0},
        {2, "Delhi", 120.5},
        {3, "Pune", 75.0},
        {4, "Mumbai", 300.0},
        {5, "Delhi", 99.9},
        {6, "pune", 10.0},
    };
 
    std::map<std::string, std::vector<Order>> byCity;
    for (const Order& o : orders) {
        byCity[o.city].push_back(o);
    }
 
    std::size_t placed = 0;
    for (const auto& [city, group] : byCity) {
        placed += group.size();
        std::cout << city << ": " << group.size() << '\n';
    }
    std::cout << "grouped " << placed << " of " << orders.size() << " orders\n";
}

The output is this.

Delhi: 2
Mumbai: 1
Pune: 2
pune: 1
grouped 6 of 6 orders

The program did not fail. It made a fourth group, pune, with one order, and the Pune group is now one order short. The count at the end is the check that catches this kind of problem. The total number of records in all groups should match the number of input records. If it does not, a record was lost or a group was created that you did not expect.

For real data, clean the key before using it, for example by trimming spaces and converting case, or by using a fixed list of allowed values. The check on the counts is cheap and should stay in the program while you develop it. When you test a new grouping program, print the number of input records and the number of grouped records every time, and treat any difference as a bug until you have explained it.

The multimap alternative

C++ also has std::multimap. A multimap holds pairs where one key can appear many times. Each order is one pair, with the city as the key and the order as the value. There is no list of orders stored under a key. Instead, the multimap keeps every pair in sorted key order, and the pairs with the same key sit next to each other.

#include <iostream>
#include <map>
#include <string>
 
struct Order {
    int id;
    std::string city;
    double total;
};
 
int main() {
    Order orders[] = {
        {1, "Pune", 250.0},
        {2, "Delhi", 120.5},
        {3, "Pune", 75.0},
        {4, "Mumbai", 300.0},
        {5, "Delhi", 99.9},
    };
 
    std::multimap<std::string, Order> byCity;
    for (const Order& o : orders) {
        byCity.insert({o.city, o});
    }
 
    auto [first, last] = byCity.equal_range("Pune");
    std::cout << "Pune orders:";
    for (auto it = first; it != last; ++it) {
        std::cout << " #" << it->second.id;
    }
    std::cout << '\n';
    std::cout << "all entries: " << byCity.size() << '\n';
}

The output is this.

Pune orders: #1 #3
all entries: 5

The method equal_range returns two iterators. An iterator is an object that points at one element in a container, and it acts a bit like a position marker. The first iterator points at the first Pune pair. The second points just past the last Pune pair. The loop walks from the first to the second and prints each order. Each it points at a pair, so it->second is the order.

The multimap stores five entries for five orders, because each order is its own entry. The map version stores three entries, one per city, and each holds a vector. Both give the same groups. They differ in how you read the groups back.

The multimap has no square-bracket operator, because one key can match many values and the bracket would not know which one to return. This program fails to compile.

#include <map>
#include <string>
 
int main() {
    std::multimap<std::string, int> byCity;
    byCity.insert({"Pune", 1});
    byCity["Pune"] = 2;
}

GCC reports the following. Only the first two lines of its message are shown here.

multimap_bracket.cpp: In function ‘int main()’:
multimap_bracket.cpp:7:11: error: no match for ‘operator[]’ (operand types are ‘std::multimap<std::__cxx11::basic_string<char>, int>’ and ‘const char [5]’)

The choice between the two designs depends on what you do with the groups. Use a map of vectors when you want each group as one object, to pass to a function, to count, to sort, or to print with its own heading. Use a multimap when you only need the pairs, or when you want to find a range of keys quickly. The lesson on ordered sets and range lookups in this module covers the lookup cost in more detail.

Looking up a key that may not exist

A map's square brackets insert a missing key, as shown in Step 2. The method at does a different thing. It returns the value for a key, and if the key is missing, it throws an exception. An exception is an error signal that stops the code that is running unless something catches it.

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
int main() {
    std::map<std::string, std::vector<int>> byCity;
    byCity["Pune"].push_back(1);
 
    std::cout << byCity.at("Pune").size() << '\n';
    std::cout << byCity.at("Goa").size() << '\n';
}

The output is this. The exit code is 134, which is the code a program returns when it stops because of an unhandled exception.

1
terminate called after throwing an instance of 'std::out_of_range'
  what():  map::at

The first line is correct, and the second call fails. what() gives the message of the exception, which here is map::at. Use at when a missing key is a bug that should stop the program. Use count, contains or find when a missing key is normal and you want to handle it.

Common mistakes

Forgetting to create the list in Java

In Java, map.get(key) returns null, which means "no value here", when the key is missing. Calling add on that null value crashes the program. A short example makes the error easy to spot.

import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class NpeDemo {
    public static void main(String[] args) {
        Map<String, List<String>> groups = new HashMap<>();
        groups.get("Pune").add("order 1");
        System.out.println(groups);
    }
}

The output is this.

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.List.add(Object)" because the return value of "java.util.Map.get(Object)" is null
	at NpeDemo.main(NpeDemo.java:8)

The message says the value returned by Map.get was null. The fix is to use computeIfAbsent, as in Step 3. Exercise 4 shows the corrected line.

Using the square brackets to check for a key

Writing if (byCity["Goa"].empty()) as a check adds a Goa entry to the map, as Step 2 showed. Later loops then print a Goa group that has no orders in it. Use count("Goa") to test for a key without inserting it.

Using at for keys that are often missing

at throws an exception, which stops the program when nothing catches it. If a missing key is normal, such as a city with no orders yet, check first with count or contains, and only then call at or the square brackets.

Copying each group in a loop

The loop for (const auto& [city, group] : byCity) uses a reference. If you write for (auto [city, group] : byCity) without the &, the vector for each city is copied on every step. The program still gives the same output, but it copies all the orders each time, which is slow when the groups are large. Use const auto& when you only read the groups.

Expecting a particular order from an unordered map

std::unordered_map and Java's HashMap do not keep their keys in sorted order. The order of the groups can change between library versions, or as the map grows. If you print the groups and the order matters, use std::map or TreeMap, or sort the keys yourself before printing.

Practice

Each exercise is followed by its answer. Try each one before you read the answer.

Exercise 1

Group these words by their length, using a std::map from the length to a vector of words. The words are cat, apple, dog, pear and fig. Print one line per length.

Show the answer

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
int main() {
    std::vector<std::string> words = {"cat", "apple", "dog", "pear", "fig"};
 
    std::map<std::size_t, std::vector<std::string>> byLength;
    for (const std::string& w : words) {
        byLength[w.size()].push_back(w);
    }
 
    for (const auto& [length, group] : byLength) {
        std::cout << length << ":";
        for (const std::string& w : group) {
            std::cout << ' ' << w;
        }
        std::cout << '\n';
    }
}

The output is this.

3: cat dog fig
4: pear
5: apple

The key here is the length, a std::size_t number, instead of a city name. The grouping steps are the same as in Step 1.

Exercise 2

What does the program in Step 1 print if the line std::cout << byCity.at("Goa").size() is added at the end of main, after the other output?

Show the answer

The Step 1 map has no Goa key, so at throws std::out_of_range. The program stops with terminate called after throwing an instance of 'std::out_of_range' and what(): map::at, and exits with code 134. On a terminal, the four Step 1 lines print first. When the output goes to a file or a pipe, none of them appear, because the abort skips flushing the output buffer.

Exercise 3

Change the multimap program so that it counts the Delhi orders and adds up their totals.

Show the answer

#include <iostream>
#include <map>
#include <string>
 
struct Order {
    int id;
    std::string city;
    double total;
};
 
int main() {
    Order orders[] = {
        {1, "Pune", 250.0},
        {2, "Delhi", 120.5},
        {3, "Pune", 75.0},
        {4, "Mumbai", 300.0},
        {5, "Delhi", 99.9},
    };
 
    std::multimap<std::string, Order> byCity;
    for (const Order& o : orders) {
        byCity.insert({o.city, o});
    }
 
    auto [first, last] = byCity.equal_range("Delhi");
    int count = 0;
    double sum = 0.0;
    for (auto it = first; it != last; ++it) {
        ++count;
        sum += it->second.total;
    }
    std::cout << "Delhi: " << count << " orders, total " << sum << '\n';
}

The output is this.

Delhi: 2 orders, total 220.4

The range from equal_range covers only the Delhi pairs, so the loop never sees the Pune or Mumbai orders.

Exercise 4

The Java program in Common mistakes calls groups.get("Pune").add("order 1") on a map that has no Pune key. Rewrite that line so that it works.

Show the answer

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class NpeFix {
    public static void main(String[] args) {
        Map<String, List<String>> groups = new HashMap<>();
        groups.computeIfAbsent("Pune", k -> new ArrayList<>()).add("order 1");
        System.out.println(groups);
    }
}

The output is this.

{Pune=[order 1]}

The method computeIfAbsent creates the list when the key is missing, so add never runs on null.

Exercise 5

What does this program print, and why is the second number not 0?

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
int main() {
    std::map<std::string, std::vector<int>> byCity;
    byCity["Pune"].push_back(1);
 
    std::cout << byCity.count("Goa") << ' ' << byCity.size() << '\n';
    std::cout << byCity.contains("Goa") << '\n';
}

Show the answer

The program prints the following.

0 1
0

The call count("Goa") returns 0, because Goa is not in the map. The call size() returns 1, because the map has only Pune. Neither call inserts anything. Compare this with Step 2, where the square brackets made the map size grow to 2. The method contains is available since C++20 and returns a bool, which prints as 0 here.

Summary

• Grouping turns a flat list of records into one list per key, using a map from each key to a list.
• In C++, byCity[key].push_back(record) creates the empty list the first time a key appears and adds the record to it.
• Java's computeIfAbsent does the same job, and get alone can return null and crash the program.
• A std::multimap stores one entry per record, and equal_range returns the entries for one key.
• Square brackets insert missing keys, count and contains only check, and at throws an exception on a missing key.