48. STL Associative Containers

Definition

Associative containers store elements based on a key — not based on physical position like sequence containers. These containers offer fast lookup by key, making them ideal for data that needs to be accessed by a unique identifier such as a name, ID, or timestamp.

The STL provides two main categories: ordered (using a red-black tree, keys sorted) and unordered (using a hash table, faster on average). Each has variants for unique keys and for duplicate keys.

map — Ordered Key-Value

map stores key-value pairs with keys sorted in ascending order. Every key is unique — no duplicates are allowed. Search, insert, and delete are O(log n) on average.

Code Example

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

int main() {
    map<string, int> score;

    // Insert with operator[]
    score["Mike"] = 90;
    score["John"] = 85;
    score["Anna"] = 92;

    // Insert with insert()
    score.insert({"Dana", 88});

    // Access
    cout << "Score for Mike: " << score["Mike"] << endl;

    // Check if a key exists
    if (score.find("Eric") != score.end()) {
        cout << "Eric found" << endl;
    } else {
        cout << "Eric not found" << endl;
    }

    // Iteration (automatically ordered by key)
    for (const auto& pair : score) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Code Explanation

• operator[] creates a new key if it doesn't exist yet, then initializes the value with its default (0 for int).
• insert() adds a key-value pair without modifying it if the key already exists.
• find() returns an iterator to the element or end() if not found.
• Iteration over a map is always ordered by key.

Everyday Use Cases

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

int main() {
    map<string, string> phone;

    phone["Mike"] = "081234567890";
    phone["John"] = "085678901234";
    phone["Anna"] = "089012345678";

    string name;
    cout << "Enter name: ";
    cin >> name;

    if (phone.find(name) != phone.end()) {
        cout << "Number " << name << ": " << phone[name] << endl;
    } else {
        cout << "Name not found in contacts." << endl;
    }

    return 0;
}

Conclusion

A map is the go-to choice for key-value data that needs to be ordered by key, such as directories, dictionaries, or in-memory databases.

unordered_map — Hash Map

unordered_map uses a hash table to store key-value pairs. Search and insert are O(1) on average — faster than map, but the order of keys is not guaranteed.

Code Example

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, double> price;

    price["Fried Rice"] = 25000;
    price["Chicken Noodles"] = 20000;
    price["Chicken Soup"] = 22000;
    price["Rendang"] = 35000;

    // Fast lookup
    string item = "Chicken Noodles";
    if (price.count(item)) {
        cout << item << " $" << price[item] << endl;
    }

    // Iteration (order not guaranteed)
    for (const auto& [name, priceItem] : price) {
        cout << name << ": $" << priceItem << endl;
    }

    // Remove an element
    price.erase("Chicken Soup");

    cout << "\nAfter removal:" << endl;
    for (const auto& pair : price) {
        cout << pair.first << ": $" << pair.second << endl;
    }

    return 0;
}

Code Explanation

• count() returns 1 if the key exists, 0 otherwise.
• The structured binding [name, priceItem] is a C++17 feature for destructuring a pair.
• erase() removes an element by key.

Everyday Use Cases

#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string text = "apple apple orange apple mango orange apple";
    unordered_map<string, int> frequency;

    stringstream ss(text);
    string word;
    while (ss >> word) {
        frequency[word]++;
    }

    cout << "Frequency of word:" << endl;
    for (const auto& [word, count] : frequency) {
        cout << word << ": " << count << " times" << endl;
    }

    return 0;
}

Conclusion

Use unordered_map when lookup performance matters more than key order. It's ideal for caching, counting, and lookup tables.

set — Ordered Unique Collection

set stores unique elements in sorted order. There is no key-value — the elements themselves are the keys. Insert, delete, and search are O(log n).

