Introduction

Welcome to our data structures revision! Today, we will delve deeply into C++ Maps. Much like a bookshelf, maps allow you to quickly select the book (value) you desire by reading its label (key). They are vital to C++ for quickly accessing values using keys, as well as for efficient key insertion and deletion. So, let's explore C++ maps for a clearer understanding of these concepts.

C++ Maps

Our journey starts with C++ maps, a pivotal data structure that holds data as key-value pairs. Imagine storing your friend's contact info in such a way that allows you to search for your friend's name (the key) and instantly find their phone number (the value).

To define a map in C++, you use the std::map template from the <map> header. For example, std::map<std::string, std::string> contacts; defines a map where both keys and values are strings. This map, contacts, can store names and their corresponding phone numbers.

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

class PhoneBook {
public:
    PhoneBook() = default;

    void addContact(const std::string& name, const std::string& phoneNumber) {
        // Method to add a contact
        contacts[name] = phoneNumber;
    }

    std::string getPhoneNumber(const std::string& name) {
        // Method to retrieve a contact's phone number, or "None" if it's not in contacts
        if (contacts.find(name) != contacts.end()) {
            return contacts[name];
        }
        return "None";
    }

private:
    std::map<std::string, std::string> contacts;
};

// Create a PhoneBook instance
int main() {
    PhoneBook phoneBook;

    // Add contacts
    phoneBook.addContact("Alice", "123-456-7890");
    phoneBook.addContact("Bob", "234-567-8901");
    std::cout << phoneBook.getPhoneNumber("Alice") << std::endl;  // Output: 123-456-7890
    std::cout << phoneBook.getPhoneNumber("Bobby") << std::endl;  // Output: None

    return 0;
}

In the above code, we create a PhoneBook class that uses a std::map to store contacts. As you can see, maps simplify the processes of adding, modifying, and accessing information with unique keys.

Operations in Maps

C++ maps enable a variety of operations for manipulating data, such as setting, getting, and deleting key-value pairs. Understanding these operations is crucial for efficient data handling in C++.

To add or update entries in a map, you directly assign a value to a key. If the key exists, the value is updated; if not, a new key-value pair is added. This flexibility allows for dynamic updates and additions to the map without needing a predefined structure.

The find operation is used to retrieve the value associated with a specific key. It provides a safe way to access values since it allows checking if the key exists, preventing errors that would arise from attempting to access a non-existent key. If the key doesn't exist, find returns an iterator to end().

Deleting an entry is done using the erase method followed by the key. This operation removes the specified key-value pair from the map, which is essential for managing the contents of the map actively. If the key doesn't exist, erase returns 0.

Let’s see how these operations work in the context of a Task Manager class:

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

class TaskManager {
public:
    TaskManager() = default;

    void addOrUpdateTask(const std::string& taskName, const std::string& status) {
        // Add a new task or update an existing task
        tasks[taskName] = status;
    }

    std::string getTaskStatus(const std::string& taskName) {
        // Retrieve the status of a task; returns "Not Found" if the task does not exist
        auto it = tasks.find(taskName);
        if (it != tasks.end()) {
            return it->second;
        }
        return "Not Found";
    }

    void deleteTask(const std::string& taskName) {
        // Removes a task using its name
        if (tasks.erase(taskName) == 0) {
            std::cout << "Task '" << taskName << "' not found." << std::endl;
        }
    }

private:
    std::map<std::string, std::string> tasks;
};

// Test the TaskManager class
int main() {
    TaskManager myTasks;
    myTasks.addOrUpdateTask("Buy Milk", "Pending");
    std::cout << myTasks.getTaskStatus("Buy Milk") << std::endl;  // Output: Pending
    myTasks.addOrUpdateTask("Buy Milk", "Completed");
    std::cout << myTasks.getTaskStatus("Buy Milk") << std::endl;  // Output: Completed

    myTasks.deleteTask("Buy Milk");
    std::cout << myTasks.getTaskStatus("Buy Milk") << std::endl;  // Output: Not Found

    return 0;
}

This example showcases how to leverage map operations in C++ to effectively manage data by adding, updating, retrieving, and deleting entries through a simulated Task Manager application.

Looping Through Maps

C++ provides an elegant way to loop through maps using iterators. We can iterate through keys, values, or both simultaneously.

Let's explore this in our Task Manager example:

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

class TaskManager {
public:
    TaskManager() = default;

    void addTask(const std::string& taskName, const std::string& status) {
        tasks[taskName] = status;
    }
        
    void printAllTasks() {
        // Prints all tasks' keys and values
        for (const auto& task : tasks) {
            std::cout << task.first << ": " << task.second << std::endl; 
        }
    }

private:
    std::map<std::string, std::string> tasks;
};

int main() {
    TaskManager myTasks;
    myTasks.addTask("Buy Milk", "Pending");
    myTasks.addTask("Pay Bills", "Completed");

    myTasks.printAllTasks();

    return 0;
}

