La mise en Œuvre interne de la STL::MAP en C++

Je voulais savoir , comment est la MAP disponible en C++ , pas MultiMap juste simple Carte , mis en œuvre en interne .

Ce que je pourrais mieux penser, c'est :

Pour Entier Cartographie : A Balanced Binary Search Tree could be used .

Pour Chaîne Cartographie : Compressed Trie or something similar could be used .

Je suis vraiment curieux de savoir , comment est-il vraiment mis en œuvre dans la STL Carte .Est une certaine fonction de hachage emploi ou est-il quelque chose de totalement différent de ce .

pourquoi ne pas tout simplement à la recherche dans le code source?
Où puis-je le trouver ?
Je crois std::map est souvent mise en œuvre à l'aide d'un Rouge-noir tree et std::unordered_map est un table de Hachage.
depuis elle est un modèle, le code source doit être disponible pour le compilateur. Vous le trouverez dans l'en-tête <map> - où c'est, dépend du compilateur et de l'installation.
Vous ne pouvez pas utiliser le hachage pour map, depuis les touches doivent être commandés. Arbres binaires sont communs; en particulier, la GNU et (je pense) MS implémentations utilisent un rouge-l'arbre noir. Le hachage est utilisé pour unordered_map (ou hash_map, comme il était connu dans la préhistoire de la STL).

OriginalL'auteur Spandan | 2013-07-23

  1. 6

    La commandé conteneurs, y compris les std::map sont mis en œuvre par l'équilibre des arbres binaires (généralement RB arbres, mais tout autre équilibrée arbre s'adapter aux exigences).

    Pour ce type de questions, la pièce la plus importante de l'information que vous avez besoin est la complexité des exigences de chacune des opérations dans le conteneur, ce qui est la norme mandats. C'est aussi, le plus important de la réponse, qui est, aussi longtemps que la complexité conditions sont remplies, la mise en œuvre effective n'a pas vraiment d'importance.

    OriginalL'auteur David Rodríguez - dribeas