C++: What is the difference between std::deque and std::vector?

deque — double-ended queue. vector — dynamic array.

std::deque:

• Double-ended.
• O(1) push_front/pop_front.
• Multiple internal blocks.
• Random access O(1).

1std::deque<int> dq = {1, 2, 3};
2dq.push_front(0);  // O(1)
3dq.push_back(4);   // O(1)
4dq[2] = 10;        // O(1)

std::vector:

• Single contiguous block.
• O(1) push_back.
• No push_front.
• Random access O(1).

1std::vector<int> v = {1, 2, 3};
2v.push_back(4);  // O(1)
3// v.push_front(0);  // Error!

When to use deque:

• Need both ends insertion.
• Queue/stack implementation.