Structures de données C++

C++ fournit une variété de structures de données, allant de celles de base telles que les tableaux, les structures et les classes, aux conteneurs STL avancés tels quevector、mapetunordered_mapetc.

Ce qui suit détaille les structures de données couramment utilisées en C++, ainsi que leurs caractéristiques et leur utilisation.

1. Tableau

Les tableaux sont les structures de données les plus basiques, utilisées pour stocker un ensemble de données du même type.

Fonctionnalités：

  • Taille fixe ; une fois déclarée, la taille ne peut pas être modifiée.
  • Accès direct aux éléments avec une complexité temporelle de O(1).
  • Adapté pour gérer des collections de taille connue avec des types d'éléments identiques.

Exemple

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // Affiche le premier élément

Avantages et inconvénients：

  • Avantage : Vitesse d'accès rapide, utilisation compacte de la mémoire.
  • Inconvénients : taille fixe, ne peut pas être étendu dynamiquement, ne convient pas aux ensembles de données de taille incertaine.

2. Struct

Les structures permettent de combiner différents types de données pour former un type de données personnalisé.

Fonctionnalités：

  • Peuvent contenir des variables membres de différents types.
  • Fournit une encapsulation de base des données, mais avec des fonctionnalités limitées.

Exemple：

Exemple

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // Sortie Alice

3. Classe

Les classes sont la structure centrale de la programmation orientée objet en C++, permettant de définir des variables membres et des fonctions membres. Par rapport àstructSimilaires, mais plus puissantes, prenant en charge des fonctionnalités telles que l'héritage, l'encapsulation et le polymorphisme.

Fonctionnalités：

  • Peut inclure des variables membres, des fonctions membres, des constructeurs et des destructeurs.
  • Prend en charge des fonctionnalités orientées objet telles que l'encapsulation, l'héritage et le polymorphisme.

Exemple

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Nom : " << name << ", Âge : " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // Sortie : Nom : Bob, Âge : 30

4. Liste chaînée

Une liste chaînée est une structure de données dynamique composée d'une série de nœuds, chacun contenant des données et un pointeur vers le nœud suivant.

Fonctionnalités：

  • Redimensionnement dynamique, pas besoin de prédéfinir la capacité.
  • Les opérations d'insertion et de suppression sont efficaces, avec une complexité temporelle de O(1) (lorsqu'on opère en tête ou en queue de liste).
  • Recherche linéaire avec une complexité temporelle de O(n).

Instance (liste simplement chaînée)

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // Insérer un nouveau nœud

Avantages et inconvénients：

  • Avantages : taille dynamique, adapté aux scénarios avec des insertions et suppressions fréquentes.
  • Inconvénients : accès aléatoire inefficace, pas aussi rapide que l'accès direct à un tableau.

5. Pile

Une pile est une structure de données de type dernier entré, premier sorti (LIFO), couramment utilisée dans des scénarios tels que la récursivité et la recherche en profondeur.

Fonctionnalités：

  • Permet uniquement des opérations d'insertion et de suppression au sommet de la pile.
  • La complexité temporelle est O(1).

Exemple

stack<int> s;
s.push(1);
s.push(2);
cout << s.top(); // Sortie 2
s.pop();

Avantages et inconvénients：

  • Avantage : opérations simples, efficacité élevée.
  • Inconvénients : les opérations ne peuvent être effectuées qu'au sommet, l'accès aux autres éléments nécessite de dépiler l'élément du sommet.

6. File

Une file est une structure de données Premier entré, premier sorti (FIFO), couramment utilisée dans des scénarios tels que la recherche en largeur et l'ordonnancement des tâches.

Fonctionnalités：

  • Les opérations d'insertion se produisent à la queue de la file, et les opérations de suppression se produisent à la tête.
  • La complexité temporelle est O(1).

Exemple

queue<int> q;
q.push(1);
q.push(2);
cout << q.front(); // Sortie 1
q.pop();

