C++ std::map vs dynamic array

Question

I'm trying to make a 3 dimensional array of booleans that tells me if I previously visited a location in 3d space for a simple navigation algorithm. The array could be quite large (something along the lines of 1,000,000 x 1,000,000 x 1,000,000 or maybe larger), so I'm wondering if it would be faster to declare an array of that size and set each boolean value to false, or to make a map with a key of coordinate (x, y, z) and a value of type bool.

From what I figure, the array would take O(1) to find or modify a coordinate, and the map would take O(log n) to find or insert a value. Obviously, for accessing values, the array is faster. However, does this offset the time it takes to declare such an array?

Thanks

• Rapptz: std::unordered_map is on average O(1)
• Xeo: Why not use a hash map (unordered_map in C++11)?
• Kerrek SB: Even at one bit per cell you'd need over 10^11 GB of memory for an array. You should probably think about a better approach.
• DavidO: Speed is the wrong optimization to be concerned with at the moment.
• Dietmar Kühl: How many elements do you expect to be set in your array? If you eventually expect to visit all cells using a compact representation of the array (e.g. using one bit per cell rather than a bool) might be the best approach. If you expect to visit paths the smaller memory footprint of a set or a hash set (std::unordered_set; you can determine the value by the presence of an element) can offset the better access patterns.

Answer 1

Even at 1 bit per bool, your array will take over 2**39 bytes. I'd suggest a set if there aren't too many elements that will be true.

You can use a class to hide the implementation details, and use a 1D set.

• David Stone: This seems like one of the few use cases where std::set is the ideal data structure, since all you care about is "Have I been here?". The "implementation details" class would have 3 data members (the x, y, and z coordinates) and define operator <. Depending on your use case, the only other thing you might need is a constructor that accepts the x, y, and z coordinates, with the data members private (if all you really ever care about for these coordinates is whether you've been there).
• VerTiGo_Etrex: Is that any faster than std::unordered_set? On that note, I've been having trouble figuring out what functions I need to implement in my class (which just contains three int values) to allow usage with an unordered_set.
• Mark Ransom: @VerTiGo_Etrex, the speed difference between std::set and std::unsorted_set will depend on the number of elements you have populated and the quality of your hash function. std::set requires a < comparator, and std::unordered_set requires a hash function and a == comparator.

Answer 2

Have you tried calculating how much memory would be needed for an array like this? A lot! Use std::map if ordering of the points is important, or std::unordeded_map if not. Also the unordered map gives you a constant time insertion and lookup. I guess that some kind of search tree is probably what you're looking for (k-d tree for example).

Answer 3

You're going to make an array that is one exabyte, assuming that you use 8 bits per point? Wow, you have a lot of RAM!

I think you should re-think your approach.