title: vector::erase and reverse_iterator
body: <p>I have a collection of elements in a std::vector that are sorted in a descending order starting from the first element. I have to use a vector because I need to have the elements in a contiguous chunk of memory. And I have a collection holding many instances of vectors with the described characteristics (always sorted in a descending order).</p>
  
  <p>Now, sometimes, when I find out that I have too many elements in the greater collection (the one that holds these vectors), I discard the smallest elements from these vectors some way similar to this pseudo-code: </p>
  
  <pre><code>grand_collection: collection that holds these vectors
  T: type argument of my vector
  C: the type that is a member of T, that participates in the &lt; comparison (this is what sorts data before they hit any of the vectors).
  
  std::map&lt;C, std::pair&lt;T::const_reverse_iterator, std::vector&lt;T&gt;&amp;&gt;&gt; what_to_delete;
  iterate(it = grand_collection.begin() -&gt; grand_collection.end())
  {
       iterate(vect_rit = it-&gt;rbegin() -&gt; it-&gt;rend())
       {
           // ...
            what_to_delete &lt;- (vect_rit-&gt;C, pair(vect_rit, *it))
            if (what_to_delete.size() &gt; threshold)
                 what_to_delete.erase(what_to_delete.begin());
           // ...  
       }
  }
  </code></pre>
  
  <p>Now, after running this code, in <code>what_to_delete</code> I have a collection of iterators pointing to the original vectors that I want to remove from these vectors (overall smallest values). Remember, the original vectors are sorted before they hit this code, which means that for any <code>what_to_delete[0 - n]</code> there is no way that an iterator on position <code>n - m</code> would point to an element further from the beginning of the same vector than <code>n</code>, where <code>m &gt; 0</code>.</p>
  
  <p>When erasing elements from the original vectors, I have to convert a reverse_iterator to iterator. To do this, I rely on C++11's §24.4.1/1: </p>
  
  <blockquote>
    <p>The relationship between reverse_iterator and iterator is
    &amp;*(reverse_iterator(i)) == &amp;*(i- 1)</p>
  </blockquote>
  
  <p>Which means that to delete a <code>vect_rit</code>, I use:</p>
  
  <pre><code>vector.erase(--vect_rit.base());
  </code></pre>
  
  <p>Now, according to C++11 standard <code>§23.3.6.5/3</code>:</p>
  
  <blockquote>
    <p>iterator erase(const_iterator position); Effects: Invalidates
    iterators and references at or after the point of the erase.</p>
  </blockquote>
  
  <p>How does this work with reverse_iterators? Are reverse_iterators internally implemented with a reference to a vector's real beginning (<code>vector[0]</code>) and transforming that vect_rit to a classic iterator so then erasing would be safe? Or does reverse_iterator use rbegin() (which is <code>vector[vector.size()]</code>) as a reference point and deleting anything that is further from vector's 0-index would still invalidate my reverse iterator?</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>Looks like reverse_iterator uses rbegin() as its reference point. Erasing elements the way I described was giving me errors about a non-deferenceable iterator after the first element was deleted. Whereas when storing classic iterators (converting to <code>const_iterator</code>) while inserting to <code>what_to_delete</code> worked correctly.</p>
  
  <p>Now, for future reference, does The Standard specify what should be treated as a reference point in case of a random-access reverse_iterator? Or this is an implementation detail?</p>
  
  <p>Thanks!</p>