Thread: map, unordered_map or vector ?

Hi i have a very simple question. I am trying to store a 2d array of integers but i don't know should i choose vector or map or unordered_map to store the data. So my particular case is:

A function in my program generates integers based on some input and those integers can span from 0 to 5*10^10. usually i get around two million ints that i need to associate to some other 2 mill ints. latter on i have to find and modify every stored int at least two times. exmp:


input > generate ints > store them into hash table

2 -> 198776
43239 -> 55
356 -> 762212
...

now i have to locate int associated with 2 and repeat this process for all numbers in the table -> i have a while loop from 0 to 5*10^10 and as a reach a particular number i check if it exists in my table and then change its value according to the present value (i repeat this twice) )

so given the above case what is the best way to store my numbers: map, vector or unordered_map? I need something that uses the smallest amount of memory and is fast. in other words efficient.

baxy

Originally Posted by baxy

I need something that uses the smallest amount of memory and is fast. in other words efficient.

std::vector will use the smallest amount of memory and will be the slowest. (Plain array underneath)
std::map will have binary tree like performance. (Both params between vector and unordered_map)
std::unordered_map will be the fastest and use the most memory.
Use it if you want a hashtable.
The memory isn't really that much.

Originally Posted by manasij7479

The memory isn't really that much.

if it's an embedded system, memory is everything.

i have a while loop from 0 to 5*10^10 and as a reach a particular number i check if it exists in my table and then change its value according to the present value

O_o

Cache misses are going to eat you alive.

Call me Sally-joe Mcgee, but why is it necessary to iterate over the possible values to check if they exist instead of just directly iterating over the values that are known to be in the input because you've just read them!? (It is remarkably trivial to figure out where you'd be in the domain from that information anyway if you are using simple iteration.) Or is every single pass intended to update a value multiple times because the position in the set changed? Why can't you do all updates in a single pass?

How did we get those three containers as choices? They do different things. The `std:vector' isn't an associative container. If you need an associative container, why is listed? Alternatively, if you don't need an associative container, how are you managing the associated values? Where are these associated values coming from? Are they calculated? Are they supplied by a file? Are the associations reversible?

As far as that goes, what does anything you said have to do with a "2d array"? An array isn't associative regardless of its dimensionality. (I don't want to hear arguments about indices as association. He has "5*10^10" domain; that would almost certainly require more RAM than he has available.)

std::unordered_map will be the fastest and use the most memory.

If he is updating the same value in the list multiple times in a single pass he is guaranteed to get useless expansions.

I don't think I'd recommend a `std::unordered_map' here, but then I'm not sure what he is doing either so you may be exactly right.

Same lookup complexity as std::map<> but with zero memory overhead

The cost of keeping the list sorted through all the potential mutations might be brutal.

Or if he doesn't need to process the list with the adjusted value he could use a tuple with that strategy.

Soma