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

Étape de débogage dans 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 aucune configuration supplémentaire?

En faisant cela, nous pouvons facilement conclure qu'un Rouge-noir arbre utilisé dans cette mise en œuvre.

Ce sens, depuis std::map, contrairement à std::unordered_map, peuvent être parcourus dans l'ordre des clés, ce qui ne serait pas efficace dans le cas d'un hachage de la carte ont été utilisés.

main.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);
}

De la compilation et de débogage:

g++ -g -std=c++11 -O0 -o main.out main.cpp
gdb -ex 'start' -q --args main.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, clairement, juste transmet à _M_t._M_emplace_unique.

Afin de nous ouvrir le fichier source dans vim et de trouver 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;

Donc _M_t est de type _Rep_type et _Rep_type est un _Rb_tree.

OK, maintenant que la preuve est suffisante pour moi. Si vous ne croyez pas que _Rb_tree est Noir-rouge arbre, étape un peu plus loin et de lire l'algorithme

unordered_map utilise une table de hachage

Même procédure, mais de remplacer map avec unordered_map sur le code.

Ce sens, depuis std::unordered_map ne peuvent être parcourus dans l'ordre, donc la norme de la bibliothèque a choisi de hachage de la carte au lieu de Rouge-l'arbre noir, depuis hachage carte a un meilleur amorti, l'heure d'insertion de la 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)...); }

Afin de nous ouvrir le fichier source dans vim et de recherche pour la définition de _M_h:

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

Afin de la table de hachage, il est.

std::set et std::unordered_set

Analogue à std::map vs std::unordered_map: Qu'est-ce que les données sous-jacentes de la structure d'un STL jeu en C++?

Caractéristiques de Performance

Vous pouvez également déduire la structure de données utilisée par le chronométrage.

Depuis std::map est analogue à std::set nous voyons clairement:

• std::map, logarithmique moment de l'insertion

• std::unordered_map, un modèle plus complexe hashmap modèle:

  • sur la non-zoom de la parcelle, nous voyons clairement la sauvegarde de tableau dynamique de doubler sur un énorme off linéaire de l'augmentation des pointes

  • sur le zoom de la parcelle, nous voyons que les temps sont essentiellement constante et en allant vers 250ns, donc beaucoup plus rapide que la std::map, sauf pour les très petites tailles de carte

    Plusieurs bandes sont clairement visibles, et leur inclinaison devient plus petit à chaque fois que le tableau de double.

    Je crois que c'est dû à moyenne linéairement croissante liée liste des promenades à l'intérieur de chaque compartiment. Puis, quand le tableau de double, nous avons plus de poubelles, de sorte que des promenades courtes.

Graphique généré avec:

• code: https://github.com/cirosantilli/cpp-cheat/blob/15066739601a701d5f4d702ec28c6c615cdbb17b/cpp/interactive/bst_vs_heap.cpp
• système: Ubuntu 18.04, GCC 7.3, Intel i7-7820HQ la CPU, de la DDR4 2400 MHz mémoire vive, la Lenovo Thinkpad P51.

Tas vs BST analyse: Tas vs Binaires un Arbre de Recherche (BST)

OriginalL'auteur Ciro Santilli 新疆改造中心996ICU六四事件

Carte utilise en interne d'auto-équilibrage de la BST . Jetez un oeil sur ce lien.auto-équilibrage des arbres binaires

OriginalL'auteur user1706047

Je dirais que si vous pensez à une carte comme une paire, vous ne pouvez pas vous tromper. La carte peut être mis en œuvre comme un arbre ou d'un hachage de la carte, mais la façon dont il est mis en œuvre n'est pas aussi important car vous pouvez être sûr que toute mise en œuvre est TSL est une efficace.

OriginalL'auteur Napalidon