Sécurité de std::unordered_map::merge()

Question

Lors de l'écriture de certains ciblage par code C++17, j'ai en quelque sorte de hit, une pierre d'achoppement de la détermination de l'exception de sécurité d'une opération de fusion de deux compatibles std::unordered_maps. Par l'actuel projet de travail, §26.2.7, tableau 91 lit, en partie, sur les conditions d' a.merge( a2 ):

Nécessite: a.get_allocator() == a2.get_allocator().

Les tentatives pour extraire chaque élément en a2 et insérez - a à l'aide de la fonction de hachage de clé et de prédicat d'égalité de a. Dans des conteneurs avec des clés uniques, si il y a un élément en a avec les principaux équivalent à la touche d'un élément d' a2, alors que l'élément n'est pas extraite d' a2.

Postconditions: les Pointeurs et les références à l'transféré les éléments d' a2 reportez-vous à ces mêmes éléments, mais comme des membres de l' a. Les itérateurs en se référant à l'transféré les éléments et tous les itérateurs se référant à l' a sera invalidée, mais les itérateurs d'éléments restant en a2 restent valables.

Jette: Rien de moins que la fonction de hachage ou d'une clé prédicat d'égalité lancers.

Il est intéressant de noter que ces conditions sont rappelle fortement celles données pour les besoins de l'ordinaire conteneurs associatifs (std::map), donnée au §26.2.6, table à 90, a.merge( a2 ):

Nécessite: a.get_allocator() == a2.get_allocator().

Les tentatives pour extraire chaque élément en a2 et insérez - a à l'aide de la comparaison de l'objet de l' a. Dans des conteneurs avec des clés uniques, si il y a un élément en a avec les principaux équivalent à la touche d'un élément d' a2, alors que l'élément n'est pas extraite d' a2.

Postconditions: les Pointeurs et les références à l'transféré les éléments d' a2 reportez-vous à ces mêmes éléments, mais comme des membres de l' a. Les itérateurs se référant aux éléments transférés continuera à se référer à leurs éléments, mais ils se comportent maintenant comme les itérateurs en a, pas en a2.

Jette: Rien de moins que la comparaison de l'objet lancers.

J'avais besoin de fusionner deux std::unordered_maps avec le même nombre d'éléments que je pouvais assurer serait unique entre les deux récipients, ce qui signifie que la carte contenant le résultat fusionné aurait le double du nombre d'éléments qu'il avait précédemment, et le conteneur fusionné-de serait vide. Ce doit être parfaitement en sécurité grâce au C++17, droite?

C'est un gain énorme en termes de performances... sauf que, j'ai eu cette lancinante doute. Hilarante, la postcondition déclaration ne dit rien quant à savoir si ou non le précédent max facteur de charge dans la fusion de carte serait à l'honneur, et bien que cela semble comme un coffre-fort hypothèse implicite, il semblait naïvement en conflit avec la déclaration sur la unordered_map de l'exception de sécurité. Si vous êtes en utilisant une table de hachage de conception dans lequel les compartiments sont de manière contiguë allouée tampons, le maintien de votre facteur de charge semblerait impliquer ressasser, ce qui semblerait impliquer la réaffectation du seau de la mémoire tampon.

Déjà, il semblait comme un exercice dans des conditions d'extrême regarder le nombril et il y a de bonnes raisons de laisser assez bien seul: il y a de plus compliqué à table de hachage pourrait être fait complètement basées sur les nœuds de la structure, similaire aux arbres rouge-noir généralement sous-tendent std::map, et dans ce cas, la spécification semble raisonnable comme une resucée n'implique pas l'attribution.

Peut-être à mon avantage, j'ai succombé à des doutes et creusé dans gcc-7.1 mise en œuvre de la fusion. C'est incroyablement compliqué, mais pour résumer mes conclusions, j'ai trouvé que les seaux sont, en effet, de manière contiguë allouée tampons, et ressasser implique une réallocation des ressources. Peut-être, pensais-je, il n'y a parfois plus profond de la magie qu'il me manquait (j'ai regardé la source de presque tout un jour et de toujours senti que j'avais une mauvaise compréhension de celui-ci) qui juste désactivé ressasser lors d'une fusion, ce qui signifie que toutes les conditions spécifiées serait confirmée, mais vous pourriez obtenir un méchant de régression de la performance après une assez grande fusion, puisque votre carte serait susceptible d'être surchargé.

