title: Is there a sorted container in the STL?
body: <p>Is there a sorted container in the STL?  </p>
  
  <p>What I mean is following: I have an <code>std::vector&lt;Foo&gt;</code>, where <code>Foo</code> is a custom made class. I also have a comparator of some sort which will compare the fields of the class <code>Foo</code>.</p>
  
  <p>Now, somewhere in my code I am doing:</p>
  
  <pre><code>std::sort( myvec.begin(), myvec.end(), comparator );
  </code></pre>
  
  <p>which will sort the vector according to the rules I defined in the comparator.</p>
  
  <p>Now I want to insert an element of class <code>Foo</code> into that vector. If I could, I would like to just write:</p>
  
  <pre><code> mysortedvector.push_back( Foo() );
  </code></pre>
  
  <p>and what would happen is that the vector will put this new element according to the comparator to its place.</p>
  
  <p>Instead, right now I have to write:</p>
  
  <pre><code>myvec.push_back( Foo() );
  std::sort( myvec.begin(), myvec.end(), comparator );
  </code></pre>
  
  <p>which is just a waste of time, since the vector is already sorted and all I need is to place the new element appropriately.</p>
  
  <p>Now, because of the nature of my program, I can't use <code>std::map&lt;&gt;</code> as I don't have a key/value pairs, just a simple vector.</p>
  
  <p>If I use <code>stl::list</code>, I again need to call sort after every insertion.</p>