✅ 1. Basic Initialization

cppCopyEditlist<int> l = {10, 20, 30};

---

✅ 2. Accessing Elements (No [] indexing)

cppCopyEditauto it = l.begin();
advance(it, 2);     // move to 3rd element
cout << *it;        // Output: 30

---

✅ 3. Modifying Value at Position

cppCopyEditadvance(it, 1);     // move to index 1
*it = 999;          // modify element
// l: 10 999 30

---

✅ 4. Modifying Value by Condition

cppCopyEditfor (auto& x : l)
    if (x == 30) x = 888;
// l: 10 999 888

---

✅ 5. Insert Elements

cppCopyEditauto it = next(l.begin(), 1);
l.insert(it, 77);     
// l: 10 77 999 888

---

✅ 6. Erase Single or Multiple Elements

cppCopyEditl.erase(next(l.begin(), 2));         
// removes element at index 2
// l: 10 77 888

l.erase(next(l.begin()), next(l.begin(), 3)); 
// removes from index 1 to 2 (77, 888)
// l: 10

---

✅ 7. Splice (Move elements from one list to another)

cppCopyEditlist<int> a = {1, 2, 3};
list<int> b = {4, 5};
a.splice(next(a.begin()), b);
// a: 1 4 5 2 3 | b: (empty)

---

✅ 8. Reverse Iterators + next()

cppCopyEditauto rit = l.rbegin();        // points to last
cout << *rit;                 // Output: last element

cout << *next(rit);           // Output: second last element

---

✅ 9. Difference: advance vs next

cppCopyEditauto it = l.begin();
advance(it, 2);     // it is now moved (changed)

auto it2 = next(l.begin(), 2); // it2 is a new moved iterator

---

✅ 10. List vs Vector – Feature Comparison

---

✅ 11. Extra Useful List Functions

cppCopyEditl.push_front(5);           // insert at front
l.pop_front();             // remove from front
l.sort();                  // sort elements
l.unique();                // remove consecutive duplicates
l.remove(20);              // remove all 20s
l.reverse();               // reverse the list

---

✅ 12. Converting list to vector for index access

cppCopyEditvector<int> v(l.begin(), l.end());
cout << v[1]; // now indexable

---

---

🔥 std::deque in C++

---

🔷 WHAT IS A DEQUE?

• Deque stands for Double Ended Queue.

• It is a sequence container from the C++ Standard Template Library (<deque>) that allows:

  • Fast insertion and deletion at both the front and the back.

• Pronounced: "deck"

---

🔷 HEADER FILE

cppCopyEdit#include <deque>

---

🔷 SYNTAX

cppCopyEditstd::deque<type> dequeName;

Example:

cppCopyEditstd::deque<int> dq;

---

🔷 INTERNAL STRUCTURE

• Not a contiguous memory container (unlike vector).

• Internally implemented as a map of blocks or array of pointers to arrays.

• This allows fast insertions/removals at both ends, unlike vector which is optimized for the back only.

---

🔷 TIME COMPLEXITY

---

🔷 KEY FUNCTIONS

✅ Basic Operations

cppCopyEditpush_back(val);   // Adds to back
push_front(val);  // Adds to front
pop_back();       // Removes from back
pop_front();      // Removes from front

✅ Element Access

cppCopyEditdq[i];            // Access via index
dq.at(i);         // Bounds-checked access
dq.front();       // First element
dq.back();        // Last element

✅ Capacity

cppCopyEditdq.empty();       // Returns true if empty
dq.size();        // Number of elements
dq.max_size();    // Maximum possible number of elements

✅ Modifiers

cppCopyEditdq.clear();                // Removes all elements
dq.insert(pos, val);       // Inserts before pos
dq.insert(pos, n, val);    // Inserts n copies
dq.insert(pos, first, last); // Inserts range

dq.erase(pos);             // Erase at pos
dq.erase(first, last);     // Erase range

dq.resize(n);              // Resize to n elements
dq.resize(n, val);         // Resize to n elements with default val

dq.swap(other);            // Swaps content with other deque

✅ Iterators

cppCopyEditbegin();       // Iterator to beginning
end();         // Iterator to end
rbegin();      // Reverse iterator to end
rend();        // Reverse iterator to beginning
cbegin();      // Const iterator
cend();        // Const end

---

🔷 EXAMPLES

🔹 Basic Usage

cppCopyEdit#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    dq.push_back(10);
    dq.push_front(20);
    dq.push_back(30);

    for (int x : dq)
        std::cout << x << " ";  // Output: 20 10 30

    dq.pop_front(); // removes 20

    std::cout << dq.front();  // Output: 10
}

🔹 Using Iterators

cppCopyEditfor (std::deque<int>::iterator it = dq.begin(); it != dq.end(); ++it) {
    std::cout << *it << " ";
}

🔹 Sort a Deque

cppCopyEdit#include <algorithm>
std::sort(dq.begin(), dq.end());

---

🔷 ADVANTAGES

• Fast insertion/removal at both ends.

• Provides random access like a vector.

• Good choice when:

  • You frequently add/remove elements from both ends.

  • You need fast indexed access.

---

🔷 DISADVANTAGES

• Slower insertions/deletions in the middle compared to linked lists.

• Not cache-friendly like vector due to non-contiguous memory.

• Slightly more memory overhead than vectors due to block storage.

---

🔷 COMPARISON TABLE

---

🔷 NOTES

• std::deque is the underlying container for std::stack and std::queue by default.

• Can be used with algorithms from <algorithm> (like sort, find, etc.) because it supports random access iterators.

• Avoid shrink_to_fit() — not supported in deque (as of current standards).

---

🔷 C++20 & BEYOND

• C++20 adds:

  • Ranges support via <ranges>

  • Use with views::filter, views::transform, etc.

Example:

cppCopyEdit#include <ranges>
auto even = dq | std::views::filter([](int x){ return x % 2 == 0; });

---

🔷 TEMPLATE SIGNATURE

cppCopyEdittemplate<
    class T,
    class Allocator = std::allocator<T>
> class deque;

So you can also provide your own memory allocator if needed.

---

🔷 TRAPS TO AVOID

• Don’t assume contiguous memory — &dq[0] and &dq[1] may not be adjacent.

• Don’t iterate and modify at the same time.

• Don’t use std::deque<bool> — it's a special case like vector<bool> that uses bit-packing (inefficient for certain operations).

---

🔷 RELATED CONTAINERS

• std::vector — better for back insertions and contiguous access.

• std::list — better for frequent insertions/removals at arbitrary positions.

• std::forward_list — single-linked list (only forward traversal).

---

🔷 WHEN TO USE DEQUE

✅ Use when:

• You need both front and back insertions/removals.

• You need random access.

• You don't care about memory contiguity.

❌ Avoid when:

• You only insert at the back → use vector.

• You heavily modify the middle → use list.