J'ai déménagé pour une pratique d'évaluation de la mise en miroir de mon cas d'utilisation (qui je l'aurais présenté, si c'était possible, j'en suis désolé), au lieu de simplement le questionnement de mon interprétation de libstdc++:

#include <memory>        // for std::shared_ptr<>
#include <new>           // for std::bad_alloc
#include <utility>       // for std::move(), std::pair<>
#include <type_traits>   // for std::true_type
#include <unordered_map> // for std::unordered_map<>
#include <functional>    // for std::hash<>, std::equal_to<>
#include <string>        // for std::string
#include <iostream>      // for std::cout
#include <cstddef>       // for std::size_t

template<typename T>
class PrimedFailureAlloc
{
public:
  using value_type = T;
  using propagate_on_container_copy_assignment = std::true_type;
  using propagate_on_container_move_assignment = std::true_type;
  using propagate_on_container_swap = std::true_type;

  PrimedFailureAlloc() = default;

  template<typename U>
  PrimedFailureAlloc( const PrimedFailureAlloc<U>& source ) noexcept
    : m_triggered{ source.m_triggered }
  { }

  template<typename U>
  PrimedFailureAlloc( PrimedFailureAlloc<U>&& source ) noexcept
    : m_triggered{ std::move( source.m_triggered ) }
  { }

  T* allocate( std::size_t n )
  {
    if ( *m_triggered ) throw std::bad_alloc{};
    return static_cast<T*>( ::operator new( sizeof( T ) * n ) );
  }

  void deallocate( T* ptr, std::size_t n ) noexcept
  {
    ::operator delete( ptr );
  }

  bool operator==( const PrimedFailureAlloc& rhs ) noexcept
  {
    return m_triggered == rhs.m_triggered;
  }

  void trigger() noexcept { *m_triggered = true; }

private:
  template<typename U>
  friend class PrimedFailureAlloc;

  std::shared_ptr<bool> m_triggered{ new bool{ false } };
};

template<typename T>
bool operator!=( const PrimedFailureAlloc<T>& lhs,
                 const PrimedFailureAlloc<T>& rhs ) noexcept
{
  return !(lhs == rhs);
}

template< typename Key
        , typename T
        , typename Hash = std::hash<Key>
        , typename KeyEqual = std::equal_to<Key>
        >
using FailingMap = std::unordered_map<
  Key,
  T,
  Hash,
  KeyEqual,
  PrimedFailureAlloc<std::pair<const Key, T>>
>;

template<typename Key, typename T>
void printMap( const FailingMap<Key, T>& map )
{
  std::cout << "{\n";
  for ( const auto& [str, index] : map )
    std::cout << "  { " << str << ", " << index << " }\n";
  std::cout << "}\n";
}

int main()
{
  PrimedFailureAlloc<std::pair<const std::string, int>> a;
  FailingMap<std::string, int> m1{ a };
  FailingMap<std::string, int> m2{ a };

  m1.insert( { { "Purple", 0 }, { "Green", 3 }, { "Indigo", 16 } } );
  m2.insert( { { "Blue", 12 }, { "Red", 2 }, { "Violet", 5 } } );

  // m1.reserve( m1.size() + m2.size() );
  a.trigger();
  m1.merge( m2 );

  std::cout << "map :=\n";
  printMap( m1 );

  return 0;
}

Bien sûr, après la compilation de ce code sous GCC-7.1, j'obtiens:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
[1]    10944 abort      ./a.out

Considérant que, en décommentant la ligne 95 (m1.reserve( m1.size() + m2.size() );), les résultats de la sortie attendue:

map :=
{
  { Red, 2 }
  { Violet, 5 }
  { Purple, 0 }
  { Green, 3 }
  { Blue, 12 }
  { Indigo, 16 }
}

Comprendre que le C++17 est encore qu'un projet de norme qui n'a pas encore été finalisé, et que gcc de la mise en œuvre est expérimental, je suppose que ma question serait:

