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.
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.
C++1#include <iostream> 2#include <string> 3#include <map> 4 5class PhoneBook { 6public: 7 PhoneBook() = default; 8 9 void addContact(const std::string& name, const std::string& phoneNumber) { 10 // Method to add a contact 11 contacts[name] = phoneNumber; 12 } 13 14 std::string getPhoneNumber(const std::string& name) { 15 // Method to retrieve a contact's phone number, or "None" if it's not in contacts 16 if (contacts.find(name) != contacts.end()) { 17 return contacts[name]; 18 } 19 return "None"; 20 } 21 22private: 23 std::map<std::string, std::string> contacts; 24}; 25 26// Create a PhoneBook instance 27int main() { 28 PhoneBook phoneBook; 29 30 // Add contacts 31 phoneBook.addContact("Alice", "123-456-7890"); 32 phoneBook.addContact("Bob", "234-567-8901"); 33 std::cout << phoneBook.getPhoneNumber("Alice") << std::endl; // Output: 123-456-7890 34 std::cout << phoneBook.getPhoneNumber("Bobby") << std::endl; // Output: None 35 36 return 0; 37}
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.
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:
C++1#include <iostream> 2#include <string> 3#include <map> 4 5class TaskManager { 6public: 7 TaskManager() = default; 8 9 void addOrUpdateTask(const std::string& taskName, const std::string& status) { 10 // Add a new task or update an existing task 11 tasks[taskName] = status; 12 } 13 14 std::string getTaskStatus(const std::string& taskName) { 15 // Retrieve the status of a task; returns "Not Found" if the task does not exist 16 auto it = tasks.find(taskName); 17 if (it != tasks.end()) { 18 return it->second; 19 } 20 return "Not Found"; 21 } 22 23 void deleteTask(const std::string& taskName) { 24 // Removes a task using its name 25 if (tasks.erase(taskName) == 0) { 26 std::cout << "Task '" << taskName << "' not found." << std::endl; 27 } 28 } 29 30private: 31 std::map<std::string, std::string> tasks; 32}; 33 34// Test the TaskManager class 35int main() { 36 TaskManager myTasks; 37 myTasks.addOrUpdateTask("Buy Milk", "Pending"); 38 std::cout << myTasks.getTaskStatus("Buy Milk") << std::endl; // Output: Pending 39 myTasks.addOrUpdateTask("Buy Milk", "Completed"); 40 std::cout << myTasks.getTaskStatus("Buy Milk") << std::endl; // Output: Completed 41 42 myTasks.deleteTask("Buy Milk"); 43 std::cout << myTasks.getTaskStatus("Buy Milk") << std::endl; // Output: Not Found 44 45 return 0; 46}
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.
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:
C++1#include <iostream> 2#include <string> 3#include <map> 4 5class TaskManager { 6public: 7 TaskManager() = default; 8 9 void addTask(const std::string& taskName, const std::string& status) { 10 tasks[taskName] = status; 11 } 12 13 void printAllTasks() { 14 // Prints all tasks' keys and values 15 for (const auto& task : tasks) { 16 std::cout << task.first << ": " << task.second << std::endl; 17 } 18 } 19 20private: 21 std::map<std::string, std::string> tasks; 22}; 23 24int main() { 25 TaskManager myTasks; 26 myTasks.addTask("Buy Milk", "Pending"); 27 myTasks.addTask("Pay Bills", "Completed"); 28 29 myTasks.printAllTasks(); 30 31 return 0; 32}
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 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.
C++1#include <iostream> 2#include <string> 3#include <map> 4 5class StudentDatabase { 6public: 7 StudentDatabase() = default; 8 9 void addStudent(const std::string& name, const std::map<std::string, std::string>& subjects) { 10 // Adds a student with a map of subjects and corresponding grades 11 students[name] = subjects; 12 } 13 14 std::string getMark(const std::string& name, const std::string& subject) { 15 // Retrieves the grade for a specific subject of a specific student; 16 // Returns "N/A" if the student or subject is not found 17 auto it = students.find(name); // Find the student by name 18 if (it != students.end()) { // Check if student exists 19 auto subIt = it->second.find(subject); // Find the subject in student's map 20 if (subIt != it->second.end()) { // Check if subject exists 21 return subIt->second; // Return the grade 22 } 23 } 24 return "N/A"; // Return "N/A" if student or subject not found 25 } 26 27 void printDatabase() { 28 // Prints all students with their subjects and corresponding grades 29 for (const auto& student : students) { 30 std::cout << "Student: " << student.first << std::endl; // Print student name 31 for (const auto& subject : student.second) { 32 std::cout << " Subject: " << subject.first << ", Grade: " << subject.second << std::endl; // Print subject and grade 33 } 34 } 35 } 36 37private: 38 // Nested map holding student names as keys 39 // and another map as their value, which holds subject names and grades 40 std::map<std::string, std::map<std::string, std::string>> students; 41}; 42 43int main() { 44 StudentDatabase studentDB; 45 studentDB.addStudent("Alice", {{"Math", "A"}, {"English", "B"}}); // Add a student with subjects 46 47 // Retrieve and print grades for specific subjects 48 std::cout << studentDB.getMark("Alice", "English") << std::endl; // Output: B 49 std::cout << studentDB.getMark("Alice", "History") << std::endl; // Output: N/A 50 51 // Print the complete database 52 studentDB.printDatabase(); 53 /* 54 Output: 55 Student: Alice 56 Subject: English, Grade: B 57 Subject: Math, Grade: A 58 */ 59 60 return 0; 61}
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.
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:
C++1#include <iostream> 2#include <string> 3#include <map> 4 5class ShoppingCart { 6public: 7 ShoppingCart() = default; 8 9 void addProduct(const std::string& productName, int quantity) { 10 // Add or update the quantity of a product in the cart 11 // If productName does not exist in the cart, no errors is thrown; 12 // instead, it is inserted in the map with a default value (0 for integers) 13 // Then the given quantity will be added to this default value 14 cart[productName] += quantity; 15 } 16 17 void removeProduct(const std::string& productName) { 18 // Remove a product from the cart 19 auto it = cart.find(productName); 20 if (it != cart.end()) { 21 cart.erase(it); 22 } else { 23 std::cout << productName << " not found in your cart." << std::endl; 24 } 25 } 26 27 void showCart() const { 28 // Display the products and their quantities in the cart 29 if (cart.empty()) { 30 std::cout << "Your shopping cart is empty." << std::endl; 31 } else { 32 for (const auto& item : cart) { 33 std::cout << item.first << ": " << item.second << std::endl; 34 } 35 } 36 } 37 38private: 39 std::map<std::string, int> cart; 40}; 41 42int main() { 43 ShoppingCart myCart; 44 45 // Add products and update their quantities 46 myCart.addProduct("Apples", 5); 47 myCart.addProduct("Bananas", 2); 48 myCart.addProduct("Apples", 3); // Updates quantity of apples to 8 49 50 // Display cart 51 myCart.showCart(); 52 53 // Output: 54 // Apples: 8 55 // Bananas: 2 56 57 // Remove a product and show the updated cart 58 myCart.removeProduct("Bananas"); 59 myCart.showCart(); 60 61 // Output: 62 // Apples: 8 63 64 return 0; 65}
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.
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!