Sequence Containers: vector, deque, list, array

#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums;          // empty vector
    nums.reserve(100);              // pre-allocate for 100 elements (no reallocation)

    for (int i = 0; i < 10; ++i) {
        nums.push_back(i * i);      // amortized O(1)
    }

    // Size vs capacity
    std::cout << "Size:     " << nums.size()     << '\n';  // 10
    std::cout << "Capacity: " << nums.capacity() << '\n';  // >= 100

    // Random access — O(1)
    std::cout << "Element 3: " << nums[3] << '\n';         // 9
    std::cout << "Element 3: " << nums.at(3) << '\n';      // 9 (bounds-checked)

    // Erase-remove idiom (pre-C++20)
    nums.erase(std::remove_if(nums.begin(), nums.end(),
                              [](int x) { return x > 50; }),
               nums.end());

    // C++20: std::erase_if (cleaner)
    std::erase_if(nums, [](int x) { return x > 30; });

    // Range-based for loop
    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

#include <deque>
#include <list>
#include <forward_list>
#include <iostream>

int main() {
    // deque — O(1) push_front and push_back
    std::deque<int> dq;
    dq.push_front(1);   // O(1) — vector cannot do this efficiently
    dq.push_back(2);    // O(1)
    dq.push_front(0);   // O(1)
    // dq: {0, 1, 2}

    // list — O(1) insert/erase at any position with iterator
    std::list<std::string> names = {"Alice", "Charlie", "Eve"};
    auto it = std::next(names.begin());  // points to "Charlie"
    names.insert(it, "Bob");             // O(1) insert before "Charlie"
    names.erase(it);                     // O(1) erase "Charlie"
    // names: {"Alice", "Bob", "Eve"}

    // list has splice — O(1) move of entire sublists
    std::list<std::string> more = {"Frank", "Grace"};
    names.splice(names.end(), more);     // moves all of 'more' into 'names'
    // names: {"Alice", "Bob", "Eve", "Frank", "Grace"}
    // more is now empty

    // forward_list — singly linked, no size(), push_front only
    std::forward_list<int> fl = {3, 1, 4, 1, 5};
    fl.push_front(0);
    fl.sort();           // member sort — O(n log n), stable
    fl.unique();         // remove consecutive duplicates
    // fl: {0, 1, 3, 4, 5}

    for (int v : fl) std::cout << v << ' ';
    std::cout << '\n';
}

#include <array>
#include <algorithm>
#include <iostream>

int main() {
    std::array<int, 5> arr = {5, 2, 8, 1, 9};

    std::sort(arr.begin(), arr.end());       // works with STL algorithms

    std::cout << "Size: " << arr.size() << '\n';   // constexpr — known at compile time
    std::cout << "Front: " << arr.front() << '\n';  // 1
    std::cout << "Back:  " << arr.back()  << '\n';  // 9

    // Bounds-checked access
    try {
        arr.at(10);  // throws std::out_of_range
    } catch (const std::out_of_range& e) {
        std::cout << "Out of range: " << e.what() << '\n';
    }

    // Compile-time size via std::tuple_size
    constexpr std::size_t n = std::tuple_size_v<decltype(arr)>;  // 5
    static_assert(n == 5);
}