When to Use Deque Instead of Vector in C++?
In C++, both deque
and vector
are sequence containers that can be used to store collections of elements. However, there are some cases where using deque
can be more beneficial than using vector
. In this article, we will learn when to use deque
instead of vector
in C++.
When to Prefer Deque Instead of Vector?
Choosing between a std::vector and std::deque depends on specific requirements such as the size of the collection, performance considerations, and ease of use. The following are the cases where using deque
in place of vector
is more advantageous:
1. Efficient Insertion and Deletion at Both Ends
Unlike vectors, deque
allows efficient insertion and deletion of elements at both ends using deque::push_back, deque::push_front, deque::pop_front, and deque::pop_back methods which makes deque a better choice when we need to perform these operations frequently.
Example:
// C++ Program to use deque for efficient insertion and
// deletion operations in C++
#include <deque>
#include <iostream>
using namespace std;
int main()
{
deque<int> dq;
// Insert from both ends
dq.push_back(10);
dq.push_front(5);
dq.push_back(15);
// Print deque elements
cout << "Deque Elements: ";
for (int x : dq) {
cout << x << " ";
}
// Remove elements from both ends
dq.pop_back();
dq.pop_front();
// Print deque elements
cout << endl;
cout << "Deque Elements after Deletion: ";
for (int x : dq) {
cout << x << " ";
}
return 0;
}
Output
Deque Elements: 5 10 15 Deque Elements after Deletion: 10
2. Storing Large Objects with Expensive Copy Operations
If we want to store large objects the deque is a better choice than vectors because deque doesn’t require contiguous memory, it can avoid costly memory reallocation and copying during resizing, leading to better performance and reduced overhead compared to vector.
Example:
// C++ Program to store large objects in the deque
#include <deque>
#include <iostream>
#include <string>
using namespace std;
class LargeObject {
private:
int id;
string name;
public:
LargeObject(int id, string name)
{
this->id = id;
this->name = name;
}
// Function to display information about the
// LargeObject
void display() const
{
cout << "ID: " << id << ", Name: " << name << endl;
}
};
int main()
{
deque<LargeObject> dq;
// Add large objects to deque without worrying about
// expensive copying overhead
for (int i = 0; i < 5; ++i) {
dq.push_back(
LargeObject(i, "Object_" + to_string(i)));
}
// Printing information about the objects stored in
// deque
cout << "Deque Elements: " << endl;
for (const auto& obj : dq) {
obj.display();
}
return 0;
}
Output
Deque Elements: ID: 0, Name: Object_0 ID: 1, Name: Object_1 ID: 2, Name: Object_2 ID: 3, Name: Object_3 ID: 4, Name: Object_4
3. Minimizing Reallocation Overhead
Deque allocates memory in smaller chunks whereas in vectors, memory is allocated in contiguous memory locations. This segmented storage approach of deque reduces the need for frequent reallocation and copying of elements when it grows in size dynamically. So, a deque offers better performance in scenarios where dynamic resizing and minimizing reallocation overhead is important.