DATA DICTIONARY - MAPS IN C++

Page Content

Welcome to the page dedicated to maps in C++! This page provides all the key information, code examples, and practical tips for working with maps. Using the table of contents, you can quickly jump to interesting sections and find the content that interests you.

Introduction

Maps in C++ are data collections that store values accessible through unique keys. They implement the concept of a "dictionary," where each key is associated with a corresponding value. By using maps, programmers can efficiently organize and search for data, as accessing elements through keys enables faster operations compared to sequential containers.

Additionally, maps are used in many applications where fast data access is required, such as databases, caching results, and various algorithms. The C++ Standard Library provides std::map, which is implemented as a balanced tree (e.g., a red-black tree), ensuring a time complexity of O(log n) for fundamental operations like insertion, deletion, and lookup.

A map is declared as follows:

std::map<key_type, value_type> map_name;

In the following sections, we will explain in detail how maps are used, how to manipulate their elements, and how to perform iteration, deletion, and sorting operations.

Declaration and Initialization of a Map

Consider the following problem:

Given the names of a group of students in a class, enter their average grades at the end of the school year. Determine the class average and find out how many students achieved above-average success.

Solution: We will solve this example using maps, where the student's name will be used as the key, and their grade will be stored as the value in the map.

To use maps in a C++ file, the map header file must be included:

#include <map>
#include <string>

Next, we need to declare the map:

std::map<std::string, double> average;

We see that the key type is string (representing student names), while the value type is double, as the values represent average grades, which are real numbers.

Map Initialization:

One way to populate a map with values is to initialize it, which is useful when we already know the students' data, their names, and their achieved grades at the end of the year.

average = {
  {"Michael", 4.52},
  {"Milica", 4.78},
  {"Nickol", 3.89}
};

Iteration and Element Access

