How is std::map different from std::vector?

How is a map similar to a vector? How is it different?

This is like comparing tomatoes and apples. std::map and std::vector are meant to serve entirely different purpose-

  1. It is a dynamic sized array which can provide random access in O(1) because the elements are contiguous.
  2. Insertion and removal is O(1) – but only at the ends.
  3. It is not sorted (you can sort it by calling sort though), hence not suitable for searching.
  4. Should be used where a array is required. Note there can be vector of vector also.


  1. It is a sorted container, usually implemented using RB tree.
  2. Unlike std::set which has only keys, map has key value pairs where keys are unique.
  3. O(log n) insertion, deletion and search.
  4. Should be used where dictionary like access is required.

@vinayak garg thanks a lot …but can you please tell me in what aspect they are similar.

@blacklisted: In that both are STL containers :stuck_out_tongue: Frankly I don’t know similarity in map and vector. Maybe you want to elaborate what you are looking for.

lolzzz…okk anyways thaks a lot for such a good explanation.

@vinayak garg sir one similarity is that both works on iterators but interesting thing is that this also becomes a part of difference because map works on bidiretional iterators and vector on random access iterators…:stuck_out_tongue:

@blacklisted: I noted that similarity when I said “both are STL containers”, as all STL containers have iterator interface :wink:

@vinayak garg
Yes,that’s the main principle of STL,the interface are same and the standard STL algorithms and operations work on all the containers