Accueil > Forum > > > > remplir une map
 remplir une map
samedi 13 août 2005 à 13:36:57 |
remplir une map
vecchio56
|
Bonjour a tous
Je dois remplir une map au debut de mon programme et je voudrais le faire le plus rapidement possible. Je pense que si je le fais de manière anarchique (sans faire attention à l'ordre d'insertion), mon arbre va devoir être rééquilibré plein de fois.
Est-ce qu'il y a une méthode pour créer mon arbre le plus rapidement possible? (j'ai pensé a prendre d'abord l'élément du milieu, puis faire la même chose à gauche et a droite, en travaillant avec un tableau auxiliaire trié selon la clé) |
|
samedi 13 août 2005 à 17:29:18 |
Re : remplir une map
steve_clamage
|
Essayes le constructeur qui prend une séquence en paramètre,
l'insertion des elements est peut etre optimisée (rien vu dans la doc).
|
|
samedi 13 août 2005 à 18:50:54 |
Re : remplir une map
vecchio56
|
J'ai fait des tests, l'insertion est plus rapide quand j'insère les éléments dans l'ordre que quand ils sont mélangés (pourtant il me semblait que c'était le pire des cas...)
|
|
samedi 13 août 2005 à 19:20:31 |
Re : remplir une map
steve_clamage
|
La construction d'un map ca revient à un tri par insertion, si tu lui
passes à chaque insert une cle plus grande (si deja trier) tu gagne du
temps (la recherche est instantanée), c'est probablement ca.
Avec le constructeur map(begin, end) c'est plus rapide ? (quelque soit l'ordre)
|
|
samedi 13 août 2005 à 20:55:13 |
Re : remplir une map
vecchio56
|
Si j'insère de manière triée c'est plus rapide mais l'arbre devient déséquilibré, un peu comme moi :)
J'ai pas trop compris ton histoire de constructeur, tu peux m'expliquer?
|
|
samedi 13 août 2005 à 20:58:14 |
Re : remplir une map
vecchio56
|
Par exemple, disons que je veux faire ceci:
map m;
m["a"] = 1;
m["b"] = 2;
m["c"] = 3;
m["d"] = 4;
m["e"] = 5;
m["f"] = 6;
Tu as une autre solution pour fabriquer cet arbre?
|
|
samedi 13 août 2005 à 21:56:26 |
Re : remplir une map
steve_clamage
|
Oui, je parlais du constructeur qui construit la map à partir d'une sequence (de pair, dans ton cas pair<string, int>).
#include <utility> // pair
#include <string>
#include <map>
int main()
{
using namespace std;
typedef pair<string, int> si_pair;
typedef map<string, int> si_map;
const si_pair v[] =
{
si_pair("a", 1),
si_pair("b", 2),
si_pair("c", 3),
si_pair("d", 4),
si_pair("e", 5),
si_pair("f", 6)
};
si_map m(v, v + sizeof v / sizeof v[0]);
}
A toi de voir si c'est plus rapide comme ca et si de cette facon l'ordre à une importance.
|
|
dimanche 14 août 2005 à 09:25:38 |
Re : remplir une map
xterminhate
|
Tu as regardé le code de la STL ?... (bon courage)
Cordialement,
Xterminhate.
|
|
dimanche 14 août 2005 à 10:00:09 |
Re : remplir une map
vecchio56
|
steve_clamage, ta méthode semble équivalente
xterminhate j'ai essayé de regardé, ca m'a fait mal au yeux
J'ai fini par tomber sur _Tree::insert(const value_type& _Val) mais ce qui me fait peux c'est que j'ai l'impression qu'il insère la clé (je comprends à peu près le code), mais on ne dirait pas qu'il regarde si l'arbre est équilibré ou non. Vous avez des infos la dessus? Est-ce qu'il est possible qu'un arbre binaire deviennent complètement pourri (un arbre en peigne par ex)?
|
|
dimanche 14 août 2005 à 10:56:21 |
Re : remplir une map
steve_clamage
|
Réponse acceptée !
Il vaut mieux eviter de ce fier à une seul implementation, le
standard spécifie juste l'interface et les complexités des différentes
opérations donc il vaut mieux tenir compte uniquement de ca et ne pas
regarder le code dans cette optique.
Le standard dit à propos de la construction (à partir d'une séquence de
N) que la complexité est linéaire en N si les élement sont deja trié
sinon N log (N).
Il est aussi dit que map (et tout les autres conteneurs associatifs)
sont implémentés avec un "arbre rouge-noir" qui s'auto équilibre (comme
tu le disais) et rend l'insertion d'un élément plus complexe.
L'article sur wikipedia anglophone, l'insertion y est expliquée.
http://en.wikipedia.org/wiki/Red-black_tree
|
|
Cette discussion est classée dans : arbre, possible, remplir, map, rapidement
 Répondre à ce message
 Sujets en rapport avec ce message
