Sign in to follow this  
Maverick Programmer

Difference between std::map and std::vector?

Recommended Posts

I've been skimming through some posts and some people use std::map and others use std::vector. They seem ( notice the word 'seem' ) to be the same, so what's the difference? Are there times when only std::vector or std::map can do the trick? ~Maverick

Share this post


Link to post
Share on other sites
std::vector is a dynamic array and std::map is a red-black tree (specifically std::map is a balanced binary tree, which means it can be alternately implemented as an AVL tree for example).

What that means is that each of those data structures are good at certain things and bad at other things.

For example, in the general case it is very efficient to search a red-black tree and very inefficient to search a dynamic array. However in the general case it is very efficient to insert into a dynamic array (as long as its not between existing elements) but it but it is less efficient to insert into a red-black tree.

Share this post


Link to post
Share on other sites
std::map associates a key with a value. The key is customizable and std::map will automatically insert a key-value pair for any element accessed with operator[]. This allows for example, associating names (e.g. strings) with, say, grades, with decent efficiency, directly, it does this by keeping the entire container sorted by key at all times.

std::vector associates an index (which is always an integer) with a value. The maximum legal index is controlled via .resize(), access beyond that with operator[] results in undefined behavior. It also holds the property of being contiguous -- meaning you can pass the data it holds to functions from C libraries or other code expecting C style arrays. Unlike std::map, std::vector leaves things in whatever order you inserted them in, which is necessary very often.

While std::vector and std::map share a lot of commonalities by design, especially if you're in the habit of thinking of arrays as associating indicies, they are absolutely not the same, and they have enough differences that Promit's suggestion bears repeating.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this