Reverse Deque in C++ STL

In this article, we have presented different ways to Reverse Deque in C++ STL. This involve the use of reverse iterator of Deque or the Reverse method in C++ STL.

Table of contents:

1. Introduction to Deque in C++ STL
2. Method 1: Make use of rbegin() and rend()
3. Method 2: Using deque's reverse () function

Pre-requisites:

• Deque in C++ STL
• Different ways to initialize Deque in C++ STL

Introduction to Deque in C++ STL

The DEQUE acts like a double-ended queue and its size is dynamic and handled by STL. It is similar to a vector, but unlike a vector, continuous storage allocation is not guaranteed here. Usually a deque is implemented as a collection of memory bocks, and these memory blocks contain elements that are in a contiguous memory. The deque allows direct element access using the subscript operator and the.at () method.
Deque enables for efficient back-and-forth insertion and deletion. However, inserting elements in areas other than the front and back are inefficient.
Deque supports all the iterators, however they may become invalid if Deque's size changes.

Certainly like all the STL containers the deque supports copy and move semantics for initialization and assignment.
Initialization of deque

std::deque<int> a{1,2,3,4,5}

Some of the most widely used methods of deque

Method	Description
push_back()	This adds a new element at the end of a deque
pop_back()	This deletes the element from the end of a deque
push_front()	This adds a new element at the front of a deque
pop_front()	This deletes the element from the front of a deque

Method 1: Make use of rbegin() and rend()

Deque::rbegin() is an inbuilt function available in the C++ STL library that returns a reverse iterator which points to the last element of the deque.

Hence, the incrementing reverse iterator moves them forward, that is, towards the beginning of the container. However, this function never throws exceptions.

• The function deque: rbegin() does not accept any parameters.
• This method returns a reverse iterator.

deque::rend() is an inbuilt function available in the C++ STL library which returns a reverse iterator pointing to the element before the first element of the deque. This function also never throws exceptions.

• There are no parameters accepted by the deque:: render () function.
• This method returns a reverse iterator pointing at the element preceding the first element of deque.
• Elements between deque::rbegin and deque::rend represent all the elements belonging to the particular deque container.

Program 1

#include <iostream>
// the deque library is included
#include <deque>

int main ()
{
//default constructed ints
  std::deque<int> deque1 (5);  

  std::deque<int>::reverse_iterator it = deque1.rbegin();

  int i=0;
  for (it = deque1.rbegin(); it!= deque1.rend(); ++it)
    *it = ++i;

  std::cout << "deque contains:";
  for (std::deque<int>::iterator bit = deque1.begin(); bit != deque1.end(); ++bit)
    std::cout << ' ' << *bit;
  std::cout << '\n';

  return 0;
}

output:

deque contains: 5 4 3 2 1

PROGRAM 2

// the deque library is included
#include <deque>
#include <iostream>
using namespace std;
int main(void)
{
    deque <int> d1;
    // deque iterator 
    deque <int>::iterator d1_Iter;
    //deque reverse iterator
    deque <int>::reverse_iterator d1_rIter;
    d1.push_back(1);
    d1.push_back(2);
    d1.push_back(3);
    d1.push_back(4);
    d1.push_back(5);
    d1.push_back(6);
    cout<<"The d1 deque : ";
    
    for (d1_Iter = d1.begin(); d1_Iter != d1.end(); d1_Iter++)
        cout<<*d1_Iter<<" ";
    cout<<"in that order."<<endl;
    
    d1_rIter = d1.rbegin();
    cout<<"Last element in the con1 deque is "<<*d1_rIter<<"."<<endl;
    // rbegin() can be used to iterate through a deque in reverse order
    cout<<"The reversed con1 deque is: ";
    for (d1_rIter = d1.rbegin(); d1_rIter != d1.rend(); d1_rIter++)
        cout<<*d1_rIter<<" ";
    cout<<endl;
    
    return 0;
}

output:

The d1 deque : 1 2 3 4 5 6 in that order.
Last element in the con1 deque is 6.
The reversed con1 deque is: 6 5 4 3 2 1

Complexity

• Here we know the maximum number of times a loop can run as it depends on the size of the input we give. Hence, although there is a loop, the given code runs at constant time. – O(1)
• Here we are not increasing the size but just reversing the elements given. Hence, there is no extra space taken for the above code, so space complexity is also constant at O (1).

Method 2: Using deque's reverse () function

Reverse () is also an inbuilt function available in the C++ STL. In order to use this, we must include the algorithm header file (# include algorithm >). This function helps in reversing the elements of any type of container. Hence, it is also used for reversing deque.

• This includes all elements between the first and last, as well as the element pointed by the first but not the last, so its range is [front, end].
• Bidirectional iterators pointing to beginning and ending positions of the sequence to be reversed. This iterator will point to a type which swap is defined efficiently.

Program 1:

// An example of a CPP programme
#include <iostream>
// Because we're going to be using strings in our code, we should include a string library
#include <string>
#include <deque>
#include <algorithm> // for reverse
using namespace std;

int main()
{
  string s("deque");


  deque<char> deque1(s.begin(), s.end());

  deque<char>::iterator i;

  for (i = deque1.begin(); i != deque1.end(); ++i)
    cout << *i;

  cout << "\n";

  reverse(deque1.begin(), deque1.end());

  for (i = deque1.begin(); i != deque1.end(); ++i)
    cout << *i;

  return 0;
}

Output

euqed

COMPLEXITY

Because we use two iterators to traverse the entire data structure and swap the value, the time complexity is O(n).

Applications in practise

Although we don’t directly use reverse deque, deque has various applications in our daily life. They are:

• In web browser history, the recently visited sites are added to the front of the queue and sites are removed from the end when a particular limit is reached upon the addition of url’s at the beginning.
• Deque is also used for storing a computer code application’s list of undo operations.
• As we know, addition and deletion are permitted at both the front and back ends of a deque; thus, a deque can be used to move elements in clockwise and anticlockwise rotations in O(1) time complexity.
• Deque is also useful in checking whether the given input is a palindrome or not. We know a palindrome is a string in which elements read in forward or reverse order will look similar. For example: madam,refer, etc..

Questions based on the above topic

• Is DEQUE efficient for deleting or adding elements other than from the starting or ending position? What is the time complexity to remove an element from that particular position?
• What are the disadvantages of using deque? Please provide an example.

With this article at OpenGenus, you must have the complete idea of how to reverse a Deque in C++ STL.