es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Mejor clase de contenedor para eliminar un elemento.

28 Jul, 2023 Programación

Necesito usar la función erase pero si uso un vector, sería muy lento. ¿Qué contenedor debo usar? Intenté con una lista pero no tenía acceso a un iterador aleatorio, que es lo que necesito. Aquí está mi código, también estaría bien una solución alternativa:

container<><ll, ll="">> m;
for (auto i=0, j=1; j < m.size();)
{
    if (m[i].first > m[j].first)
    {
        cout << m[i].second << endl;
        m.erase(m.begin()+i);
    }
}

Edit: Usar iterador y lista funciona increíblemente bien.</ll,>

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Si se requiere acceso aleatorio y la función de borrado necesita ser eficiente, una opción podría ser utilizar el contenedor deque. Ofrece complejidad constante de tiempo para inserciones y eliminaciones al principio y al final, así como O(sqrt(n)) para inserciones y eliminaciones en cualquier otra posición, lo cual es significativamente mejor que la complejidad O(n) del contenedor vector.

    Para utilizar deque, reemplace la declaración del vector con:

    “`c++
    deque<><ll,ll>> m;


    Esto permitirá que la función de borrado funcione de manera mucho más eficiente que cuando se utiliza un vector.

Como alternativa, ya que las listas no tienen acceso aleatorio, se puede iterar a través de la lista con un iterador y utilizar la función de borrado en cada elemento:

```c++
list<><ll,ll>> m;
for (auto it=m.begin(); it != m.end();)
{
    auto curr = it++;
    if (it != m.end() && curr->first > it->first)
    {
        cout << curr->second << endl;
        m.erase(curr);
    }
}

    Este enfoque puede ser más lento que el uso de deque o vector, pero aún puede ser más rápido que el uso de la función de borrado del vector.</ll,ll></ll,ll>

Comments are closed.