What is the advantage of using map datastructure?

Question

I am a member of some online coding website and today when I submitted a solution in C++, I saw there were much better answers in C++ itself which took considerably less time. The solutions were open so I went on through some of them and found all of them using map datastructure. I could not figure out where exactly it takes an edge. I made some googling but it was not convincing. Please help.

Answer 1

map is a fairly well-rounded dictionary-type container that provides several advantages over std::list (linked lists) and std::vector (arrays). Although its not strictly specified, the performance constraints required on a map pretty much forces it to be implemented as some kind of self-balancing binary tree. So if its helpful to you to think about it in those terms, consider the advantages of binary trees over normal arrays/linked lists if you have learned about them in the past.

Lookup time

If you know your keys (what you're using to lookup your data) fall into a very narrow integer range, then an array (or preferably a vector) is ideal if all you care about is lookup. You can look up using a key in constant time with no fuss.

This breaks down if your key space becomes too large or is not an integer. You obviously can't have an array that has an item stored only in the 0th slot and the 2^32 spot without wasting tons of memory. A map lets you maintain reasonable lookup performance (O(log(n))), but only takes up 2 spots to store the memory. A map also lets you lookup on any type that defines a < operator or specifies to the map through a template argument how to compare keys. So you can have reasonable lookup on maps of strings -> another value. So a map will let you do map["Bob"] = 5; for example.

Ordered

map stores items in key order. So you can iterate over all the items in a map, from begin to end, in sorted key order. You obviously can do this with an array/vector, however as was said earlier, a map lets you have any arbitrary key type with any arbitrary ordering defined.

Insertion

To insert into the middle of an array/vector you have to shift all the items over to the left. For a dynamic array and a vector you have to resize the vector, which will cause you to copy the entire array to new memory.

A map has reasonable insertion time (O(log(n))).

Alternatives w/different tradeoffs

• multimap is like map but allows the keys to be not unique
• unordered_map is a map that does not store items in order, but can provide better lookup performance if a good hash function is provided

Answer 2

For most purposes the classes from the standard library are likely to outperform any quickly-put-together data structure / container / algorithm you will write. This is assuming you choose the right abstraction (std::vector and std::list have different trade-offs, for example). A lot of time and effort by a lot of smart people has gone into making those libraries both generic and as fast as possible given the generic nature of the libraries.

If you have a very specific case that you know really well, and you also know your standard library classes really well, you might be able to write a custom class that outperforms the best standard equivalent for your specific, limited purpose, but such a thing should only be done when profiling your application demonstrates a need for such optimization.