Code Example

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> numbers;

    numbers.insert(50);
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(30); // duplicate ignored
    numbers.insert(40);

    cout << "Size set: " << numbers.size() << endl;

    // Check existence
    if (numbers.count(30)) {
        cout << "30 is in the set" << endl;
    }

    // Ordered iteration
    for (const auto& val : numbers) {
        cout << val << " ";
    }
    cout << endl;

    // Remove
    numbers.erase(30);

    // Set operations
    set<int> other = {40, 60, 70};
    set<int> result;

    // Union
    set_union(numbers.begin(), numbers.end(),
              other.begin(), other.end(),
              inserter(result, result.begin()));

    cout << "Union: ";
    for (const auto& val : result) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

• insert() doesn't add duplicates — a second element with the same value is ignored.
• count() returns 0 or 1 for a set (because elements are unique).
• set_union() is an STL algorithm for computing the union of two sorted sets.
• inserter is a special iterator for inserting into a container.

Everyday Use Cases

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> uniqueWords;

    string text;
    cout << "Enter a sentence: ";
    getline(cin, text);

    stringstream ss(text);
    string word;
    while (ss >> word) {
        uniqueWords.insert(word);
    }

    cout << "Unique words (" << uniqueWords.size() << "):" << endl;
    for (const auto& k : uniqueWords) {
        cout << "- " << k << endl;
    }

    return 0;
}

Conclusion

A set is suitable for collecting unique elements when you need sorted order, such as counting unique words or validating input.

unordered_set — Hash Set

unordered_set stores unique elements using a hash table. Search is O(1) on average, faster than a set but without any ordering.

Code Example

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> bilangan;

    bilangan.insert(15);
    bilangan.insert(7);
    bilangan.insert(23);
    bilangan.insert(7);
    bilangan.insert(42);

    cout << "Size: " << bilangan.size() << endl;

    // Fast O(1) lookup
    if (bilangan.count(23)) {
        cout << "23 found" << endl;
    }

    for (const auto& val : bilangan) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

• Basic operations are the same as a set, but without ordering.
• Average lookup time is O(1), worst case O(n) if there are many hash collisions.
• Uses std::hash to hash elements.

Everyday Use Cases

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {1, 2, 3, 4, 5, 2, 3, 6, 7, 5, 8};
    unordered_set<int> unique(data.begin(), data.end());

    cout << "Total element: " << data.size() << endl;
    cout << "Unique elements: " << unique.size() << endl;

    // Check for duplicates
    unordered_set<int> seen;
    for (int val : data) {
        if (!seen.insert(val).second) {
            cout << "Duplikat: " << val << endl;
        }
    }

    return 0;
}

Conclusion

An unordered_set is optimal for deduplicating data and checking element existence without needing any order.

multimap and multiset

multimap allows duplicate keys in a map. multiset allows duplicate elements in a set.

Code Example

#include <iostream>
#include <map>
#include <set>
using namespace std;

int main() {
    // Multimap: one key can have many values
    multimap<string, int> classMap;

    classMap.insert({"A", 90});
    classMap.insert({"B", 85});
    classMap.insert({"A", 88});
    classMap.insert({"A", 92});

    string classToFind = "A";
    auto range = classMap.equal_range(classToFind);

    cout << "Students in class " << classToFind << ":" << endl;
    for (auto it = range.first; it != range.second; ++it) {
        cout << "  Score: " << it->second << endl;
    }

    // Multiset: duplicate elements allowed
    multiset<int> grade;
    grade.insert(85);
    grade.insert(90);
    grade.insert(85);
    grade.insert(95);
    grade.insert(90);

    cout << "\nFrequency of 85: " << grade.count(85) << endl;
    cout << "Frequency of 90: " << grade.count(90) << endl;

    return 0;
}

Code Explanation

• equal_range() returns a pair of iterators marking the range of elements with a given key.
• count() on a multiset returns the number of occurrences of an element.

Everyday Use Cases

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

