Maps_sets

Maps and Sets

Maps and sets are associative containers that store elements in sorted order and provide fast lookup. This chapter covers how to use them effectively.

std::map

std::map stores key-value pairs in sorted order by key.

Creating Maps

#include <map>
#include <iostream>

int main() {
    // Empty map
    std::map<std::string, int> ages;

    // Initialize from list (C++11)
    std::map<std::string, int> ages2 = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    // Using insert
    ages.insert({"David", 28});
    ages.insert(std::make_pair("Eve", 22));
    ages.insert(std::pair<std::string, int>("Frank", 40));
}

Accessing Elements

std::map<std::string, int> ages = {{"Alice", 30}, {"Bob", 25}};

// Using at() - throws if key doesn't exist
int alice = ages.at("Alice");

// Using [] - creates if doesn't exist (careful!)
int newPerson = ages["NewPerson"];  // Creates entry with value 0

// Find returns iterator
auto it = ages.find("Bob");
if (it != ages.end()) {
    std::cout << it->first << ": " << it->second << "\n";
}

// Check existence
if (ages.count("Alice")) {  // 1 if exists, 0 if not
    std::cout << "Alice exists\n";
}

Modifying Maps

std::map<std::string, int> ages = {{"Alice", 30}};

// Insert or update
ages["Bob"] = 25;              // Insert
ages["Alice"] = 31;            // Update

// Insert (doesn't overwrite)
ages.insert({"Alice", 35});     // No effect - key exists
ages.insert_or_assign("Alice", 35);  // Overwrites

// Erase
ages.erase("Bob");             // By key
auto it = ages.find("Alice");
if (it != ages.end()) {
    ages.erase(it);             // By iterator
}

Iteration

std::map<std::string, int> ages = {{"Alice", 30}, {"Bob", 25}};

// Range-based for (C++17 structured bindings)
for (const auto& [name, age] : ages) {
    std::cout << name << ": " << age << "\n";
}

// Traditional
for (auto it = ages.begin(); it != ages.end(); ++it) {
    std::cout << it->first << ": " << it->second << "\n";
}

std::multimap

Allows multiple values for the same key:

std::multimap<std::string, int> scores;

scores.insert({"Math", 95});
scores.insert({"Math", 87});
scores.insert({"Science", 92});

auto range = scores.equal_range("Math");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";  // 95 87
}

std::set

Stores unique elements in sorted order:

#include <set>

std::set<int> numbers = {5, 2, 8, 1, 9, 2, 5};

// Elements are unique and sorted: {1, 2, 5, 8, 9}
for (int n : numbers) {
    std::cout << n << " ";  // 1 2 5 8 9
}

// Find
auto it = numbers.find(5);
if (it != numbers.end()) {
    std::cout << "Found: " << *it;
}

// Insert
numbers.insert(10);
numbers.erase(5);

std::multiset

Allows duplicate elements:

std::multiset<int> numbers = {5, 2, 8, 2, 5};

// Contains: {2, 2, 5, 5, 8}
auto count = numbers.count(2);  // 2

Custom Comparators

// Case-insensitive string map
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](char c1, char c2) {
                return std::tolower(c1) < std::tolower(c2);
            }
        );
    }
};

std::map<std::string, int, CaseInsensitiveCompare> ciMap;
ciMap["Alice"] = 30;
ciMap["ALICE"] = 25;  // Updates previous

Unordered Map (Hash Table)

Fast O(1) average lookup, no ordering:

#include <unordered_map>

std::unordered_map<std::string, int> hashMap;

hashMap["key1"] = 100;
hashMap["key2"] = 200;

// Faster for large datasets
// No ordering guaranteed

// Custom hash
struct MyHash {
    size_t operator()(const std::string& s) const {
        return std::hash<std::string>{}(s);
    }
};

When to Use Which

Container	Use Case	Complexity
std::map	Need sorted keys	O(log n)
std::unordered_map	Need fast lookup	O(1) average
std::set	Need unique sorted elements	O(log n)
std::unordered_set	Need fast lookup, no ordering	O(1) average
std::multimap	Multiple values per key	O(log n)

Complete Example: Phone Book

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

class PhoneBook {
private:
    std::map<std::string, std::string> contacts;  // name -> phone

public:
    void addContact(const std::string& name, const std::string& phone) {
        contacts[name] = phone;
    }

    bool removeContact(const std::string& name) {
        auto it = contacts.find(name);
        if (it != contacts.end()) {
            contacts.erase(it);
            return true;
        }
        return false;
    }

    std::string getPhone(const std::string& name) const {
        auto it = contacts.find(name);
        if (it != contacts.end()) {
            return it->second;
        }
        return "Not found";
    }

    void search(const std::string& query) const {
        // Find contacts containing query in name
        for (const auto& [name, phone] : contacts) {
            if (name.find(query) != std::string::npos) {
                std::cout << name << ": " << phone << "\n";
            }
        }
    }

    void displayAll() const {
        std::cout << "=== Phone Book ===\n";
        for (const auto& [name, phone] : contacts) {
            std::cout << name << ": " << phone << "\n";
        }
        std::cout << "Total contacts: " << contacts.size() << "\n";
    }
};

int main() {
    PhoneBook pb;

    pb.addContact("Alice", "555-1234");
    pb.addContact("Bob", "555-5678");
    pb.addContact("Charlie", "555-9012");
    pb.addContact("Diana", "555-3456");

    pb.displayAll();

    std::cout << "\nSearching for 'li':\n";
    pb.search("li");

    std::cout << "\nAlice's phone: " << pb.getPhone("Alice") << "\n";

    pb.removeContact("Bob");
    pb.displayAll();

    return 0;
}

Complete Example: Word Frequency Counter

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

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog "
                       "the fox is quick and the dog is lazy";

    std::map<std::string, int> wordCount;

    // Parse words
    std::stringstream ss(text);
    std::string word;
    while (ss >> word) {
        wordCount[word]++;  // Increment count
    }

    // Display in alphabetical order
    std::cout << "Word frequencies (sorted):\n";
    for (const auto& [word, count] : wordCount) {
        std::cout << word << ": " << count << "\n";
    }

    // For frequency order, use multimap
    std::multimap<int, std::string> freqMap;
    for (const auto& [word, count] : wordCount) {
        freqMap.insert({count, word});
    }

    std::cout << "\nMost common words:\n";
    for (auto it = freqMap.rbegin(); it != freqMap.rend(); ++it) {
        std::cout << it->second << ": " << it->first << "\n";
    }

    return 0;
}

Key Takeaways

• std::map provides sorted key-value storage with O(log n) lookup
• std::set provides sorted unique elements
• Use custom comparators for custom ordering
• std::unordered_map provides O(1) average lookup
• Maps and sets are self-balancing (typically red-black trees)

Next Steps

Let’s learn about STL algorithms.

Next Chapter: 17_algorithms.md - STL Algorithms