In each loop iteration, the next pair containing both the key and the value (student's name and average grade) is retrieved. The key is accessed using the first attribute, while the value is accessed using the second attribute.

// Printing data stored in the map
for(auto keyValuePair : average){
    std::cout << keyValuePair.first << " " 
                << keyValuePair.second << std::endl;
}

Figure 1: Printing elements in the map - program execution

Types of Iteration and Printing Map Elements

In C++, there are two main ways to iterate through a map: using a range-based for loop and using iterators. Both approaches have their advantages and use cases, and their characteristics and usage recommendations are presented below.

1. Range-based for Loop

This approach is intuitive and makes the code more readable, especially when working with a map that does not require element modification during iteration.

std::map<string, int> participants = { {"Mark", 3}, {"Anna", 2}, {"Ivan", 1} };
for (const auto& pair : participants) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

Advantages:

Simple and easy to understand.
Efficiency: Uses const auto& to avoid copying pairs.
Suitable for cases where direct control over map elements is not needed.

Disadvantages:

Less flexibility when element modification or specific positioning is required.

2. Iterators

Iterators offer greater flexibility by providing direct access to elements, which can be useful when modifying the map’s content or controlling the iteration flow.

std::map<string, int> participants = { {"Mark", 3}, {"Anna", 2}, {"Ivan", 1} };
for (auto it = participants.begin(); it != participants.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

Advantages:

Allows modifying element values during iteration.
Supports complex operations, such as removing the current element (it = participants.erase(it)).

Disadvantages:

Code can become less readable, especially for beginners.
More complex than a range-based for loop.

Performance Comparison:

For iterating through all elements of a map, both approaches are equally efficient, with a time complexity of O(n). The range-based for loop is often preferable when only reading elements, while iterators provide more flexibility for modifications.

Usage Recommendations:

Use the range-based for loop when you need simple iteration without modifying the contents.
Use iterators when modifying element values, skipping certain elements, or deleting elements from the map during iteration.

Test your code in the editor!

// Write your C++ code here...

Enter input for the program:

Inputing a C++ Map

Another way to populate a map with values is by loading from standard input, where the user is asked to enter a student's name along with their achieved score.

Entering a key-value pair can be added to the map at its end using the insert function. Let's look at the following code:

// Loading key-value pairs into the map;
int n;
string studentName;
double average;
std::cout << "Enter the number of students" << std::endl;
std::cin >> n;
for(int i = 0; i < n; i++){
    std::cout << "Enter student name" << std::endl;
    std::cin >> studentName;
    std::cout << "Enter average score" << std::endl;
    std::cin >> average;
    averageMap.insert(pair<string, double>(studentName, average));
}
// Printing data stored in the map
for(auto keyValuePair : averageMap){
    std::cout << keyValuePair.first << " "
                << keyValuePair.second << std::endl;
}

Entering data into the map while checking if the key already exists – inserting data into the map using the [] operator.

Example:

#include <iostream>
#include <map>
#include <string>
using namespace std;
  
int main() {
    map<string, int> participants;
  
    // Example of participant entry
    string entries[] = {"Mark", "Ana", "Mark", "Ivan", "Ana"};
    for (const string& name : entries) {
        participants[name]++; // Increases participation count (default value for new keys is 0)
    }
  
    // Printing the map
    for (const auto& pair : participants) {
        std::cout << "Participant: " << pair.first
                  << ", Participation count: " << pair.second
                  << std::endl;
    }
  
    return 0;
}

Explanation:
Operator [] – If a key (e.g., "Mark") does not exist in the map, it creates it with a default value (0 for int). Then, the value is increased by 1.

Note: If we use:
participants["NewParticipant"]++;
This adds "NewParticipant" with a value of 1, even if it was not previously entered.
To avoid this, we use find:
auto it = participants.find("NewParticipant");
if (it != participants.end()) {
it->second++;
} else {
std::cout << "Participant not found!" << std::endl;
}

Note for Users

If you don't want to constantly write the std:: prefix before functions, types, and other members of the standard library in C++ code, you can use the following command:

 using namespace  std;

This command tells the compiler to automatically use the std namespace throughout the rest of the code, eliminating the need to repeatedly specify the prefix.

Advantages:

Simplicity and readability: It shortens the code and makes it easier to write, which is useful in smaller projects, examples, and educational situations.
Faster coding: There's no need to constantly type std::, which can speed up the development and testing of simple programs.

Disadvantages:

Potential name conflicts: In larger projects or when using multiple libraries, using namespace std; may cause name conflicts, as different libraries may have functions or types with the same names.
Lack of explicitness: When using namespace std; is used, it's not immediately clear where individual symbols come from, which can make it harder to understand the code during maintenance or when working in teams.
Professional standards: In professional projects, it's often recommended to explicitly use std:: to clearly define the origin of each symbol, improving code readability and maintainability.

In conclusion, using using namespace std; is practical for smaller projects and examples, but in larger or professional codebases, it is recommended to explicitly use the std:: prefix.

Printing a map using an iterator

We define an iterator (cursor) that points to a specific pair within the map and can easily move through the map:



    map<string, double>::iterator iter;

Loop-based printing:


    void printMap(map<string, double> averageMap){
        // printing data stored within the map
        map<string, double>::iterator iter;
        for(iter = averageMap.begin(); iter != averageMap.end(); ++iter){
            cout << iter -> first << " " << iter -> second << endl;
        }
    }

Copying from one map to another

A map averageMap2 is declared, which will have the same elements as Map 1. When declaring it, we need to pass iterators to the beginning and end of the first map.


// copying a map
cout << "Map 2: " << endl;
map<string, double> averageMap2(averageMap.begin(), averageMap.end());
printMap(averageMap2);

Here, we moved the map printing functionality into a separate function printMap, which takes a map as a parameter and prints its contents.


void printMap(map<string, double> averageMap){
    // printing data stored within the map
    for(auto keyValuePair: averageMap){
        cout << keyValuePair.first << " " << keyValuePair.second << endl;
    }
}

If we combine assigning a map, entering new pairs into the map, and finally copying the contents from one map to another, the complete code would be:

Working with a C++ Map: Inserting and Copying

This example demonstrates how to create a map to store student names and their average scores, insert new entries from user input, copy the map, and print its contents.

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

// Function to print the contents of the map
void printMap(map<string, double> averageMap)
{
    // Using an iterator to loop through the map
    map<string, double>::iterator iter;
    for(iter = averageMap.begin(); iter != averageMap.end(); ++iter)
    {
        // Printing the key and value (student name and average score)
        cout << iter -> first << " " << iter -> second << endl;
    }
}

int main()
{
    // Creating a map to store student names and their average scores
    map<string, double> averageMap;
    averageMap =
    {
        {"Michael", 4.52},
        {"Milica", 4.78},
        {"Nickol", 3.89}
    };

    // Variable to hold the number of students to input
    int n;
    string studentName;
    double avg;

    // Prompt the user to enter the number of students
    cout << "Enter the number of students" << endl;
    cin >> n;

    // Loop to enter the name and average score of each student
    for(int i = 0; i < n; i++)
    {
        cout << "Enter student name" << endl;
        cin >> studentName;
        cout << "Enter average score" << endl;
        cin >> avg;

        // Inserting the new student name and score into the map
        averageMap.insert(pair<string, double>(studentName, avg));
    }

    // Create a copy of the original map (averageMap)
    cout << "Map 2: " << endl;
    map<string, double> averageMap2(averageMap.begin(), averageMap.end());

    // Print the copied map
    printMap(averageMap2);

    return 0;
}

After execution:

Figure 2: Overwriting elements from one map to another - program execution

Deleting Elements in a C++ Map

Deleting elements from a map can be done using the erase function.

Deleting Elements with a Specific Key Value

If we want to delete an element whose key is, for example, nameToDelete, this can be done as follows:


// Deleting elements with a specific key value
string nameToDelete = "Nicholas";
averageMap2.erase(nameToDelete);
cout << "After deletion, map 2 looks like " << endl;
print2(averageMap2);

Deleting All Elements in a Map


// Deleting all elements in the map
averageMap2.clear();
cout << "After deletion, using clear, the number of elements in map 2 is " 
     << averageMap2.size();

After deletion, map 2 will have no elements, i.e., its size will be zero.

Deleting Elements in Maps: Recommendations and Caution

The erase function allows deleting elements from a map using a key, iterator, or range of iterators. However, when using this function, pay attention to several potential mistakes:

1. Deleting a Non-Existent Key

If you try to delete a key that does not exist in the map, erase will not cause an error, but it will have no effect. To avoid unnecessary operations, it is recommended to check for the key's presence first:


auto it = map.find(key);
if (it != map.end()) {
    map.erase(it);
}

2. Deleting During Iteration

When deleting elements while iterating through a map, use the return value of erase (a new iterator pointing to the next element) to avoid iterator invalidation:


for (auto it = map.begin(); it != map.end(); ) {
    if (condition) {
        it = map.erase(it);
    } else {
        ++it;
    }
}

3. Deleting Multiple Elements (Bulk Deletion)

When you want to delete all elements in a given range, use erase with a range of iterators:


map.erase(map.begin(), map.find("keys_up_to_here"));

4. Performance Impact

The erase function has a complexity of O(log N) for individual elements, while deleting an entire range can be faster as operations are optimized for larger data sets. It is recommended to choose an approach based on the number of elements being deleted.

5. Practical Tips

When to use find before erase: In critical systems or where key presence is uncertain.
When to use erase directly: When you are sure the key exists or in simple cases.

6. Example Error

If you use an iterator that has become invalid after deletion:


auto it = map.erase(map.begin());
cout << it->first; // Correct, iterator is valid.

Finding Values in a Map

Finding a Value by Key

If the key is known, the find function first returns an iterator pointing to the pair whose key was passed to the function. Then, the value can be extracted using the iterator, as shown in the following code:


string key = "Michael";
map<string, double>::iterator it;
it = averageMap.find(key);
cout << endl << it->first << " has an average of " << it->second;

Finding Elements by Value

If we want to find an element in the map based on its value (not the key), we need to iterate through the entire map and check if any value matches the given one:


double targetValue = 9.5;
bool found = false;

for (auto it : averageMap) {
    if (it.second == targetValue) {
        cout << "Found: " << it.first << " with an average of " << it.second << endl;
        found = true;
        break;
    }
}

if (!found) {
    cout << "No student found with the given average!" << endl;
}

This method searches the map by values, but due to iterating through all elements, it has a time complexity of O(n).

Sorting a Map by Value

First, the elements need to be transferred into a vector:


// Declaring a vector of pairs from the map
vector <pair<string, double>> A;

// Copying key-value pairs from the map into the vector
for (auto& it : averageMap) {
    A.push_back(it);
}

Then, sorting is performed in ascending order by value using the sort function with a custom comparator. The comparator function compares the second element (the value) of each pair and returns true if the first value is less than the second, ensuring an ascending order.


// Comparator function to sort pairs in ascending order by their value
bool compareByValue(const pair<string, double>& a, 
                 const pair<string, double>& b) {
    return a.second < b.second;
}

sort(A.begin(), A.end(), compareByValue);
cout << "After sorting, the vector (sorted by value in ascending order):" << endl;
for(auto& it : A) {
    cout << it.first << ": " << it.second << endl;
}

If we combine the previous parts of the code into a single unit, which should give an initial map of student averages, add n more students and their averages, delete a student named Nickolas, write the data into a new map, and finally sort that map by value and print it, then it would look like below:

Combined Code Example

In this section, we merge the previous parts of the code into one complete program. The program demonstrates how to create a map to store student names and their average scores, add new entries via user input, delete a specific element from the map, and finally sort the data by average score using a vector and a custom comparator.


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

using namespace std;

// Function to print the contents of a map
void printMap(const map<string, double>& averageMap)
{
    for (const auto& iter : averageMap)
    {
        cout << iter.first << " " << iter.second << endl;
    }
}

// Comparator function to sort elements by value (the second element of the pair) in ascending order
bool compareByValue(const pair<string, double>& a, 
                      const pair<string, double>& b)
{
    return a.second < b.second;
}

int main()
{
    // Creating a map to store student names and their average scores
    map<string, double> averageMap =
    {
        {"Michael", 4.52},
        {"Milica", 4.78},
        {"Nickolas", 3.89}
    };

    // User input for additional students
    int n;
    string studentName;
    double avg;

    cout << "Enter the number of students" << endl;
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cout << "Enter student name" << endl;
        cin >> studentName;
        cout << "Enter average score" << endl;
        cin >> avg;

        // Adding student name and score to the map
        averageMap[studentName] = avg;
    }

    // Creating a copy of the map and deleting a specific element
    map<string, double> averageMap2(averageMap.begin(), averageMap.end());
    string nameToDelete = "Nickolas";
    averageMap2.erase(nameToDelete);

    cout << "After deletion, map 2 looks like: " << endl;
    printMap(averageMap2);

    // Copying map elements into a vector of pairs for sorting
    vector<pair<string, double>> A(averageMap2.begin(), averageMap2.end());

    // Sorting the vector by values (average scores) in ascending order using the custom comparator
    sort(A.begin(), A.end(), compareByValue);

    // Displaying sorted student names and scores
    cout << "Sorted vector (by average score):" << endl;
    for(const auto& it : A)
    {
        cout << it.first << ": " << it.second << endl;
    }

    return 0;
}

Additional Explanation:
The program begins by including the necessary headers and setting up the std namespace. It defines two helper functions:

printMap – Prints each key-value pair in the map.
compareByValue – A custom comparator used with the sort function to arrange pairs in ascending order based on their values.

In the main function, an initial map of student names and average scores is created. The program then prompts the user to enter additional student data, which is added to the map. A copy of the map is made, and a specific entry ("Nickolas") is removed. The remaining map elements are then copied into a vector, which is sorted by the average scores in ascending order using the custom comparator. Finally, the sorted data is printed to the console.

Figure 3: Sorting a map by value in random order - program execution

Iterating through a vector with key-value pairs as elements (pair<string,int>) can also be done as follows:


sort(A.begin(), A.end());
cout << " After sorting, the map looks like: " << endl;
cout << "Sorted vector:" << endl;
for(pair<string, int> pair : A) {
    cout << pair.first << " " << pair.second << endl;
}

Sorting a map by value in descending order

Example: The results of 4 quarter-final matches, 2 semi-final matches, and a final match of the tournament knockout phase are recorded (a total of 7 matches). The input results are not sorted (for example, the last row in the input does not necessarily mean that the match was the last one played). Determine the winner and the runner-up of the tournament.

Assume that the sorted data is already entered into the map. In C++, since std::map does not support direct sorting by value (as it is sorted by key), you can transfer the pairs from the map into a vector, sort the vector by value, and then print the top two participants with the highest participation count. Here’s an example of how this can be done:


#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    map<string, int> participants = {
        {"Peter", 5},
        {"Anna", 8},
        {"Mark", 3},
        {"Joanna", 7}
    };

    // Transferring pairs to a vector
    vector<pair<string, int>> participantsVector(participants.begin(), participants.end());

    // Sorting the vector by value, descending
    sort(participantsVector.begin(), participantsVector.end(), 
         [](const pair<string, int> &a, const pair<string, int> &b) {
             return a.second > b.second; // Sorts descending by participation count
         });

    // Printing the top two participants with the highest participation count
    cout << "The top two participants with the highest participation count are:\n";
    for (int i = 0; i < min(2, (int)participantsVector.size()); ++i) {
        cout << participantsVector[i].first << " (" 
             << participantsVector[i].second << " participations)" << endl;
    }

    return 0;
}

