Utilizar o Deque Container em C++

1. Utilizar o std::deque Container para processar operações de inserção/remoção rápida de filas
2. Utilizar std::push_back/std::push_front Métodos para inserir elementos em std::deque
3. Utilizar a função Wrapper para o método push_front para implementar a fila de tamanho fixo

Este artigo demonstrará múltiplos métodos sobre como utilizar o std::deque contentor em C++.

Utilizar o std::deque Container para processar operações de inserção/remoção rápida de filas

std::deque implementa uma fila de duas pontas que proporciona operações de inserção e eliminação de tempos constantes nas suas extremidades. Assim, esta estrutura de dados deve ser utilizada em cenários em que tais operações constituem a maior parte das transacções. Do lado negativo, os elementos std::deque não são armazenados em locais de memória consecutivos, e necessita de alguma operação extra para lidar com operações, resultando em mais tamanhos de objectos do que o contentor std::vector. O exemplo seguinte mostra um deque de strings construídas a partir do objecto vector. Note-se que um novo elemento da entrada da string é recomendado para ser adicionado utilizando o método 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);
}

Resultado:

[ plie, flie, blie, clie, hlie ]

Utilizar std::push_back/std::push_front Métodos para inserir elementos em std::deque

std::deque tem múltiplas funções incorporadas para fornecer características ricas de manipulação de elementos. As mais comuns são os métodos push_back e push_front, que adicionam os objectos dados como elementos ao lado correspondente do deque. Note-se que estas funções têm os seus métodos invertidos para remover os elementos - pop_back e pop_front. O exemplo seguinte mostra a utilização básica dos métodos acima referidos.

#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);
}

Resultado:

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

Utilizar a função Wrapper para o método push_front para implementar a fila de tamanho fixo

Outro método para utilizar o contentor std::deque para operar sobre ele como a pilha de tamanho fixo que armazena n número de elementos, e quando está cheio, remove automaticamente um elemento da parte de trás em cada nova inserção. Neste caso, implementámos esta funcionalidade envolvendo os métodos push_front e pop_back numa função separada. Note-se que a mesma funcionalidade também pode ser obtida utilizando o adaptador de contentor std::stack, que é descrito extensivamente nesta página.

#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);
}

Resultado:

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