Je portait un peu de code C très ancien dans C ++ et je rencontre une liste liée implémentée dans un tableau. L'élément est une structure simple: en tant que tableau, il y a un accès rapide aux données, si vous connaissez l'index. L'aspect lié à la liste lie permet aux éléments d'être déplacé et "supprimé" de la liste. Les éléments peuvent être déplacés dans la liste, en fonction de la fréquence d'utilisation (en haut pour MRU et vers le bas pour le LRU). J'aime trouver un meilleur moyen de mettre en œuvre cela que d'utiliser un autre tableau. J'aimerais utiliser STL, mais je ne suis pas certain quel conteneur est préférable à utiliser. Quelqu'un a des pensées?
3 Réponses :
Comme il s'agit d'une liste liée, vous devriez probablement utiliser std :: Liste ...
La règle de base est que vous souhaitez utiliser une liste liée lorsque vous devez insérer des éléments dans des positions aléatoires dans la liste ou supprimer des éléments aléatoires de la liste. Si vous devez principalement ajouter / supprimer des éléments à / à partir de la fin de la liste, vous devez utiliser Gardez à l'esprit, nous parlons de probabilités ici. Si vous avez besoin d'insérer un élément au milieu d'un D'autre part, l'avantage de l'utilisation d'un vecteur est que ses éléments sont contigus en mémoire, ce qui améliore considérablement la performance si vous avez simplement besoin de les traverser dans l'ordre en raison de la mise en cache. std :: vecteur . Si vous devez ajouter / supprimer des éléments à / à partir du début ou de la fin de la liste, vous devez utiliser std :: deque . .
std :: vecteur une fois dans une lune bleue, cela ira probablement bien. Mais si vous avez besoin de le faire tout le temps, il aura un impact majeur sur la performance, car le vecteur devra constamment déplacer ses éléments et réaffectera probablement sa mémoire aussi.
L'accès direct est l'accès le plus commun
@kberson NB. Cette liste STD :: La liste ne prend pas en charge l'accès direct par index.
Besoin de pouvoir accéder directement aux éléments avec juste l'index. Besoin de pouvoir déplacer des éléments, alors stl :: vecteur ne fonctionne pas.
@Kberson: Si cela fonctionnait à l'aide d'un tableau, il fonctionnera certainement avec un std :: vecteur ...
Que voulez-vous dire par "Déplacer des éléments"? Si vous avez besoin d'échanger deux éléments, il n'y a pas de problème. Si vous devez ajouter plus d'éléments à la fin du vecteur, il s'agira automatiquement. Mais si vous avez besoin d'insérer un élément à, dites, indice 5, puis le vecteur devra déplacer tous les éléments commençant par un numéro 5 en un.
@kberson: Notez que ce n'est pas que c'est impossible pour std :: vecteur pour insérer des éléments au milieu - c'est juste que, à cause de la nature même des vecteurs, ce n'est pas si efficace, car tous les éléments après que le point d'insertion doit être déplacé.
voir ici:
http://linuxsoftware.co.nz/cppcontainers.html
Il y a un organigramme pour vous aider à choisir le bon conteneur en bas.
Étant donné que les données de cette liste sont des pointeurs, pourquoi vous embêter avec une liste liée du tout? Pour les petits pods, std :: vecteur est généralement le meilleur premier pari, et en raison de la meilleure localité de ses données jouant bien avec les caches de processeur, il effectue souvent une liste liée, même si, en théorie, Une liste liée devrait être meilleure. Je choisirais std :: vecteur jusqu'à ce que certains profilage montrent qu'il existe un problème de performance et std :: list fonctionne mieux.
La vitesse d'accès aléatoire est-elle cruciale? Je veux dire, cela se produit beaucoup , par opposition à itération?
Cela dépend entièrement de la manière dont il est utilisé par le reste du code. Un accès direct est-il un moyen courant d'accéder à des éléments ou est-ce que cela fait principalement en entrant dans la liste? Certains éléments sont-ils accessibles plus souvent que d'autres?
Une fois, j'ai lu un article réclamé (et défendu) l'affirmation selon laquelle
std :: vecteur est presque toujours un meilleur choix questd :: Liste , même si vous ajoutez / Supprimer des articles du milieu du conteneur. Je ne trouve pas l'article maintenant, alors j'ai ajouté cela comme un commentaire au lieu d'une réponse. J'apprécierais que d'autre qui est au courant de l'article pouvait poster un lien.@Michael Burr: Cela dépend presque toujours de la fréquence à laquelle vous devez ajouter / supprimer des éléments, le nombre d'éléments dont vous avez besoin pour ajouter / supprimer à la fois et ce que vous faites avec le conteneur après.
@DIMA: Je ne connais aucun article spécifique, mais sachez de ma propre expérience et d'autres personnes qui, si la copie est suffisamment bon marché,
std :: vecteur est presque toujours meilleur questd :: Liste , même si cela ne devrait pas être en théorie. C'est certainement si vous stockez uniquement les pointeurs. Voir ma réponse.