0

The candidates I know:

  1. Vector. Finding item in worst scenario takes to iter over all of it.
  2. unordered_map. Does same thing as above under the hood?
trshmanx
  • 600
  • 7
  • 16
  • 2
    unorderd_map usually has lookup O(1) (with slight overhead in case of hash collisions), and vector O(n). unordered_map is a hash_table, vector is linear in memory and map uses a tree and has O(log n) lookup. What is actually faster depends on your container initialization and thereafter your memory access pattern. (vector can be faster if you use a predictable stride, cache prediction etc) – Pepijn Kramer Oct 15 '21 at 07:19
  • Where is the resource that `unordered_map` does the same as a `vector`? – sbecker Oct 15 '21 at 07:19
  • 1
    Unordered containers are usually fastest (from the standard containers). Simple benchmark: https://quick-bench.com/q/u2pbnt8z-2C3JtvcaZRgq1ew5OY. Of course, it may depend on the quality of the hash function etc. – Daniel Langr Oct 15 '21 at 07:21
  • 1
    You should read this: https://en.cppreference.com/w/cpp/container – mch Oct 15 '21 at 07:21
  • 2
    if you can lookup by index in an array, then use std::vector if the key by which you lookup your element is more complex then use hashed containers like unorderd_map – marcinj Oct 15 '21 at 07:22
  • https://stackoverflow.com/questions/24542936/vector-vs-map-performance-confusion – Superlokkus Oct 15 '21 at 07:28
  • 2
    It depends on how you are using each. For different uses, each can be faster. What are your specific circumsances? – Galik Oct 15 '21 at 07:39
  • For only a few elements, a `std::vector` can beat the `std::unordered_map` due to implementation details. While the elements of the `std::vector` are stored consecutively this is not that likely for the elements of a `std::unorder_map`. Hence, the caching may cause that the O(N) search in `std::vector` out-performs any amortized search of `std::unordered_map`. – Scheff's Cat Oct 15 '21 at 08:57
  • Ufff. Lots of opinions. – trshmanx Oct 15 '21 at 10:12

0 Answers0