Difference Between Map with Integer Key and Vector

Question

Is vector the specialized form of unordered_map with integer key? It seems so because a vector has integer keys, too.

If not, what are the differences?

Answer 1

The main difference is in how the data is stored.

A vector stores the data in an internal array that it resizes and you add more elements. An unordered_map uses a hash table internally.

Practically, a vector gives you amortized constant time insertions at the back (it needs to resize and copy/move everything once in a while), constant time access by index, and up to linear time insertion and deletion (all the subsequent elements have to be shifted). Also, since a vector is contiguous, you can pass it into functions expecting a c-style array.

unordered_map gives you amortized constant time lookup by key (because hashing is not perfect, and collisions force the lookup to traverse through internal linked lists), amortized constant time inserts and deletes.

See: http://en.cppreference.com/w/cpp/container/unordered_map and: http://en.cppreference.com/w/cpp/container/vector

Answer 2

Nope, indexes in a vector are continuous, in a map they don't have to be.

Also, values in a vector are guaranteed to be in continuous memory, not in a map.

These two imply different complexities for most operations on the two.

Answer 3

The main difference is in how the data is stored.

A vector stores the data in an internal array that it resizes and you add more elements. An unordered_map uses a hash table internally.

Practically, a vector gives you amortized constant time insertions at the back (it needs to resize and copy/move everything once in a while), constant time access by index, and up to linear time insertion and deletion (all the subsequent elements have to be shifted). Also, since a vector is contiguous, you can pass it into functions expecting a c-style array.

unordered_map gives you amortized constant time lookup by key (because hashing is not perfect, and collisions force the lookup to traverse through internal linked lists), amortized constant time inserts and deletes.

See: http://en.cppreference.com/w/cpp/container/unordered_map and: http://en.cppreference.com/w/cpp/container/vector