Estructura de datos eficiente para la inserción

Question

Estoy buscando una estructura de datos (tipo array) que permita una inserción arbitraria (más rápida que O (N)) de valores en la estructura. La estructura de datos debe poder imprimir sus elementos en la forma en que se insertaron. Esto es similar a algo como List.Insert() (que es demasiado lento ya que tiene que desplazar cada elemento), excepto que no necesito acceso o eliminación aleatorios. La inserción siempre estará dentro del tamaño de la 'matriz'. Todos los valores son únicos. No se necesitan otras operaciones.

Por ejemplo, si Insert (x, i) inserta el valor x en el índice i (0-indexación). Entonces:

• Insert (1, 0) da {1}
• Insert (3, 1) da {1,3}
• Insert (2, 1) da {1,2,3}
• Insertar (5, 0) da {5,1,2,3}

Y tendrá que ser capaz de imprimir {5,1,2,3} al final.

Estoy usando C++.

Answer 1

Use skip list. Otra opción debería ser tiered vector. La lista de omisiones realiza inserciones en const O (log (n)) y mantiene los números en orden. El vector de niveles admite insertar en O (sqrt (n)) y de nuevo puede imprimir los elementos en orden.

EDIT: por el comentario de Amit voy a explicar cómo encontrar el elemento k-ésimo en una lista de omisión:

Para cada elemento tiene una torre en los enlaces con los siguientes elementos y para cada enlace sabes ¿Cuántos elementos salta? Así que, buscando el elemento k-ésimo, comienzas con el encabezado de la lista y bajas por la torre hasta que encuentras un enlace que salta sobre no más de k elementos. Vas al nodo al que apunta este nodo y reduces k con la cantidad de elementos sobre los que has saltado. Seguir haciendo eso hasta que tiene k = 0.

Answer 2

¿Consideró que usa std::map o std::vector?

Puede usar un std::map con el rango de inserción como clave. Y vector tiene una función de miembro reserve.

Answer 3

en C++, puedes usar un mapa de vectores, así:

int main() { 
    map<int, vector<int> > data; 
    data[0].push_back(1); 
    data[1].push_back(3); 
    data[1].push_back(2); 
    data[0].push_back(5); 
    map<int, vector<int> >::iterator it; 
    for (it = data.begin(); it != data.end(); it++) { 
    vector<int> v = it->second; 
    for (int i = v.size() - 1; i >= 0; i--) { 
     cout << v[i] << ' '; 
    } 
    } 
    cout << '\n'; 
} 

Esta impresora:

5 1 2 3 

Al igual que usted quiere, y los insertos son O (log n).

Answer 4

Puede usar un std::map pares de mapeo (índice, tiempo de inserción) a valores, donde el tiempo de inserción es un entero "autoincrement" (en términos de SQL).El orden de los pares debe ser

(i, t) < (i*, t*) 

si y sólo si

i < i* or t > t* 

En código:

struct lt { 
    bool operator()(std::pair<size_t, size_t> const &x, 
        std::pair<size_t, size_t> const &y) 
    { 
     return x.first < y.first || x.second > y.second; 
    } 
}; 

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like; 

void insert(array_like &a, int value, size_t i) 
{ 
    a[std::make_pair(i, a.size())] = value; 
} 

Answer 5

En cuanto a su comentario:

List.Insert() (que es demasiado lento ya que tiene que cambiar cada elemento),

Las listas no cambian sus valores, se repiten sobre ellos para encontrar la ubicación que desea insertar, tenga cuidado con lo que dice. Esto puede ser confuso para los novatos como yo.

Answer 6

Una solución que se incluye con GCC de forma predeterminada es cuerda estructura de datos. Aquí está el documentation. Normalmente, las cuerdas vienen a la mente cuando se trabaja con largas cadenas de caracteres. Aquí tenemos int s en lugar de caracteres, pero funciona igual. Simplemente use int como parámetro de la plantilla. (También podría ser pair s, etc.)

Aquí está el description of rope on Wikipedia.

Básicamente, es un árbol binario que mantiene cuántos elementos hay en los subárboles izquierdo y derecho (o información equivalente, que es lo que se conoce como estadísticas de orden), y estos recuentos se actualizan apropiadamente como subárboles se giran cuando los elementos se insertan y eliminan Esto permite operaciones O (lg n).