C++ : Bien choisir ses structures de données

Difficulté Moyen
Note
Thématiques
Mis à jour le mardi 19 novembre 2013

Ce cours s'adresse aux programmeurs en C++.

On est souvent amené à implémenter des choses qui nécessitent de stocker beaucoup de données et on s'aperçoit assez vite qu'on y applique souvent le même jeu d'opérations. À partir de là, on peut se poser la question du choix de cette structure : laquelle présentera les meilleures performances pour ce que je veux faire ? Et comme il n'est quasiment jamais question de réinventer la roue, il existe un nombre important de structures déjà implémentées (dans la STL ou dans Boost). Comment s'y retrouver ?

Ce tutoriel est là pour répondre à ces deux questions. Beaucoup de débutants ne se les posent pas, ou pas assez. Il n'est ainsi pas surprenant de les voir "patauger" sur le forum de ce site en essayant soit de tout faire avec un std::vector, en écrivant eux-même une structure de tas parce qu'ils en ont besoin, ou encore en utilisant std::set pour les ensembles où l'ordre n'a pas d'importance.
Souvent, le manque de recherche et l'ignorance en sont la cause. Mais ce n'est pas la seule : certains débutants sont également rebutés par des bibliothèques tierces comme Boost parce que cela sort du cadre de ce qu'ils ont l'habitude de voir sur ce site. C'est bien dommage.

Ce cours s'adresse aussi aux plus expérimentés. Une piqure de rappel ne fait jamais de mal.

De manière concrète, ce cours présentera brièvement chaque structure de données "connue", la complexité des différentes opérations qu'on serait susceptibles d'y appliquer, ainsi qu'un tableau résumant les classes C++ les plus utilisées pour chaque structure en précisant dans quel cas leur utilisation est justifiée.


L'auteur