std::deque

std::deque (short for “double-ended queue”) is a sequence container provided by the Standard Template Library (STL).

It is similar to std::vector in that it dynamically resizes to accommodate elements as needed. However, unlike std::vector, which uses a dynamic array, std::deque uses a double-ended queue, allowing for efficient insertion and deletion of elements at both ends.

Creating a std::deque:

To use std::deque, you need to include the <deque> header.

#include <iostream>
#include <deque>

int main() {
    // Create an empty deque of integers
    std::deque<int> myDeque;

    // Create a deque with initial values using initializer list
    std::deque<int> initializedDeque = {10, 20, 30, 40, 50};

    return 0;
}

Advantages of std::deque:

1. Efficient insertion and deletion: std::deque allows constant time insertion and deletion of elements at both ends.
2. Dynamic resizing: It dynamically resizes to accommodate elements as needed.
3. Efficient memory usage: Unlike std::vector, it does not require shifting elements during insertion and deletion.
4. Stable iterators: Iterators remain valid even after inserting or erasing elements.

Disadvantages of std::deque:

1. Higher memory overhead: Each element in the deque requires extra memory for two pointers (for the previous and next nodes).
2. Slower access time: Accessing elements in the middle of the deque is slower compared to std::vector due to the indirect nature of indexing.

std::deque is suitable for scenarios where efficient insertion and deletion at both ends of the container are required. It provides better performance for such operations compared to std::vector. However, if constant-time access using indexing is crucial and the majority of operations involve accessing elements by index, std::vector might be a better choice.

Important Functions of std::deque:

push_back(value):

Adds an element to the end of the deque.

• Time Complexity: Amortized constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque;

    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    return 0;
}

push_front(value):

Adds an element to the beginning of the deque.

• Time Complexity: Amortized constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque;

    myDeque.push_front(10);
    myDeque.push_front(20);
    myDeque.push_front(30);

    return 0;
}

pop_back():

Removes the last element from the deque.

• Time Complexity: Amortized constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    myDeque.pop_back(); // After this, myDeque contains {10, 20}

    return 0;
}

pop_front():

• Time Complexity: Amortized constant time (O(1)).
• Space Complexity: Constant space (O(1)).

Removes the first element from the deque.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    myDeque.pop_front(); // After this, myDeque contains {20, 30}

    return 0;
}

size():

Returns the number of elements in the deque.

• Time Complexity: Constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    std::cout << "Size of the deque: " << myDeque.size() << std::endl; // Output: 3

    return 0;
}

empty():

Checks if the deque is empty.

• Time Complexity: Constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque;

    if (myDeque.empty()) {
        std::cout << "Deque is empty." << std::endl;
    } else {
        std::cout << "Deque is not empty." << std::endl;
    }

    return 0;
}

clear():

Removes all elements from the deque.

• Time Complexity: Linear time (O(n)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    myDeque.clear(); // After this, myDeque is empty

    return 0;
}

front():

Returns a reference to the first element in the deque.

• Time Complexity: Constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    int firstElement = myDeque.front(); // firstElement = 10

    return 0;
}

back():

Returns a reference to the last element in the deque.

• Time Complexity: Constant time (O(1)).
• Space Complexity: Constant space (O(1)).

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    int lastElement = myDeque.back(); // lastElement = 30

    return 0;
}

emplace_front(args…):

Adds a new element to the beginning of the deque using its constructor with provided arguments.

#include <iostream>
#include <deque>

class MyClass {
public:
    MyClass(int a, int b) {
        std::cout << "Constructor called with arguments " << a << " and " << b << std::endl;
    }
};

int main() {
    std::deque<MyClass> myDeque;

    myDeque.emplace_front(10, 20); // Calls the constructor of MyClass with arguments 10 and 20

    return 0;
}

emplace_back(args…):

Adds a new element to the end of the deque using its constructor with provided arguments.

#include <iostream>
#include <deque>

class MyClass {
public:
    MyClass(int a, int b) {
        std::cout << "Constructor called with arguments " << a << " and " << b << std::endl;
    }
};

int main() {
    std::deque<MyClass> myDeque;

    myDeque.emplace_back(10, 20); // Calls the constructor of MyClass with arguments 10 and 20

    return 0;
}

insert(position, value):

Inserts an element with the specified value at the given position in the deque.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 30};

    auto it = myDeque.begin();
    ++it; // Move iterator to the second position

    myDeque.insert(it, 20); // After this, myDeque contains {10, 20, 30}

    return 0;
}

erase(position):

Removes the element at the specified position from the deque.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque = {10, 20, 30};

    auto it = myDeque.begin();
    ++it; // Move iterator to the second position

    myDeque.erase(it); // After this, myDeque contains {10, 30}

    return 0;
}