Deque: Container, C++

Deque Container in C++: Usage and Operations

In C++, the deque container (short for double-ended queue) is part of the Standard Template Library (STL). A deque is a dynamic sequence container that allows efficient insertion and deletion of elements at both the front and the back. Unlike vector, which is optimized for operations at the back, deque provides nearly constant-time complexity for operations at both ends. deque is ideal when you need frequent additions and removals from either end but still require random access to elements.

In this guide, we will explore everything about the deque container, including how to construct deques, perform common operations, and use its capabilities effectively in C++.

Table of Contents

1. Introduction to Deque in C++
2. Different Ways to Construct a Deque
3. Common Operations on Deque
   • push_back()
   • push_front()
   • pop_back()
   • pop_front()
   • insert()
   • erase()
   • size()
   • empty()
   • clear()
   • at() and []
4. Working with Custom Data Types
5. Iterators in Deques
6. Deque of Deques
7. Summary and Best Practices

1. Introduction to Deque in C++

A deque in C++ is a sequence container that supports fast insertion and deletion at both ends. Internally, a deque is implemented as a dynamic array of fixed-size arrays, allowing it to grow or shrink efficiently at either end.

Key Features:

• Dynamic Sizing: deque dynamically resizes itself as elements are added or removed.
• Efficient Operations at Both Ends: Insertions and deletions at the front and back are efficient (constant time on average).
• Random Access: Elements can be accessed in constant time using an index.
• Bidirectional Iteration: Supports bidirectional iterators for traversal.

When to Use:

• Use deque when you need frequent additions or removals at both ends.
• If only one end requires frequent modification, consider vector for better memory locality.

2. Different Ways to Construct a Deque

You can create a deque in several ways, depending on your requirements.

2.1 Default Constructor

The default constructor creates an empty deque.

deque<int> dq;

This creates an empty deque of integers, which can be populated later.

2.2 Constructor with Initial Size

You can create a deque with a specific size, where each element is initialized to the default value of the type.

deque<int> dq(5);  // Creates a deque of size 5 with default-initialized elements (0 for int)

To initialize the elements to a specific value, provide a second argument.

deque<int> dq(5, 10);  // Creates a deque of size 5 with each element initialized to 10

2.3 Constructor with an Initializer List

You can initialize a deque directly with a list of values.

deque<int> dq = {1, 2, 3, 4, 5};

This creates a deque containing the values 1, 2, 3, 4, 5.

2.4 Constructor with Another Container

You can create a deque by copying elements from another container.

deque<int> dq1 = {1, 2, 3, 4, 5};
deque<int> dq2(dq1);  // Creates a deque that is a copy of dq1

2.5 Constructor with Iterators

You can initialize a deque using a range of iterators from another container, such as a vector or list.

vector<int> v = {1, 2, 3, 4, 5};
deque<int> dq(v.begin(), v.end());  // Initializes a deque using iterators from a vector

You can also initialize a deque from arrays using pointers.

int arr[] = {1, 2, 3, 4, 5};
deque<int> dq(arr, arr + 5);  // Initializes a deque using pointers to an array

2.6 Assignment Operator

The assignment operator allows you to copy elements from one deque to another.

deque<int> dq1 = {1, 2, 3};
deque<int> dq2;
dq2 = dq1;  // Now dq2 contains the same elements as dq1

The assignment operator performs a deep copy, so the elements of dq1 are fully copied into dq2.

3. Common Operations on Deque

3.1 push_back()

The push_back() function adds an element to the end of the deque. This operation is constant time on average.

Syntax:

dq.push_back(element);

Example:

deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);

After this, the deque dq will contain: [10, 20, 30].

3.2 push_front()

The push_front() function adds an element to the front of the deque. This operation is also constant time on average.

Syntax:

dq.push_front(element);

Example:

deque<int> dq = {10, 20, 30};
dq.push_front(5);  // Adds 5 at the front

After this, the deque dq will contain: [5, 10, 20, 30].

3.3 pop_back()

The pop_back() function removes the last element from the deque. This operation is constant time on average.

Syntax:

dq.pop_back();

Example:

deque<int> dq = {10, 20, 30};
dq.pop_back();  // Removes 30

After calling pop_back(), the deque will contain: [10, 20].

3.4 pop_front()

The pop_front() function removes the first element from the deque.

Syntax:

dq.pop_front();

Example:

deque<int> dq = {10, 20, 30};
dq.pop_front();  // Removes 10

After calling pop_front(), the deque will contain: [20, 30].

3.5 insert()

