#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>   // for std::accumulate
#include <iterator>  // for std::distance
#include <cassert>   // for assert

// Helper function: print vector contents
template<typename T>
void print(const std::vector<T>& v, const std::string& name = "") {
    if (!name.empty()) std::cout << name << ": ";
    std::cout << "[ ";
    for (const auto& elem : v) std::cout << elem << " ";
    std::cout << "]\n";
}

// Helper function: print vector capacity info
template<typename T>
void print_capacity_info(const std::vector<T>& v, const std::string& name = "") {
    if (!name.empty()) std::cout << name << " - ";
    std::cout << "size = " << v.size() << ", capacity = " << v.capacity() << ", empty = " << std::boolalpha << v.empty() << "\n";
}

int main() {
    // ==================== 1. Construction and initialization ====================
    std::cout << "========== 1. Construction and initialization ==========\n";
    std::vector<int> v1;                    // default construct, empty vector
    std::vector<int> v2(5, 10);             // construct with 5 elements of value 10
    std::vector<int> v3 = {1, 2, 3, 4, 5};  // list initialization (C++11)
    std::vector<int> v4(v3);                // copy construct
    std::vector<int> v5(std::move(v3));     // move construct (v3 becomes empty afterwards)
    std::vector<int> v6(v2.begin(), v2.end() - 2); // range construct (first 3 elements)

    print(v2, "v2");
    print(v5, "v5 (from move of v3)");
    print(v6, "v6 (range construction)");
    std::cout << "v3 after move: "; print(v3, "v3");

    // ==================== 2. Element access ====================
    std::cout << "\n========== 2. Element access ==========\n";
    std::vector<int> vec = {10, 20, 30, 40, 50};
    print(vec, "original vec");

    // operator[] (no bounds checking)
    std::cout << "vec[0] = " << vec[0] << "\n";
    // at() (bounds checked, throws std::out_of_range on invalid access)
    try {
        std::cout << "vec.at(4) = " << vec.at(4) << "\n";
        // std::cout << "vec.at(10) = " << vec.at(10) << "\n"; // out-of-range
    } catch (const std::out_of_range& e) {
        std::cout << "Caught exception: " << e.what() << "\n";
    }

    // front / back
    std::cout << "vec.front() = " << vec.front() << ", vec.back() = " << vec.back() << "\n";

    // data() returns pointer to underlying array
    int* data_ptr = vec.data();
    std::cout << "First element via data(): " << *data_ptr << "\n";

    // ==================== 3. Iterators ====================
    std::cout << "\n========== 3. Iterators ==========\n";
    std::vector<int> it_vec = {1,2,3,4,5};
    // forward iterator
    std::cout << "Forward iteration: ";
    for (auto it = it_vec.begin(); it != it_vec.end(); ++it) std::cout << *it << " ";
    std::cout << "\n";

    // const iterator
    std::cout << "Const iteration: ";
    for (auto it = it_vec.cbegin(); it != it_vec.cend(); ++it) std::cout << *it << " ";
    std::cout << "\n";

    // reverse iterator
    std::cout << "Reverse iteration: ";
    for (auto rit = it_vec.rbegin(); rit != it_vec.rend(); ++rit) std::cout << *rit << " ";
    std::cout << "\n";

    // range-based for loop (C++11)
    std::cout << "Range-based for: ";
    for (int x : it_vec) std::cout << x << " ";
    std::cout << "\n";

    // ==================== 4. Capacity-related ====================
    std::cout << "\n========== 4. Capacity-related ==========\n";
    std::vector<double> cap_vec;
    print_capacity_info(cap_vec, "initial empty vector");

    cap_vec.reserve(10); // reserve capacity to avoid multiple reallocations
    print_capacity_info(cap_vec, "after reserve(10)");

    cap_vec.push_back(1.1);
    cap_vec.push_back(2.2);
    print_capacity_info(cap_vec, "after adding two elements");

    cap_vec.shrink_to_fit(); // request reduction of unused capacity (C++11)
    print_capacity_info(cap_vec, "after shrink_to_fit");

    cap_vec.resize(5, 3.3); // resize, filling new elements with 3.3
    print_capacity_info(cap_vec, "after resize(5, 3.3)");
    print(cap_vec, "contents");

    cap_vec.resize(2); // shrink
    print_capacity_info(cap_vec, "after resize(2)");

    // max_size and empty
    std::cout << "max_size: " << cap_vec.max_size() << "\n";
    std::cout << "empty: " << std::boolalpha << cap_vec.empty() << "\n";

    // ==================== 5. Modifiers ====================
    std::cout << "\n========== 5. Modifiers ==========\n";
    std::vector<int> mod_vec;

    // assign
    mod_vec.assign(3, 7);          // fill with three 7s
    print(mod_vec, "assign(3,7)");
    mod_vec.assign({10,20,30,40}); // initializer list assignment
    print(mod_vec, "assign({10,20,30,40})");

    // push_back / pop_back
    mod_vec.push_back(50);
    print(mod_vec, "push_back(50)");
    mod_vec.pop_back();
    print(mod_vec, "pop_back()");

    // insert
    auto it = mod_vec.begin() + 2;
    mod_vec.insert(it, 99); // insert 99 at position 2
    print(mod_vec, "insert(pos, 99)");

    mod_vec.insert(mod_vec.begin() + 3, 2, 88); // insert two 88s
    print(mod_vec, "insert(pos, 2, 88)");

    std::vector<int> src = {1,2,3};
    mod_vec.insert(mod_vec.end(), src.begin(), src.end()); // insert range
    print(mod_vec, "insert range {1,2,3}");

    // emplace (C++11) construct element in place, avoid copies
    mod_vec.emplace(mod_vec.begin(), 100);
    print(mod_vec, "emplace 100 at beginning");

    // emplace_back
    mod_vec.emplace_back(200);
    print(mod_vec, "emplace_back 200");

    // erase
    mod_vec.erase(mod_vec.begin() + 1); // erase second element
    print(mod_vec, "erase index 1");

    mod_vec.erase(mod_vec.begin() + 2, mod_vec.begin() + 4); // erase range [2,4)
    print(mod_vec, "erase range [2,4)");

    // clear
    mod_vec.clear();
    std::cout << "after clear size = " << mod_vec.size() << "\n";

    // swap
    std::vector<int> a = {1,2,3};
    std::vector<int> b = {4,5,6,7};
    a.swap(b);
    print(a, "a after swap");
    print(b, "b after swap");

    // ==================== 6. Comparison operations ====================
    std::cout << "\n========== 6. Comparison operations ==========\n";
    std::vector<int> cmp1 = {1,2,3};
    std::vector<int> cmp2 = {1,2,3};
    std::vector<int> cmp3 = {1,2,4};
    std::cout << std::boolalpha;
    std::cout << "cmp1 == cmp2: " << (cmp1 == cmp2) << "\n";
    std::cout << "cmp1 != cmp3: " << (cmp1 != cmp3) << "\n";
    std::cout << "cmp1 <  cmp3: " << (cmp1 < cmp3) << "\n"; // lexicographical order

    // ==================== 7. Algorithms with vector ====================
    std::cout << "\n========== 7. Algorithms with vector ==========\n";
    std::vector<int> alg_vec = {5,2,8,1,9,3};
    print(alg_vec, "original");

    // sort
    std::sort(alg_vec.begin(), alg_vec.end());
    print(alg_vec, "after ascending sort");

    // reverse
    std::reverse(alg_vec.begin(), alg_vec.end());
    print(alg_vec, "after reverse");

    // find
    auto find_it = std::find(alg_vec.begin(), alg_vec.end(), 8);
    if (find_it != alg_vec.end())
        std::cout << "Found element 8 at index: " << std::distance(alg_vec.begin(), find_it) << "\n";

    // accumulate (requires <numeric>)
    int sum = std::accumulate(alg_vec.begin(), alg_vec.end(), 0);
    std::cout << "sum of elements: " << sum << "\n";

    // remove specific value (erase-remove idiom)
    alg_vec.erase(std::remove(alg_vec.begin(), alg_vec.end(), 5), alg_vec.end());
    print(alg_vec, "after removing all 5s");

    // unique (remove duplicates after sorting)
    std::vector<int> dup_vec = {1,1,2,3,3,3,4};
    std::sort(dup_vec.begin(), dup_vec.end());
    auto last = std::unique(dup_vec.begin(), dup_vec.end());
    dup_vec.erase(last, dup_vec.end());
    print(dup_vec, "after removing duplicates");

    // ==================== 8. Other advanced features ====================
    std::cout << "\n========== 8. Other advanced features ==========\n";

    // vector<bool> specialization (bit-packed, not ideal as a normal container)
    std::vector<bool> bool_vec = {true, false, true};
    std::cout << "vector<bool>: ";
    for (bool b : bool_vec) std::cout << b << " ";
    std::cout << "\n";

    // concise iterator insertion and deletion
    std::vector<int> demo = {10,20,30,40};
    // insert one element
    demo.insert(demo.begin() + 2, 25);
    print(demo, "after inserting 25");
    // remove even numbers
    for (auto it = demo.begin(); it != demo.end(); ) {
        if (*it % 2 == 0) it = demo.erase(it);
        else ++it;
    }
    print(demo, "after removing even numbers");

    // use emplace_back to construct complex objects (Point example)
    struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} };
    std::vector<Point> points;
    points.emplace_back(1, 2);  // pass constructor arguments directly
    points.emplace_back(3, 4);
    std::cout << "emplace_back constructing Point: ";
    for (const auto& p : points) std::cout << "(" << p.x << "," << p.y << ") ";
    std::cout << "\n";

    // exception safety demonstration (show possible exception usage; real code should use try-catch)
    std::vector<int> safe_vec = {1,2,3};
    try {
        // reserve may throw std::bad_alloc if memory is insufficient
        safe_vec.reserve(1000000000000ULL); // likely to throw
    } catch (const std::bad_alloc& e) {
        std::cout << "Memory allocation exception: " << e.what() << "\n";
    }

    // ==================== End ====================
    std::cout << "\nAll examples complete!\n";
    return 0;
}