This is the 9th Part of Tutorial series on std::map in C++. In this tutorial, we’ll learn how to use a custom class as a key in a map in C++, focusing on overloading necessary operators for key comparison.

How Sorting works in map in C++?

A map is an STL container that stores data in key-value pairs. It organizes its elements based on key comparison, maintaining a sorted order of keys. This allows efficient searching, insertion, and deletion operations, which are typically logarithmic in complexity.

Here’s how things work internally in std::map:

  1. Key Comparison: When you insert a key-value pair into a std::map, the map uses the given comparison function or std::less() associated with the key’s type to determine the correct position to maintain sorted order.

  2. Element Storage: The map stores the key-value pair in the correct position to maintain the sorted order of keys.

  3. Lookup and Retrieval: When you want to retrieve a value associated with a specific key, the map performs a binary search using the key comparison function, allowing efficient access to the value.

Using a comparison function allows std::map to maintain order and provide efficient access to elements. However, it does require that the key type is comparable using this function.

How Map compares the Keys?

For built-in types like int and std::string, std::map uses the default comparison function std::less, which works fine. However, when using a custom class as a key, you need to ensure that it supports comparison operations.

Here’s the corrected version of your text:

For example, if you have an std::map<std::string, int>, the map will use the default std::less<std::string>() to compare the keys and sort the key-value pairs by key inside the map.

When you want to use your custom class type as a key in a std::map, then it’s necessary to overload the less-than operator (<) in the class or provide a comparator while declaring the map object. Let’s look at both techniques one by one.

Technique 1: By Overloading < Operator for the Key Type

Suppose we have a Message class with sender, receiver, messageID, and messageText as its member variables. In this case, messageID will serve as the unique key. To use this Message class as a key in an std::map, we need to overload the < Operator in this Message class. The less than operator must use the messageID member variable only for comparing the keys.

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

class Message 
{
public:
    std::string sender;
    std::string receiver;
    std::string messageID;
    std::string messageText;

    Message(std::string sender,
            std::string receiver,
            std::string messageID,
            std::string messageText)
        : sender(sender),
          receiver(receiver),
          messageID(messageID),
          messageText(messageText)
    {

    }

    // Overload the less-than operator
    bool operator<(const Message &other) const 
    {
        return messageID < other.messageID;
    }
};

In the above code, the Message class is defined with four member variables. The < operator is overloaded to compare Message objects based on their messageID.

Now that we have our Message class with the required operator overloading, we can use it in the map as a key. Let’s see the code for that:

int main() 
{
    // Creating a map with Message as key
    std::map<Message, std::string> messageMap;

    // Creating Messages
    Message msg1("Ritika", "Atharv", "ID1", "Good Morning !!");
    Message msg2("Atharv", "Varun", "ID2", "Good Evening !!");

    // Adding Messages to the map
    messageMap[msg1] = "First Message";
    messageMap[msg2] = "Second Message";

    // Accessing data
    for (const auto& pair : messageMap) {
        std::cout << "Key(MessageID): " << pair.first.messageID << " Value: " << pair.second << std::endl;
    }

    return 0;
}

Output:

Key(MessageID): ID1 Value: First Message
Key(MessageID): ID2 Value: Second Message

In the main() function, we declared a map object named messageMap that uses Message objects as keys. We then create two Message objects and add them to the map. The for loop iterates over the map in sorted order of messageID and prints each key-value pair.

Technique 2: By Providing a Custom Comparator in Map

Instead of overloading the < operator, we can also create a comparator using a function object. This function object will have an operator() function, which accepts two objects of Message type as arguments and compares them. Then, pass this function object or comparator as a template parameter while declaring the map object. The map will use this comparator to compare the keys while sorting key-value pairs. Let’s see the complete example.

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

class Message 
{
public:
    std::string sender;
    std::string receiver;
    std::string messageID;
    std::string messageText;

    Message(std::string sender,
            std::string receiver,
            std::string messageID,
            std::string messageText)
        : sender(sender),
          receiver(receiver),
          messageID(messageID),
          messageText(messageText)
    {

    }
};

// Define a custom comparison function for Message objects
struct MessageComparator
{
    bool operator()(const Message &message1, const Message &message2) const
    {
        return message1.messageID < message2.messageID;
    }
};

int main() 
{
    // Creating a map with Message as key using the custom comparator
    std::map<Message, std::string, MessageComparator> messageMap;

    // Creating Messages
    Message msg1("Ritika", "Atharv", "ID1", "Good Morning !!");
    Message msg2("Atharv", "Varun", "ID2", "Good Evening !!");

    // Adding Messages to the map
    messageMap[msg1] = "First Message";
    messageMap[msg2] = "Second Message";

    // Accessing data
    for (const auto& pair : messageMap) {
        std::cout << "Key(MessageID): " << pair.first.messageID << " Value: " << pair.second << std::endl;
    }

    return 0;
}

Output:

Key(MessageID): ID1 Value: First Message
Key(MessageID): ID2 Value: Second Message

Summary

Today, we learned how to use a custom class as a key in a map in C++. This involved overloading the less-than operator for the class to ensure proper key comparison and ordering or we can also provide a custom comparator while declaring the map object.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.