vector :: erase y reverse_iterator

Question

Tengo una colección de elementos en un std :: vector que se ordenan en orden descendente a partir del primer elemento. Tengo que usar un vector porque necesito tener los elementos en un trozo contiguo de memoria. Y tengo una colección que contiene muchas instancias de vectores con las características descritas (siempre ordenadas en orden descendente).

Ahora, a veces, cuando me entero de que tengo demasiados elementos en la mayor colección (la que sostiene estos vectores), descarto los elementos más pequeños de estos vectores de alguna manera similares a este pseudo-código:

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 < comparison (this is what sorts data before they hit any of the vectors). 

std::map<C, std::pair<T::const_reverse_iterator, std::vector<T>&>> what_to_delete; 
iterate(it = grand_collection.begin() -> grand_collection.end()) 
{ 
    iterate(vect_rit = it->rbegin() -> it->rend()) 
    { 
     // ... 
      what_to_delete <- (vect_rit->C, pair(vect_rit, *it)) 
      if (what_to_delete.size() > threshold) 
       what_to_delete.erase(what_to_delete.begin()); 
     // ... 
    } 
} 

Ahora, después de ejecutar este código, en what_to_delete tengo una colección de iteradores que apuntan a los vectores originales que quiero eliminar de estos vectores (valores más pequeños en general). Recuerde, los vectores originales se ordenan antes de que lleguen a este código, lo que significa que para cualquier what_to_delete[0 - n] no hay forma de que un iterador en la posición n - m apunte a un elemento más al principio del mismo vector que n, donde m > 0.

Al borrar elementos de los vectores originales, tengo que convertir un reverse_iterator en un iterador. Para ello, me baso en C++ de 11 §24.4.1/1:

La relación entre reverse_iterator y iterador es & * (reverse_iterator (i)) == & * (i-1)

lo que significa que para eliminar un vect_rit, utilizo:

vector.erase(--vect_rit.base()); 

Ahora, de acuerdo con C++ 11 estándar §23.3.6.5/3:

iterator erase (const_iterator position); Efectos: invalida iteradores y referencias en o después del punto del borrado.

¿Cómo funciona esto con reverse_iterators? ¿Los reverse_iterators se implementan internamente con una referencia al comienzo real de un vector (vector[0]) y transformando ese vect_rit en un iterador clásico para que luego borrarlo sea seguro? ¿O reverse_iterator usa rbegin() (que es vector[vector.size()]) como punto de referencia y borrar todo lo que esté más alejado del índice 0 del vector aún invalidaría mi iterador inverso?

Editar:

Parece que reverse_iterator utiliza rbegin() como punto de referencia. Borrar elementos de la manera que describí me estaba dando errores sobre un iterador no deferencial después de que se eliminó el primer elemento. Mientras que al almacenar iteradores clásicos (convirtiendo a const_iterator) al insertar en what_to_delete funcionó correctamente.

Ahora, para referencia futura, ¿The Standard especifica qué se debe tratar como un punto de referencia en caso de un reverse_iterator de acceso aleatorio? O este es un detalle de implementación?

Gracias!

Answer 1

En la cuestión ya se ha citado exactamente lo que la norma dice que un reverse_iterator es:

La relación entre reverse_iterator y iterador es & * (reverse_iterator (i)) == & * (i-1)

recordar que un reverse_iterator es sólo un 'adaptador' en la parte superior del iterador subyacente (reverse_iterator::current). El 'punto de referencia', como usted lo dice, para un reverse_iterator es ese iterador envuelto, current. Todas las operaciones en el reverse_iterator realmente ocurren en ese iterador subyacente.Puede obtener ese iterador usando la función reverse_iterator::base().

Si borra --vect_rit.base(), de hecho está borrando --current, por lo que current se invalidará.

