Group by Key - C++ DSA

Build buckets keyed by a shared field, preserving the first-seen key order.

Algorithm

Canonical pairs (a,1), (b,2), (a,3), (c,4), (b,5) print {a: [1, 3], b: [2, 5], c: [4]}. The replay uses the same input in every language, so this C++ DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.cpp

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<pair<string, int>> pairs = {{"a", 1}, {"b", 2}, {"a", 3}, {"c", 4}, {"b", 5}};
    map<string, vector<int>> groups;
    vector<string> order;
    for (auto [key, value] : pairs) {
        if (groups.find(key) == groups.end()) {
            order.push_back(key);
        }
        groups[key].push_back(value);
    }
    cout << "{";
    for (size_t i = 0; i < order.size(); i++) {
        const string& key = order[i];
        if (i > 0) cout << ", ";
        cout << key << ": [";
        for (size_t j = 0; j < groups[key].size(); j++) {
            if (j > 0) cout << ", ";
            cout << groups[key][j];
        }
        cout << "]";
    }
    cout << "}\n";
}

Complexity

Time: O(n) average
Space: O(k + n) for buckets and values

Implementation notes

Keep output formatting deterministic. Do not rely on unordered hash-map printing when the lesson needs cross-language comparison.
The trace highlights the hash table state after each write.

bucket map Each key owns a list. A new key creates a bucket; a repeated key appends to the existing bucket.