int main() {
    multimap<string, string> schedule;

    schedule.insert({"Monday", "Mathematics"});
    schedule.insert({"Monday", "Language"});
    schedule.insert({"Tuesday", "Physics"});
    schedule.insert({"Tuesday", "Chemistry"});
    schedule.insert({"Monday", "English"});

    string day = "Monday";
    cout << "Schedule " << day << ":" << endl;
    auto range = schedule.equal_range(day);
    for (auto it = range.first; it != range.second; ++it) {
        cout << "  - " << it->second << endl;
    }

    return 0;
}

Conclusion

Multimap and multiset are used when duplicates need to be allowed, such as a class schedule with several subjects per day.

pair and tuple

pair stores two values of different types. tuple stores n values of different types.

Code Example

#include <iostream>
#include <tuple>
#include <string>
using namespace std;

int main() {
    // Pair
    pair<string, int> student = {"Mike", 90};
    cout << "Name: " << student.first << ", Score: " << student.second << endl;

    // Create a pair with make_pair
    auto score = make_pair("John", 85);

    // Tuple
    tuple<string, int, double> data = {"Anna", 20, 3.75};

    // Access tuple with get<>
    cout << "\nStudent data:" << endl;
    cout << "Name: " << get<0>(data) << endl;
    cout << "Age: " << get<1>(data) << endl;
    cout << "GPA: " << get<2>(data) << endl;

    return 0;
}

Code Explanation

• pair has two members: first and second.
• tuple can hold many elements, accessed with get<index>().
• make_pair() and make_tuple() make creation easier without writing the types explicitly.

Everyday Use Cases

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<string, int>> grade = {
        {"Mike", 85},
        {"John", 92},
        {"Anna", 78},
        {"Dana", 95}
    };

    // Sort by score (descending)
    sort(grade.begin(), grade.end(),
         [](const pair<string, int>& a, const pair<string, int>& b) {
             return a.second > b.second;
         });

    cout << "Peringkat student:" << endl;
    int rank = 1;
    for (const auto& [name, score] : grade) {
        cout << rank++ << ". " << name << " - " << score << endl;
    }

    return 0;
}

Conclusion

Pairs and tuples are very useful for returning multiple values from a function or for storing heterogeneous data in simple structures.

Structured Bindings (C++17)

C++17 introduced structured bindings for elegantly destructuring pairs, tuples, and arrays.

Code Example

#include <iostream>
#include <map>
#include <tuple>
using namespace std;

int main() {
    // Destructuring a pair
    pair<string, int> student = {"Mike", 90};
    auto [name, score] = student;
    cout << name << " received a score of " << score << endl;

    // Destructuring a map
    map<string, double> gpa = {
        {"John", 3.5},
        {"Anna", 3.8}
    };

    for (const auto& [studentName, gpaValue] : gpa) {
        cout << studentName << " GPA: " << gpaValue << endl;
    }

    // Destructuring a tuple
    tuple<string, int, string> info = {"Dana", 21, "Teknik"};
    auto [studentName, age, major] = info;
    cout << studentName << ", " << age << " years, " << major << endl;

    return 0;
}

Code Explanation

• auto [name, score] = student; declares variables and fills them with values from the pair automatically.
• Works with pairs, tuples, arrays, and structs (with certain limitations).

Everyday Use Cases

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<tuple<string, int, double>> student = {
        {"Mike", 20, 3.5},
        {"John", 21, 3.8},
        {"Anna", 19, 3.2}
    };

    sort(student.begin(), student.end(),
         [](const auto& a, const auto& b) {
             return get<2>(a) > get<2>(b);
         });

    cout << "Students by GPA:" << endl;
    for (const auto& [name, age, gpa] : student) {
        cout << name << " (age " << age << ") - GPA: " << gpa << endl;
    }

    return 0;
}

Conclusion

Structured bindings make code cleaner and easier to read, especially when working with pairs and tuples in iteration.

Choosing the Right Container

Summary

Associative containers are the foundation of data-driven programming in C++. Map and set for sorted order, unordered variants for speed. Pairs and tuples make managing heterogeneous data easier. Choosing the right one significantly improves both performance and code readability.