arbre binaire [ par moltese ]
Salut, je cherche à savoir si il est possible de créer un arbre binaire par itération? Et si oui est-il possible d'en avoir le code? Merci
comment inclure un conteneur dans une classe [ par kharrat ]
Salut,Je cherche désespérément à créer une classe qui a un conteneur map pour faire un carnet d'adresse (je m'amuse comme je peux...) en C++.Le compil
juste une question [ par lespleiades ]
salut tt le monde^^, bon en fait j'ai une question qui me trotte dans la tete depuis plusieurs jours (je ne connais pas le C++ et je n'ai aucuns proje
cpp template et map [ par sebome ]
Bonjour à tous.Je me suis lancé a faire un petit programme pour apprendre a me servir des map.J'ai essayé aussi de faire des fonctions template pour a
Upload fichier via HTTP [ par Taron31 ]
Bonjour, je souhaiterais connaitre un moyen simple et efficace (si possible) d'uploader un fichier via HTTP, sur des sites du genre upoad.free.fr ou a
dev-C++ définir une command [ par snpier wolf ]
Bonjour à tous voila je voulais savoir si il est possible de définire a l'ade de #define une command de C++ cette a dir par exemple if#define si if.s
remplir un LDAP via un fichier texte [ par Kaazar ]
Bonjour, je dois développer un petit outil permettant de populer (remplir) un annuaire LDAP à l'aide d'un fichier texte. Je vois comment lire ce fichi
sauvegarder une map sur fichier borland c++ [ par treets ]
Bonjour à tous,je suis en train de développer une application windows de gestion d'accès pour un ensemble de batiments.J'ai une classe PERSONNEL et un
STL map et plusieurs types de valeurs ? [ par RV2931 ]
Bonjour à tous,J'ai découvert récemment les STL C++ car je souhaite retrouver un outils permettant de retrouver la puissance et la flexibilité des tab
décrire XML sous forme de graphe [ par convexe ]
Bonjour, Je suis débutant en base de données et j'aurais besoin d'une classe C++ qui permetrait de décrire les fichiers xml sous la forme de graphe ,
 Livres en rapport
|
Derniers Blogs
 POUR RAPPEL ! LES SPéCIFICATIONS DES PROTOCOLES OFFICE ET SHAREPOINT SONT DISPONIBLES SUR MSDNPOUR RAPPEL ! LES SPéCIFICATIONS DES PROTOCOLES OFFICE ET SHAREPOINT SONT DISPONIBLES SUR MSDN par neodante
Quelle est le point commun entre : Microsoft il y a 10 ans et Apple aujourd'hui ? Réponse: avoir une politique de protocoles propriétaires et fermés :) Car pour rappel (si si je vous assure c'est important de le rappeler), la majorité des spécifications e...
Cliquez pour lire la suite de l'article par neodante JOYEUX ANNIVERSAIRE NIXJOYEUX ANNIVERSAIRE NIX par ebartsoft
Souhaitons un bon et joyeux anniversaire à notre hôte à tous, Nix.
Je ne le répéterais jamais assez mais sans lui rien ne serait possible. Il défit en permanence les lois de la gravité et comme il le dit si bien, si tu lui fais confiance ça devra...
Cliquez pour lire la suite de l'article par ebartsoft IMAGINE CUP 2012, MAKE A SIGN EN FINALEIMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg
Voilà qui est fait, la nouvelle est officielle ! L'équipe belge "Make a Sign" va au pays des kangourous défendre son projet dans la catégorie Software Design. http://www.imaginecup.com/CompetitionsContent/Competition/WorldwideFinalists.aspx V...
Cliquez pour lire la suite de l'article par junarnoalg KINECT 1.5 IS OUT !KINECT 1.5 IS OUT ! par Vko
La version 1.5 du Kinect For Microsoft vient tout juste de sortir ! Plein de nouveautés: Tracking de squelette en Near Mode Détection en position assise Détection faciale avec un SDK dédié Documentation et des guideline (enfin) Un out...
Cliquez pour lire la suite de l'article par Vko LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc
Mise à jour des Web API du 14 Mai
Réservez dès maintenant votre journée du 20 juin pour le Windows Azure Dev Camp 2012 à Paris
Mise à jour de Team Foundation Service
MechCommander 2 sur Windows 8
Entity Framework 5 Release Candidate e...
Cliquez pour lire la suite de l'article par richardc
Forum
 MATLAB PROGRAMME MATLAB PROGRAMME par wahab1087
Cliquez pour lire la suite par wahab1087
Logiciels
 sDEVIS-FACTURES vlPRO (8.1.0.3)SDEVIS-FACTURES VLPRO (8.1.0.3)sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa... Cliquez pour télécharger sDEVIS-FACTURES vlPRO 974 Application Server (12.2.4.6)974 APPLICATION SERVER (12.2.4.6)Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc... Cliquez pour télécharger 974 Application Server vPicture (1.4.2.1)VPICTURE (1.4.2.1)Avec vPicture, hébergez vos images facilement et rapidement.
vPicture est un utilitaire simple, ... Cliquez pour télécharger vPicture Easy-Planning (2.2.1.6)EASY-PLANNING (2.2.1.6)Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au... Cliquez pour télécharger Easy-Planning COM-BACKUP (2.0)COM-BACKUP (2.0)
COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...
Cliquez pour télécharger COM-BACKUP
|