Ordered and Unordered Maps

Unordered Maps

Unordered maps are used when there is no need to maintain the order of keys, and on the other hand, access speed to individual keys is higher in an unsorted map.

To use unordered maps, the following header must be included:

#include <unordered_map>

map vs unordered_map

Characteristics of map:

Implementation: map is implemented as a balanced binary search tree (usually a red-black tree).
Sorting: Keys in map are always sorted in ascending order.
Complexity: Insert, delete, and access operations have a complexity of O(log n) due to the tree structure.
Iteration Order: Iterating through map will always be in sorted key order.

When to use?

When sorted storage of key-value pairs is required.
When logarithmic time complexity is needed.
When iteration order is important.

Characteristics of unordered_map:

Implementation: unordered_map is implemented as a hash table.
Sorting: Keys in unordered_map are not sorted; elements are distributed based on the result of a hash function.
Complexity: Insert, delete, and access operations have an average complexity of O(1), but in the worst case, the complexity can be O(n) due to possible hash collisions.
Iteration Order: Iterating through unordered_map does not follow any specific key order.

When to use?

When faster storage and access to elements (on average) is needed.
When key order is not important.
When working with large data sets and hash collisions are minimal or well controlled.

Example of an Ordered Map

Task: Define 3 key-value pairs in a map and then print them.


