Comment puis-je conserver efficacement l'ordre d'insertion dans une carte ?

Préserver l'ordre d'insertion dans une carte

Dans le domaine des structures de données, une carte est un conteneur qui stocke des paires clé-valeur. Une exigence courante pour les cartes est de conserver l'ordre dans lequel ces paires ont été insérées, garantissant que lors de l'itération dans la carte, les éléments sont accessibles dans l'ordre dans lequel ils ont été ajoutés. Cependant, l'implémentation par défaut d'une carte standard ne garantit pas cette préservation de l'ordre d'insertion.

Pour répondre à ce besoin, plusieurs alternatives peuvent être envisagées. Une option consiste à utiliser un vecteur de paires, ce qui permet de maintenir l'ordre d'insertion. Cependant, pour les scénarios impliquant un grand nombre d'opérations, comme l'itération sur 10 000 000 de paires clé-valeur, un vecteur peut ne pas être le choix optimal en raison de problèmes de performances.

Alternativement, pour les systèmes avec un nombre limité de clés -des paires de valeurs, comme le scénario de la question avec environ 50 paires, convertissant la carte en vecteur et utilisant la bibliothèque de tri standard (std :: sort) avec un ordre approprié un comparateur, tel qu'un foncteur, peut être une approche viable.

Une autre option pour préserver l'ordre d'insertion dans les cartes consiste à exploiter la bibliothèque multi-index Boost. Cette bibliothèque fournit différents types d'index qui peuvent être combinés pour créer des conteneurs multi-index. Par exemple, dans le scénario de la question, une carte multi-index pourrait être utilisée avec deux indices : un pour l'accès aléatoire (en préservant l'ordre d'insertion) et un autre index unique haché pour des recherches de chaînes efficaces. L'extrait de code suivant illustre comment une carte multi-index pourrait être implémentée pour ce scénario :

struct value_t {
  string s;
  int i;
};

struct string_tag {};

typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique<tag<string_tag>, member<value_t, string, &value_t::s>>
    >
> values_t;

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!