Is There “Connie” in the Map?

Today is Pi (π) Day, and I wanted to celebrate with this blog post (even if it’s C++-related and not math-related). Hope you’ll find it useful, and maybe even enjoy it.

 

std::map is one of those useful containers implemented in the C++ Standard Library. It basically stores key-value pairs, with unique keys. In other words, std::map maps unique keys to values.

As a concrete example, you can think of an address book: The “key” is the person’s name, and the “value” associated with it can be a custom data structure storing information like address, e-mail address, telephone number, and so on.

This can be translated in C++ code like that:

std::map<std::string, Person> addressBook;

Another interesting application could be counting words in a document. In this case, you still have a string key (i.e. the word you’re counting), and the associated value in the key-value pair would be an integer representing the occurrences of that word:

map<string, int> wordCount;

E.g.: If you have 500 “Connie”s in a document, “Connie” is mapped to 500.

You can use a map from string to int for word counting applications.

A common operation you can do on a map is checking if there is an element with a given key in the container (i.e. a given name in the previous address book example, or a given word in the word counting one).

So, assuming that you have some std::map object with std::string keys, how to check if “Connie” is a key contained in the map?

Method #1: Invoking map::find()

Well, std::map offers a find() method. You pass as input the key of the element to search for, and find() returns an iterator to the element with that given key. If such element doesn’t exist in the map container, then std::find() returns the map’s end iterator.

So, if you want to check if “Connie” is a key in the map, you can call std::map::find(), and compare the returned iterator to the map’s end iterator:

if (myMap.find("Connie") != myMap.end())
{
    // "Connie" is in the map
    cout << "Found! \n";
}

Method #2: Invoking map::count()

There’s also another option. std::map offers the count() method, which returns the number of elements with the given key, which is either 1 or 0 for std::map (as std::map contains unique keys).

So, translated in C++ you get something like that:

if (myMap.count("Connie") == 1)
{
    // "Connie" is in the map
    cout << "Found! \n";
}

 

Two options for checking if an element with a given key is contained in a std::map, invoking the find or count methods

Method #3: Back to the Future, and Thank You C++20

Honestly, I found the previous two methods kind of obscure and unclear (especially before someone has already introduced them to you). I mean: If I want to check if a std::map contains an element with a given key, why can’t I just ask the container in a simple straightforward way? Something like that:

if (myMap.contains("Connie"))
{
    // "Connie" is in the map
    cout << "Found! \n";
}

I even found a newsgroup post dating back to 2009, in which I expressed my wish for a simple clear map::contains() method:

Fortunately, it seems that C++20 will finally add it! 😊

As a general rule of class interface design, I believe it’s better to add a direct clear straightforward method to the public interface, than forcing your class users to “fight” the interface and circumnavigate it to get the result.

 

OK, since today is π Day, I think there’s room for some math 😊 So, all these methods (find, count and contains) have logarithmic asymptotic complexity (O(log(N)) in the size of the container. If you are curious about the Big-O notation and asymptotic complexity, you may want to check out my course on Introduction to Data Structures and Algorithms in C++.

Big-O doesn’t have to be boring!

 

Leave a Reply

Your email address will not be published. Required fields are marked *