Jonathan Boccara's blog

How to Check If an Inserted Object Was Already in a Map (with Expressive Code)

Published September 27, 2019 - 0 Comments

To insert a new entry into an STL set or map, or any of their multi- and unordered- equivalents, we use the insert method:

std::map<int, std::string> myMap = // myMap is initialized with stuff...

myMap.insert({12, "twelve"});

insert performs the action of inserting the new entry into the container, if that entry wasn’t there already. But insert doesn’t only perform that action: it also returns two pieces of information about how the insertion went:

  • where the new element is now in the map, in the form of an iterator,
  • whether the new was actually inserted (it wouldn’t be inserted if an equivalent value was already there), in the form of a boolean.

To return those two pieces of information, the insert interface of all the associative containers of the STL operate the same way: they return an std::pair<iterator, bool>.

This interface makes the code that performs the insertion confusing. Let’s see what’s wrong with it, and how to improve it.

The problems of the insert interface

Let’s focus on the boolean indicating whether the element was inserted, because it has all the problems that the iterator has, plus one more. Say that we want to take a certain action if the element turns out to have been in the map already. There are several ways to write this code. One of them is this:

std::pair<std::map<int, std::string>::iterator, bool> insertionResult = myMap.insert({12, "twelve"});

if (!insertionResult.second)
{
    std::cout << "the element was already in the set.\n";
}

This code is horrible for several reasons:

  • std::pair<std::map<int, std::string>::iterator, bool> is such a big mouthful of code,
  • insertionResult is not something you’d expect to read in business code,
  • the bool does not show what it means,
  • even if you know the interface of insert and that the bool depends on whether the element was already there, it’s confusing whether it means “successful insertion”, or the opposite “the element was already there”
  • insertionResult.second is meaningless,
  • !insertionResult.second is meaningless and more complex.

We can mitigate some of its problems by hiding the returned type behind an auto, and by naming the bool with an explicit name:

auto const insertionResult = mySet.insert(12);
auto const wasAlreadyInTheSet = !insertionResult.second;

if (wasAlreadyInTheSet)
{
    std::cout << "the element was already in the set.\n";
}

Or, from C++17 on, we can use structured bindings (as suggested in the comment section–thanks for pointing it out!):

auto const [position, hasBeenInserted]  = myMap.insert({12, "twelve"});

if (!hasBeenInserted)
{
    std::cout << "the element was already in the set.\n";
}

If you don’t do anything else, at least do this, if you need to check whether the element was already in the container.

I think that this code is OK, but the technical aspects of the insert interface are still showing, in particular with the .second before C++17, and the risk of having the bool wrong even in C++17. To go further, we can encapsulate it in a function.

A little function that makes the check

A simple way to hide the offending pair from the calling code is to wrap the code that gets its .second in a function, whose name reveals its intention:

template<typename Iterator>
bool wasAlreadyInTheMap(std::pair<Iterator, bool> const& insertionResult)
{
    return !insertionResult.second;
}

Then the calling code looks like this:

auto const insertionResult = myMap.insert({12, "twelve"});

if (wasAlreadyInTheMap(insertionResult))
{
    std::cout << "the element was already in the map.\n";
}

The ugly .second is no longer visible.

The other types of associative containers

Note that this function doesn’t only work for std::map. Since all STL associative containers have a similar insert interface, it also works for std::multimap, std::unordered_map, std::unordered_multimapstd::set, std::multiset, std::unordered_set and std::unordered_multiset.

So the name wasAlreadyInTheMap is less generic than what the function can accept. We could rename the function wasAlreadyInAssociativeContainer. But even if it’s more accurate that wasAlreadyInTheMap, the latter looks nicer in calling code.

It is tempting to make a set of overloads for all the different types of STL associative containers:

template<typename Key, typename Value>
bool wasAlreadyInTheMap(std::pair<typename std::map<Key, Value>::iterator, bool> const& insertionResult)
{
    return !insertionResult.second;
}

template<typename Key, typename Value>
bool wasAlreadyInTheMap(std::pair<typename std::multimap<Key, Value>::iterator, bool> const& insertionResult)
{
    return !insertionResult.second;
}

...

But this doesn’t work, as this sort of type deduction is not possible. Indeed, the nested type iterator is not enough to deduce the container type.

If we want two different names, we can implement two functions differing only by their names, but it doesn’t enforce that they will operate with only a std::set or std::map.

template<typename Iterator>
bool wasAlreadyInTheMap(std::pair<Iterator, bool> const& insertionResult)
{
    return !insertionResult.second;
}

template<typename Iterator>
bool wasAlreadyInTheSet(std::pair<Iterator, bool> const& insertionResult)
{
    return !insertionResult.second;
}

I hope these suggestions will help clarify your code that checks if an elements was inserted in an STL associative container! Don’t hesitate to share your feedback in a comment.

You may also like

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin