Double-Ended Queues using std::deque

Performance differences between `std::vector` and `std::deque`

When should I use a `std::deque` instead of a `std::vector` for optimal performance?

Vector art representing computer hardware

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:

1#include <deque>
2#include <vector>
3#include <iostream>
4#include <chrono>
5
6int main() {
7  using std::chrono::high_resolution_clock;
8  const int size = 10000;
9
10  auto start = high_resolution_clock::now();
11  std::deque<int> d;
12  for (int i = 0; i < size; ++i) {
13    d.emplace_front(i);
14  }
15  auto end = high_resolution_clock::now();
16  auto dequeTime = end - start;
17
18  start = high_resolution_clock::now();
19  std::vector<int> v;
20  for (int i = 0; i < size; ++i) {
21    v.emplace(v.begin(), i);
22  }
23  end = high_resolution_clock::now();
24  auto vectorTime = end - start;
25
26  std::cout
27    << "Deque time:  " << dequeTime.count()
28    << "\nVector time: " << vectorTime.count();
29}

1Deque time:  1695200
2Vector time: 6918000

The deque insertion is much faster because it's optimized for this operation.

This Question is from the Lesson:

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

Answers to questions are automatically generated and may not have been reviewed.

7 months ago

This Question is from the Lesson:

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

Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

125 Lessons
550+ Code Samples
96% Positive Reviews
Regularly Updated
Help and FAQ

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Contact|Privacy Policy|Terms of Use

Performance differences between `std::vector` and `std::deque`

When should I use a `std::deque` instead of a `std::vector` for optimal performance?

Double-Ended Queues using `std::deque`

How does a `std::deque` store its elements in memory?

Which `std::deque` operations are exception-safe?

What are the advantages of using `emplace_front()` or `emplace_back()` instead of `push_front()` or `push_back()`?

When do `std::deque` operations invalidate iterators?

Is `std::deque` thread-safe? Can multiple threads access a `deque` concurrently?

Double-Ended Queues using `std::deque`

Professional C++

This course includes:

Professional C++

Performance differences between std::vector and std::deque

When should I use a std::deque instead of a std::vector for optimal performance?

Double-Ended Queues using std::deque

How does a std::deque store its elements in memory?

Which std::deque operations are exception-safe?

What are the advantages of using emplace_front() or emplace_back() instead of push_front() or push_back()?

When do std::deque operations invalidate iterators?

Is std::deque thread-safe? Can multiple threads access a deque concurrently?

Double-Ended Queues using std::deque

Professional C++

This course includes:

Professional C++

Performance differences between `std::vector` and `std::deque`

When should I use a `std::deque` instead of a `std::vector` for optimal performance?

Double-Ended Queues using `std::deque`

How does a `std::deque` store its elements in memory?

Which `std::deque` operations are exception-safe?

What are the advantages of using `emplace_front()` or `emplace_back()` instead of `push_front()` or `push_back()`?

When do `std::deque` operations invalidate iterators?

Is `std::deque` thread-safe? Can multiple threads access a `deque` concurrently?

Double-Ended Queues using `std::deque`