c++ - tipos - ¿Cómo se inserta el valor en un vector ordenado?

vectores c++

Question

TODAS,

Esta pregunta es una continuación de esta . Creo que STL pierde esta funcionalidad, pero es solo mi IMHO.

Ahora, a la pregunta.

Considera seguir el código:

class Foo
{
public:
    Foo();
...........
private:
    int paramA, paramB;
    std::string name;
};

int main()
{
    std::vector<Foo> foo;
    Sorter sorter;
    sorter.paramSorter = 0;
    std::sort( foo.begin(), foo.end(), sorter );
}

struct Sorter
{
    bool operator()(const Foo &foo1, const Foo &foo2)
    {
         switch( paramSorter )
         {
             case 0:
                 return foo1.name < foo2.name;
             case 1:
                 return foo1.paramA < foo2.paramB;
             case 2:
                 return foo1. paramA > foo2.paramB;
         }
    }
private:
    int paramSorter;
}

En cualquier momento dado, el vector puede ser reordenado. La clase también tiene los métodos captadores que se usan en la estructura del clasificador.

¿Cuál sería la forma más eficiente de insertar un nuevo elemento en el vector?

La situación que tengo es:

Tengo una cuadrícula (hoja de cálculo) que usa el vector ordenado de una clase. En cualquier momento dado, el vector se puede volver a clasificar y la cuadrícula mostrará los datos clasificados en consecuencia.

Ahora tendré que insertar un nuevo elemento en el vector / grid. Puedo insertar, luego volver a ordenar y luego volver a mostrar toda la cuadrícula, pero esto es muy ineficiente, especialmente para la gran red.

Cualquier ayuda sería apreciada.

Answer 1

Cuando desee cambiar entre órdenes de clasificación, puede usar múltiples estructuras de datos de índice, cada una de las cuales mantiene en orden ordenado (probablemente algún tipo de árbol balanceado, como std :: map, que asigna sort-keys a vector-index, o std :: configurado para almacenar punteros a los que obedece, pero con diferentes funciones de comparación).

Aquí hay una biblioteca que hace esto: http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html

Para cada cambio (inserción de nuevos elementos o actualización de claves) debe actualizar toda la estructura de datos del índice o marcarlos como no válidos.

Esto funciona si no hay "demasiados" órdenes de clasificación y no "demasiadas" actualizaciones de su estructura de datos. De lo contrario, mala suerte, debes volver a ordenar cada vez que quieras cambiar el orden.

En otras palabras: cuantos más índices necesite (para acelerar las operaciones de búsqueda), más tiempo necesitará para las operaciones de actualización. Y cada índice necesita memoria, por supuesto.

Para mantener el recuento de índices pequeño, puede usar algún motor de consulta que combine los índices de varios campos para admitir órdenes de clasificación más complejas en varios campos. Como un optimizador de consultas SQL. Pero eso puede ser exagerado ...

Ejemplo: si tiene dos campos, a y b, puede admitir 4 órdenes de clasificación:

1. un
2. segundo
3. primero a luego b
4. primero b luego un

con 2 índices (3. y 4.). Con más campos, las posibles combinaciones de órdenes de clasificación se hacen grandes, rápidas. Pero aún puede usar un índice que ordena "casi como lo desea" y, durante la consulta, ordenar los campos restantes que no pudo capturar con ese índice, según sea necesario. Para la salida ordenada de toda la información, esto no ayuda mucho. Pero si solo desea buscar algunos elementos, el primer "estrechamiento" puede ayudar mucho.

Answer 2

En lugar de insertar y ordenar. Debe hacer un hallazgo y luego insertar

Mantenga el vector ordenado. (ordenar una vez). Cuando tienes que insertar

1. encuentre el primer elemento que se compare como mayor al que va a insertar.

2. Haga una inserción justo antes de esa posición.

De esta manera, el vector permanece ordenado.

Aquí hay un ejemplo de cómo funciona.

start {} empty vector

insert 1 -> find first greater returns end() = 1 -> insert at 1 -> {1}
insert 5 -> find first greater returns end() = 2 -> insert at 2 -> {1,5}
insert 3 -> find first greater returns 2 -> insert at 2 -> {1,3,5}
insert 4 -> find first greater returns 3 -> insert at 3 -> {1,3,4,5}

Answer 3

La respuesta simple a la pregunta:

