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.
