¿Qué estructura de datos se usa ampliamente en C?

Question

Hace un par de días me pregunté qué estructura de datos debería tener en una función en C. Normalmente escribo en C++ y la elección habría caído a std :: vector.

Hay alguna algunas opciones posibles:

• un estáticas array (lo suficientemente grande)
• una matriz dinámica que crece cuando sea necesario (por ejemplo, duplicar su tamaño)
• una implementación propia lista como estructura con una puntero siguiente

La última opción parece ser inusual. ¿Hay algún proyecto más grande en el que alguien use estructuras propias como listas ? ¿Existe una regla general para la decisión entre matriz o propias estructuras de datos?

Cuando necesitaría una estructura de árbol, no lo pensaría dos veces y solo escribiría un árbol. ¿Hay libs ampliamente utilizados con tales estructuras (como boost para C++)? ¿O es considerado como un estilo malo porque tendría que almacenar un vacío * en lugar de el tipo real?

¡Muchas gracias por su experiencia!

Answer 1

Cada uno tiene sus propias ventajas y desventajas.

• Arrays estáticos: perfectos para tablas de búsqueda y datos que no cambian su tamaño durante la ejecución del programa. Se asignan al inicio del programa, por lo que no tiene que administrar esta memoria de ninguna manera. Una desventaja es que no puede cambiar el tamaño ni liberar una matriz estática, sino que permanece allí hasta que finaliza el programa.

• Arrays de crecimiento dinámico: una estructura de datos fácil de administrar que casi puede ser un sustituto de vectores en C++. Una desventaja es la sobrecarga de asignar memoria en tiempo de ejecución, pero eso se puede aliviar si asigna fragmentos más grandes a la vez.

• Listas vinculadas: tenga cuidado si va a tener muchos elementos porque asignar cada uno por separado sin usar un conjunto de memoria puede ocasionar pérdida de memoria y fragmentación.

Answer 2

Las listas de vínculos dinámicos se utilizan ampliamente en C, donde se desconoce el número de elementos que se almacenarán.

Answer 3

Vector es una matriz dinámica y se implementa internamente como una matriz dinámica. Le sugiero que use vectores ya que las máquinas están optimizadas para recuperar las ubicaciones de memoria continua, mientras que la lista de enlaces no se almacenará en una ubicación continua.

Habiendo dicho eso, si no requiere la rápida recuperación de elemento por índice en su caso de uso, entonces puede ir también a la lista de enlaces. La lista de enlaces también tiene la ventaja de no desperdiciar el espacio a diferencia del arreglo dinámico (doblando cuando está a punto de llenarse) y también la inserción en el inicio o entre los elementos es más barata en comparación con la matriz.

Answer 4

Diferentes estructuras de datos ofrecen una complejidad computacional diferente para inserciones, búsquedas y otras operaciones.

para tomar su ejemplo específico, hay un número de diferencias entre una matriz y una lista enlazada:

• de búsqueda por índice es O(1) en una matriz y O(n) en una lista;
• las inserciones en una lista son O(1) o O(n) (dependiendo de si requieren cruce), y en una matriz se amortizan O(1) si se hace bien;
• eliminaciones de una matriz son O(n) mientras que ciertos tipos de eliminaciones de listas se pueden hacer en O(1) vez;
• Las matrices ofrecen una mejor ubicación de referencia y, en consecuencia, un mejor rendimiento de la memoria caché.

Usted puede encontrar la siguiente página útil: http://essays.hexapodia.net/datastructures/

Como regla general, la hora de elegir una estructura de datos que primero considerar si tengo fuertes razones para creer que la ejecución del código en cuestión va a ser importante:

• si no lo hago, que optan por la estructura de datos más simple que hacer el trabajo, o el que se presta para el código más claro;
• si hago, pienso cuidadosamente sobre qué operaciones voy a realizar en la estructura y elijo en consecuencia, posiblemente seguido de perfilado.

En cuanto a las recomendaciones para las buenas bibliotecas estructura de datos C, echar un vistazo a Are there any open source C libraries with common data structures?

Answer 5

En C puro Yo sobre todo utilizar matrices estáticas. Está conectado con la programación de dispositivos integrados que tienen problemas para asignar y liberar memoria: fragmentación de pila.

Pero si hay una necesidad de utilizar la lista, implemento una yo mismo - a veces su implementación se basa en matrices estáticas (de nuevo).

Creo que hay bibliotecas para C que ofrecen una implementación decente de estructuras de datos más complejas. AFAIK glib es ampliamente utilizado y ofrece al menos listas vinculadas.

Answer 6

Depende completamente de qué operaciones va a realizar en la estructura de datos. Si va a recuperar datos por índice (por ejemplo, datos [3]), entonces una lista es una idea horrible, ya que cada lectura requerirá que recorra la lista. Si va a insertar mucho en la primera posición (por ejemplo, datos [0] = x), una matriz será terrible porque moverá todos los datos para cada inserción.

Si va a usar std :: vector, una matriz dinámica es probablemente la mejor alternativa. Pero quizás std :: vector no hubiera sido la elección correcta.

Answer 7

Recuerdo que leí un documento de Apple hace algún tiempo diciendo que tal cosa podría ser implementado inocentemente con una estructura similar a:

struct { 
    void *data; //other type rather than void is easier 
    int length; 
} MyArray; 

MyArray *MyArrayCreate(){ 
    //mallocate memory 
    return ... 
} 
void MyArrayRelease(){ 
    free(...); 
} 

y poner en práctica una función que comprueba la longitud de la matriz y su no lo suficiente, se asignará otra matriz lo suficientemente grande, se copiarán los datos anteriores y se agregarán nuevos datos.

MyArrayInsertAt(MyArray *array, index, void *object){ 
    if (length < index){ 
     //mallocate again, copy data 
     //update length 
    } 
    data[index] = object; 
} 

lo tanto, puede utilizarse como tal:

MyArray *array = MyArrayCreate(); 
MyArrayInsertAt(array, 5, something); 
MyArrayRelease(array); 

MyArrayInsertAt() no va a ganar un precio por su rendimiento, pero podría ser una solución para no programas/aplicaciones exigentes de alto

No puedo encontrar el enlace ... ¿quizás alguien lo haya leído también?

AÑADIDOS: He encontrado que GNU NSMutableArray (Objective-C) métodos de implementación se realizan en C y hacen lo mismo que el anterior. Doblan el tamaño de la matriz cada vez que se agrega un objeto y no cabe en la matriz. Consulte la línea 131 a 145