C++ - Insertion dans une map et hints

Vous est-il déjà arrivé d'insérer des éléments dans une map, en sachant qu'ils étaient déjà ordonnés? Quelle perte de temps, dans ce cas, de payer une insertion logarithmique lorsque l'on sait déjà où l'élément doit aller. Cela tombe bien, std::map fournit la possibilité d'indiquer où l'élément se situe, via un "hint", et d'insérer en temps constant amorti. La documentation n'est cependant pas très précise sur le sujet. Voyons donc ce que ça donne, aidé de notre fidèle nano-horloge (attention, pour Linux seulement).

#include <iostream>
#include <ctime>
#include <vector>
#include <map>

int main()
{
  timespec t1, t2, t3;

  std::vector<int> keys;
  for(int i = 0; i < 100000; i++)
  {
    keys.push_back(i);
  }

  std::map<int, int> m1;
  std::map<int, int> m2;

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t1);

  for(int i = 0; i < keys.size(); i++)
  {
    m1.insert(m1.begin(), std::make_pair(i, i));
  }

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t2);

  for(int i = 0; i < keys.size(); i++)
  {
    m2.insert(std::make_pair(i, i));
  }

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t3);

  std::cout << "m1: " << t2.tv_nsec - t1.tv_nsec << std::endl;
  std::cout << "m2: " << t3.tv_nsec - t2.tv_nsec << std::endl;

  return 0;
}

Voilà comment réduire fortement le temps d'insertion (dans la réalité, l'on pourrait avoir à copier quelque chose d'un peu plus lourd qu'un entier, et les gains seraient plus réduits, mais quand même!). Scénario improbable, me direz-vous? Pas tant que ça. Par exemple, sérialisation / désérialisation vers un fichier, ou un format réseau: si l'on contrôle la sérialisation, l'on peut simplement écrire les éléments dans l'ordre du conteneur, et utiliser les hints au moment de la désérialisation. Facile, et fournissant un gain immédiat!