C++ List and Deque

Besides vector, the standard library has two other sequence containers. std::deque (double-ended queue) is fast at both ends. std::list is a doubly linked list, fast at inserting and removing anywhere once you have a position.

deque

A deque supports push_front and pop_front as well as push_back and pop_back, and still allows indexing with [].

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {2, 3};
    d.push_front(1);
    d.push_back(4);
    for (int x : d) std::cout << x << " ";
    std::cout << "\n";
    d.pop_front();
    std::cout << "front " << d.front() << ", d[1] = " << d[1] << "\n";
    return 0;
}

1 2 3 4 
front 2, d[1] = 3

A deque suits queues of tasks or a sliding window over data, where elements arrive at one end and leave at the other.

list

A list stores each element in its own node, linked to the previous and the next. It has no indexing, but inserting or removing in the middle is quick and does not move the other elements. It also has useful member functions such as sort, remove and reverse.

#include <algorithm>
#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> tasks = {"wash", "cook", "read"};
    tasks.push_front("wake up");
    auto it = tasks.begin();
    ++it;                               // the second position
    tasks.insert(it, "exercise");
    tasks.remove("cook");
    tasks.sort();
    for (const auto& t : tasks) std::cout << t << ", ";
    std::cout << "\n" << tasks.size() << " tasks\n";
    return 0;
}

exercise, read, wake up, wash, 
4 tasks

Which container?

In practice vector wins far more often than you might expect, because its elements sit next to each other in memory, which modern processors read very fast. Start with vector, and switch only when you have a reason.

Practice exercises

1. Use a deque as a queue: add five customer names at the back and serve them from the front.
2. Keep a deque of the last three numbers the user typed, dropping the oldest when a fourth arrives.
3. Remove every even number from a list<int> with remove_if and a lambda.