Je cherche un container qui me permette de faire les operations suivantes le
plus rapidement possible :
- Recuperer l'element le plus petit (très fréquent)
- Supprimer un élement (suppression de l'élement le plus petit très
fréquente, suppression d'un element quelconque assez rare)
- Inserer un élement (très fréquent)
- Supprimer tout les élements (très rare).
J'avais au début pensé à une priority_queue, mais on ne peut pas la vider
(?!), et on ne peut pas supprimer un élement quelconque.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Vincent Lascaux
- Supprimer un élement (suppression de l'élement le plus petit très fréquente, suppression d'un element quelconque assez rare)
En fait ca serait plutot
- Suppression de l'element le plus petit (très frequent) - Déplacement d'un élément (sa clé change, il faut le replacer au bon endroit dans le container) (assez rare)
-- Vincent
- Supprimer un élement (suppression de l'élement le plus petit très
fréquente, suppression d'un element quelconque assez rare)
En fait ca serait plutot
- Suppression de l'element le plus petit (très frequent)
- Déplacement d'un élément (sa clé change, il faut le replacer au bon
endroit dans le container) (assez rare)
- Supprimer un élement (suppression de l'élement le plus petit très fréquente, suppression d'un element quelconque assez rare)
En fait ca serait plutot
- Suppression de l'element le plus petit (très frequent) - Déplacement d'un élément (sa clé change, il faut le replacer au bon endroit dans le container) (assez rare)
-- Vincent
Christophe Lephay
Vincent Lascaux wrote:
- Supprimer un élement (suppression de l'élement le plus petit très fréquente, suppression d'un element quelconque assez rare)
En fait ca serait plutot
- Suppression de l'element le plus petit (très frequent) - Déplacement d'un élément (sa clé change, il faut le replacer au bon endroit dans le container) (assez rare)
std::set ou std::map...
Chris
Vincent Lascaux wrote:
- Supprimer un élement (suppression de l'élement le plus petit très
fréquente, suppression d'un element quelconque assez rare)
En fait ca serait plutot
- Suppression de l'element le plus petit (très frequent)
- Déplacement d'un élément (sa clé change, il faut le replacer au bon
endroit dans le container) (assez rare)
- Supprimer un élement (suppression de l'élement le plus petit très fréquente, suppression d'un element quelconque assez rare)
En fait ca serait plutot
- Suppression de l'element le plus petit (très frequent) - Déplacement d'un élément (sa clé change, il faut le replacer au bon endroit dans le container) (assez rare)
std::set ou std::map...
Chris
Jean-Marc Bourguet
"Vincent Lascaux" writes:
Bonjour,
Je cherche un container qui me permette de faire les operations suivantes le plus rapidement possible :
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
- Recuperer l'element le plus petit (très fréquent) - Supprimer un élement (suppression de l'élement le plus petit très fréquente, pop_head
suppression d'un element quelconque assez rare)
supprimer l'element et appel de make_heap (qui est en O(n))
- Inserer un élement (très fréquent) push_heap
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
"Vincent Lascaux" <nospam@nospam.org> writes:
Bonjour,
Je cherche un container qui me permette de faire les operations suivantes le
plus rapidement possible :
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
- Recuperer l'element le plus petit (très fréquent)
- Supprimer un élement (suppression de l'élement le plus petit très
fréquente,
pop_head
suppression d'un element quelconque assez rare)
supprimer l'element et appel de make_heap (qui est en O(n))
- Inserer un élement (très fréquent)
push_heap
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 cherche un container qui me permette de faire les operations suivantes le plus rapidement possible :
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
- Recuperer l'element le plus petit (très fréquent) - Supprimer un élement (suppression de l'élement le plus petit très fréquente, pop_head
suppression d'un element quelconque assez rare)
supprimer l'element et appel de make_heap (qui est en O(n))
- Inserer un élement (très fréquent) push_heap
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
Vincent Lascaux
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
Ca a l'air bien. Sont-ce ces fonctions qui sont encapsulées dans priority_queue ? (simple curiosité)
-- Vincent
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
Ca a l'air bien. Sont-ce ces fonctions qui sont encapsulées dans
priority_queue ? (simple curiosité)
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
Ca a l'air bien. Sont-ce ces fonctions qui sont encapsulées dans priority_queue ? (simple curiosité)
-- Vincent
Jean-Marc Bourguet
"Vincent Lascaux" writes:
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
Ca a l'air bien. Sont-ce ces fonctions qui sont encapsulées dans priority_queue ? (simple curiosité)
Effectivement, si j'ai bonne memoire priority_queue est bien defini en fonction de ces fonctions.
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
"Vincent Lascaux" <nospam@nospam.org> writes:
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
Ca a l'air bien. Sont-ce ces fonctions qui sont encapsulées dans
priority_queue ? (simple curiosité)
Effectivement, si j'ai bonne memoire priority_queue est bien defini en
fonction de ces fonctions.
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
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
Ca a l'air bien. Sont-ce ces fonctions qui sont encapsulées dans priority_queue ? (simple curiosité)
Effectivement, si j'ai bonne memoire priority_queue est bien defini en fonction de ces fonctions.
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
Vincent Lascaux
supprimer l'element et appel de make_heap (qui est en O(n))
Etant donné que le vecteur est organisé d'une certaine facon (et même d'une facon certaine), est ce qu'il n'y a pas mieux à faire qu'une recherche linéaire pour retrouver l'element que je veux supprimer ? et comment faire cette recherche ?
D'autre part, une autre solution proposée était multimap ou multiset (car je risque fort d'avoir plusieurs élements avec la même clé). Qu'est ce qui sera plus rapide entre les ces trois containers (heap, multimap ou multiset) ?
-- Vincent
supprimer l'element et appel de make_heap (qui est en O(n))
Etant donné que le vecteur est organisé d'une certaine facon (et même d'une
facon certaine), est ce qu'il n'y a pas mieux à faire qu'une recherche
linéaire pour retrouver l'element que je veux supprimer ? et comment faire
cette recherche ?
D'autre part, une autre solution proposée était multimap ou multiset (car je
risque fort d'avoir plusieurs élements avec la même clé). Qu'est ce qui sera
plus rapide entre les ces trois containers (heap, multimap ou multiset) ?
supprimer l'element et appel de make_heap (qui est en O(n))
Etant donné que le vecteur est organisé d'une certaine facon (et même d'une facon certaine), est ce qu'il n'y a pas mieux à faire qu'une recherche linéaire pour retrouver l'element que je veux supprimer ? et comment faire cette recherche ?
D'autre part, une autre solution proposée était multimap ou multiset (car je risque fort d'avoir plusieurs élements avec la même clé). Qu'est ce qui sera plus rapide entre les ces trois containers (heap, multimap ou multiset) ?
-- Vincent
Jean-Marc Bourguet
"Vincent Lascaux" writes:
supprimer l'element et appel de make_heap (qui est en O(n))
Etant donné que le vecteur est organisé d'une certaine facon (et même d'une facon certaine), est ce qu'il n'y a pas mieux à faire qu'une recherche linéaire pour retrouver l'element que je veux supprimer ? et comment faire cette recherche ?
Pas a ma connaissance. La structure de heap ne permet que de trouver facilement le plus petit element, c'est tout.
D'autre part, une autre solution proposée était multimap ou multiset (car je risque fort d'avoir plusieurs élements avec la même clé). Qu'est ce qui sera plus rapide entre les ces trois containers (heap, multimap ou multiset) ?
Ca risque de dependre des donnees. Si c'est des objets faciles a copier, le tas sera mieux. Si c'est des objets tres long a copier, un des deux autres sera vraissemblablement plus rapide (puisqu'ils ne les copieront vraissemblablement jamais lors des reorg).
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
"Vincent Lascaux" <nospam@nospam.org> writes:
supprimer l'element et appel de make_heap (qui est en O(n))
Etant donné que le vecteur est organisé d'une certaine facon (et même d'une
facon certaine), est ce qu'il n'y a pas mieux à faire qu'une recherche
linéaire pour retrouver l'element que je veux supprimer ? et comment faire
cette recherche ?
Pas a ma connaissance. La structure de heap ne permet que de trouver
facilement le plus petit element, c'est tout.
D'autre part, une autre solution proposée était multimap ou multiset
(car je risque fort d'avoir plusieurs élements avec la même
clé). Qu'est ce qui sera plus rapide entre les ces trois containers
(heap, multimap ou multiset) ?
Ca risque de dependre des donnees. Si c'est des objets faciles a
copier, le tas sera mieux. Si c'est des objets tres long a copier, un
des deux autres sera vraissemblablement plus rapide (puisqu'ils ne les
copieront vraissemblablement jamais lors des reorg).
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
supprimer l'element et appel de make_heap (qui est en O(n))
Etant donné que le vecteur est organisé d'une certaine facon (et même d'une facon certaine), est ce qu'il n'y a pas mieux à faire qu'une recherche linéaire pour retrouver l'element que je veux supprimer ? et comment faire cette recherche ?
Pas a ma connaissance. La structure de heap ne permet que de trouver facilement le plus petit element, c'est tout.
D'autre part, une autre solution proposée était multimap ou multiset (car je risque fort d'avoir plusieurs élements avec la même clé). Qu'est ce qui sera plus rapide entre les ces trois containers (heap, multimap ou multiset) ?
Ca risque de dependre des donnees. Si c'est des objets faciles a copier, le tas sera mieux. Si c'est des objets tres long a copier, un des deux autres sera vraissemblablement plus rapide (puisqu'ils ne les copieront vraissemblablement jamais lors des reorg).
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
Jean-Marc Bourguet wrote in message news:...
"Vincent Lascaux" writes:
Je cherche un container qui me permette de faire les operations suivantes le plus rapidement possible :
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
- Recuperer l'element le plus petit (très fréquent) - Supprimer un élement (suppression de l'élement le plus petit très fréquente, pop_head
suppression d'un element quelconque assez rare)
supprimer l'element et appel de make_heap (qui est en O(n))
- Inserer un élement (très fréquent) push_heap
Sans savoir la taille, c'est difficile à dire. Moi, j'utiliserais d'office set ou multiset ; l'interface convient le mieux, je crois. Si par la suite, il y a réelement de problèmes de performance (ce que je doute -- les set sont assez efficace pour les opérations qui l'intéresse), il y a toujours le temps de changer.
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
Jean-Marc Bourguet <jm@bourguet.org> wrote in message
news:<pxbsmlm8yoh.fsf@news.bourguet.org>...
"Vincent Lascaux" <nospam@nospam.org> writes:
Je cherche un container qui me permette de faire les operations
suivantes le plus rapidement possible :
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
- Recuperer l'element le plus petit (très fréquent)
- Supprimer un élement (suppression de l'élement le plus petit très
fréquente,
pop_head
suppression d'un element quelconque assez rare)
supprimer l'element et appel de make_heap (qui est en O(n))
- Inserer un élement (très fréquent)
push_heap
Sans savoir la taille, c'est difficile à dire. Moi, j'utiliserais
d'office set ou multiset ; l'interface convient le mieux, je crois. Si
par la suite, il y a réelement de problèmes de performance (ce que je
doute -- les set sont assez efficace pour les opérations qui
l'intéresse), il y a toujours le temps de changer.
--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
Je cherche un container qui me permette de faire les operations suivantes le plus rapidement possible :
J'utiliserais make_heap, push_heap et pop_heap sur un vecteur.
- Recuperer l'element le plus petit (très fréquent) - Supprimer un élement (suppression de l'élement le plus petit très fréquente, pop_head
suppression d'un element quelconque assez rare)
supprimer l'element et appel de make_heap (qui est en O(n))
- Inserer un élement (très fréquent) push_heap
Sans savoir la taille, c'est difficile à dire. Moi, j'utiliserais d'office set ou multiset ; l'interface convient le mieux, je crois. Si par la suite, il y a réelement de problèmes de performance (ce que je doute -- les set sont assez efficace pour les opérations qui l'intéresse), il y a toujours le temps de changer.
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
