title: Sorted data structure for in-order iteration, ordered push, and removal (N elements only from top)
body: <p>What is considered an optimal data structure for pushing something in order (so inserts at any position, able to find correct position), in-order iteration, and popping N elements off the top (so the N smallest elements, N determined by comparisons with threshold value)?  The push and pop need to be particularly fast (run every iteration of a loop), while the in-order full iteration of the data happens at a variable rate but likely an order of magnitude less often.  The data can't be purged by the full iteration, it needs to be unchanged.  Everything that is pushed will eventually be popped, but since a pop can remove multiple elements there can be more pushes than pops.  The scale of data in the structure at any one time could go up to hundreds or low thousands of elements.</p>
  
  <p>I'm currently using a <code>std::deque</code> and binary search to insert elements in ascending order.  Profiling shows it taking up the majority of the time, so something has got to change.  <code>std::priority_queue</code> doesn't allow iteration, and hacks I've seen to do it won't iterate in order.  Even on a limited test (no full iteration!), the <code>std::set</code> class performed worse than my <code>std::deque</code> approach.</p>
  
  <p>None of the classes I'm messing with seem to be built with this use case in mind.  I'm not averse to making my own class, if there's a data structure not to be found in STL or boost for some reason.</p>
  
  <p>edit:</p>
  
  <p>There's two major functions right now, <code>push</code> and <code>prune</code>.  <code>push</code> uses 65% of the time, <code>prune</code> uses 32%.  Most of the time used in <code>push</code> is due to insertion into the <code>deque</code> (64% out of 65%).  Only 1% comes from the binary search to find the position.</p>
  
  <pre><code>template&lt;typename T, size_t Axes&gt;
  void Splitter&lt;T, Axes&gt;::SortedData::push(const Data&amp; data) //65% of processing
  {
   size_t index = find(data.values[(axis * 2) + 1]);
  
   this-&gt;data.insert(this-&gt;data.begin() + index, data); //64% of all processing happens here
  }
  
  template&lt;typename T, size_t Axes&gt;
  void Splitter&lt;T, Axes&gt;::SortedData::prune(T value) //32% of processing
  {
   auto top = data.begin(), end = data.end(), it = top;
  
   for (; it != end; ++it)
   {
    Data&amp; data = *it;
  
    if (data.values[(axis * 2) + 1] &gt; value) break;
   }
  
   data.erase(top, it);
  }
  
  template&lt;typename T, size_t Axes&gt;
  size_t Splitter&lt;T, Axes&gt;::SortedData::find(T value)
  {
   size_t start = 0;
   size_t end = this-&gt;data.size();
  
   if (!end) return 0;
  
   size_t diff;
  
   while (diff = (end - start) &gt;&gt; 1)
   {
    size_t mid = diff + start;
  
    if (this-&gt;data[mid].values[(axis * 2) + 1] &lt;= value)
    {
     start = mid;
    }
    else
    {
     end = mid;
    }
   }
  
   return this-&gt;data[start].values[(axis * 2) + 1] &lt;= value ? end : start;
  }
  </code></pre>