Utiliser le conteneur deque en C++

1. Utiliser le conteneur std::deque pour traiter des opérations rapides d’insertion/suppression de files d’attente
2. Utilisez les méthodes std::push_back/std::push_front pour insérer des éléments dans std::deque
3. Utiliser la fonction Wrapper pour la méthode push_front pour implémenter une file d’attente de taille fixe

Cet article présente plusieurs méthodes pour utiliser le conteneur std::deque en C++.

Utiliser le conteneur std::deque pour traiter des opérations rapides d’insertion/suppression de files d’attente

Le système std::deque met en œuvre une file d’attente à deux extrémités qui permet des opérations d’insertion et de suppression à temps constant à ses extrémités. Ainsi, cette structure de données doit être utilisée dans les scénarios où ces opérations constituent la plupart des transactions. L’inconvénient est que les éléments std::deque ne sont pas stockés dans des emplacements mémoire consécutifs, et qu’il faut une opération supplémentaire pour traiter les opérations, ce qui se traduit par des tailles d’objets plus importantes que le conteneur std::vector. L’exemple suivant montre une deque de chaînes de caractères construite à partir de l’objet vector. Notez qu’il est recommandé d’ajouter un nouvel élément à partir de la chaîne de caractères entrée en utilisant la méthode emplace_back.

#include <deque>
#include <iostream>
#include <vector>

using std::cout;
using std::deque;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printElements(deque<T> &d) {
  cout << "[ ";
  for (const auto &item : d) {
    cout << item << ", ";
  }
  cout << "\b\b ]" << endl;
}

int main() {
  vector<string> vec = {"plie", "flie", "blie", "clie"};
  ;

  deque<string> deque2(vec.begin(), vec.end());
  deque2.emplace_back("hlie");
  printElements(deque2);

  exit(EXIT_SUCCESS);
}

Production :

[ plie, flie, blie, clie, hlie ]

Utilisez les méthodes std::push_back/std::push_front pour insérer des éléments dans std::deque

std::deque possède de multiples fonctions intégrées pour offrir de riches fonctionnalités de manipulation des éléments. Les plus communes d’entre elles sont les méthodes push_back et push_front, qui ajoutent les objets donnés comme éléments au côté correspondant de deque. Notez que ces fonctions ont leurs méthodes inversées pour supprimer les éléments - pop_back et pop_front. L’exemple suivant montre l’utilisation de base des méthodes ci-dessus.

#include <deque>
#include <iostream>
#include <vector>

using std::cout;
using std::deque;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printElements(deque<T> &d) {
  cout << "[ ";
  for (const auto &item : d) {
    cout << item << ", ";
  }
  cout << "\b\b ]" << endl;
}

int main() {
  vector<string> vec = {"plie", "flie", "blie", "clie"};
  ;

  deque<string> deque2(vec.begin(), vec.end());

  string str1("alie");
  deque2.push_back(str1);
  printElements(deque2);
  deque2.push_front(str1);
  printElements(deque2);

  deque2.pop_back();
  deque2.pop_front();
  printElements(deque2);

  exit(EXIT_SUCCESS);
}

Production :

[ plie, flie, blie, clie, alie ]
[ alie, plie, flie, blie, clie, alie ]
[ plie, flie, blie, clie ]

Utiliser la fonction Wrapper pour la méthode push_front pour implémenter une file d’attente de taille fixe

Une autre méthode consiste à utiliser le conteneur std::deque pour fonctionner comme une pile de taille fixe qui stocke un nombre n d’éléments, et lorsqu’elle est pleine, elle retire automatiquement un élément de l’arrière à chaque nouvelle insertion. Dans ce cas, nous avons implémenté cette fonctionnalité en enveloppant les méthodes push_front et pop_back dans une fonction séparée. Notez que la même fonctionnalité peut également être réalisée en utilisant l’adaptateur de conteneur std::stack, qui est décrit en détail sur cette page.

#include <deque>
#include <iostream>

using std::cout;
using std::deque;
using std::endl;
using std::string;

template <typename T>
void printElements(deque<T> &d) {
  cout << "[ ";
  for (const auto &item : d) {
    cout << item << ", ";
  }
  cout << "\b\b ]" << endl;
}

template <typename T>
void pushElement(T &elem, deque<T> &d) {
  d.push_front(elem);
  d.pop_back();
}

int main() {
  deque<int> deque1 = {3, 5, 7, 9};
  int i1 = 11;

  printElements(deque1);
  pushElement(i1, deque1);
  printElements(deque1);

  exit(EXIT_SUCCESS);
}

Production :

[ 3, 5, 7, 9 ]
[ 11, 3, 5, 7 ]