template< typename T >
typename std::vector<T>::iterator 
   insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert
        ( 
            std::upper_bound( vec.begin(), vec.end(), item ),
            item 
        );
}

Versión con un predicado.

template< typename T, typename Pred >
typename std::vector<T>::iterator
    insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
    return vec.insert
        ( 
           std::upper_bound( vec.begin(), vec.end(), item, pred ),
           item 
        );
}

Donde Pred es un predicado estrictamente ordenado en el tipo T.

Para que esto funcione, el vector de entrada ya debe estar ordenado en este predicado.

La complejidad de hacer esto es O(log N) para la búsqueda upper_bound (encontrar dónde insertar) pero hasta O(N) para la inserción misma.

Para una mejor complejidad, puede usar std::set<T> si no va a haber ningún duplicado o std::multiset<T> si puede haber duplicados. Estos mantendrán un orden ordenado para usted automáticamente y usted podrá especificar su propio predicado en estos también.

Hay varias otras cosas que podría hacer que son más complejas, por ejemplo, administrar un vector y un vector set / multiset / sorted vector de los elementos recién agregados y luego combinarlos cuando haya suficientes. Cualquier tipo de iteración a través de su colección deberá ejecutarse en ambas colecciones.

Usar un segundo vector tiene la ventaja de mantener sus datos compactos. Aquí su vector elementos "recién agregados" será relativamente pequeño, por lo que el tiempo de inserción será O(M) donde M es el tamaño de este vector y podría ser más factible que el O(N) de insertar en el vector grande todo el tiempo. La fusión sería O(N+M) que es mejor que O(NM) , sería insertar uno a la vez, por lo que en total sería O(N+M) + O(M²) para insertar M elementos y luego fusionar .

Probablemente también mantendrías el vector de inserción en su capacidad, de modo que a medida que crezcas no harás reasignaciones, solo movimientos de elementos.

Answer 4

Si necesita mantener el vector ordenado todo el tiempo, primero puede considerar si usar std::set o std::multiset no simplificará su código.

Si realmente necesita un vector ordenado y desea insertar rápidamente un elemento en él, pero no desea aplicar un criterio de clasificación para estar satisfecho todo el tiempo, entonces primero puede usar std::lower_bound() para encontrar la posición en un rango ordenado donde el elemento debe insertarse en tiempo logarítmico, luego use la función miembro insert() del vector para insertar el elemento en esa posición.

Si el rendimiento es un problema, considere el benchmarking std::list vs std::vector . Para artículos pequeños, se sabe que std::vector es más rápido debido a una tasa de aciertos de caché más alta, pero la operación de insert() misma es computacionalmente más rápida en las listas (no es necesario mover los elementos).

Answer 5

Solo una nota, también puedes usar upper_bound dependiendo de tus necesidades. upper_bound asegurará nuevas entradas que son equivalentes a otras aparecerán al final de su secuencia, lower_bound asegurará nuevas entradas equivalentes a otras aparecerán al comienzo de su secuencia. Puede ser útil para ciertas implementaciones (¡tal vez clases que pueden compartir una "posición" pero no todos sus detalles!)

Ambos le asegurarán que el vector permanece ordenado de acuerdo con < resultado de elementos, aunque insertar en lower_bound significa mover más elementos.

Ejemplo:

insert 7 @ lower_bound of { 5, 7, 7, 9 } => { 5, *7*, 7, 7, 9 }
insert 7 @ upper_bound of { 5, 7, 7, 9 } => { 5, 7, 7, *7*, 9 }

Answer 6

Suponiendo que realmente quiere usar un vector, y el criterio de ordenación o las claves no cambian (para que el orden de los elementos ya insertados permanezca siempre igual): inserte el elemento al final, luego muévalo al frente un paso a la vez tiempo, hasta que el elemento anterior no sea más grande.

No se puede hacer más rápido (con respecto a la complejidad asintótica, o "gran notación O"), porque debe mover todos los elementos más grandes. Y esa es la razón por la que STL no proporciona esto, porque es ineficiente en vectores, y no debería usarlos si lo necesita.

Editar: Otra suposición: Comparar los elementos no es mucho más caro que moverlos. Ver comentarios.

Editar 2: como mi primera suposición no se cumple (quiere cambiar el criterio de clasificación), elimine esta respuesta y vea la otra: https://.com/a/15843955/1413374