The insert() function allows you to insert an element at a specific position in the deque.

Syntax:

• Insert a single element:

  dq.insert(position, element);

• Insert multiple identical elements:

  dq.insert(position, count, element);

• Insert elements from another container:

  dq.insert(position, container.begin(), container.end());

Example 1: Insert a Single Element

deque<int> dq = {10, 20, 30};
auto it = dq.begin();
advance(it, 1);
dq.insert(it, 15);  // Inserts 15 at position 1

After this, the deque dq will contain: [10, 15, 20, 30].

Example 2: Insert Multiple Identical Elements

dq.insert(it, 3, 100);  // Inserts three 100's at position 1

After this, the deque dq will contain: [10, 100, 100, 100, 15, 20, 30].

Example 3: Insert Elements from Another Container

deque<int> dq1 = {1, 2, 3};
deque<int> dq2 = {4, 5, 6};
dq1.insert(dq1.end(), dq2.begin(), dq2.end());  // Inserts all elements from dq2 at the end of dq1

After this, the deque dq1 will contain: [1, 2, 3, 4, 5, 6].

3.6 erase()

The erase() function removes elements from the deque at a specified position or range of positions.

Syntax:

• Erase a single element:

  dq.erase(position);

• Erase a range of elements:

  dq.erase(start, end);  // Removes elements from start to end-1

Example 1: Erase a Single Element

deque<int> dq = {10, 20, 30};
auto it = dq.begin();
advance(it, 1);
dq.erase(it);  // Removes element at position 1 (20)

After this, the deque dq will contain: [10, 30].

Example 2: Erase a Range of Elements

deque<int> dq = {10, 20, 30, 40, 50};
auto it1 = dq.begin();
advance(it1, 1);
auto it2 = dq.begin();
advance(it2, 4);
dq.erase(it1, it2);  // Removes elements from position 1 to 3 (20, 30, 40)

After this, the deque dq will contain: [10, 50].

3.7 size()

The size() function returns the number of elements in the deque.

Syntax:

size_t size = dq.size();

Example:

deque<int> dq = {10, 20, 30};
cout << "Size of deque: " << dq.size() << endl;  // Outputs: 3

3.8 empty()

The empty() function checks whether the deque is empty.

Syntax:

bool isEmpty = dq.empty();

Example:

deque<int> dq;
cout << "Is deque empty? " << (dq.empty() ? "Yes" : "No") << endl;  // Outputs: Yes
dq.push_back(10);
cout << "Is deque empty? " << (dq.empty() ? "Yes" : "No") << endl;  // Outputs: No

3.9 clear()

The clear() function removes all elements from the deque.

Syntax:

dq.clear();

Example:

deque<int> dq = {10, 20, 30};
dq.clear();  // Removes all elements

After calling clear(), the deque will be empty.

3.10 at() and []

The at() function provides access to an element at a specific position with bounds checking, while the [] operator provides direct access without bounds checking.

Example:

deque<int> dq = {10, 20, 30};
cout << dq.at(1) << endl;  // Outputs: 20
cout << dq[2] << endl;     // Outputs: 30

4. Working with Custom Data Types

Like other STL containers, deque can store custom data types such as classes or structs.

Example:

class Student {
public:
    string name;
    int age;

    Student(string n, int a) : name(n), age(a) {}
};

deque<Student> students;
students.push_back(Student("John", 20));
students.push_front(Student("Alice", 22));

5. Iterators in Deques

Deques support iterators for bidirectional traversal. The begin() and end() functions return iterators pointing to the first and one-past-the-last elements.

Example Using Iterators:

deque<int> dq = {10, 20, 30};
for (auto it = dq.begin(); it != dq.end(); ++it) {
    cout << *it << " ";  // Output: 10 20 30
}

6. Deque of Deques

A deque can store other deques, enabling the creation of complex data structures like matrices.

Example:

deque<deque<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

You can access elements with nested loops or iterators.

for (auto& row : matrix) {
    for (auto elem : row) {
        cout << elem << " ";  // Outputs: 1 2 3 4 5 6 7 8 9
    }
}

7. Summary and Best Practices

• deque is a versatile container, suitable for scenarios requiring efficient insertions and deletions at both ends.
• Use deque when you need random access but also frequent modifications at both ends.
• Avoid using deque if you need very large contiguous memory storage; in such cases, vector may be more appropriate.
• Always prefer at() over [] for bounds-checked element access.

By mastering the deque container, you can effectively handle dynamic sequences with flexible operations in your C++ programs.