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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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 (
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.
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
Alternatives w/different tradeoffs
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.