top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

C++: What are the differences between Vector and Map?

+4 votes
C++: What are the differences between Vector and Map?
posted Jan 27, 2015 by Muskan

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote
Best answer

Maps are usually implemented as binary search trees, and walking a binary tree always comes with a little overhead (performing comparisons, walking links, etc.) Vectors are basically just arrays. For very small amounts of data, maybe 8 or 12 elements, sometimes it's faster just to do a linear search over an array than to walk a binary search tree.
Maps do tend to have a bunch of small allocations all over the heap, whereas vectors are contiguous so the cache-hit rate of vectors can sometimes be a little better in cases where you're iterating over all the elements from front to back.

Map look up and retrieval take O(log N), but the items may be scattered throughout the memory, thus not playing well with caching strategies.

Vector are more cache friendly, however unless you sort it you'll have O(N) performance on find

There is a point where maps become faster than vectors depends on the implementation, on your processor, what data is in the map, and subtle things like what memory is in the processor's cache. The point where map becomes faster is somewhere between 5-30 elements.

Firstly, finding an item in a very small vector can easily be faster than the same thing in a map, because all the memory in a vector is always contiguous (and so plays more nicely with computers' caches and such things), and the number of comparisons needed to find something in a vector might be about the same as for a map. Finding an element in a map needs fewer operations in the limit of very large containers.

answer Feb 27, 2015 by Amit Kumar Pandey
Similar Questions
+4 votes

What are the advantages of Vector over an array in C++? give Exmaple.

+1 vote

I wanted to ask what is the GCC C++ equivalent implementation of Windows _ MyFirst and _MyLast vector pointers?

These give direct access to the vectors first and last element, but they are not present in the GCC implementation of the vector class.