Como nota al margen, la expresión --vect_rit.base() podría no compilarse siempre. Si el iterador es en realidad solo un puntero sin formato (como podría ser el caso de vector), entonces vect_rit.base() devuelve un rvalue (un prvalue en términos de C++ 11), por lo que el operador de decremento previo no trabajará en él, ya que el operador necesita un valor l modificable. Consulte "Artículo 28: Entender cómo usar una base de reverse_iteratoriterator" en "STL efectivo" por Scott Meyers. (Una versión anterior del artículo se puede encontrar en línea en la "Guía 3" de http://www.drdobbs.com/three-guidelines-for-effective-iterator/184401406).

Puede usar la expresión aún más fea, (++vect_rit).base(), para evitar ese problema. O desde que usted está tratando con un vector y iteradores de acceso aleatorio: vect_rit.base() - 1

De cualquier manera, vect_rit se invalida por el borrado porque vect_rit.current se invalida.

Sin embargo, recuerde que vector::erase() devuelve un iterador válido a la nueva ubicación del elemento que siguió al que acaba de borrarse. Se puede utilizar eso a 'volver a sincronizar' vect_rit:

vect_rit = vector_type::reverse_iterator(vector.erase(vect_rit.base() - 1)); 

Answer 2

Desde un punto de vista estándar (y lo admitiré, no soy un experto en el estándar): del §24.5.1.1:

namespace std { 
    template <class Iterator> 
    class reverse_iterator ... 
    { 
     ... 
      Iterator base() const; // explicit 
     ... 
     protected: 
      Iterator current; 
     ... 
    }; 
} 

Y desde §24.5.1.3.3:

Iterator base() const; // explicit 
    Returns: current. 

Por lo tanto me parece que mientras no borrar nada en el vector antes de lo que uno de sus reverse_iterator s señala, dijo reverse_iterator debe seguir siendo válido.

Por supuesto, dada su descripción, hay un inconveniente: si tiene dos elementos contiguos en su vector que desea eliminar, el hecho de que vector.erase(--vector_rit.base()) significa que ha invalidado el reverse_iterator "apuntando" a el elemento inmediatamente anterior, por lo que su siguiente vector.erase(...) es un comportamiento indefinido.

Sólo en caso de que es claro como el barro, permítanme decir que de otra manera:

std::vector<T> v=...; 
... 
// it_1 and it_2 are contiguous 
std::vector<T>::reverse_iterator it_1=v.rend(); 
std::vector<T>::reverse_iterator it_2=it_1; 
--it_2; 

// Erase everything after it_1's pointee: 

// convert from reverse_iterator to iterator 
std::vector<T>::iterator tmp_it=it_1.base(); 

// but that points one too far in, so decrement; 
--tmp_it; 

// of course, now tmp_it points at it_2's base: 
assert(tmp_it == it_2.base()); 

// perform erasure 
v.erase(tmp_it); // invalidates all iterators pointing at or past *tmp_it 
        // (like, say it_2.base()...) 

// now delete it_2's pointee: 
std::vector<T>::iterator tmp_it_2=it_2.base(); // note, invalid iterator! 

// undefined behavior: 
--tmp_it_2; 
v.erase(tmp_it_2); 

---

En la práctica, sospecho que se encontrará con dos implementaciones posibles: más comúnmente, la iterator subyacente ser poco más que un puntero crudo (adecuadamente envuelto), y así todo funcionará perfectamente feliz. Con menos frecuencia, el iterador podría en realidad tratar de rastrear invalidaciones/realizar comprobaciones de límites (¿no hizo Dinkumware STL tales cosas cuando se compiló en modo depuración en un punto?), Y podría gritarte.

Answer 3

El reverse_iterator, al igual que el iterator normal, apunta a una determinada posición en el vector. Los detalles de implementación son irrelevantes, pero si usted debe saber, ambos son (en una implementación típica) simples punteros antiguos en su interior. La diferencia es la dirección. El iterador inverso tiene su + y - invertido w.r.t. el iterador regular (y también ++ y --, > y < etc.).

Esto es interesante de saber, pero en realidad no implica una respuesta a la pregunta principal.

Si se lee el lenguaje cuidado, que dice:

Invalida iteradores y referencias en o después del punto del borrado.

Las referencias no tienen un sentido de dirección incorporado. Por lo tanto, el lenguaje se refiere claramente al propio sentido de dirección del contenedor. Las posiciones después del punto del borrado son aquellas con índices más altos. Por lo tanto, la dirección del iterador es irrelevante aquí.