title: 3D-Grid of bins: nested std::vector vs std::unordered_map
body: <p>pros, I need some performance-opinions with the following:</p>
  
  <h2>1st Question:</h2>
  
  <p>I want to store objects in a 3D-Grid-Structure, overall it will be ~33% filled, i.e. 2 out of 3 gridpoints will be empty.
  Short image to illustrate:</p>
  
  <p><img src="https://i.stack.imgur.com/8CbiR.png" alt="enter image description here"></p>
  
  <p>Maybe Option A)</p>
  
  <pre><code>vector&lt;vector&lt;vector&lt;deque&lt;Obj&gt;&gt; grid;// (SizeX, SizeY, SizeZ);
  grid[x][y][z].push_back(someObj);
  </code></pre>
  
  <p>This way I'd have a lot of empty deques, but accessing one of them would be fast, wouldn't it?</p>
  
  <p>The Other Option B) would be</p>
  
  <pre><code>std::unordered_map&lt;Pos3D, deque&lt;Obj&gt;, Pos3DHash, Pos3DEqual&gt; Pos3DMap; 
  </code></pre>
  
  <p>where I add&amp;delete deques when data is added/deleted. Probably less memory used, but maybe less fast? What do you think?</p>
  
  <h2>2nd Question (follow up)</h2>
  
  <p>What if I had multiple containers at each position? Say 3 buckets for 3 different entities, say object types ObjA, ObjB, ObjC per grid point, then my data essentially becomes 4D?</p>
  
  <p>Another illustration:
  <img src="https://i.stack.imgur.com/zkUGv.png" alt="enter image description here"></p>
  
  <p>Using Option 1B I could just extend Pos3D to include the bucket number to account for even more sparse data.
  Possible queries I want to optimize for:</p>
  
  <ol>
  <li>Give me all Objects out of ObjA-buckets from the entire structure</li>
  <li>Give me all Objects out of ObjB-buckets for a set of
  grid-positions</li>
  <li>Which is the nearest non-empty ObjC-bucket to
  position x,y,z?</li>
  </ol>
  
  <h2>PS:</h2>
  
  <p>I had also thought about a tree based data-structure before, reading about nearest neighbour approaches. Since my data is so regular I had thought I'd save all the tree-building dividing of the cells into smaller pieces and just make a static 3D-grid of the final leafs. Thats how I came to ask about the best way to store this grid here.
  Question associated with this, if I have a <code>map&lt;int, Obj&gt;</code> is there a fast way to ask for "all objects with keys between 780 and 790"? Or is the fastest way the building of the above mentioned tree?</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I ended up going with a 3D boost::multi_array that has fortran-ordering. It's a little bit like the chunks games like minecraft use. Which is a little like using a kd-tree with fixed leaf-size and fixed amount of leaves? Works pretty fast now so I'm happy with this approach.</p>