title: Store 2D points for quick retrieval of those inside a rectangle
body: <p>I have a large number of 2D points and I want to quickly get those that lie in a certain rectangle.
  Let's say a '.' is any point and 'X' is a point I want to find inside a rectangle which has 'T' as TopLeft and 'B' as BottomRight points:</p>
  
  <pre><code>. . . . . .
  . T-----+ .
  . | X X | .
  . +-----B .
  . . . . . .
  </code></pre>
  
  <p>I have tried a std::set with a sort functor which sorts the TopLeft point at the beginning and the BottomRight at the end of the set. When sorting by X value first, this would result in the following points being found.</p>
  
  <pre><code>. . . . . .
  . T-----+ .
  X | X X | X
  . +-----B .
  . . . . . .
  </code></pre>
  
  <p>This means I would have to check each found point, whether it really is inside the rectangle. Not really good.</p>
  
  <p>What would be a better way to do this?</p>
  
  <p>My language is C++ (Windows) and I have the STL as well as boost available.</p>
  
  <h3>Update</h3>
  
  <p>Having read the answers so far, I noticed that I haven't accounted for all parameters of my problem: There is not one fixed rectangle.
  Rectangles can be set by the user at runtime. This means sorting the set of points promises to be more efficient than a linear search through all points as suggested by Artelius before this update.
  I will still give it a try, though! I don't expect the user to set a rectangle <em>very</em> frequent. So regarding the implementation effort it might show up to be a good solution for me.</p>