#include <iostream>
#include <map>

using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "one";
    myMap[3] = "three";
    myMap[2] = "two";
    
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

Output:

1: one
2: two
3: three

Example of an Unordered Map

Task: Define 3 key-value pairs in an unordered map and then print them.


#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<int, string> myUnorderedMap;
    myUnorderedMap[1] = "one";
    myUnorderedMap[3] = "three";
    myUnorderedMap[2] = "two";
    
    for (const auto& pair : myUnorderedMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

Practical Usage Examples

Maps in C++ are useful for solving a wide range of real-world problems where it is necessary to establish a relationship between a key and a value.

1. Counting word frequencies in a text

One classic example of using a map is counting how many times each word appears in a text:


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

using namespace std;

int main() {
    string tekst = "this is a sample text where we count words words are key";
    map<string, int> frequencies;

    // Split the text into words
    stringstream ss(tekst);
    string word;
    while (ss >> word) {
        frequencies[word]++;
    }

    // Print the results
    for (const auto& pair : frequencies) {
        cout << "Word: " << pair.first << ", Occurrences: " << pair.second << endl;
    }
    
    return 0;
}

Practical application: This example can serve as the basis for implementing a simple text analyzer, e.g., for counting keywords in documents.

2. Tracking student grades

A map can be used to track the average grades of students:


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

using namespace std;

int main() {
    map<string, double> students;
    students["Marko"] = 8.5;
    students["Ana"] = 9.2;
    students["Ivan"] = 7.8;

    // Print average grades
    for (const auto& pair : students) {
        cout << "Student: " << pair.first << ", Average: " << pair.second << endl;
    }
    
    return 0;
}

Practical application: This approach can be used in school or university management systems.

3. Implementing a phone book

A map allows for easy creation of a phone book where names are mapped to phone numbers:


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

using namespace std;

int main() {
    map<string, string> phonebook;
    phonebook["Marko"] = "0641234567";
    phonebook["Ana"] = "0659876543";

    // Search in the phonebook
    string searchedName = "Ana";
    if (phonebook.find(searchedName) != phonebook.end()) {
        cout << "Phone number for " << searchedName << ": " << phonebook[searchedName] << endl;
    } else {
        cout << "Contact not found." << endl;
    }
    
    return 0;
}

Practical application: This structure can be used in contact management applications.

Suggestions for additional expansions

Add examples for more complex applications, such as implementing leaderboards, voting systems, or inventory management.
Include visual data representations using graphics libraries or reports (e.g., sorted leaderboards or charts).

Add-ons: Advanced functions and comparison with `unordered_map`

Function emplace

The emplace function allows inserting elements into the map directly at their memory location, often reducing the copy costs compared to insert. This can lead to better performance, especially when inserting more complex data types. For example:


#include <iostream>

#include <map>



using namespace std;



int main() {

      map<string, int> participants;

    

      // Insertion using emplace

      participants.emplace("Marko", 5);

      participants.emplace("Ana", 3);

    

      for (const auto& pair : participants) {

        cout << "Participant: " << pair.first << ", Number of participations: " << pair.second << endl;

      }

    

      return 0;

}

Difference compared to insert:

While insert takes an already created pair (or a copy), emplace constructs the object directly at the appropriate location, avoiding additional copy or move operations.

Comparison between std::map and std::unordered_map

std::map:
- Implementation based on a balanced binary tree (e.g., Red-Black Tree).
- Maintains elements sorted by key.
- Insertion, search, and deletion operations have logarithmic complexity O(log n).
- Suitable when the order of elements matters.
std::unordered_map:
- Implementation based on a hash table.
- Elements are not sorted.
- Insertion, search, and deletion operations have an average complexity of O(1), but could be O(n) in the worst case.
- Suitable when search performance is a priority, and order does not matter.

When to use which?

std::map: When order is important or when iterating over elements in sorted order.
std::unordered_map: When fast search is needed, and order is not important.

Previous
|< Vectors in c++

Next
>|

DATA DICTIONARY - MAPS IN C++

Page Content

Introduction

Declaration and Initialization of a Map

Iteration and Element Access

Types of Iteration and Printing Map Elements

1. Range-based for Loop

2. Iterators

Test your code in the editor!

Inputing a C++ Map

Note for Users

Advantages:

Disadvantages:

Printing a map using an iterator

Copying from one map to another

Working with a C++ Map: Inserting and Copying

Deleting Elements in a C++ Map

Deleting Elements with a Specific Key Value

Deleting All Elements in a Map

2. Deleting During Iteration

3. Deleting Multiple Elements (Bulk Deletion)

4. Performance Impact

5. Practical Tips

6. Example Error

Finding Values in a Map

Finding a Value by Key

Finding Elements by Value

Sorting a Map by Value

Combined Code Example

Sorting a map by value in descending order

Ordered and Unordered Maps

Unordered Maps

map vs unordered_map

Characteristics of map:

When to use?

Characteristics of unordered_map:

When to use?

Example of an Ordered Map

Example of an Unordered Map

Practical Usage Examples

1. Counting word frequencies in a text

2. Tracking student grades

3. Implementing a phone book

Suggestions for additional expansions

Add-ons: Advanced functions and comparison with unordered_map

Function emplace

Comparison between std::map and std::unordered_map

When to use which?

Cookie settings

Add-ons: Advanced functions and comparison with `unordered_map`