Un petit problème théorique (voire rhétorique) : est-il possible d'implémenter un std::list<> en termes de std::vector<> ?
C'est à dire ?
Bien sûr, un list<T> n'est pas implémentable directement avec un vector<T>.
J'avais pensé au début l'implémenter en termes de vector<T*>, mais ça ne donne pas grand-chose de bon.
Y a-t-il une solution (quitte à être un peu moins rapide que le std::list "normal"), sans bien sûr sacrifier le cahier des charges de std::list<> ?
Que cherches-tu à faire ? Je ne comprends pas.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. Paul Éluard)
Jean-Marc Bourguet
Fabien LE LEZ writes:
Y a-t-il une solution (quitte à être un peu moins rapide que le std::list "normal"), sans bien sûr sacrifier le cahier des charges de std::list<> ?
J'ai un probleme avec les appels aux constructeurs et aux destructeurs.
Sinon, tu fais un vector<tuple<T, size_t, size_t> > en gerant toi meme dans les deux size_t des indices plutot que des pointeurs... il te faut en plus garder l'indice de ta tete de liste, et un indice de la tete de ta liste d'elements libres pour pouvoir les recuperer.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Fabien LE LEZ <gramster@gramster.com> writes:
Y a-t-il une solution (quitte à être un peu moins rapide que le
std::list "normal"), sans bien sûr sacrifier le cahier des charges de
std::list<> ?
J'ai un probleme avec les appels aux constructeurs et aux
destructeurs.
Sinon, tu fais un vector<tuple<T, size_t, size_t> > en gerant toi meme
dans les deux size_t des indices plutot que des pointeurs... il te
faut en plus garder l'indice de ta tete de liste, et un indice de la
tete de ta liste d'elements libres pour pouvoir les recuperer.
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Y a-t-il une solution (quitte à être un peu moins rapide que le std::list "normal"), sans bien sûr sacrifier le cahier des charges de std::list<> ?
J'ai un probleme avec les appels aux constructeurs et aux destructeurs.
Sinon, tu fais un vector<tuple<T, size_t, size_t> > en gerant toi meme dans les deux size_t des indices plutot que des pointeurs... il te faut en plus garder l'indice de ta tete de liste, et un indice de la tete de ta liste d'elements libres pour pouvoir les recuperer.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
kanze
Fabien LE LEZ wrote:
Un petit problème théorique (voire rhétorique) : est-il possible d'implémenter un std::list<> en termes de std::vector<> ?
Je ne suis pas sûr ce que tu cherches à faire, mais...
std::list< int > l ; l.push_back( 1 ) ; std::list< int >::iterator i = l.begin() ; for ( int i = 0 ; i < 1000 ; ++ i ) { l.push_back( i ) ; } *i = 2 ;
C'est garanti avec std::list. Je ne vois pas comment tu vas le faire avec std::vector. Les garanties en ce qui concerne les itérateurs et les pointeurs ou les références à des éléments sont bien différentes.
-- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Fabien LE LEZ wrote:
Un petit problème théorique (voire rhétorique) : est-il
possible d'implémenter un std::list<> en termes de
std::vector<> ?
Je ne suis pas sûr ce que tu cherches à faire, mais...
std::list< int > l ;
l.push_back( 1 ) ;
std::list< int >::iterator
i = l.begin() ;
for ( int i = 0 ; i < 1000 ; ++ i ) {
l.push_back( i ) ;
}
*i = 2 ;
C'est garanti avec std::list. Je ne vois pas comment tu vas le
faire avec std::vector. Les garanties en ce qui concerne les
itérateurs et les pointeurs ou les références à des éléments
sont bien différentes.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Un petit problème théorique (voire rhétorique) : est-il possible d'implémenter un std::list<> en termes de std::vector<> ?
Je ne suis pas sûr ce que tu cherches à faire, mais...
std::list< int > l ; l.push_back( 1 ) ; std::list< int >::iterator i = l.begin() ; for ( int i = 0 ; i < 1000 ; ++ i ) { l.push_back( i ) ; } *i = 2 ;
C'est garanti avec std::list. Je ne vois pas comment tu vas le faire avec std::vector. Les garanties en ce qui concerne les itérateurs et les pointeurs ou les références à des éléments sont bien différentes.
-- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Fabien LE LEZ
On 3 Jul 2006 09:50:49 -0700, "kanze" :
C'est garanti avec std::list.
Oui.
Je ne vois pas comment tu vas le faire avec std::vector.
Moi non plus. C'est pour ça que je pose la question ;-) Note que pour la durée de validité des itérateurs, Jean-Marc semble avoir une solution.
Un jour, un y a un bon bout de temps, je crois bien être tombé sur une incompatibilité entre std::list<> (celui de mon très vieux compilo) et je ne sais plus quoi. Une des solutions envisagées a été d'essayer de pondre ma propre implémentation de list<>[*]. Et mon premier réflexe fut tout naturellement d'essayer de stocker les données sous forme d'un std::vector<>. Mais je n'y suis pas arrivé. Et depuis, le problème (devenu purement théorique, car je ne compte pas implémenter une éventuelle solution) trotte dans un coin de mon cerveau.
[*] Finalement, il s'est avéré plus simple d'aller chercher une version qui fonctionne chez SGI ;-)
On 3 Jul 2006 09:50:49 -0700, "kanze" <kanze@gabi-soft.fr>:
C'est garanti avec std::list.
Oui.
Je ne vois pas comment tu vas le faire avec std::vector.
Moi non plus. C'est pour ça que je pose la question ;-)
Note que pour la durée de validité des itérateurs, Jean-Marc semble
avoir une solution.
Un jour, un y a un bon bout de temps, je crois bien être tombé sur une
incompatibilité entre std::list<> (celui de mon très vieux compilo) et
je ne sais plus quoi.
Une des solutions envisagées a été d'essayer de pondre ma propre
implémentation de list<>[*].
Et mon premier réflexe fut tout naturellement d'essayer de stocker les
données sous forme d'un std::vector<>. Mais je n'y suis pas arrivé. Et
depuis, le problème (devenu purement théorique, car je ne compte pas
implémenter une éventuelle solution) trotte dans un coin de mon
cerveau.
[*] Finalement, il s'est avéré plus simple d'aller chercher une
version qui fonctionne chez SGI ;-)
Je ne vois pas comment tu vas le faire avec std::vector.
Moi non plus. C'est pour ça que je pose la question ;-) Note que pour la durée de validité des itérateurs, Jean-Marc semble avoir une solution.
Un jour, un y a un bon bout de temps, je crois bien être tombé sur une incompatibilité entre std::list<> (celui de mon très vieux compilo) et je ne sais plus quoi. Une des solutions envisagées a été d'essayer de pondre ma propre implémentation de list<>[*]. Et mon premier réflexe fut tout naturellement d'essayer de stocker les données sous forme d'un std::vector<>. Mais je n'y suis pas arrivé. Et depuis, le problème (devenu purement théorique, car je ne compte pas implémenter une éventuelle solution) trotte dans un coin de mon cerveau.
[*] Finalement, il s'est avéré plus simple d'aller chercher une version qui fonctionne chez SGI ;-)
Jean-Marc Bourguet
Fabien LE LEZ writes:
On 3 Jul 2006 09:50:49 -0700, "kanze" :
C'est garanti avec std::list.
Oui.
Je ne vois pas comment tu vas le faire avec std::vector.
Moi non plus. C'est pour ça que je pose la question ;-) Note que pour la durée de validité des itérateurs, Jean-Marc semble avoir une solution.
Je n'ai fait que suggerer une implementation classique d'une liste en utilisant un vector<> comme source de memoire plutot que de l'allocation dynamique. On peut avoir au moins deux raisons de faire ca: - les donnees sont serialisables facilement (puisqu'il n'y a pas de pointeurs) - une meilleure localite des acces (donc a priori mieux pour les caches, du moins tant qu'il n'y a pas d'effet de resonnance, mais un tel effet peut aussi avoir lieu avec l'allocation dynamique)
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Fabien LE LEZ <gramster@gramster.com> writes:
On 3 Jul 2006 09:50:49 -0700, "kanze" <kanze@gabi-soft.fr>:
C'est garanti avec std::list.
Oui.
Je ne vois pas comment tu vas le faire avec std::vector.
Moi non plus. C'est pour ça que je pose la question ;-)
Note que pour la durée de validité des itérateurs, Jean-Marc semble
avoir une solution.
Je n'ai fait que suggerer une implementation classique d'une liste en
utilisant un vector<> comme source de memoire plutot que de
l'allocation dynamique. On peut avoir au moins deux raisons de faire
ca:
- les donnees sont serialisables facilement (puisqu'il n'y a pas
de pointeurs)
- une meilleure localite des acces (donc a priori mieux pour les
caches, du moins tant qu'il n'y a pas d'effet de resonnance, mais
un tel effet peut aussi avoir lieu avec l'allocation dynamique)
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Je ne vois pas comment tu vas le faire avec std::vector.
Moi non plus. C'est pour ça que je pose la question ;-) Note que pour la durée de validité des itérateurs, Jean-Marc semble avoir une solution.
Je n'ai fait que suggerer une implementation classique d'une liste en utilisant un vector<> comme source de memoire plutot que de l'allocation dynamique. On peut avoir au moins deux raisons de faire ca: - les donnees sont serialisables facilement (puisqu'il n'y a pas de pointeurs) - une meilleure localite des acces (donc a priori mieux pour les caches, du moins tant qu'il n'y a pas d'effet de resonnance, mais un tel effet peut aussi avoir lieu avec l'allocation dynamique)
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
