vector or map, which one to use?

by

I presume you’re comparing map<A, B> with vector<pair<A, B> >.

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.

The 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. Typically, the point where map becomes faster would be about 5-30 elements.

An alternative is to use a hash container. They are often named hash_map or unordered_map. Classes named hash_map are not part of the official standard (and there are a few variants out there); std::tr1::unordered_map is. A hash map is often faster than a normal map for lookups, regardless of how many elements are in it, but whether it is actually faster depends on what the key is, how it is hashed, what values you have to deal with, and how the key is compared in std::map. It doesn’t keep things in a specific order like std::map, but you’ve said that you don’t care about that. I’d recommend hash maps particularly if the keys are integers or pointers, because these hash very quickly.

More Related Contents:

  1. Is std::vector so much slower than plain arrays?
  2. How to overload std::swap()
  3. Relative performance of std::vector vs. std::list vs. std::slist?
  4. What’s faster, iterating an STL vector with vector::iterator or with at()?
  5. Efficiency of the STL priority_queue
  6. Performance of qsort vs std::sort?
  7. What is the easiest way to initialize a std::vector with hardcoded elements?
  8. Initializing a static std::map in C++
  9. How do I sort a vector of pairs based on the second element of the pair?
  10. What is the efficient way to count set bits at a position or lower?
  11. Best way to extract a subvector from a vector?
  12. Does vector::erase() on a vector of object pointers destroy the object itself?
  13. How are iterators and pointers related?
  14. Extending the C++ Standard Library by inheritance?
  15. How to implode a vector of strings into a string (the elegant way)
  16. How to update an existing element of std::set?
  17. Is there a production ready lock-free queue or hash implementation in C++ [closed]
  18. Multidimensional std::array [duplicate]
  19. Reorder vector using a vector of indices [duplicate]
  20. Is the C++ std::set thread-safe?
  21. How to choose between map and unordered_map?
  22. Does std::stack expose iterators?
  23. Why does a push_back on an std::list change a reverse iterator initialized with rbegin?
  24. Fastest way to get a positive modulo in C/C++
  25. Why is the STL so heavily based on templates instead of inheritance?
  26. How to sort an STL vector?
  27. How can I make the map::find operation case insensitive?
  28. Comparing 3 modern c++ ways to convert integral values to strings
  29. what does `using std::swap` inside the body of a class method implementation mean?
  30. Why is pow(int, int) so slow?

Leave a Comment