Skip to main content

Maps and Sets

Introduction#

Map and Set is used for storing and fetching data. The idea is pretty simple for both, Map allows to retrieve and store data corresponding to any key efficiently, while Set allows to store and maintain a unique set of keys. Both of these data structures or containers as they are called in STL will help you in optimising your code and are much needed for more complex and advanced level algorithms to work efficiently and properly.

Hashing#

To tell you in brief, hashing is a technique to convert your original value in the domain to obtain a value in the range via any suitable intermediate method or function, which is usually a black box known only to you. Why to do hashing and how to do hashing? These are some of the questions you should be able to answer post reading these wonderful articles.

String Hashing#

Hashing of string is usually considered more complex than simple integers, so here are some useful string hashing methods that will help you in solving problems. Avoid writing your own hash functions as much as possible instead use the STL provided map and set.

Map#

It is about time you became familiar with the STL provided Map container, you will use it instead of implementing and writing your own map. The STL containers are very flexible, they also allow you to define map and unordered_map for custom data types and hash functions, for that you need to do some operator overloading similar to priority queue. So don’t just stare at the screen, start reading.

Caution

The following STL utilities for Map in C++ is a must know : size(), insert(), erase(), begin(), end(), find(), pair_insert().

If you are wondering how map compares with unordered_map, you have good affinity for knowledge. The main differentiating factor comes in how they are implemented. Different data structures are used in their implementation, which results in different time complexities for the same operation, all of this and much more is there for you to know, so read on.

Tips

Remember the worst case time complexities of insert, delete and search operations in map and unordered_map.

Set#

Moving on from Map, you will now learn how to use STL provided Set. The STL Set Container can also be used for custom data types which makes it very versatile and handy, read on and you will learn how to do so.

Caution

The following STL utilities for Set in C++ is a must know : size(), insert(), erase(), begin(), end(), find().

You should know about the advantages of set and unordered_set over one another to be able to use the more appropriate container in your code. Similar to the case with map and unordered_map, set and unordered_set deploy different data structures which yields different time complexity for the insert, delete and search operations, to know about the data structure used, the time complexity of insert, delete and search and other differences, read on.