surrounding objects algorithm
<p>I'm working on a game where exactly one object may exist at location <code>(x, y)</code> where <code>x</code> and <code>y</code> are <code>ints</code>. For example, an object may exist at <code>(0, 0)</code> or it may not, but it is not possible for multiple objects to exist there at once.</p>

<p>I am trying to decide which STL container to use for the problem at hand and the best way to solve this problem.</p>

<p>Basically, I start with an object and its <code>(x, y)</code> location. The goal is to determine the <strong>tallest</strong>, largest possible rectangle based on that object's surrounding objects. The rectangle must be created by using all objects above and below the current object. That is, it must be the tallest that it can possibly be based on the starting object position.</p>

<p>For example, say the following represents my object grid and I am starting with the green object at location <code>(3, 4)</code>:</p>

<p><img src="http://i.stack.imgur.com/5l3rV.png" alt="enter image description here"></p>

<p>Then, the rectangle I am looking for would be represented by the pink squares below:</p>

<p><img src="http://i.stack.imgur.com/HbQvy.png" alt="enter image description here"></p>

<p>So, assuming I start with the object at <code>(3, 4)</code> like the example shows, I will need to check if objects also exist at <code>(2, 4)</code>, <code>(4, 4)</code>, <code>(3, 3)</code>, and <code>(3, 5)</code>. If an object exists at any of those locations, I need to repeat the process for the object to find the largest possible rectangle.</p>

<p>These objects are rather rare and the game world is massive. It doesn't seem practical to just <code>new</code> a 2D array for the entire game world since most of the elements would be empty. However, I need to be to index into any position to check if an object is there at any time.</p>

<p>Instead, I thought about using a <code>std::map</code> like so:</p>

<pre><code>std::map&lt; std::pair&lt;int, int&gt;, ObjectData&gt; m_objects;
</code></pre>

<p>Then, as I am checking the surrounding objects, I could use <code>map::find()</code> in my loop, checking if the surrounding objects exist:</p>

<pre><code>if(m_objects.find(std::pair&lt;3, 4&gt;) != m_objects.end())
{
    //An object exists at (3, 4).
    //Add it to the list of surrounding objects.
}
</code></pre>

<p>I could potentially be making a lot of calls to <code>map::find()</code> if I decide to do this, but the map would take up much less memory than <code>new</code>ing a 2D array of the entire world.</p>

<p>Does anyone have any advice on a simple algorithm I could use to find what I am looking for? Should I continue using a <code>std::map</code> or is there a better container for a problem like this?</p>
