manera rápida de implementar pop_front a std :: vector

Question

Estoy usando algunas clases y varios métodos de utilidad que usan std :: vector.

Ahora necesito usar cada fotograma un método pop_front - push_back en una de esas clases (pero todas están vinculadas, y funcionan juntas, así que no puedo cambiar solo una).

La mayoría de las operaciones se repiten sobre todas las operaciones de elementos y push_back, entonces lo que debo hacer para el mejor trabajo es: bifurcar el repositorio de esas clases y utilidades, plantilla todo y usar deque o list.

Pero esto significa mucha reescritura de código y muchas pruebas que me harán perder la fecha límite.

Así que necesito consejos para escribir un pop_front eficiente en un vector de tamaño estático (el tamaño no cambiará).

he encontrado una manera here:

template<typename T> 
void pop_front(std::vector<T>& vec) 
{ 
    vec.front() = vec.back(); 
    vec.pop_back(); 
    vec.front() = vec.back(); // but should this work? 
} 

Y otra idea debería ser:

template<typename T> 
void pop_front(std::vector<T>& vec, already_allocated_vector vec1) 
{ 
    vec1.clear(); 
    copy(vec.begin(), vec.end()-1, vec1.begin()); 
    copy(vec1.begin(), vec1.end(), vec.begin()); 
} 

¿Cuál es el más rápido de estas dos soluciones? ¿Alguna otra solución?

Answer 1

yo esperaría:

template<typename T> 
void pop_front(std::vector<T>& vec) 
{ 
    assert(!vec.empty()); 
    vec.front() = std::move(vec.back()); 
    vec.pop_back(); 
} 

a ser la forma más eficiente de hacerlo, pero no mantiene el orden de los elementos en el vector.

Si necesita mantener el orden de los elementos restantes en vec, que puede hacer:

template<typename T> 
void pop_front(std::vector<T>& vec) 
{ 
    assert(!vec.empty()); 
    vec.erase(vec.begin()); 
} 

Esto tendrá tiempo lineal en el número de elementos en vec, pero es lo mejor que puede hacer sin cambiar su estructura de datos

Ninguna de estas funciones mantengan la vector en un tamaño constante, porque una operación de pop_front se por definición eliminar un elemento de un contenedor.

Answer 2

Desde pop_front() sólo borra el primer elemento, la aplicación directa es la siguiente:

template <typename V> 
void pop_front(V & v) 
{ 
    assert(!v.empty()); 
    v.erase(v.begin()); 
} 

No se preocupe por la velocidad por ahora. Si desea volver atrás y optimizar el código, solicite tiempo dedicado al proyecto.

Answer 3

IgushArray (https://github.com/igushev/IgushArray) que, como una matriz, tiene una operación rápida de acceso constante, pero la operación de inserción/borrado toma solo O (N^1/2) tiempo. Entonces, en su caso, insertarlo al comienzo sería muy efectivo aquí. Tenga cuidado, la estructura es muy sensible para la reserva().

template <class T> 
void pop_front(IgushArray<T>& v) 
{ 
    if (!v.empty()) 
    v.erase(v.begin()); 
} 

En la primera opción que escribió usted viola el orden de los elementos. ¿Es un problema?

Si es así, utilice la variante que escribí.

Si no es así y el orden de los elementos no importa en absoluto, puede ser mejor usar std :: set o std :: multiset.

Answer 4

si sólo intenta borrar el primer elemento a continuación, en la función de su uso:

if (my_vector.size()){ //check if there any elements in the vector array 
    my_vector.erase(my_vector.begin()); //erase the firs element 
} 

si desea emular frontal pop por toda la matriz de vectores (que desea mantener el pop a cabo todos los elementos desde el principio hasta fin), sugiero en:

reverse(my_vector.begin(),my_vector.end()); // reverse the order of the vector array 
my_vector.pop_back(); // now just simple pop_back will give you the results