J'ai une liste de listes comme ceci: Je l'ai rempli de listes avec des doubles en eux (en fait beaucoup, c'est pourquoi je n'utilise pas de vecteur. Tous Cette copie prend beaucoup de temps.) Dites que je veux accéder à l'élément qui pourrait être accessible comme Je sais que l'accès des éléments d'une liste est accompli en utilisant un itérateur. Je ne pouvais pas comprendre comment sortir le double si. Liste [3] [3] si la liste n'était pas une liste mais un vecteur ou un tableau de deux dimensions. Comment je ferais cela?
3 Réponses :
template<typename Container>
typename Container::iterator begin(Container &container)
{
return container.begin();
}
template<typename Container>
typename Container::const_iterator begin(const Container &container)
{
return container.begin();
}
template<typename T, int n>
T *begin(T (&array)[n])
{
return &array[0];
}
template<typename Iterator>
Iterator next(Iterator it, typename std::iterator_traits<Iterator>::difference_type n = 1)
{
std::advance(it, n);
return it;
}
Pour accéder à cela, mais pas sur l'insertion. Le vecteur doit être copié dans un nouvel emplacement de mémoire chaque fois que la taille de sa taille est élargie. Depuis que la liste sera accueillie plus tard (non à des fins de test) d'une manière linéaire, je pense que cela n'a pas d'importance qu'il s'agisse d'une liste et d'un temps de recherche linéaire pour un élément
@OAKTREEE: D'ailleurs que vous pouvez réserver () pour atténuer cela, cela alloue toujours tant d'espace supplémentaire qu'il n'a pas à réaffecter à tous les redimensionnements.
@Plasmahh je pouvais réserver la mémoire si je savais exactement combien d'éléments doivent être ajoutés. J'ajoute environ 512 éléments par liste et j'ai environ 400 listes. Je sais que ce n'est pas encore une énorme quantité, mais un peu ...
@ecatmur My STL ne semble pas avoir std :: Suivant (Suivant () ou y compris Itérateur n'est tout simplement pas suffisant. Il semble également manquer std :: début ()
@oaktree std :: Suivant et std :: commence a été ajouté à C ++ 11.
@ecatmur je suppose que cela prendra du temps jusqu'à ce que le compilateur CL soutient que ^^
@oaktree en supposant que vous parlez de Visual Studio, Microsoft ajoutez des fonctionnalités C ++ 11 depuis VC10 et VC12 est réputée assez bonne. Il est facile d'écrire un remplacement de compatibilité pour std :: Suivant ; Je vais le montrer ci-dessus.
Pour répondre strictement à votre question, Joachim Pileborg's La réponse est la voie à suivre: Maintenant, de votre question et de vos commentaires supplémentaires, il n'est pas clair si vous ajoutez toujours des éléments à la fin des listes ou que vous pouvez ajouter n'importe où. Si vous ajoutez toujours à la fin, en plus de cela, en utilisant et vous réservez également pour chaque Prenez en compte que votre liste de listes prendra beaucoup plus d'espace. Pour chaque vecteur vecteur réserve () , comme les autres ont déjà dit, aider beaucoup avec les réaffectations. Vous n'avez pas besoin de réserver pour la taille combinée de tous les vecteurs, mais uniquement pour chaque vecteur individuel. Donc: vecteur v . C'est tout. double dans la liste interne, il devra attribuer au moins deux pointeurs supplémentaires, ainsi que deux autres pointeurs supplémentaires pour chaque liste à l'intérieur du moins global. Cela signifie que la mémoire totale prise par votre conteneur sera à peu près trois fois celle du vecteur. Et toute cette allocation et cette direction prend également des heures d'exécution supplémentaires.
avancement ne fonctionnera pas de manière temporaire telle que retournée par commencer . Vous devez utiliser Suivant .
J'ai oublié d'ajouter quelque chose. Si vous ne connaissez pas vraiment la taille finale du conteneur et vous préoccupez d'attribuer trop d'espace ou trop peu, envisagez d'utiliser deque <> . Il est généralement un peu plus lent que vecteur <> , mais pousse beaucoup mieux, car il n'a pas besoin de se copier. Pour cette raison, deque <> n'a pas de méthode réserve () .
@ecatmur: En fait, avance () ne fonctionne pas comme je l'ai écrit. Je modifie le code.
Vous devez utiliser
vecteur . Utilisez la listeuniquement lorsque vous devez épisser.@avakar Si vous n'avez pas besoin d'un accès aléatoire et que vous devez supprimer des éléments de début / milieu du conteneur - l'utilisation du vecteur est une très mauvaise idée.
Utilisez
Vector :: Réservez Pour réserver la mémoire et éviter des copies supplémentaires si c'est votre préoccupation. En outre, même si vous pouvez obteniropérateur [] pour ce que vous voulez, ce sera vraiment inefficace.STD :: Vecteur est généralement assez intelligent quand il doit réaffecter, de sorte que cela augmente, il faut moins que cela doive réaffecter et copier.Std :: Liste est seulement plus rapide si vous créez le conteneur de nombreux temps beaucoup pendant la durée de vie du programme.@Forever, vous avez raison, si vous devez insérer / supprimer du début / milieu, vous ne devez pas utiliser de vecteur non plus. Ce n'est pas parce que vous n'avez pas besoin d'un accès aléatoire que vous ne devriez pas utiliser le vecteur.
Il y a une structure de données de liste dans Boost qui offre à la fois les capacités de STD :: Vector and List \