Je ne sais pas quel conteneur choisir pour les exigences suivantes :
- Un Element possede plusieurs Attribute
- Un Attribut possede un Name et une Value
- L'ordre des Attribut dans Element est important
- 2 Attributes ayant le meme Name est interdit.
Premiere approche : std::map<Attribute::Name, Attribute>
Pour assurer l'unicité d'un attribut donnée, c'est nickel, mais il sont
forcement rangé dans l'ordre alphabetique.
Deuxieme approche : std::list<Attribute>
Pour l'ordre, c'est nickel, par contre, pour assurer l'unicité d'un
Attribute, il faut se taper a chaque ajout une recherche dans la list
afin de verifier qu'un Attribute ayant le même Name n'existe pas. BOF aussi.
D'ailleurs, je ne sais pas trop si vector<> et list<> ici ne sont pas
équivalent ?
Troisieme approche : Un joyeu combiné des 2 solutions précedentes :
- std::map<Attribute::Name, Attribute>
- std::list< std::map<Attribute::Name, Attribute>::const_iterator >
ou std::list< std::map<Attribute::Name*>
J'ai pas testé, mais je pense que cela fonctionne. Ca me parrait juste
un poil lourd pour ce que je veux faire, non ?
Quatrieme approche : std::map<Attribute::Name, Attribute, ????>
Rajouter un predicat qui n'est pas std::less<std::string> (par defaut),
mais un autre qui ne change pas l'ordre d'insertion dans la map. C'est
possible ca ?
On Mon, 11 Jun 2007 22:50:18 +0200, Michael DOUBEZ :
vector, queue et list suffisent souvent faire une lifo ou une fifo.
Disons que si tu utilises queue, il y a des chances pour que tu utitises deque, puisque c'est la valeur par défaut du deuxième argument template.
Ah tiens. oui ! Pris en flag de ne pas lire la doc. :)
Michael
Michael DOUBEZ
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Michael
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé
que cela soit contraignant pour des grandes listes dans la phase de
test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le
cas (gcc3.x je crois).
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Michael
Michael DOUBEZ
On Mon, 11 Jun 2007 23:04:24 +0200, Michael DOUBEZ :
Pris en flag de ne pas lire la doc. :)
Note que si tu détestes vraiment deque<>, tu peux assez facilement baser une queue sur std::list<>.
J'ai pas de gout personnel en la matière.
J'utilise ce qui marche et si en plus ça m'évite du travail et du debug, c'est encore mieux.
Michael
On Mon, 11 Jun 2007 23:04:24 +0200, Michael DOUBEZ
<michael.doubez@free.fr>:
Pris en flag de ne pas lire la doc. :)
Note que si tu détestes vraiment deque<>, tu peux assez facilement
baser une queue sur std::list<>.
J'ai pas de gout personnel en la matière.
J'utilise ce qui marche et si en plus ça m'évite du travail et du debug,
c'est encore mieux.
On Mon, 11 Jun 2007 23:04:24 +0200, Michael DOUBEZ :
Pris en flag de ne pas lire la doc. :)
Note que si tu détestes vraiment deque<>, tu peux assez facilement baser une queue sur std::list<>.
J'ai pas de gout personnel en la matière.
J'utilise ce qui marche et si en plus ça m'évite du travail et du debug, c'est encore mieux.
Michael
Loïc Joly
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Table 65Container requirements (continued)
expression return type semantics pre/postcondition complexity a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked (Note A) should have constant complexity.
-- Loïc
Un désavantage marginal est la méthode size() en O(n). Ca m'est
arrivé que cela soit contraignant pour des grandes listes dans la
phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le
cas (gcc3.x je crois).
Table 65Container requirements (continued)
expression return type semantics pre/postcondition complexity
a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are
defined in clause
25. Those entries marked (Note A) should have constant complexity.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Table 65Container requirements (continued)
expression return type semantics pre/postcondition complexity a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked (Note A) should have constant complexity.
-- Loïc
Michael DOUBEZ
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Table 65Container requirements (continued)
expression return type semantics pre/postcondition complexity a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked (Note A) should have constant complexity.
Un should n'est pas un must.
Les fonctions succeptibles d'ête O(n) sont entre autre size(), swap()et max_size() pour les container soit: list::swap list::max_size deque::size deque::max_size deque::swap vector::size vector::max_size vector::swap map::size map::max_size map::swap multimap::size multimap::max_size multimap::swap set::size set::max_size set::swap multiset::size multiset::max_size multiset::swap
A noter que empty est garanti en O(1).
Michael
Un désavantage marginal est la méthode size() en O(n). Ca m'est
arrivé que cela soit contraignant pour des grandes listes dans la
phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le
cas (gcc3.x je crois).
Table 65Container requirements (continued)
expression return type semantics pre/postcondition complexity
a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are
defined in clause
25. Those entries marked (Note A) should have constant complexity.
Un should n'est pas un must.
Les fonctions succeptibles d'ête O(n) sont entre autre size(), swap()et
max_size() pour les container soit:
list::swap
list::max_size
deque::size
deque::max_size
deque::swap
vector::size
vector::max_size
vector::swap
map::size
map::max_size
map::swap
multimap::size
multimap::max_size
multimap::swap
set::size
set::max_size
set::swap
multiset::size
multiset::max_size
multiset::swap
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Table 65Container requirements (continued)
expression return type semantics pre/postcondition complexity a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked (Note A) should have constant complexity.
Un should n'est pas un must.
Les fonctions succeptibles d'ête O(n) sont entre autre size(), swap()et max_size() pour les container soit: list::swap list::max_size deque::size deque::max_size deque::swap vector::size vector::max_size vector::swap map::size map::max_size map::swap multimap::size multimap::max_size multimap::swap set::size set::max_size set::swap multiset::size multiset::max_size multiset::swap
A noter que empty est garanti en O(1).
Michael
James Kanze
On Jun 11, 10:50 pm, Michael DOUBEZ wrote:
On Jun 11, 9:20 pm, Fabien LE LEZ wrote:
On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche :
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis un addepte de std::map ou std::list. Faut il que je reserve de l'espa ce pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi std::vector plutot que std::list ?
Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d' un tableau quelque part dans un programme, j'utilise vector<>, sauf si j'ai de bonnes raisons de penser qu'il ne convient pas.
Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.
vector<> est très rapide pour l'accès aléatoire, mais très len t pour l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "tr ès lent" -- il faut un sacré paquet d'éléments pour que ça se voi t.
Ou des éléments dont la copie est très chère.
Mais seulement au moment ou la mémoire de travail de l'objet est étendue. Dans le cas où cela pose problème et où c'est possible, reserve() peut faire passer la pillule.
Je ne comprends pas ta remarque. Si la copie d'un objet est chère, toute opération qui implique une copie devient chère, indépendamment de la mémoire. Et l'insertion autrement qu'à la fin d'un vector impose toujours une copie, indépendamment de la capacité du vector.
list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais permet une insertion rapide d'un élément n'importe où.
Ou que tu as besoins de garder des itérateurs, ou des pointeurs ou des références à des éléments, tout en insérant ou en enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des autres collections, que ses itérateurs ne sont que bi-directionnels, et non aléatoire. Elle a l'avantage, en révanche, qu'ils restent valides tant que l'élément reste dans la collection.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arriv é que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
La norme exige que size() soit O(1), c-à-d d'une complexité constante. (Ça veut dire, dans le cas de list, que la collection le cache, pour ne pas avoir à le récalculer chaque fois. Aussi, je ne sais pas comment ça marche avec splice, qui doit aussi avoir une complexité constante. Je ne vois pas de tête comment faire les deux en complexité constante.)
Quand tu as vraiment beaucoup d'éléments (des centaines de milliers, voire plus), ou que tu fais des insertions et des suppressions en pagaille, elle a aussi le désavantage de fragmenter la mémoire et d'avoir une très mauvaise localisation.
deque<> est un peu au milieu. Il ménage la chèvre et le chou, et e st à préférer si tu as besoin d'insérer (ou supprimer) des élémen ts au début et à la fin. Bizarrement, alors qu'il semble fournir le meil leur des deux mondes, il est assez peu utilisé.
Je n'ai pour ainsi dire jamais eu besoin d'insérer et de supprimer des deux cotés d'un container. vector, queue et list suffisent souvent faire une lifo ou une fifo.
Sauf qu'il n'y a pas ce collection « queue ». « queue », comme « stack » n'est qu'un adaptateur -- un wrapper d'une autre collection (par défaut deque).
D'après ce que j'ai compris, il y a eu une erreur dans les premières versions qui faisaient qu'elle était affreusement lente. Dans la pratique, je m'en sers assez souvent, chaque fois que j'ai besoin d'une queue, en fait. (Pour des piles et des tableaux, je me sers de std::vector.)
Pourquoi pas queue tout simplement ?
Parce que ce n'est qu'un adaptateur, et l'apatation ne me convient pas toujours.
Le seul reproche que je lui trouve c'est de ne pas fournir d'iterator (ou au moins de const_iterator) ce qui serait pratique pour les traces.
C'est précisement le problème. L'adaptation est trop contraignante. Je préfère utiliser deque directement, qui n'est pas plus difficile, et qui permet des opérations en plus, comme itérer. (Comme tu dis, l'itération peut être utile pour des méta-opérations, genre trace ou, si la queue contient des pointeurs à des objets dynamiques, le destructeur.)
-- James Kanze (GABI Software, from CAI) 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 Jun 11, 10:50 pm, Michael DOUBEZ <michael.dou...@free.fr> wrote:
On Jun 11, 9:20 pm, Fabien LE LEZ <grams...@gramster.com> wrote:
On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche <jfou...@voila.fr>:
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis
un addepte de std::map ou std::list. Faut il que je reserve de l'espa ce
pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi
std::vector plutot que std::list ?
Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d' un
tableau quelque part dans un programme, j'utilise vector<>, sauf si
j'ai de bonnes raisons de penser qu'il ne convient pas.
Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.
vector<> est très rapide pour l'accès aléatoire, mais très len t pour
l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "tr ès
lent" -- il faut un sacré paquet d'éléments pour que ça se voi t.
Ou des éléments dont la copie est très chère.
Mais seulement au moment ou la mémoire de travail de l'objet est
étendue. Dans le cas où cela pose problème et où c'est possible,
reserve() peut faire passer la pillule.
Je ne comprends pas ta remarque. Si la copie d'un objet est
chère, toute opération qui implique une copie devient chère,
indépendamment de la mémoire. Et l'insertion autrement qu'à la
fin d'un vector impose toujours une copie, indépendamment de la
capacité du vector.
list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais
permet une insertion rapide d'un élément n'importe où.
Ou que tu as besoins de garder des itérateurs, ou des pointeurs
ou des références à des éléments, tout en insérant ou en
enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des
autres collections, que ses itérateurs ne sont que
bi-directionnels, et non aléatoire. Elle a l'avantage, en
révanche, qu'ils restent valides tant que l'élément reste dans
la collection.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arriv é
que cela soit contraignant pour des grandes listes dans la phase de test
et de validation.
La norme exige que size() soit O(1), c-à-d d'une complexité
constante. (Ça veut dire, dans le cas de list, que la collection
le cache, pour ne pas avoir à le récalculer chaque fois. Aussi,
je ne sais pas comment ça marche avec splice, qui doit aussi
avoir une complexité constante. Je ne vois pas de tête comment
faire les deux en complexité constante.)
Quand tu as vraiment beaucoup d'éléments (des centaines de
milliers, voire plus), ou que tu fais des insertions et des
suppressions en pagaille, elle a aussi le désavantage de
fragmenter la mémoire et d'avoir une très mauvaise localisation.
deque<> est un peu au milieu. Il ménage la chèvre et le chou, et e st à
préférer si tu as besoin d'insérer (ou supprimer) des élémen ts au
début et à la fin. Bizarrement, alors qu'il semble fournir le meil leur
des deux mondes, il est assez peu utilisé.
Je n'ai pour ainsi dire jamais eu besoin d'insérer et de supprimer des
deux cotés d'un container. vector, queue et list suffisent souvent faire
une lifo ou une fifo.
Sauf qu'il n'y a pas ce collection « queue ». « queue »,
comme « stack » n'est qu'un adaptateur -- un wrapper d'une
autre collection (par défaut deque).
D'après ce que j'ai compris, il y a eu une erreur dans les
premières versions qui faisaient qu'elle était affreusement
lente. Dans la pratique, je m'en sers assez souvent, chaque fois
que j'ai besoin d'une queue, en fait. (Pour des piles et des
tableaux, je me sers de std::vector.)
Pourquoi pas queue tout simplement ?
Parce que ce n'est qu'un adaptateur, et l'apatation ne me
convient pas toujours.
Le seul reproche que je lui trouve c'est de ne pas fournir d'iterator
(ou au moins de const_iterator) ce qui serait pratique pour les traces.
C'est précisement le problème. L'adaptation est trop
contraignante. Je préfère utiliser deque directement, qui n'est
pas plus difficile, et qui permet des opérations en plus, comme
itérer. (Comme tu dis, l'itération peut être utile pour des
méta-opérations, genre trace ou, si la queue contient des
pointeurs à des objets dynamiques, le destructeur.)
--
James Kanze (GABI Software, from CAI) 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
On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche :
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis un addepte de std::map ou std::list. Faut il que je reserve de l'espa ce pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi std::vector plutot que std::list ?
Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d' un tableau quelque part dans un programme, j'utilise vector<>, sauf si j'ai de bonnes raisons de penser qu'il ne convient pas.
Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.
vector<> est très rapide pour l'accès aléatoire, mais très len t pour l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "tr ès lent" -- il faut un sacré paquet d'éléments pour que ça se voi t.
Ou des éléments dont la copie est très chère.
Mais seulement au moment ou la mémoire de travail de l'objet est étendue. Dans le cas où cela pose problème et où c'est possible, reserve() peut faire passer la pillule.
Je ne comprends pas ta remarque. Si la copie d'un objet est chère, toute opération qui implique une copie devient chère, indépendamment de la mémoire. Et l'insertion autrement qu'à la fin d'un vector impose toujours une copie, indépendamment de la capacité du vector.
list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais permet une insertion rapide d'un élément n'importe où.
Ou que tu as besoins de garder des itérateurs, ou des pointeurs ou des références à des éléments, tout en insérant ou en enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des autres collections, que ses itérateurs ne sont que bi-directionnels, et non aléatoire. Elle a l'avantage, en révanche, qu'ils restent valides tant que l'élément reste dans la collection.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arriv é que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
La norme exige que size() soit O(1), c-à-d d'une complexité constante. (Ça veut dire, dans le cas de list, que la collection le cache, pour ne pas avoir à le récalculer chaque fois. Aussi, je ne sais pas comment ça marche avec splice, qui doit aussi avoir une complexité constante. Je ne vois pas de tête comment faire les deux en complexité constante.)
Quand tu as vraiment beaucoup d'éléments (des centaines de milliers, voire plus), ou que tu fais des insertions et des suppressions en pagaille, elle a aussi le désavantage de fragmenter la mémoire et d'avoir une très mauvaise localisation.
deque<> est un peu au milieu. Il ménage la chèvre et le chou, et e st à préférer si tu as besoin d'insérer (ou supprimer) des élémen ts au début et à la fin. Bizarrement, alors qu'il semble fournir le meil leur des deux mondes, il est assez peu utilisé.
Je n'ai pour ainsi dire jamais eu besoin d'insérer et de supprimer des deux cotés d'un container. vector, queue et list suffisent souvent faire une lifo ou une fifo.
Sauf qu'il n'y a pas ce collection « queue ». « queue », comme « stack » n'est qu'un adaptateur -- un wrapper d'une autre collection (par défaut deque).
D'après ce que j'ai compris, il y a eu une erreur dans les premières versions qui faisaient qu'elle était affreusement lente. Dans la pratique, je m'en sers assez souvent, chaque fois que j'ai besoin d'une queue, en fait. (Pour des piles et des tableaux, je me sers de std::vector.)
Pourquoi pas queue tout simplement ?
Parce que ce n'est qu'un adaptateur, et l'apatation ne me convient pas toujours.
Le seul reproche que je lui trouve c'est de ne pas fournir d'iterator (ou au moins de const_iterator) ce qui serait pratique pour les traces.
C'est précisement le problème. L'adaptation est trop contraignante. Je préfère utiliser deque directement, qui n'est pas plus difficile, et qui permet des opérations en plus, comme itérer. (Comme tu dis, l'itération peut être utile pour des méta-opérations, genre trace ou, si la queue contient des pointeurs à des objets dynamiques, le destructeur.)
-- James Kanze (GABI Software, from CAI) 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
James Kanze
On Jun 12, 8:56 am, Michael DOUBEZ wrote:
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Table 65: Container requirements (continued)
expression return type semantics pre/postcondition complexity a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked ??(Note A)?? should have constant complexity.
Un should n'est pas un must.
Il est dans la norme. (Encore que le mot "standard" est "shall".)
Je sais qu'il y a eu des discussions là-dessus, parce que splice() doit aussi être O(1), et guarantir les deux n'est pas réelement possible : si tu caches le nombre d'éléments, il faut le récalculer lors d'un splice, et sinon, size() n'est pas O(1).
Il y a aussi la question de l'unité de mesure. Quand on parle de la complexité d'un constructeur, par exemple, elle se mesure en nombre de constructions. (La norme ne parle jamais de temps d'exécution.) Est-ce que ce qu'elle essaie de dire ici, c'est que size() appelle toujours le constructeur un nombre constante de fois:-) ?
Les fonctions succeptibles d'ête O(n) sont entre autre size(), swap()et max_size()
Aucunement. La norme est très formelle là-dessus : ces trois fonctions doivent avoir une complexité constante. (Dans le cas de swap(), il y a énormement de code qui en dépend.)
-- James Kanze (GABI Software, from CAI) 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 Jun 12, 8:56 am, Michael DOUBEZ <michael.dou...@free.fr> wrote:
Un désavantage marginal est la méthode size() en O(n). Ca m'est
arrivé que cela soit contraignant pour des grandes listes dans la
phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le
cas (gcc3.x je crois).
Table 65: Container requirements (continued)
expression return type semantics pre/postcondition complexity
a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are
defined in clause
25. Those entries marked ??(Note A)?? should have constant complexity.
Un should n'est pas un must.
Il est dans la norme. (Encore que le mot "standard" est
"shall".)
Je sais qu'il y a eu des discussions là-dessus, parce que
splice() doit aussi être O(1), et guarantir les deux n'est pas
réelement possible : si tu caches le nombre d'éléments, il faut
le récalculer lors d'un splice, et sinon, size() n'est pas O(1).
Il y a aussi la question de l'unité de mesure. Quand on parle de
la complexité d'un constructeur, par exemple, elle se mesure en
nombre de constructions. (La norme ne parle jamais de temps
d'exécution.) Est-ce que ce qu'elle essaie de dire ici, c'est
que size() appelle toujours le constructeur un nombre constante
de fois:-) ?
Les fonctions succeptibles d'ête O(n) sont entre autre size(), swap()et
max_size()
Aucunement. La norme est très formelle là-dessus : ces trois
fonctions doivent avoir une complexité constante. (Dans le cas
de swap(), il y a énormement de code qui en dépend.)
--
James Kanze (GABI Software, from CAI) 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
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
Elle est sensée être O(1)...
Pas pour les list. Le standard ne garanti que O(n) et c'était bien le cas (gcc3.x je crois).
Table 65: Container requirements (continued)
expression return type semantics pre/postcondition complexity a.size() size type a.end()- a.begin() (Note A)
Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked ??(Note A)?? should have constant complexity.
Un should n'est pas un must.
Il est dans la norme. (Encore que le mot "standard" est "shall".)
Je sais qu'il y a eu des discussions là-dessus, parce que splice() doit aussi être O(1), et guarantir les deux n'est pas réelement possible : si tu caches le nombre d'éléments, il faut le récalculer lors d'un splice, et sinon, size() n'est pas O(1).
Il y a aussi la question de l'unité de mesure. Quand on parle de la complexité d'un constructeur, par exemple, elle se mesure en nombre de constructions. (La norme ne parle jamais de temps d'exécution.) Est-ce que ce qu'elle essaie de dire ici, c'est que size() appelle toujours le constructeur un nombre constante de fois:-) ?
Les fonctions succeptibles d'ête O(n) sont entre autre size(), swap()et max_size()
Aucunement. La norme est très formelle là-dessus : ces trois fonctions doivent avoir une complexité constante. (Dans le cas de swap(), il y a énormement de code qui en dépend.)
-- James Kanze (GABI Software, from CAI) 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
Michael DOUBEZ
On Jun 11, 10:50 pm, Michael DOUBEZ wrote:
On Jun 11, 9:20 pm, Fabien LE LEZ wrote:
On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche :
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis un addepte de std::map ou std::list. Faut il que je reserve de l'espace pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi std::vector plutot que std::list ?
Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d'un tableau quelque part dans un programme, j'utilise vector<>, sauf si j'ai de bonnes raisons de penser qu'il ne convient pas.
Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.
vector<> est très rapide pour l'accès aléatoire, mais très lent pour l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "très lent" -- il faut un sacré paquet d'éléments pour que ça se voit.
Ou des éléments dont la copie est très chère.
Mais seulement au moment ou la mémoire de travail de l'objet est étendue. Dans le cas où cela pose problème et où c'est possible, reserve() peut faire passer la pillule.
Je ne comprends pas ta remarque. Si la copie d'un objet est chère, toute opération qui implique une copie devient chère, indépendamment de la mémoire. Et l'insertion autrement qu'à la fin d'un vector impose toujours une copie, indépendamment de la capacité du vector.
Je croyait qu'il était ici question de la reallocation de la memoire dans vector dans le cas d'un nombre élevé d'éléments et/ou de copie onéreuse. J'ai mal lu le "ailleurs qu'à la fin".
list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais permet une insertion rapide d'un élément n'importe où.
Ou que tu as besoins de garder des itérateurs, ou des pointeurs ou des références à des éléments, tout en insérant ou en enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des autres collections, que ses itérateurs ne sont que bi-directionnels, et non aléatoire. Elle a l'avantage, en révanche, qu'ils restent valides tant que l'élément reste dans la collection.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
La norme exige que size() soit O(1), c-à-d d'une complexité constante. (Ça veut dire, dans le cas de list, que la collection le cache, pour ne pas avoir à le récalculer chaque fois. Aussi, je ne sais pas comment ça marche avec splice, qui doit aussi avoir une complexité constante. Je ne vois pas de tête comment faire les deux en complexité constante.)
Oui. Donc la complexité de list::size() est en général "sacrifié" car moins utile dans le cas d'une liste.
[snip]
Michael
On Jun 11, 10:50 pm, Michael DOUBEZ <michael.dou...@free.fr> wrote:
On Jun 11, 9:20 pm, Fabien LE LEZ <grams...@gramster.com> wrote:
On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche <jfou...@voila.fr>:
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis
un addepte de std::map ou std::list. Faut il que je reserve de l'espace
pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi
std::vector plutot que std::list ?
Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d'un
tableau quelque part dans un programme, j'utilise vector<>, sauf si
j'ai de bonnes raisons de penser qu'il ne convient pas.
Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.
vector<> est très rapide pour l'accès aléatoire, mais très lent pour
l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "très
lent" -- il faut un sacré paquet d'éléments pour que ça se voit.
Ou des éléments dont la copie est très chère.
Mais seulement au moment ou la mémoire de travail de l'objet est
étendue. Dans le cas où cela pose problème et où c'est possible,
reserve() peut faire passer la pillule.
Je ne comprends pas ta remarque. Si la copie d'un objet est
chère, toute opération qui implique une copie devient chère,
indépendamment de la mémoire. Et l'insertion autrement qu'à la
fin d'un vector impose toujours une copie, indépendamment de la
capacité du vector.
Je croyait qu'il était ici question de la reallocation de la memoire
dans vector dans le cas d'un nombre élevé d'éléments et/ou de copie
onéreuse. J'ai mal lu le "ailleurs qu'à la fin".
list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais
permet une insertion rapide d'un élément n'importe où.
Ou que tu as besoins de garder des itérateurs, ou des pointeurs
ou des références à des éléments, tout en insérant ou en
enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des
autres collections, que ses itérateurs ne sont que
bi-directionnels, et non aléatoire. Elle a l'avantage, en
révanche, qu'ils restent valides tant que l'élément reste dans
la collection.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé
que cela soit contraignant pour des grandes listes dans la phase de test
et de validation.
La norme exige que size() soit O(1), c-à-d d'une complexité
constante. (Ça veut dire, dans le cas de list, que la collection
le cache, pour ne pas avoir à le récalculer chaque fois. Aussi,
je ne sais pas comment ça marche avec splice, qui doit aussi
avoir une complexité constante. Je ne vois pas de tête comment
faire les deux en complexité constante.)
Oui. Donc la complexité de list::size() est en général "sacrifié" car
moins utile dans le cas d'une liste.
On Mon, 11 Jun 2007 19:56:08 +0200, jeremie fouche :
Pour info, je ne crois pas avoir déjà utilisé std::vector, car je suis un addepte de std::map ou std::list. Faut il que je reserve de l'espace pour ce conteneur ? Est il aussi souple que std::list ? Pourquoi std::vector plutot que std::list ?
Disons que vector<> est le conteneur "par défaut". Si j'ai besoin d'un tableau quelque part dans un programme, j'utilise vector<>, sauf si j'ai de bonnes raisons de penser qu'il ne convient pas.
Dans l'ensemble, vector<>, deque<> et list<> sont interchangeables.
vector<> est très rapide pour l'accès aléatoire, mais très lent pour l'insertion ailleurs qu'à la fin. Il faut toutefois relativiser "très lent" -- il faut un sacré paquet d'éléments pour que ça se voit.
Ou des éléments dont la copie est très chère.
Mais seulement au moment ou la mémoire de travail de l'objet est étendue. Dans le cas où cela pose problème et où c'est possible, reserve() peut faire passer la pillule.
Je ne comprends pas ta remarque. Si la copie d'un objet est chère, toute opération qui implique une copie devient chère, indépendamment de la mémoire. Et l'insertion autrement qu'à la fin d'un vector impose toujours une copie, indépendamment de la capacité du vector.
Je croyait qu'il était ici question de la reallocation de la memoire dans vector dans le cas d'un nombre élevé d'éléments et/ou de copie onéreuse. J'ai mal lu le "ailleurs qu'à la fin".
list<>, c'est le contraire : il ne fait pas d'accès aléatoire, mais permet une insertion rapide d'un élément n'importe où.
Ou que tu as besoins de garder des itérateurs, ou des pointeurs ou des références à des éléments, tout en insérant ou en enlevant d'autres éléments. Elle a la désavantage, vis-à-vis des autres collections, que ses itérateurs ne sont que bi-directionnels, et non aléatoire. Elle a l'avantage, en révanche, qu'ils restent valides tant que l'élément reste dans la collection.
Un désavantage marginal est la méthode size() en O(n). Ca m'est arrivé que cela soit contraignant pour des grandes listes dans la phase de test et de validation.
La norme exige que size() soit O(1), c-à-d d'une complexité constante. (Ça veut dire, dans le cas de list, que la collection le cache, pour ne pas avoir à le récalculer chaque fois. Aussi, je ne sais pas comment ça marche avec splice, qui doit aussi avoir une complexité constante. Je ne vois pas de tête comment faire les deux en complexité constante.)
Oui. Donc la complexité de list::size() est en général "sacrifié" car moins utile dans le cas d'une liste.
