Using std::map Wisely With Modern C++
Using std::map Wisely With Modern C++
In this article, see some reasons to use std::map with Modern C++.
Join the DZone community and get the full member experience.Join For Free
std::map and its siblings (std::multimap, std::unordered_map/multimap) used to be my favourite containers when I was doing competitive programming. In fact, I still like them(though using less frequently nowadays). And with Modern C++, we now have more reasons to use std::map. That's why I have decided to address this topic by writing an article summarizing these new features. So, without much gibberish, let's dive-in directly.
std::map::containsmember function is a good step towards code expressiveness. And I am also tire of writing:
The code we write is written first for human consumption & only secondarily for the computer to understand.
- John Sonmez
std::map::try_emplace (C++17)While inserting into the map, we have 2 different possibilities:
- The key doesn't exist yet. Create a fresh key-value pair.
- The key does exist already. Take the existing item and modify it.
std::mapis by using
std::map::emplace. But, in all of these cases, we have to bear the cost of default/specialized constructor or assignment call. And the worst part is if an item already exists, we have to drop the freshly created item.
std::map::insert_or_assign (C++17)When you have to insert element anyhow. For the sake of convenience, you use std::map::operator[ ]. Which is OK( and dangerous)! Unless you have any constraint on insertion or assignment.
std::map::operator[ ]isn't feasible. Rather,
std::map::insert_or_assignis more appropriate and returns more information than
std::map::operator[ ]. It also does not require default-constructibility of the mapped type. Consider the following example for the same.
std::map::insert With Hint (C++11/17)Looking up items in an
O(log(n))time. This is the same for inserting new items. Because the position where to insert them must looked up. Naive insertion of
Mnew items would thus take
O(M * log(n))time.
std::mapinsertion functions accept an optional insertion hint parameter. The insertion hint is basically an iterator, which points near the future position of the item that is to be inserted. If the hint is correct, then we get amortized
**Note:* It is important to know that before C++11, insertion hints were considered correct when they pointed before the position of the newly inserted item.*
std::map::merge (C++17)Same as std::list:splice, which transfers the elements from one list to another. we have
std::map::mergewhich can merge the two same type of
std::map::mergethat transfers the elements in bulk,
std::map::inserttransfers element piecewise. But what is the more compelling application of
std::map::extractis modifying keys.
std::mapkeys are always unique and sorted. Hence, It is crucial that users cannot modify the keys of map nodes that are already inserted. In order to prevent the user from modifying the key items of perfectly sorted map nodes, the const qualifier is added to the key type.
std::mapthe wrong way. But what if we really need to change the keys of some map items?
std::mapto imitate the racing position. And after a while, Jenti took the lead and Mickel left behind. In this case, how we have switched the keys(position on a race track) of those players.
std::map::extractcomes in two flavours:
What If the Node With a Particular Key Does Not Exist?If we try to extract an item that doesn't exist with the second method (the one that searches using a key), it returns an empty
node_typeinstance i.e. node handle. The
empty()member method or overloaded bool operator tells us that whether a
node_typeinstance is empty or not.
OK! Then How Do I Modify std::map Keys?After extracting nodes, we were able to modify their keys using the
key()method, which gives us non-const access to the key, although keys are usually const.
node_typeinstance, this does not result in actual moves of any of the container values.
Can I Modify Associated Values in std::map Also?Yes! You can use the accessor methods
nh.key()) to manipulate the pieces of the entry in a
nh.value()for the single piece of data in an element of a
std::set). Thus you can extract, manipulate, and reinsert a key without ever copying or moving its actual data.
But What About Safety?If you extract a node from a map and then throw an exception before you've managed to re-insert it into the destination map.
std::map::extractby-default(without insert) will act as std::map::erase!
There Is More! InteroperabilityMap nodes that have been extracted using the
std::map::extractare actually very versatile. We can extract nodes from a map instance and insert it into any other map or even multimap instance.
Difference Between operator[ ] vs insert() vs at()
This is trivial for experienced devs but, still I want to go over it quickly.
- Not usable for
const std::map, as it will create the element if it doesn't exist.
- Not suitable for value type that does not default constructible and assignable(in layman term, doesn't have default constructor & copy/move constructor).
std::pair) and uses the key(first member) and to insert it. As
std::mapdoes not allow for duplicates, if there is an existing element it will not insert anything.
- Liberty in calling insert different ways that require the creation of the value_type externally and the copy of that object into the container.
- Highly applicable when item insertion sequence is somewhat predictable to gain the performance.
exception of type std::out_of_range is thrown.
- Not recommended using
at()when accessing const maps and when element absence is a logic error.
- Yes, it's better to use
std::map::find()when you're not sure element is there. Because, throwing and catching std::logic_error exception will not be a very elegant way of programming, even if we don't think about performance.
If you see the table of content for this article above, more than half of the member functions are around inserting the elements into the map. To the newbie, this is the reason for anxiety(or standard committee would say modernness). But if you account for the new features & complexity of language those are pretty much justified. BTW, this modernness doesn't stop here, we do have other specialization also available for map like std::swap (C++17), std::erase_if (C++20) & bunch of comparison operators.
Published at DZone with permission of Vishal Chovatiya . See the original article here.
Opinions expressed by DZone contributors are their own.