Structures de données

Ces notes de cours explorent les conteneurs généralement implantés dans la bibliothèque normalisée (Standard Library – SL) de C++ et décrivent différentes façons de les implanter efficacement. La mécanique de C++ pour créer des types abstraits (la classe) est décrite et ensuite utilisée pour créer des conteneurs dont la fonctionnalité est aussi proche que possible de celle de la SL, sans trop s’aventurer dans les détails du langage. On y implante les conteneurs séquentiels de différentes façons (array, vector, deque, list, forward_list). Les conteneurs associatifs (set et map) sont implantés avec une liste à enjambement (skip_list), un arbre AVL (l’ancêtre de tous les arbres binaires de recherche), un arbre bicolore (Red-Black Tree). Les conteneurs asscociatifs sans ordre (unordered_set et unordered_map) sont aussi implantés avec l’adressage dispersé (hashing). Enfin, quelques structures spécialisées sont implantées, comme les monceaux, les monceaux binomiaux et les arbres équilibrés en poids.

Accéder à la ressource

Ordre(s) d'enseignementUniversitaire

Domaine(s)Informatique

Type(s) de ressourceManuel et livre

Langue(s)Français

Droits d'utilisationCC BY-SA

Format1 document PDF (179 pages)

Sujet(s)C++ (Langage de programmation) Programmation (Informatique) Conteneurs (Informatique) Complexité algorithmique Types abstraits de données (Informatique) Structures de données (Informatique)