Recherche d'un élément dans une table

Les problèmes de recherche sont modélisés à l'aide de structures contenant au moins deux champs : key et info. Le champ key est souvent une chaîne de caractères (un nom) qui permet de désigner de façon unique un objet. Les autres champs, info1, info2, etc, contiennent toutes sortes d'informations relatives à cet objet. On représentera ces objets à l'aide du type struct :

struct data {
  string  key;
  int info1;
  double info2;
  // ...
};

Ces enregistrements doivent à leur tour être placés dans une structure de données appropriée, que l'on appellera une table ou dictionnaire. Les deux opérations principales sont l'insertion d'un objet et la recherche d'un objet désigné par sa clé. Une autre opération qui peut être demandée est la suppression d'un objet désigné par sa clé. Ces trois opérations ne sont pas réalisées avec la même fréquence. Dans le cas d'un annuaire, les interrogations (ou recherches) sont beaucoup plus fréquentes que les insertions ou les suppressions. On peut donc chercher à optimiser les recherches plutôt que les deux autres opérations.

Il sera commode de disposer d'un objet vide de type data, qui sera retourné en cas d'échec. On peut le définir comme une constante à l'aide de l'initialisation partielle suivante, qui a pour effet d'initialiser à la chaîne vide le premier champ, et à la valeur nulle les champs suivants.

const data empty_data = {""};