Avantages et inconvénients：

  • Avantages : adapté aux scénarios qui traitent les données dans l'ordre, tels que l'ordonnancement des tâches.
  • Inconvénient : Impossible d'accéder aléatoirement aux éléments.

7. File à double extrémité (Deque)

Un deque permet des opérations d'insertion et de suppression aux deux extrémités, combinant les fonctionnalités d'une pile et d'une file.

Fonctionnalités：

  • Permet l'insertion et la suppression aux deux extrémités.
  • La complexité temporelle est O(1).

Exemple

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // Sortie 2
dq.pop_front();

Avantages et inconvénients：

  • Avantage : Opérations bidirectionnelles flexibles.
  • Inconvénients : utilisation d'espace plus importante, adapté aux scénarios nécessitant des opérations fréquentes aux deux extrémités.

8. Table de hachage

Une table de hachage est une structure de données qui stocke des données via des paires clé-valeur, prenant en charge des opérations rapides de recherche, d'insertion et de suppression. En C++,unordered_mapUne implémentation d'une table de hachage.

Fonctionnalités：

  • Utilise une fonction de hachage pour localiser rapidement les éléments, avec une complexité temporelle de O(1).
  • Ne garantit pas l'ordre des éléments.

Exemple

unordered_map<string, int> hashTable;
hashTable["apple"] = 10;
cout << hashTable["apple"]; // Sortie 10

Avantages et inconvénients：

  • Avantages : grande efficacité pour les opérations de recherche, d'insertion et de suppression.
  • Inconvénients : ne peut pas garantir l'ordre des éléments, et les performances se dégradent lorsque des collisions de hachage se produisent.

9. Map

mapIl s'agit d'un conteneur ordonné de paires clé-valeur, implémenté à l'aide d'un arbre rouge-noir. Comparé àunordered_mapDifférent, il garantit l'ordre des clés, avec des complexités temporelles de O(log n) pour la recherche, l'insertion et la suppression.

Fonctionnalités：

  • Garantit que les éléments sont disposés dans l'ordre de leurs clés.
  • Implémenté à l'aide d'un arbre de recherche binaire.

Exemple

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // Sortie 10

Avantages et inconvénients：

  • Avantages : les éléments sont ordonnés, ce qui convient aux scénarios qui nécessitent de traiter les données dans l'ordre.
  • Inconvénient : efficacité opérationnelle inférieure àunordered_mapLégèrement plus faible.

10. Set

setC'est un ensemble ordonné permettant de stocker des éléments uniques, également implémenté à l'aide d'un arbre rouge-noir. Il garantit que les éléments ne sont pas dupliqués et sont ordonnés.

Fonctionnalités：

  • Garantit l'unicité des éléments.
  • Les éléments sont automatiquement disposés par ordre croissant.
  • La complexité temporelle est O(log n).

Exemple

set<int> s;
s.insert(1);
s.insert(2);
cout << *s.begin(); // Sortie 1

Avantages et inconvénients：

  • Avantage : tri automatique et garantie d'unicité.
  • Inconvénients : l'efficacité d'insertion et de suppression est inférieure à celle des ensembles non ordonnés.

11. Tableau dynamique (vecteur)

vectorIl s'agit d'une implémentation de tableau dynamique fournie par la bibliothèque standard C++, qui peut étendre dynamiquement sa capacité et prend en charge l'accès aléatoire.

Fonctionnalités：

  • Redimensionnement dynamique.
  • Prend en charge l'accès aléatoire avec une complexité temporelle de O(1).
  • Lorsque la capacité est insuffisante, il s'étend dynamiquement, avec une complexité temporelle amortie de O(1).

Exemple

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // Sortie 1

Avantages et inconvénients：

  • Avantages : prend en charge l'accès aléatoire et l'expansion dynamique.
  • Inconvénients : faible efficacité lors de l'insertion ou de la suppression d'éléments au milieu.
autres extensions