Performance differences between std::vector and std::deque
When should I use a std::deque instead of a std::vector for optimal performance?
The choice between std::deque and std::vector depends on your specific use case. Here are some guidelines:
Use a std::deque when:
- You need to frequently insert or remove elements from the front of the container
- You don't need the cache-friendly contiguous memory layout provided by
std::vector
Use a std::vector when:
- You primarily access elements by their position index
- You want the best possible performance for iteration and random access
- You don't need to frequently insert or remove elements from the front
Here's an example demonstrating the performance difference for inserting at the front:
#include <deque>
#include <vector>
#include <iostream>
#include <chrono>
int main() {
using std::chrono::high_resolution_clock;
const int size = 10000;
auto start = high_resolution_clock::now();
std::deque<int> d;
for (int i = 0; i < size; ++i) {
d.emplace_front(i);
}
auto end = high_resolution_clock::now();
auto dequeTime = end - start;
start = high_resolution_clock::now();
std::vector<int> v;
for (int i = 0; i < size; ++i) {
v.emplace(v.begin(), i);
}
end = high_resolution_clock::now();
auto vectorTime = end - start;
std::cout
<< "Deque time: " << dequeTime.count()
<< "\nVector time: " << vectorTime.count();
}Deque time: 1695200
Vector time: 6918000The deque insertion is much faster because it's optimized for this operation.
Double-Ended Queues using std::deque
A guide to double-ended queues - a structure that behaves like a vector, specialised for manipulating objects at the edges of the collection