The basic concept of std::map

Kevin Cheung
3 min readJan 7, 2021

--

When I dig deep into the std::map class, I found there are many areas that I need to talk about such as the Deep copy, the Shallow Copy, Time Complexity of the map class. Let us firstly introduces some basic concepts of maps in this post before digging deep into the related topic when we use a map.

The basic concept of the std::map template class

  • It stores key-value pair (like a lookup table)
  • An iterator in the map refers to the type pair, which is another template class in STL.

There are 2 ways to insert key-value pairs in std::map. Consider the following code.

If we try to access a value that is not in the map, the array subscript operator will be overloaded and assign the key with a value 0 into the map. Consider the following code and result

0 
Alex has an age of 23
Billy has an age of 28
Cyril has an age of 27
David has an age of 32
Eason has an age of 0

.find() method

it returns an iterator that points to the element found or the end of the map if it is not found.

Eason is found.

Custom Object as Map Values

Consider the following class and main function.

The above cannot be compiled. We can add a constructor that assigns a null value to solve the compile error message.

A default constructor is needed for using the map. When the user-defined constructor is defined, it lost the default implementation of a constructor with no parameters. The map needs the default constructor with no parameters to constructor an object and assigns values.

We can solve it by declaring a parameterless constructor.

However, the above code is not a good way to implement it and involves the concept of a shallow copy. I will create another post to talk about both the shallow copy and the deep copy later.

Key Sorting in Maps

The map will always sort the values in the order of keys. Consider the following code and result to see the order of inserting elements and printing order during iteration.

8: Billy has an age of 28 
17: Alex has an age of 23
23: Cyril has an age of 27

Conclusion

I have mentioned some basic methods and how to use the std::map in some general ways. In the part where I describe a parameterless constructor, it actually involves concept like shallow copy which I will further talk about it before going to talk about unordered_map or multimap.

--

--

Kevin Cheung

一個放棄了十年音樂夢的碌碌無為程序員