By now, you've probably spent most of your time with std::vector. It's the default for a reason—it's fast and cache-friendly. But in the real world, you'll run into scenarios where a vector is actually the wrong tool, especially if you're doing a lot of inserting or removing elements from the front of your collection. That's where std::deque and std::list come in.

To show you how these actually differ in practice, let's build a simple Recent Actions Log for a hypothetical text editor. We want to keep track of the last 10 things the user did, and we want to be able to remove specific entries if the user "undoes" a specific action out of order.

Handling the "Sliding Window" with Deque

First, I need a way to store the actions. Since I only care about the most recent 10, I'll be pushing new actions to the back and popping the oldest ones off the front. If I used a vector, pop_front would require shifting every single other element over by one, which is a performance nightmare.

#include <iostream>
#include <deque>
#include <string>

std::deque<std::string> actionLog;

void addAction(const std::string& action) {
    actionLog.push_back(action);
    if (actionLog.size() > 10) {
        actionLog.pop_front(); // Efficiently remove the oldest entry
    }
}

A std::deque (double-ended queue) is perfect here. Unlike a vector, it doesn't store everything in one giant contiguous block of memory. Instead, it uses a series of smaller chunks. This makes adding or removing from either end very cheap.

The Pivot to List for Mid-Log Deletions

Now, let's say our editor gets a new feature: the user can right-click a specific action in the log and delete it, regardless of where it sits in the timeline. While you could do this with a deque, deleting from the middle still requires shifting elements.

This is where std::list shines. A list is a doubly-linked list. Every element is its own node with a pointer to the next and previous one. To delete something, you just snap the pointers around it. Let's swap our deque for a list.

#include <list>

std::list<std::string> actionLogList;

void addActionToList(const std::string& action) {
    actionLogList.push_back(action);
    if (actionLogList.size() > 10) {
        actionLogList.pop_front();
    }
}

A Classic Mistake: Trying to Index a List

Here is where I usually trip up when I'm switching gears between vectors and lists. I wanted to print the third item in the log to verify a deletion, so I instinctively wrote this:

// This will NOT compile!
std::cout < "The third action was: " < actionLogList[2] < std::endl;

I forgot that std::list does not support random access. There is no [] operator because the computer doesn't know where the third node is without starting at the head and following the pointers. I have to use an iterator instead.

Here is the fix. I'll use std::next to move the iterator forward from the beginning:

#include <iterator>

auto it = actionLogList.begin();
std::advance(it, 2); // Move the iterator to the 3rd element
std::cout < "The third action was: " < *it < std::endl;

Choosing Between the Two

So, which one should you actually use? I generally follow this rule of thumb: if you only need to add/remove from the ends, use std::deque. It's faster for traversal and more memory-efficient than a list. If you find yourself constantly inserting or erasing elements in the middle of a large collection, std::list is your best friend. Just remember that you lose the ability to jump directly to an index.

📋 Practical Task

Implementing a Selective Undo History

Build a program that simulates a command history for a drawing app. Your program should:

• Use a std::list<std::string> to store a history of commands (e.g., "Draw Line", "Fill Circle", "Erase Segment").
• Implement a function addCommand(std::string cmd) that adds a command to the end and ensures the list never exceeds 5 items.
• Implement a function removeCommand(std::string cmd) that searches for a specific command string in the list and removes all occurrences of it using an iterator.
• Print the final history to the console after adding 7 different commands and removing one specific command that appears twice.