Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
Well, that did you do that turned out to be slower? –  delnan Nov 2 '11 at 16:46
    
the program i referred used recursion. the difference i felt in other codes than mine was that I returned the value but the other one's assigned it to a mapping. –  user841923 Nov 2 '11 at 16:50
2  
That's unclear. Did you recompute values instead of storing them in a map? If so, the difference isn't really the mapping but the avoidance of (unneeded) work. –  delnan Nov 2 '11 at 16:52
    
What delnan is talking about is also known as memoization. –  Sedate Alien Nov 3 '11 at 0:40
add comment

2 Answers

up vote 9 down vote accepted

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
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.