C++ lié liste code existant à STL - allocation liée taille de la liste à la volée

Question

Je travaille sur un code existant qui définit une liste chaînée (ne pas utiliser conteneur STL)

Je veux convertir ce code afin utiliser la liste STL. Comme vous pouvez le voir dans l'exemple suivant, la liste liée est affectée d'une valeur initiale pour tous les N. Ensuite, certains éléments de la liste ont une certaine valeur. Ensuite, les "éléments vides" de la liste sont "nettoyés".

Je cherche une meilleure façon de le faire en utilisant STL. surtout, peut-on éviter cette suppression du code des éléments vides? J'ai vérifié la documentation de STL .. elle définit une méthode remove mais ce n'est pas exactement ce dont j'ai besoin ici. Existe-t-il un moyen d'allouer dynamiquement la taille de la liste liée? J'apprécierais vos suggestions!

Mise à jour J'ai modifié le code. Cela ressemble au code principal que j'ai. Mais pour éviter toute confusion, j'écris un pseudo code ci-dessous pour expliquer comment cela fonctionne.

étapes

1. Allouer une taille elementIds à la liste chaînée (struct my_list)
2. Il y a une autre liste chaînée meshElem et je suis intéressé par certaines valeurs de meshElem->elem struct.
   • Par exemple: J'ai besoin elemId = meshElem->elem->id; Ce elemId est à portée 0 to elementIds.
   • Le elemId sera utilisé comme index pour rechercher un élément particulier dans struct my_list lst. lst[elemId]
3. Dans la fonction doSomething(), boucle à travers 0 to elementIds. Dans cette boucle, si certaines conditions sont remplies, le lst->number est attribué une valeur entière = someArray[i] où i est dans la gamme 0 to N (fait en appendElement)
4. les éléments sans next l'entrée dans le struct my_list lst, sont nettoyés (Question: cela peut être évité?)
5. La valeur lst-> number est utilisée plus loin dans le code pour un autre traitement.

Maintenant, le code modifié:

struct my_list 
{ 
    int number; 
    struct my_list *prev; 
    struct my_list *next; 
} 

