Quelle est la structure des données à l'intérieur de std:: map en C++?

std::map est un conteneur associatif. La seule exigence de la norme est que le conteneur doit avoir une interface de conteneur associative et le comportement, la mise en œuvre n'est pas définie. Alors que la mise en œuvre répond aux exigences de complexité et d'interface, est une mise en œuvre valide.

d'autre part, std::map est généralement mis en œuvre avec un arbre rouge-noir , comme la référence dit.

comme l'a écrit chris, la norme ne définit pas la structure interne de la norme std::map ou std::set. Il définit les exigences d'interface et de complexité pour des opérations comme l'insertion d'un élément. Ces structures de données peuvent bien sûr être mises en œuvre sous forme d'arbres. Par exemple, L'implémentation fournie avec VisualStudio est basée sur un arbre rouge-noir.

Carte utilise en interne d'auto-équilibrage de la BST . Jetez un oeil sur ce lien. arbre de recherche binaire auto-équilibrant

visualisé extérieurement une carte est juste un conteneur associatif: elle se comporte extérieurement comme un" tableau "(supporte une expression a[x] ) où x peut être n'importe quel type (pas nécessairement entier) est "comparable par <" (donc ordonné).

mais:

• parce que x peut être n'importe quelle valeur, il ne peut pas être un tableau simple (sinon il doit supporter n'importe quelle valeur d'index: si vous assignez un[1] et un[100] vous avez besoin aussi le 2..99 éléments dans le moyen)
• parce qu'il doit être rapide dans insert et trouver à n'importe quelle position, il ne peut pas être une structure "linéaire" (sinon les éléments doivent être décalés, et la recherche doit être séquentielle, et les exigences sont "moins que le temps de recherche proportionnel".

l'implémentation la plus courante utilise en interne un arbre d'auto-équilibrage (chaque noeud est une paire clé/valeur, et sont liés àgheter de sorte que le côté gauche a des touches plus basses, et le côté droit a higer touches, de sorte que seraching est relancée pour une recherche binaire), un multi-skip-list (plus rapide que l'arbre dans la récupération, le ralentissement de l'insert) ou une base de hachage table (où chaque valeur de x est relancée à un indice d'un tableau)

debug Step into g++ 6.4 stdlibc++ source

saviez-vous que sur Ubuntu 16.04 par défaut g++-6 paquet ou un GCC 6.4 construire à partir de la source vous pouvez entrer dans la bibliothèque C++ sans autre configuration?

en faisant cela nous concluons facilement qu'un arbre rouge-noir utilisé.

cela a du sens, puisque std::map peut être traversé dans l'ordre clé, ce qui ne serait pas efficace si une carte de hachage était utilisée.

a.cpp:

#include <cassert>
#include <map>

int main() {
    std::map<int, int> m;
    m.emplace(1, -1);
    m.emplace(2, -2);
    assert(m[1] == -1);
    assert(m[2] == -2);
}

compiler et déboguer:

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex 'start' -q --args a.out

Maintenant, si vous entrez dans s.emplace(1, -1) vous atteignez immédiatement /usr/include/c++/6/bits/stl_map.h :

556       template<typename... _Args>
557     std::pair<iterator, bool>
558     emplace(_Args&&... __args)
559     { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }

qui passe clairement juste avant à _M_t._M_emplace_unique .

donc nous ouvrons le fichier source dans vim et trouvons la définition de _M_t :

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
            key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;

So _M_t est du type _Rep_type et _Rep_type est un _Rb_tree .

OK, maintenant c'est assez de preuves pour moi. Si vous ne croyez pas que _Rb_tree est un arbre noir-rouge, aller un peu plus loin et lire l'algorithme

unordered_map utilise une table de hachage

même procédure, mais remplacer map par unordered_map sur le code.

cela a du sens, puisque std::unordered_map ne peut pas être traversé dans l'ordre, de sorte que la bibliothèque standard a choisi Hachette carte au lieu de l'arbre rouge-noir, puisque Hachette carte a une meilleure amortie insert time complexité.

entrer dans emplace conduit à /usr/include/c++/6/bits/unordered_map.h :

377       template<typename... _Args>
378     std::pair<iterator, bool>
379     emplace(_Args&&... __args)
380     { return _M_h.emplace(std::forward<_Args>(__args)...); }

donc nous ouvrons le fichier source dans vim et cherchons la définition de _M_h :

      typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;

donc c'est une table de hachage.

analogue pour std::set : Quelle est la structure de données sous-jacente d'un ensemble STL en C++?

je dirais que si vous pensez à une carte comme une paire, vous ne pouvez pas vous tromper. Map peut être implémenté comme un arbre ou une carte de hachage, mais la façon dont il est implémenté n'est pas aussi importante puisque vous pouvez être sûr que toute implémentation est STL est une implémentation efficace.