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:

#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) {
  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;

    << "Deque time:  " << dequeTime.count()
    << "\nVector time: " << vectorTime.count();
Deque time:  1695200
Vector time: 6918000

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

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

Free, Unlimited Access

Professional C++

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

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved