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
On Wed, 06 Aug 2008 10:35:21 +0200, Michael DOUBEZ :
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;
Oui. Tu peux même encapsuler ça dans une classe à toi. Cf aussi http://objectmix.com/c/243079-solution-fast-std-list-size-fast-std-list-splice.html
Mais le gars qui a besoin de contraintes fortes sur certaines parties du code, ne peut pas plus appeler list<>::size(), parce qu'il ne saura pas si la taille a déjà été calculée ou pas.
en o(n)
Attention aux notations ! Une fonction f est dite en o(n) si f(n)/n tend vers 0 quand n tend vers l'infini. C'est différent de O(n).
On Wed, 06 Aug 2008 10:35:21 +0200, Michael DOUBEZ
<michael.doubez@free.fr>:
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;
Oui. Tu peux même encapsuler ça dans une classe à toi. Cf aussi
http://objectmix.com/c/243079-solution-fast-std-list-size-fast-std-list-splice.html
Mais le gars qui a besoin de contraintes fortes sur certaines parties
du code, ne peut pas plus appeler list<>::size(), parce qu'il ne saura
pas si la taille a déjà été calculée ou pas.
en o(n)
Attention aux notations !
Une fonction f est dite en o(n) si f(n)/n tend vers 0 quand n tend
vers l'infini. C'est différent de O(n).
On Wed, 06 Aug 2008 10:35:21 +0200, Michael DOUBEZ :
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;
Oui. Tu peux même encapsuler ça dans une classe à toi. Cf aussi http://objectmix.com/c/243079-solution-fast-std-list-size-fast-std-list-splice.html
Mais le gars qui a besoin de contraintes fortes sur certaines parties du code, ne peut pas plus appeler list<>::size(), parce qu'il ne saura pas si la taille a déjà été calculée ou pas.
en o(n)
Attention aux notations ! Une fonction f est dite en o(n) si f(n)/n tend vers 0 quand n tend vers l'infini. C'est différent de O(n).
Michael DOUBEZ
Fabien LE LEZ a écrit :
On Wed, 06 Aug 2008 10:35:21 +0200, Michael DOUBEZ :
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;
Oui. Tu peux même encapsuler ça dans une classe à toi. Cf aussi http://objectmix.com/c/243079-solution-fast-std-list-size-fast-std-list-splice.html
OK. D'où ma question d'origine sur C++0X.
Vu les réponses, je suppose que ce sera comme avant ou alors que je vais devoir aller chercher confirmation dans le brouillon (toujours N2691?).
Mais le gars qui a besoin de contraintes fortes sur certaines parties du code, ne peut pas plus appeler list<>::size(), parce qu'il ne saura pas si la taille a déjà été calculée ou pas.
A l'heure actuelle, il ne peut déjà pas l'appeler (de façon portable) puisque list::size() peut déjà être O(n).
Comme je l'ai écrit ce serait bizarre d'avoir à la fois des splices et une contrainte de calcul de calcul de longueur en O(1): * soit list est considéré comme un conteneur au même titre que vector ou deque mais il est sorti gagnant pour la cas considéré, auquel cas size() en O(1) se justifie * soit c'est la capacité de décomposition rapide préservant les itérateurs qui est demandée et donc splice est utilisé activement mais dans ce cas la taille est rarement un élément déterminant (et AMA ça ne gène pas si elle est en O(n)).
Le seul point négatif est le cout de maintenir une taille de liste alors qu'il est peut probable que la taille soit demandée.
Enfin, ce que je trouve aussi intéressant est l'argument de ne pas fournir de méthode size() si celui ci n'est pas en O(1). De façon générale, je préfère cette méthode à avoir à lire la doc; et ça simplifie les concepts: requires has_method_size<T> plutôt que de spécialiser sur list.
-- Michael
Fabien LE LEZ a écrit :
On Wed, 06 Aug 2008 10:35:21 +0200, Michael DOUBEZ
<michael.doubez@free.fr>:
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;
Oui. Tu peux même encapsuler ça dans une classe à toi. Cf aussi
http://objectmix.com/c/243079-solution-fast-std-list-size-fast-std-list-splice.html
OK. D'où ma question d'origine sur C++0X.
Vu les réponses, je suppose que ce sera comme avant ou alors que je vais
devoir aller chercher confirmation dans le brouillon (toujours N2691?).
Mais le gars qui a besoin de contraintes fortes sur certaines parties
du code, ne peut pas plus appeler list<>::size(), parce qu'il ne saura
pas si la taille a déjà été calculée ou pas.
A l'heure actuelle, il ne peut déjà pas l'appeler (de façon portable)
puisque list::size() peut déjà être O(n).
Comme je l'ai écrit ce serait bizarre d'avoir à la fois des splices et
une contrainte de calcul de calcul de longueur en O(1):
* soit list est considéré comme un conteneur au même titre que vector
ou deque mais il est sorti gagnant pour la cas considéré, auquel cas
size() en O(1) se justifie
* soit c'est la capacité de décomposition rapide préservant les
itérateurs qui est demandée et donc splice est utilisé activement mais
dans ce cas la taille est rarement un élément déterminant (et AMA ça ne
gène pas si elle est en O(n)).
Le seul point négatif est le cout de maintenir une taille de liste alors
qu'il est peut probable que la taille soit demandée.
Enfin, ce que je trouve aussi intéressant est l'argument de ne pas
fournir de méthode size() si celui ci n'est pas en O(1). De façon
générale, je préfère cette méthode à avoir à lire la doc; et ça
simplifie les concepts: requires has_method_size<T> plutôt que de
spécialiser sur list.
On Wed, 06 Aug 2008 10:35:21 +0200, Michael DOUBEZ :
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;
Oui. Tu peux même encapsuler ça dans une classe à toi. Cf aussi http://objectmix.com/c/243079-solution-fast-std-list-size-fast-std-list-splice.html
OK. D'où ma question d'origine sur C++0X.
Vu les réponses, je suppose que ce sera comme avant ou alors que je vais devoir aller chercher confirmation dans le brouillon (toujours N2691?).
Mais le gars qui a besoin de contraintes fortes sur certaines parties du code, ne peut pas plus appeler list<>::size(), parce qu'il ne saura pas si la taille a déjà été calculée ou pas.
A l'heure actuelle, il ne peut déjà pas l'appeler (de façon portable) puisque list::size() peut déjà être O(n).
Comme je l'ai écrit ce serait bizarre d'avoir à la fois des splices et une contrainte de calcul de calcul de longueur en O(1): * soit list est considéré comme un conteneur au même titre que vector ou deque mais il est sorti gagnant pour la cas considéré, auquel cas size() en O(1) se justifie * soit c'est la capacité de décomposition rapide préservant les itérateurs qui est demandée et donc splice est utilisé activement mais dans ce cas la taille est rarement un élément déterminant (et AMA ça ne gène pas si elle est en O(n)).
Le seul point négatif est le cout de maintenir une taille de liste alors qu'il est peut probable que la taille soit demandée.
Enfin, ce que je trouve aussi intéressant est l'argument de ne pas fournir de méthode size() si celui ci n'est pas en O(1). De façon générale, je préfère cette méthode à avoir à lire la doc; et ça simplifie les concepts: requires has_method_size<T> plutôt que de spécialiser sur list.
-- Michael
Michael DOUBEZ
Michael DOUBEZ a écrit :
je vais devoir aller chercher confirmation dans le brouillon (toujours N2691?).
Il y a bien toujours l'infamant: Those entries marked “(Note A)” should have constant complexity.
AMHA une note sur list en particulier aurait été la bienvenue.
-- Michael
Michael DOUBEZ a écrit :
je vais devoir aller chercher confirmation dans le brouillon (toujours N2691?).
Il y a bien toujours l'infamant:
Those entries marked “(Note A)” should have constant complexity.
AMHA une note sur list en particulier aurait été la bienvenue.
je vais devoir aller chercher confirmation dans le brouillon (toujours N2691?).
Il y a bien toujours l'infamant: Those entries marked “(Note A)” should have constant complexity.
AMHA une note sur list en particulier aurait été la bienvenue.
-- Michael
Fabien LE LEZ
On Wed, 06 Aug 2008 11:35:40 +0200, Michael DOUBEZ :
* soit list est considéré comme un conteneur au même titre que vector [...] auquel cas size() en O(1) se justifie * soit c'est la capacité de décomposition rapide préservant les itérateurs qui est demandée et donc splice est utilisé activement
Je crois que tu as mis le doigt sur un problème intéressant : ne faudrait-il pas avoir deux list<> différents ?
Manifestement, la rapidité de splice() est considéré comme le plus important dans std::list<> ; or j'utilise principalement ce conteneur comme un vector<> qui n'invalide pas ses itérateurs à tout bout de champ. Pour bien faire, il me faudrait donc un conteneur hybride. Que j'ai déjà, d'ailleurs, en utilisant list<> dans VC++.
On Wed, 06 Aug 2008 11:35:40 +0200, Michael DOUBEZ
<michael.doubez@free.fr>:
* soit list est considéré comme un conteneur au même titre que vector
[...] auquel cas
size() en O(1) se justifie
* soit c'est la capacité de décomposition rapide préservant les
itérateurs qui est demandée et donc splice est utilisé activement
Je crois que tu as mis le doigt sur un problème intéressant : ne
faudrait-il pas avoir deux list<> différents ?
Manifestement, la rapidité de splice() est considéré comme le plus
important dans std::list<> ; or j'utilise principalement ce conteneur
comme un vector<> qui n'invalide pas ses itérateurs à tout bout de
champ. Pour bien faire, il me faudrait donc un conteneur hybride. Que
j'ai déjà, d'ailleurs, en utilisant list<> dans VC++.
On Wed, 06 Aug 2008 11:35:40 +0200, Michael DOUBEZ :
* soit list est considéré comme un conteneur au même titre que vector [...] auquel cas size() en O(1) se justifie * soit c'est la capacité de décomposition rapide préservant les itérateurs qui est demandée et donc splice est utilisé activement
Je crois que tu as mis le doigt sur un problème intéressant : ne faudrait-il pas avoir deux list<> différents ?
Manifestement, la rapidité de splice() est considéré comme le plus important dans std::list<> ; or j'utilise principalement ce conteneur comme un vector<> qui n'invalide pas ses itérateurs à tout bout de champ. Pour bien faire, il me faudrait donc un conteneur hybride. Que j'ai déjà, d'ailleurs, en utilisant list<> dans VC++.
James Kanze
On Aug 6, 9:58 am, Mickaël Wolff wrote:
James Kanze a écrit :
> Oui. Un itérateur itère.
C'est pourtant évident. Mais à force d'utiliser les outils pour autre chose que ce qu'ils sont, on oublie leur utilité première.
Surtout quand leur « conception » prévoit tous les abus explicitement.
> Un itérateur qui se convertit implicitement en bool me semble > assez louche aussi.
Aujourd'hui, si on fait du C++, on se trouve devant un dilèmme. Si on fait proprement, et implémente un itérateur qui ne supporte que les trois fonctions de base, on ne peut pas s'en servir avec la STL. Du coup, on est amené à l'étendre. (Dans mon cas, ça veut dire fournir une fonction isEqual aussi, et dériver de STLIterator< MyIterator >, qui a tout ce qu'il faut pour mapper l'interface propre en interface STL.)
> Oui. C'est le genre de problème qui arrive quand on > surcharge abusivement.
Ça m'apprendra.
Ce n'est pas toi qui a commencé:-).
-- 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, 9:58 am, Mickaël Wolff <mickael.wo...@laposte.net> wrote:
James Kanze a écrit :
> Oui. Un itérateur itère.
C'est pourtant évident. Mais à force d'utiliser les outils
pour autre chose que ce qu'ils sont, on oublie leur utilité
première.
Surtout quand leur « conception » prévoit tous les abus
explicitement.
> Un itérateur qui se convertit implicitement en bool me semble
> assez louche aussi.
Aujourd'hui, si on fait du C++, on se trouve devant un dilèmme.
Si on fait proprement, et implémente un itérateur qui ne
supporte que les trois fonctions de base, on ne peut pas s'en
servir avec la STL. Du coup, on est amené à l'étendre. (Dans mon
cas, ça veut dire fournir une fonction isEqual aussi, et dériver
de STLIterator< MyIterator >, qui a tout ce qu'il faut pour
mapper l'interface propre en interface STL.)
> Oui. C'est le genre de problème qui arrive quand on
> surcharge abusivement.
Ça m'apprendra.
Ce n'est pas toi qui a commencé:-).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
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
Aujourd'hui, si on fait du C++, on se trouve devant un dilèmme. Si on fait proprement, et implémente un itérateur qui ne supporte que les trois fonctions de base, on ne peut pas s'en servir avec la STL. Du coup, on est amené à l'étendre. (Dans mon cas, ça veut dire fournir une fonction isEqual aussi, et dériver de STLIterator< MyIterator >, qui a tout ce qu'il faut pour mapper l'interface propre en interface STL.)
> Oui. C'est le genre de problème qui arrive quand on > surcharge abusivement.
Ça m'apprendra.
Ce n'est pas toi qui a commencé:-).
-- 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