void doSomething(void){ 
    const int N = 50000; 
    const int elementIds = 10000; 
    int i, elemId, node_i;  
    struct my_list *lst;  
    lst = new struct my_list[elementIds]; 
    int someArray[12]; 

    meshElem = mesh->next;  

    for(i=0; i<=elementIds; i++) { 
     lst[i].num = 0; 
     lst[i].next = NIL; 
     lst[i].prev = NIL; 
     }  

    while(meshElem != NIL){ 
     // Element id (int) 
     // Note that any elemId will be in range [0 - elemId ] 
     elemId = meshElem->elem->id; 

     // Do some operations to populate "lst"  
     // Note that 'lst' gets values ONLY for certain 
     // values of i 
     for (i = 0; i<=N; i++){   
      // if certain conditions are satisfied, 
      // it updates the linked list element 
      // lst[meshIdx]. foo1(), foo2() are just some conditions... 

      if (foo1()){ 
       appendElement(someArray[i], &lst[meshIdx]) 
       } 
      else if (foo2()){ 
       appendElement(someArray[i], &lst[meshIdx])   
      } 
     }   

     meshElem = meshelem->next; 

    } // End of while(meshElem != NIL) 

    // Clean up the linked list lst 
    // by removing unassigned items. 

    struct my_list *lst_2 

    for(i=1; i<=N; i++) { 
    lst_2 = &lst[i]; 
    while(lst != NIL) {  
     if(lst->next != NIL && lst->next->number == 0) { 
     delete lst_2->next; 
     lst_2->next = NIL; 
     } // end of if loop 
     lst = lst_2->next; 

    } // end of while while(lst != NIL) 

    } // End of for(i=1; i<=N; i++) 


    // Do some more stuff that uses struct my_list lst 
    for(i=1;i<=elementIds;i++) { 

     while(lst[i] != NIL && (node_i = lst[i]->number)) { 
      if(node_i == 0) { 
       lst[i] = lst[i]->next; 
       continue; 
      } 
      // Use this "node_i" index in some other arrays to 
      // do more stuff. 
      //.. 
      //.. 
      //.. 
      lst[i] = lst[i]->next;  
     } 

} 


void appendElement(int n, struct my_list *lst) { 
    int exists = 0; 
    while(lst->next != NIL) { 
    if(lst->number == n) { 
    exists = 1; 
    lst=lst->next; 
    } 
    if(exists < 1) { 
    lst->number = n2; 
    insertElemAfter(lst, 0); 
    } 
} 

Answer 1

struct my_list { 
    int number; 
} 

void doSomething(void){ 
    std::list<my_list> lst; 
    const int N = 10000;   
    for (int i = 0; i<=N; ++i) {   
     if (1 == foo(N)) { //I'm guessing this is what you meant 
      my_list new_element; //Initalize with something; 
      lst.push_back(new_element); 
     } 
    } 
} 

int 
foo(int n) { 
    // some function that returns 0 or 1 based on 
    // the value of n 
    return 1; 
} 

Answer 2

std::list<int> lst; 

Answer 3

Dans votre logique au lieu de créer tous les noeuds au début pourquoi ne pas vous exécutez la boucle une seule fois et de créer un des éléments dynamiquement pour la condition vraie et l'ajouter dans la liste.

for (i = 0; i<=N; i++) 
{ 
    if (i == foo(N)) 
     node = createNode(); 
    appendElement(node); 
} 

Answer 4

Je pense que vous voulez juste:

std::list<int> lst; 

for (i = 0; i<=N; i++){   
    if (i == foo(N)) 
    lst.push_back(/*some new value*/); 
} 

Answer 5

Une liste chaînée généralement ne pas utiliser la mémoire contiguë, mais plutôt fragmentés nœuds attribués-tas.Je suppose que si vous fournissez le constructeur std::list avec un nombre initial, au moins autant de nœuds seront contigus. Autre que cela, vous devez écrire votre propre allocateur pour aller avec std::list.

Answer 6

Votre liste liée héritée est essentiellement un vecteur sparse threadé. Le tableau avec NULLs est le vecteur fragmenté et la liste liée fournit le thread. Les deux combinés donnent un accès constant aux nœuds individuels (accès aléatoire dans le tableau) et une traversée efficace sur les nœuds "valides" (évitant les NULL).

En supposant que ces deux aspects sont importants, et en supposant que les données peut-être plus complexe que le simple vous int montrer, vous pouvez ensuite créer une structure de données telles que:

class ThreadedSparseVector { 
private: 
    std::vector<Data*> m_thread; 
    std::vector<int> m_sparse_vector; 
}; 

Lors de l'initialisation, vous pouvez pré taille m_sparse_vector et initialise les valeurs à -1. Comme vous ajoutez des éléments (ou les accès), vérifier si elle est déjà « valide » d'abord, en ajoutant au fil sinon:

void ThreadedSparseVector::appendElement(int i) { 
    if (-1 == m_sparse_vector[i]) { 
     // Add new data 
     m_sparse_vector[i] = m_thread.size() 
     m_thread.push_back(new Data(i)); 
    } 

    Data* data = m_thread[m_sparse_vector[i]]; 
    // Initialize/update data as necessary 
} 

Si le filetage est plus important que l'accès aléatoire, une autre option est simplement utiliser une carte STL. Si l'accès aléatoire est plus important que le threading, vous pouvez simplement utiliser un vecteur STL et tolérer les valeurs NULL pendant l'itération (ou créer un itérateur personnalisé qui ignore automatiquement les valeurs NULL). Une autre alternative, en fonction de votre motivation pour convertir en STL, consiste à créer un wrapper autour du code existant qui implémente une interface compatible STL, par opposition à la conversion de la structure de données elle-même pour utiliser STL.