Est-ce une erreur que de croire que la différence entre deux
itérateurs, avec l'opérateur -, fait sens ?
Je pose la question parce que je suis tombé sur un itérateur,
Gtk::TextBuffer::iterator, qui ne fournissait pas cet opérateur, ce qui
fait que l'itérateur se castait en bool (ce qui est ballot).
Finalement j'utilises std::difference. Mais c'est surprenant quand on
a l'habitude d'utiliser l'arithmétique des pointeurs, et que les
itérateurs (qui peuvent être confondus avec des pointeurs) ne le
supporte pas totalement.
Merci pour vos avis !
--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Est-ce une erreur que de croire que la différence entre deux itérateurs, avec l'opérateur -, fait sens ?
Finalement j'utilises std::difference.
Les iterateurs sont une classification plus fine, certains (ceux a acces aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un cout proportionnel a la valeur retournee (je ne me souviens plus si std::difference a un cout constant pour les iterateurs a acces aleatoire ou pas); pour les derniers (ostream_iterator par exemple), std::difference n'a meme pas de sens.
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
Mickaël Wolff <mickael.wolff@laposte.net> writes:
Est-ce une erreur que de croire que la différence entre deux itérateurs,
avec l'opérateur -, fait sens ?
Finalement j'utilises std::difference.
Les iterateurs sont une classification plus fine, certains (ceux a acces
aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un
cout proportionnel a la valeur retournee (je ne me souviens plus si
std::difference a un cout constant pour les iterateurs a acces aleatoire ou
pas); pour les derniers (ostream_iterator par exemple), std::difference n'a
meme pas de sens.
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
Est-ce une erreur que de croire que la différence entre deux itérateurs, avec l'opérateur -, fait sens ?
Finalement j'utilises std::difference.
Les iterateurs sont une classification plus fine, certains (ceux a acces aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un cout proportionnel a la valeur retournee (je ne me souviens plus si std::difference a un cout constant pour les iterateurs a acces aleatoire ou pas); pour les derniers (ostream_iterator par exemple), std::difference n'a meme pas de sens.
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
Michael DOUBEZ
Jean-Marc Bourguet a écrit :
Mickaël Wolff writes:
Est-ce une erreur que de croire que la différence entre deux itérateurs, avec l'opérateur -, fait sens ?
L'opérateur - n'est requis que pour les random_iterator.
Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour une zone de mémoire contigüe.
Finalement j'utilises std::difference.
Vous devez parler de std::distance().
Les iterateurs sont une classification plus fine, certains (ceux a acces aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un cout proportionnel a la valeur retournee
(je ne me souviens plus si std::difference a un cout constant pour les iterateurs a acces aleatoire ou pas);
Ça ne doit pas être garanti par le standard mais en pratique ça m'étonnerais que ce ne soit pas le cas.
pour les derniers (ostream_iterator par exemple), std::difference n'a meme pas de sens.
C'est surtout qu'il est impossible de comparer deux output_iterator. Par contre, distance() fonctionne avec un istream_iterator par exemple (l'intérêt doit quand même être limité)..
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu l'utilises ?
-- Michael
Jean-Marc Bourguet a écrit :
Mickaël Wolff <mickael.wolff@laposte.net> writes:
Est-ce une erreur que de croire que la différence entre deux itérateurs,
avec l'opérateur -, fait sens ?
L'opérateur - n'est requis que pour les random_iterator.
Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour
une zone de mémoire contigüe.
Finalement j'utilises std::difference.
Vous devez parler de std::distance().
Les iterateurs sont une classification plus fine, certains (ceux a acces
aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un
cout proportionnel a la valeur retournee
(je ne me souviens plus si
std::difference a un cout constant pour les iterateurs a acces aleatoire ou
pas);
Ça ne doit pas être garanti par le standard mais en pratique ça
m'étonnerais que ce ne soit pas le cas.
pour les derniers (ostream_iterator par exemple), std::difference n'a
meme pas de sens.
C'est surtout qu'il est impossible de comparer deux output_iterator. Par
contre, distance() fonctionne avec un istream_iterator par exemple
(l'intérêt doit quand même être limité)..
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu
l'utilises ?
Est-ce une erreur que de croire que la différence entre deux itérateurs, avec l'opérateur -, fait sens ?
L'opérateur - n'est requis que pour les random_iterator.
Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour une zone de mémoire contigüe.
Finalement j'utilises std::difference.
Vous devez parler de std::distance().
Les iterateurs sont une classification plus fine, certains (ceux a acces aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un cout proportionnel a la valeur retournee
(je ne me souviens plus si std::difference a un cout constant pour les iterateurs a acces aleatoire ou pas);
Ça ne doit pas être garanti par le standard mais en pratique ça m'étonnerais que ce ne soit pas le cas.
pour les derniers (ostream_iterator par exemple), std::difference n'a meme pas de sens.
C'est surtout qu'il est impossible de comparer deux output_iterator. Par contre, distance() fonctionne avec un istream_iterator par exemple (l'intérêt doit quand même être limité)..
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu l'utilises ?
-- Michael
Jean-Marc Bourguet
Michael DOUBEZ writes:
Jean-Marc Bourguet a écrit : > Mickaël Wolff writes: > >> Est-ce une erreur que de croire que la différence entre deux itérateurs, >> avec l'opérateur -, fait sens ?
L'opérateur - n'est requis que pour les random_iterator.
Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour une zone de mémoire contigüe.
> >> Finalement j'utilises std::difference.
Vous devez parler de std::distance().
C'est bien ce a quoi je pensais, mais j'ai recopie ce qu'a ecrit Mickael.
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu l'utilises ?
Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique la confusion ci-dessus.
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
Michael DOUBEZ <michael.doubez@free.fr> writes:
Jean-Marc Bourguet a écrit :
> Mickaël Wolff <mickael.wolff@laposte.net> writes:
>
>> Est-ce une erreur que de croire que la différence entre deux itérateurs,
>> avec l'opérateur -, fait sens ?
L'opérateur - n'est requis que pour les random_iterator.
Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour une
zone de mémoire contigüe.
>
>> Finalement j'utilises std::difference.
Vous devez parler de std::distance().
C'est bien ce a quoi je pensais, mais j'ai recopie ce qu'a ecrit Mickael.
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu
l'utilises ?
Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique
la confusion ci-dessus.
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
Jean-Marc Bourguet a écrit : > Mickaël Wolff writes: > >> Est-ce une erreur que de croire que la différence entre deux itérateurs, >> avec l'opérateur -, fait sens ?
L'opérateur - n'est requis que pour les random_iterator.
Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour une zone de mémoire contigüe.
> >> Finalement j'utilises std::difference.
Vous devez parler de std::distance().
C'est bien ce a quoi je pensais, mais j'ai recopie ce qu'a ecrit Mickael.
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu l'utilises ?
Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique la confusion ci-dessus.
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
Michael DOUBEZ
Jean-Marc Bourguet a écrit :
Michael DOUBEZ writes:
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu l'utilises ?
Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique la confusion ci-dessus.
J'ai trouvé un exemple sur Google ou une personne avait besoin de connaitre l'index d'un iterator. Et après réflexion, std::distance() peut être utilisé pour connaitre le nombre d'éléments entre deux valeurs dans un conteneur trié.
Un intérêt arrivera peut être dans certains cas (voir article ci-après).
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
- - - - - http://blog.emmanueldeloget.com/index.php/2008/03/25/124-le-futur-standard-c-nouvelle-version-du-draft * STL Singly Linked Lists (N2543)* Par Matt Austern
Elles ont mis du temps à venir, mais elles sont enfin là : les listes chainées simples font leur entrée dans la librairie standard du C++. Accueillons la nouvelle venue avec le respect qui lui est du.
Concrètement, cet ajout prend la forme d'un nouveau conteneur nommé std::forward_list (anciennement std::slist). La proposition de Matt Austern fait certains choix particuliers qui sont rendus explicite par l'interface de la classe. Ainsi, l'opération d'insertion est différente de cette d'une std::list : le nouvel élément est inséré après le noeud courant plutôt qu'avant. Ce choix est illustré par le nom de la fonction d'insertion, qui devient std::forward_list::insert_after(). De même, erase() disparait au profit de std::forward_list::erase_after(). Cela peut poser des problèmes si les conteneurs sont manipulés par des fonctions template.
Autre choix important : std::forward_list ne contient pas de méthode size(). Pour trouver la taille d'une liste, il faudra utiliser l'algorithme std::distance() (un algorithme d'une complexité linéaire). L'auteur explique ce choix en deux phases : 1. avoir une méthode size() qui fonctionnerait en O(N) serait contre-intuitif. 2. ajouter dans la classe une variable pour stocker la taille courante (et transformer size() en une méthode de complexité constante) implique de ne pas respecter l'un des principes d'architecture du langage C++ (you pay for what you use) puisque les opérations de maintenance de cette variable ainsi que sa présence même représentent des coûts cachés pour le programmeur utilisateur.
-- Michael
Jean-Marc Bourguet a écrit :
Michael DOUBEZ <michael.doubez@free.fr> writes:
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu
l'utilises ?
Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique
la confusion ci-dessus.
J'ai trouvé un exemple sur Google ou une personne avait besoin de
connaitre l'index d'un iterator. Et après réflexion, std::distance()
peut être utilisé pour connaitre le nombre d'éléments entre deux valeurs
dans un conteneur trié.
Un intérêt arrivera peut être dans certains cas (voir article ci-après).
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?
- - - - -
http://blog.emmanueldeloget.com/index.php/2008/03/25/124-le-futur-standard-c-nouvelle-version-du-draft
* STL Singly Linked Lists (N2543)* Par Matt Austern
Elles ont mis du temps à venir, mais elles sont enfin là : les listes
chainées simples font leur entrée dans la librairie standard du C++.
Accueillons la nouvelle venue avec le respect qui lui est du.
Concrètement, cet ajout prend la forme d'un nouveau conteneur nommé
std::forward_list (anciennement std::slist). La proposition de Matt
Austern fait certains choix particuliers qui sont rendus explicite par
l'interface de la classe. Ainsi, l'opération d'insertion est différente
de cette d'une std::list : le nouvel élément est inséré après le noeud
courant plutôt qu'avant. Ce choix est illustré par le nom de la fonction
d'insertion, qui devient std::forward_list::insert_after(). De même,
erase() disparait au profit de std::forward_list::erase_after(). Cela
peut poser des problèmes si les conteneurs sont manipulés par des
fonctions template.
Autre choix important : std::forward_list ne contient pas de méthode
size(). Pour trouver la taille d'une liste, il faudra utiliser
l'algorithme std::distance() (un algorithme d'une complexité linéaire).
L'auteur explique ce choix en deux phases :
1. avoir une méthode size() qui fonctionnerait en O(N) serait
contre-intuitif.
2. ajouter dans la classe une variable pour stocker la taille
courante (et transformer size() en une méthode de complexité constante)
implique de ne pas respecter l'un des principes d'architecture du
langage C++ (you pay for what you use) puisque les opérations de
maintenance de cette variable ainsi que sa présence même représentent
des coûts cachés pour le programmeur utilisateur.
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu l'utilises ?
Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique la confusion ci-dessus.
J'ai trouvé un exemple sur Google ou une personne avait besoin de connaitre l'index d'un iterator. Et après réflexion, std::distance() peut être utilisé pour connaitre le nombre d'éléments entre deux valeurs dans un conteneur trié.
Un intérêt arrivera peut être dans certains cas (voir article ci-après).
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
- - - - - http://blog.emmanueldeloget.com/index.php/2008/03/25/124-le-futur-standard-c-nouvelle-version-du-draft * STL Singly Linked Lists (N2543)* Par Matt Austern
Elles ont mis du temps à venir, mais elles sont enfin là : les listes chainées simples font leur entrée dans la librairie standard du C++. Accueillons la nouvelle venue avec le respect qui lui est du.
Concrètement, cet ajout prend la forme d'un nouveau conteneur nommé std::forward_list (anciennement std::slist). La proposition de Matt Austern fait certains choix particuliers qui sont rendus explicite par l'interface de la classe. Ainsi, l'opération d'insertion est différente de cette d'une std::list : le nouvel élément est inséré après le noeud courant plutôt qu'avant. Ce choix est illustré par le nom de la fonction d'insertion, qui devient std::forward_list::insert_after(). De même, erase() disparait au profit de std::forward_list::erase_after(). Cela peut poser des problèmes si les conteneurs sont manipulés par des fonctions template.
Autre choix important : std::forward_list ne contient pas de méthode size(). Pour trouver la taille d'une liste, il faudra utiliser l'algorithme std::distance() (un algorithme d'une complexité linéaire). L'auteur explique ce choix en deux phases : 1. avoir une méthode size() qui fonctionnerait en O(N) serait contre-intuitif. 2. ajouter dans la classe une variable pour stocker la taille courante (et transformer size() en une méthode de complexité constante) implique de ne pas respecter l'un des principes d'architecture du langage C++ (you pay for what you use) puisque les opérations de maintenance de cette variable ainsi que sa présence même représentent des coûts cachés pour le programmeur utilisateur.
-- Michael
James Kanze
On Aug 6, 8:28 am, Mickaël Wolff wrote:
Est-ce une erreur que de croire que la différence entre deux itérateurs, avec l'opérateur -, fait sens ?
Oui. Un itérateur itère. Logiquement, c'est tout ce qu'il doit supporter. (Dans le cas de la STL, on y a ajouté d'autres choses, et certains itérateurs STL supportent la soustraction. Mais pas tous.)
Je pose la question parce que je suis tombé sur un itérateur, Gtk::TextBuffer::iterator, qui ne fournissait pas cet opérateur, ce qui fait que l'itérateur se castait en bool (ce qui est ballot).
Un itérateur qui se convertit implicitement en bool me semble assez louche aussi.
Fondamentalement, un itérateur supporte trois opérations : accès à l'élement courant (éventuellement indirectement), passage à l'élément suivant, et la détermination si on a fini ou non. Trois fonctions, donc : element(), next() et isDone(). Puisqu'aucune de ces fonctions ne correspond réelement à une opération définie sur les types de bases, tout surcharge d'opérateur est un peu un abus. (Note bien que « abus » est rélatif ; l'utilisation de ++ pour next() n'est certainement pas si abusive que l'utilisation de + unaire pour isDone() -- que j'ai réelement vu conseillé. Tout est rélatif.)
Finalement j'utilises std::difference. Mais c'est surprenant quand on a l'habitude d'utiliser l'arithmétique des pointeurs, et que les itérateurs (qui peuvent être confondus avec des pointeurs) ne le supporte pas totalement.
Oui. C'est le genre de problème qui arrive quand on surcharge abusivement.
-- James Kanze (GABI Software) email: 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
On Aug 6, 8:28 am, Micka=EBl Wolff <mickael.wo...@laposte.net> wrote:
Est-ce une erreur que de croire que la diff=E9rence entre deux
it=E9rateurs, avec l'op=E9rateur -, fait sens ?
Oui. Un it=E9rateur it=E8re. Logiquement, c'est tout ce qu'il doit
supporter. (Dans le cas de la STL, on y a ajout=E9 d'autres
choses, et certains it=E9rateurs STL supportent la soustraction.
Mais pas tous.)
Je pose la question parce que je suis tomb=E9 sur un it=E9rateur,
Gtk::TextBuffer::iterator, qui ne fournissait pas cet
op=E9rateur, ce qui fait que l'it=E9rateur se castait en bool (ce
qui est ballot).
Un it=E9rateur qui se convertit implicitement en bool me semble
assez louche aussi.
Fondamentalement, un it=E9rateur supporte trois op=E9rations :
acc=E8s =E0 l'=E9lement courant (=E9ventuellement indirectement),
passage =E0 l'=E9l=E9ment suivant, et la d=E9termination si on a fini ou
non. Trois fonctions, donc : element(), next() et isDone().
Puisqu'aucune de ces fonctions ne correspond r=E9element =E0 une
op=E9ration d=E9finie sur les types de bases, tout surcharge
d'op=E9rateur est un peu un abus. (Note bien que =AB abus =BB est
r=E9latif ; l'utilisation de ++ pour next() n'est certainement
pas si abusive que l'utilisation de + unaire pour isDone() --
que j'ai r=E9element vu conseill=E9. Tout est r=E9latif.)
Finalement j'utilises std::difference. Mais c'est surprenant
quand on a l'habitude d'utiliser l'arithm=E9tique des pointeurs,
et que les it=E9rateurs (qui peuvent =EAtre confondus avec des
pointeurs) ne le supporte pas totalement.
Oui. C'est le genre de probl=E8me qui arrive quand on surcharge
abusivement.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34
Est-ce une erreur que de croire que la différence entre deux itérateurs, avec l'opérateur -, fait sens ?
Oui. Un itérateur itère. Logiquement, c'est tout ce qu'il doit supporter. (Dans le cas de la STL, on y a ajouté d'autres choses, et certains itérateurs STL supportent la soustraction. Mais pas tous.)
Je pose la question parce que je suis tombé sur un itérateur, Gtk::TextBuffer::iterator, qui ne fournissait pas cet opérateur, ce qui fait que l'itérateur se castait en bool (ce qui est ballot).
Un itérateur qui se convertit implicitement en bool me semble assez louche aussi.
Fondamentalement, un itérateur supporte trois opérations : accès à l'élement courant (éventuellement indirectement), passage à l'élément suivant, et la détermination si on a fini ou non. Trois fonctions, donc : element(), next() et isDone(). Puisqu'aucune de ces fonctions ne correspond réelement à une opération définie sur les types de bases, tout surcharge d'opérateur est un peu un abus. (Note bien que « abus » est rélatif ; l'utilisation de ++ pour next() n'est certainement pas si abusive que l'utilisation de + unaire pour isDone() -- que j'ai réelement vu conseillé. Tout est rélatif.)
Finalement j'utilises std::difference. Mais c'est surprenant quand on a l'habitude d'utiliser l'arithmétique des pointeurs, et que les itérateurs (qui peuvent être confondus avec des pointeurs) ne le supporte pas totalement.
Oui. C'est le genre de problème qui arrive quand on surcharge abusivement.
-- James Kanze (GABI Software) email: 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
Mickaël Wolff
Michael DOUBEZ a écrit :
Finalement j'utilises std::difference.
Vous devez parler de std::distance().
Évidemment, mais le fait de devoir utiliser le type iterator::difference_type pour recevoir le retour std::distance couplé au manque de sommeil fait des ravages ;)
Évidemment, mais le fait de devoir utiliser le type
iterator::difference_type pour recevoir le retour std::distance couplé
au manque de sommeil fait des ravages ;)
Évidemment, mais le fait de devoir utiliser le type iterator::difference_type pour recevoir le retour std::distance couplé au manque de sommeil fait des ravages ;)
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de splice.
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
Michael DOUBEZ <michael.doubez@free.fr> writes:
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de
splice.
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
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de splice.
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
Michael DOUBEZ
Jean-Marc Bourguet a écrit :
Michael DOUBEZ writes:
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de splice.
Je suis d'accord mais le cout peut être amorti, par exemple en maintenant une taille de liste et en l'invalidant en cas de splice; le premier appel à size() calcule la taille de la liste en o(n) et mets à jour le membre.
Il est rare d'avoir besoin d'une taille de liste et de splice en même temps (ou même l'un ou l'autre).
-- Michael
Jean-Marc Bourguet a écrit :
Michael DOUBEZ <michael.doubez@free.fr> writes:
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de
splice.
Je suis d'accord mais le cout peut être amorti, par exemple en
maintenant une taille de liste et en l'invalidant en cas de splice; le
premier appel à size() calcule la taille de la liste en o(n) et mets à
jour le membre.
Il est rare d'avoir besoin d'une taille de liste et de splice en même
temps (ou même l'un ou l'autre).
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de splice.
Je suis d'accord mais le cout peut être amorti, par exemple en maintenant une taille de liste et en l'invalidant en cas de splice; le premier appel à size() calcule la taille de la liste en o(n) et mets à jour le membre.
Il est rare d'avoir besoin d'une taille de liste et de splice en même temps (ou même l'un ou l'autre).
-- Michael
Fabien LE LEZ
On 06 Aug 2008 10:19:36 +0200, Jean-Marc Bourguet :
L'argument sur size() est intéressant. Est ce que C++0x garanti std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de splice.
Effectivement.
Apparemment certains implémenteurs ignorent cette contrainte, et obtiennent ainsi un temps constant pour size(). Microsoft par exemple.
On 06 Aug 2008 10:19:36 +0200, Jean-Marc Bourguet <jm@bourguet.org>:
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?
Non. En fait, c'est incompatible avec la contrainte sur la complexite de
splice.
Effectivement.
Apparemment certains implémenteurs ignorent cette contrainte, et
obtiennent ainsi un temps constant pour size(). Microsoft par exemple.