1. Ai-je gravement mal interprété la sécurité de l'opération de fusion comme défini dans la norme? Sont là les meilleures pratiques à l'aide d' std::unordered_map::merge() que j'ai manqué? Étais-je censé être implicitement la responsabilité d'assurer la répartition des seaux? Le fait d'utiliser des std::unordered_map::reserve() être réellement portable lorsque clang, MSVC, Intel et enfin le support C++17? Je veux dire, mon programme d'avorter lorsqu'une exception-libre de fusion a été impossible n', après une notion, d'adhérer à la liste postconditions...
2. Est-ce réellement un défaut dans la norme? La similitude de la formulation entre non ordonnée conteneurs associatifs et de simples conteneurs associatifs aurait peut-être involontaire de garanties pour se glisser dans si le texte était, disons, copie-collé.
3. Est-ce juste un bug de gcc?

Il est intéressant de noter que je n'ai vérifier gcc bug tracker avant cette écriture-up et semblait trouver pas de bugs ouverts correspondant à mon description, et de plus, j'ai vérifié le C++ standard de rapport de défaut et de même semblait venir jusqu'vide (il est vrai que, de faire une recherche de texte de ce site est aggravantes et j'ai peut-être été moins approfondie). Ce dernier n'est pas surprenant, puisque les défauts et leurs solutions de contournement ou conséquences sont généralement noté dans gcc code source et je n'ai pas trouvé de telles notations au cours de mon examen. J'ai essayé de compiler mon code d'exemple dans ma plus récente à la caisse d'clang (sur une semaine), mais le compilateur segfaulted donc j'ai pris mon examen il n'y pas plus loin, et n'ont pas consulté la libc++.

Answer 1

Ce n'est qu'un défaut dans la norme, c'est-à-à-d., votre possibilité 2.

LWG vient de déplacer LWG numéro 2977 à "Prêt" statut, qui va frapper la clause de lancers erronées.

Answer 2

Afin de comprendre si le libellé de la norme qui est bon ou pas, vous devez regarder dans les fonctions sous-jacentes.
De fusion est lui-même constitué de deux opérations.

• réglage des pointeurs vers des éléments ajoutés. Comme ils sont déjà attribués, il n'y a pas d'allocation ici
• dans le cas où les limites pour le nombre d'éléments dans le seau est atteint, la resucée() est appelée.

L'appel de resucée() est le point, où vous attendent exception. Sol voyons dans son exception de sécurité.

23.2.5.1 Exception de garanties de sécurité [unord.req.sauf]
1 Pour les non-ordonnée des conteneurs associatifs, aucune fonction clear() lève une exception. effacer(k) ne pas jeter un exception, à moins que l'exception est levée par le conteneur de Hachage ou Pred objet (le cas échéant).
2 Pour les non-ordonnée des conteneurs associatifs, si une exception est levée par aucune autre opération que le conteneur fonction de hachage à partir d'une insertion ou d'emplace fonction d'insertion d'un élément unique, de l'insertion n'a pas de effet.
3 Pour les non-ordonnée des conteneurs associatifs, sans fonction d'échange déclenche une exception à moins que cette exception est levée par l'échange du conteneur de Hachage ou Pred objet (le cas échéant).
4 Pour les non-ordonnée des conteneurs associatifs, si une exception est levée à partir d'une resucée() fonction autre que celle d' par le conteneur de la fonction de hachage ou de la fonction de comparaison, la mouture() la fonction n'a aucun effet.

Comme vous pouvez le voir pour le réchauffé() la fonction est définie et qu'il ne fait rien si l'exception est générée à l'intérieur d'autres que pour le haschich ou de la fonction de comparaison. C'est, à mon avis, parfaitement en ligne avec la définition de fusion:

Jette: Rien de moins que la fonction de hachage ou d'une clé prédicat d'égalité lancers.

Ma compréhension est que quand il n'y a pas de place à l'augmentation sous-jacente de la structure de données pour la liste de seau, puis il est maintenu dans sa forme originale. Cela pourrait conduire à un peu inefficace accès à des éléments comme il pourrait y avoir plus d'éléments dans les différents seaux que défini. Même chose peut se produire au cours de l'insertion.

Où est le problème dans votre cas? Éventuellement dans la mise en œuvre de la resucée() la fonction qui génère où il ne devrait pas.

DISCLAIMER: je ne suis pas un expert sur le sujet. C'est juste ce que j'ai trouvé. Alors n'hésitez pas à me corriger si je me trompe.