L'initialisation d'une std::map lorsque la taille est connue à l'avance

Je voudrais initialiser un std::map. Pour l'instant, je suis en utilisant ::insert mais j'ai l'impression de gaspiller quelques temps de calcul puisque je connais déjà la taille que je veux allouer. Est-il possible d'allouer une taille fixe de la carte et de les remplir à la carte ?

  • Pourquoi ne pas utiliser l'itérateur ou liste d'initialiseur version de l'insert? Connaissez-vous le nombre d'éléments à l'avance, mais pas leurs valeurs?
  • Oui, je sais le nombre, mais pas les paires clés-valeurs.
  • Est map::insert vraiment le goulot d'étranglement dans votre programme?
  • pas possible sans en connaître les clés
  • Une grande question de montrer la vraie nature de std::map. C'est certainement plus qu'une "sorte de vecteur plus de la magie".
InformationsquelleAutor vanna | 2012-10-24
  1. 38

    Non, les membres de la carte est stockée en interne dans une structure en arbre. Il n'y a aucun moyen de construire l'arbre jusqu'à ce que vous connaissez les clés et les valeurs qui doivent être stockés.

    • Au mieux, on pourrait allouer tous les nœuds à l'avance.
    • Il ne serait pas beaucoup de différence, puisque chaque nœud doit être affecté (et deallocable) séparément. Il n'y a vraiment très peu à gagner de connaissance à l'avance du contenu de la carte (sauf si elle a été complètement constexpr).
    • Faire cela ne sauvera pas tout le temps. (Contrairement à l' vector.reserve(), ce qui permet de gagner du temps en évitant beaucoup de redimensionnement et de la copie.)
    • Vous pouvez créer une piscine de taille moyenne de l'allocateur, ce qui ferait de la répartition des nœuds individuels nettement plus rapide. Pour que cela soit réellement efficace, cependant, vous devez également savoir que le nombre de nœuds ne changera jamais. Si vous savez tout cela, il ne devrait pas être difficile à écrire un allocateur personnalisé qui devrait faire le travail.
    InformationsquelleAutor Bo Persson
  2. 21

    La réponse courte est: oui, c'est possible, mais il n'est pas trivial. Vous avez besoin de définir un allocateur personnalisé pour votre carte. L'idée de base est que votre allocateur personnalisé sera mis de côté un seul bloc de mémoire de la carte. Comme la carte nécessite de nouveaux nœuds, l'allocation sera tout simplement de leur assigner des adresses à l'intérieur de la pré-bloc alloué. Quelque chose comme ceci:

    std::map<KeyType, ValueType, std::less<KeyType>, MyAllocator> myMap;

myMap.get_allocator().reserve( nodeSize * numberOfNodes );

    Il y a un certain nombre de questions que vous aurez à traiter avec, cependant.

    Tout d'abord, vous ne savez pas vraiment la taille de chaque carte du nœud ou du nombre d'allocations de la carte sera à effectuer. Ce sont la mise en œuvre interne de détails. Vous pouvez essayer de trouver, mais vous ne pouvez pas supposer que les résultats seront valables dans différents compilateurs (ou même les futures versions de la même compilateur). Par conséquent, vous ne devriez pas vous inquiéter au sujet de l'allocation d'un "fixe" de la taille de la carte. Au contraire, votre objectif devrait être de réduire le nombre d'allocations nécessaires à une poignée.

    Deuxièmement, cette stratégie devient un peu plus complexe si vous voulez soutenir la suppression.

    Troisième, n'oubliez pas de mémoire problèmes d'alignement. Les pointeurs de votre allocation de retour doit être correctement aligné pour les différents types d'objets de la mémoire store.

    Tout cela étant dit, avant de l'essayer, assurez-vous qu'il est nécessaire. L'allocation de la mémoire peut être très coûteux, mais vous ne devriez pas supposer que c'est un problème pour votre programme. Mesure de trouver. Vous devriez également envisager d'autres stratégies plus naturellement permettre de pré-affectation. Par exemple, une liste triée ou un std::unordered_map.

    • J'ai vraiment d'accord avec le dernier paragraphe. Probablement une triés vecteur sera la solution la plus efficace dans ce cas.
    • Est-il de l'espoir pour une méthode standardisée pour l'obtention du nœud de taille ou allons-nous rester dépend des estimations?
    • Je ne peux pas voir ce qui se passe. Si vous regardez de près à la définition de std::map, vous verrez qu'il n'a même pas de promesse d'être mis en œuvre comme un arbre.
    • La fonction get_alloc retourne allocator_type (en valeur), ce qui signifie que myMap.get_allocator().reserve( nodeSize * numberOfNodes ); appels reserve temporaire MyAllocator instance. En outre, sachant que le nœud de l'arborescence de la taille d'une carte de mise en œuvre est sans importance parce que l'allocateur est utilisé pour allouer des objets de type std::pair<const Key, T> ce qui signifie que vous pouvez parfaitement connaître la taille à l'avance.
    • Cela dépendra de l'application de la feuille, mais je m'attends plus à combiner à la fois la paire clé/valeur et liées info nœud dans un seul objet. Dans tous les cas, si vous voulez faire une allocation unique pour votre carte, alors vous devez savoir deux la taille des données que vous avez l'intention de stocker plus de la carte de surcharge. Il est vrai que get_allocator() renvoie une copie, ce qui peut être un méchant chat. Si myMap.get_allocator().reserve(...) fait ce que vous espérer dépend de l'allocateur de mise en œuvre. Tout ce scénario est beaucoup plus facile avec la nouvelle polymorphes allocateurs en C++17.
    InformationsquelleAutor Peter Ruderman
  3. 2

    Vous parlez block allocators. Mais il est difficile à mettre en œuvre. Mesurer, avant de penser à de telles choses difficiles. De toute façon Boost a quelques articles sur la mise en œuvre de bloquer l'allocateur. Ou utilisez déjà mis en œuvre préaffectés carte Stree

    InformationsquelleAutor Denis Ermolin
  4. 1

    Ne sais pas si cela répond à votre question, mais coup de pouce.Conteneur a un flat_map dans lesquelles vous pouvez réserver un espace. Fondamentalement, vous pouvez voir cela comme une triés vecteur de (clé, valeur) paires. Mais là encore, si votre entrée a déjà été constante, vous ne l'utilisez une std::map en premier lieu. Autre conseil: si vous savez que votre entrée est triée, vous pouvez utiliser insert avec indication de la performance maximale.

    InformationsquelleAutor gast128