¿Existe alguna estructura ya creada que sería simplemente basic array de doubly linked list nodes?

Quiero decir, entonces usa get(int index) y devolvería el elemento directamente desde la matriz (array[i].element). Con esta estructura, también podría hacer foreach fácilmente porque cada elemento estaría vinculado entre sí, por lo que no tendría que pensar en lugares de matriz en blanco.

P: ¿Por qué necesito esto? R: Tengo memoria ilimitada, sé el tamaño de la matriz que necesito y quiero que la estructura sea más rápida.

1
Vinigas 25 ene. 2016 a las 18:55

3 respuestas

La mejor respuesta

Aquí hay una pequeña guía de contenedores de C ++ 11 , simplemente establezca sus restricciones y siga las flechas:

enter image description here

En mi opinión, std::deque es el candidato más probable.

En caso de que desee crear algo usted mismo, aquí hay un ejemplo de cómo podría verse:

struct Node{
    // constructor
    Node (int v, Node* n = 0, Node* p = 0) 
        : value(v), next(n), prev(p) { }

    // data member
    int value;
    // pointer to next node
    Node* next;
    // pointer to previous node
    Node* prev;
};

size_t number_of_nodes = 10;
Node* ptr = new Node[number_of_nodes];
4
Ziezi 25 ene. 2016 a las 16:27

Creo que lo que buscas es el contenedor deque ya presente en el STL. Consulte - & gt; http://en.cppreference.com/w/cpp/container/deque Si no es el que está buscando, probablemente encuentre aquí el contenedor que necesita: & gt; http://www.cplusplus.com/reference/stl/

Espero que esta ayuda

2
Grégory Vaumourin 25 ene. 2016 a las 16:05

Según su descripción, creo que la estructura de datos más adecuada sería una cola de dos extremos; o, en C ++, un std::deque.

Cómo es como una lista doblemente enlazada:

  • Almacena punteros delanteros y traseros
    • {push,pop}_{front,back} son O(1)
  • No necesita reasignaciones cuando la expansión es necesaria

Cómo es como una matriz:

  • Permite la indexación de subíndices
    • O(1) acceso aleatorio

La operación get que está buscando es operator[] o std::deque::at.

Algunas consideraciones son que la inserción / eliminación de elementos que no se encuentran en los extremos polares de la estructura (es decir, en algún lugar en el medio) son un caso promedio O(n) en el número de elementos por la misma razón es O(n) para eliminar un elemento de una matriz básica.

Caso de uso básico obligatorio

3
erip 25 ene. 2016 a las 17:07