In this case, the loop iterates through all key-value pairs in the map and prints the keys (task names) followed by the values (statuses) of the tasks. Here, task.first (from the pair object returned by the iterator) returns the key (task name), and task.second returns the value (task status).

Nesting with Maps

Nesting in maps involves storing maps within another map. It's useful when associating multiple pieces of information with a key. Let's see how this works in a Student Database example. Here, we are using iterator-based loops to navigate through the nested maps.

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

class StudentDatabase {
public:
    StudentDatabase() = default;

    void addStudent(const std::string& name, const std::map<std::string, std::string>& subjects) {
        // Adds a student with a map of subjects and corresponding grades
        students[name] = subjects;
    }

    std::string getMark(const std::string& name, const std::string& subject) {
        // Retrieves the grade for a specific subject of a specific student;
        // Returns "N/A" if the student or subject is not found
        auto it = students.find(name);  // Find the student by name
        if (it != students.end()) {  // Check if student exists
            auto subIt = it->second.find(subject);  // Find the subject in student's map
            if (subIt != it->second.end()) {  // Check if subject exists
                return subIt->second;  // Return the grade
            }
        }
        return "N/A";  // Return "N/A" if student or subject not found
    }

    void printDatabase() {
        // Prints all students with their subjects and corresponding grades
        for (const auto& student : students) {
            std::cout << "Student: " << student.first << std::endl;  // Print student name
            for (const auto& subject : student.second) {
                std::cout << "    Subject: " << subject.first << ", Grade: " << subject.second << std::endl;  // Print subject and grade
            }
        }
    }

private:
    // Nested map holding student names as keys
    // and another map as their value, which holds subject names and grades
    std::map<std::string, std::map<std::string, std::string>> students;
};

int main() {
    StudentDatabase studentDB;
    studentDB.addStudent("Alice", {{"Math", "A"}, {"English", "B"}});  // Add a student with subjects
    
    // Retrieve and print grades for specific subjects
    std::cout << studentDB.getMark("Alice", "English") << std::endl;  // Output: B
    std::cout << studentDB.getMark("Alice", "History") << std::endl;  // Output: N/A
    
    // Print the complete database
    studentDB.printDatabase();
    /*
    Output:
    Student: Alice
        Subject: English, Grade: B
        Subject: Math, Grade: A
    */

    return 0;
}

C++ maps are ordered data structures, meaning they automatically sort their keys. In the printDatabase method, subjects will be printed in lexicographical order, which is why "English" comes before "Math" in the output. This ordering ensures that the data remains structured and predictable. If ordering is not required and faster average access times are preferred, you can use std::unordered_map instead, which does not maintain any order for its keys and offers average constant-time complexity for insertions and lookups.

Hands-on Example

Let's shift our focus to a more interactive and familiar scenario: managing a shopping cart in an online store. This hands-on example will demonstrate how maps can be used to map product names to their quantities in a shopping cart. You will learn how to add products, update quantities, and retrieve the total number of items in the cart.

Here’s how you can implement and manipulate a shopping cart using a C++ map:

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

class ShoppingCart {
public:
    ShoppingCart() = default;

    void addProduct(const std::string& productName, int quantity) {
        // Add or update the quantity of a product in the cart
        // If productName does not exist in the cart, no errors is thrown; 
        // instead, it is inserted in the map with a default value (0 for integers)
        // Then the given quantity will be added to this default value
        cart[productName] += quantity;  
    }

    void removeProduct(const std::string& productName) {
        // Remove a product from the cart
        auto it = cart.find(productName);
        if (it != cart.end()) {
            cart.erase(it);
        } else {
            std::cout << productName << " not found in your cart." << std::endl;
        }
    }

    void showCart() const {
        // Display the products and their quantities in the cart
        if (cart.empty()) {
             std::cout << "Your shopping cart is empty." << std::endl;
        } else {
            for (const auto& item : cart) {
                std::cout << item.first << ": " << item.second << std::endl;
            }
        }
    }

private:
    std::map<std::string, int> cart;
};

int main() {
    ShoppingCart myCart;

    // Add products and update their quantities
    myCart.addProduct("Apples", 5);
    myCart.addProduct("Bananas", 2);
    myCart.addProduct("Apples", 3);  // Updates quantity of apples to 8

    // Display cart
    myCart.showCart();
    
    // Output:
    // Apples: 8
    // Bananas: 2

    // Remove a product and show the updated cart
    myCart.removeProduct("Bananas");
    myCart.showCart();

    // Output:
    // Apples: 8

    return 0;
}

This example showcases the practical application of maps to manage a dynamic dataset, such as an online shopping cart. By using product names as keys and their quantities as values, we achieve efficient and flexible data manipulation. This exercise provides a solid foundation for understanding how to handle complex data structures in real-world C++ applications.

Lesson Summary and Practice

Well done! Today, we delved into C++ maps and explored various operations on maps. We now invite you to get hands-on experience with the upcoming practice exercises. To master these concepts and hone your C++ map skills, practice is key. Happy learning!

Previous
Next
Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal