Quelle est la complexité de travailler avec les conteneurs map et unordered_map en C++?

std::map (Arbre rouge-noir)

• Insertion, suppression, recherche : O(log N) en moyenne et dans le pire des cas. N est le nombre d éléments.
• Accès par clé avec operator[] ou méthode at(): O(log N).
• Obtenir un itérateur au début/fin: O(1).
• Itérer sur tous les éléments: O(N).
• Mémoire: O(N).

std::unordered_map (Table de hachage)

• Insertion, suppression, recherche: O(1) en moyenne. O(N) dans le pire des cas (lorsque il y a de fortes collisions de hachage). N est le nombre d éléments.
• Accès par clé avec operator[] ou méthode at(): O(1) en moyenne. O(N) dans le pire des cas.
• Obtenir un itérateur au début/fin: O(1).
• Itérer sur tous les éléments: O(N) en moyenne. L ordre d itération n est pas garanti.
• Mémoire: O(N). Dépend du facteur de charge et de l implémentation de la table de hachage.

Comparaison :

Opération	std::map (O)	std::unordered_map (O)
Insertion, Suppression	log N	1 (moyenne), N (pire)
Recherche	log N	1 (moyenne), N (pire)
Accès par clé	log N	1 (moyenne), N (pire)
Itération sur tous	N	N (moyenne)

std::unordered_map est généralement plus rapide pour les opérations individuelles (insertion, recherche, suppression) grâce à O(1) en moyenne, mais nécessite une bonne fonction de hachage et est sensible aux collisions. std::map garantit une complexité logarithmique indépendamment des données, maintient les éléments dans l ordre trié et ne nécessite pas de fonction de hachage pour le type de clé.