Réflexions sur la façon de mettre en œuvre?

Je porte un c-code très ancien en C++ et j'ai parcouru une liste chaînée implémentée dans un tableau. L'élément est une structure simple:Réflexions sur la façon de mettre en œuvre?

struct element 
{ 
    void *m_ptrData; 
    short m_nextEntry; 
    short m_prevEntry; 
};

En tant que tableau, vous disposez d'un accès rapide aux données si vous connaissez l'index. L'aspect liste chaînée permet de déplacer les éléments et de les "supprimer" de la liste. Les éléments peuvent être déplacés dans la liste, en fonction de la fréquence d'utilisation (en hausse pour MRU et en baisse pour LRU).

J'aime trouver une meilleure façon de mettre en œuvre cela que d'utiliser un autre tableau. Je voudrais utiliser STL, mais je ne suis pas certain quel conteneur est le mieux à utiliser.

Quelqu'un a des idées?

Source

2010-12-10 kberson

La vitesse d'accès aléatoire est-elle cruciale? Je veux dire que cela se produit * beaucoup *, par opposition à l'itération? – Guy

Cela dépend entièrement de la façon dont il est utilisé par le reste du code. Est-ce que l'accès direct est un moyen courant d'accéder aux éléments, ou est-ce fait principalement en parcourant la liste? Certains éléments sont-ils accessibles plus souvent que d'autres? – suszterpatt

Une fois, j'ai lu un article qui affirmait (et défendait) l'assertion que 'std :: vector' est presque toujours un meilleur choix que' std :: list', même si vous ajoutez/supprimez des éléments du milieu du conteneur . Je ne trouve pas l'article maintenant, donc j'ai ajouté ceci comme commentaire au lieu d'une réponse. Je serais reconnaissant si quelqu'un d'autre qui est au courant de l'article pourrait poster un lien. –

Comme il est une liste chaînée, vous devriez probablement utiliser std::list ...

La règle de base est que vous souhaitez utiliser une liste chaînée lorsque vous devez insérer des éléments dans des positions aléatoires dans la liste, ou supprimer les éléments aléatoires de la liste. Si vous avez principalement besoin d'ajouter/supprimer des éléments à/de la fin de la liste, vous devez utiliser std::vector. Si vous devez ajouter/supprimer des éléments à partir du début ou de la fin de la liste, vous devez utiliser std::deque. N'oubliez pas, nous parlons de probabilités ici. Si vous avez besoin d'insérer un élément au milieu d'une lune bleue, ce sera probablement OK. Mais si vous avez besoin de le faire tout le temps, cela aura un impact majeur sur les performances, car le vecteur devra constamment déplacer ses éléments et probablement réallouer sa mémoire. D'autre part, l'avantage d'utiliser un vecteur est que ses éléments sont contigus en mémoire, ce qui améliore considérablement les performances si vous avez simplement besoin de les parcourir dans l'ordre en raison de la mise en cache.

Source

2010-12-10 18:58:42 Dima

Accès direct est l'accès le plus commun – kberson

@kberson nb. que std :: list ne supporte pas l'accès direct par index. – razlebe

Besoin d'être en mesure d'accéder directement aux éléments avec juste l'index. Besoin de pouvoir déplacer des éléments, donc stl :: vector ne fonctionne pas. – kberson

Voir ici:

http://linuxsoftware.co.nz/cppcontainers.html

Il y a un organigramme pour vous aider à choisir le bon conteneur au fond.

Source

2010-12-10 19:20:22

Puisque les données de cette liste sont des pointeurs, pourquoi s'embêter avec une liste chaînée? Pour les petits PODs, std::vector est généralement le meilleur premier pari, et en raison de la meilleure localisation de ses données jouant bien avec les caches de processeur, il surpasse souvent une liste chaînée même si, en théorie, une liste chaînée devrait être meilleure. Je choisirais std::vector jusqu'à ce que certains profils montrent qu'il y a un problème de performance et std::list fonctionne mieux.

Source

2010-12-10 19:34:56 sbi

Réflexions sur la façon de mettre en œuvre?

Répondre

Questions connexes