vector_1d_operations.cpp

/*
 * ============================================================================
 *  1D Vector Operations — Comprehensive Demo
 *  File: vector_1d_operations.cpp
 *
 *  Covers all essential std::vector operations for a one-dimensional array:
 *    1. Construction & initialization
 *    2. Adding / removing elements
 *    3. Accessing elements
 *    4. Size, capacity, and memory
 *    5. Iterators & range-based for
 *    6. Searching & finding
 *    7. Sorting & removing duplicates
 *    8. Modifying (insert, erase, swap)
 *    9. Algorithms (accumulate, min/max, count, reverse, rotate)
 *   10. 2D-like usage (vector of vectors) is in the companion file
 *
 *  Compile: g++ -std=c++11 -Wall -o vector_1d_operations vector_1d_operations.cpp
 *  Run:     ./vector_1d_operations
 * ============================================================================
 */

#include <iostream>
#include <vector>
#include <algorithm>   // sort, reverse, find, count, rotate, unique, min/max_element
#include <numeric>     // accumulate, iota
#include <iterator>    // back_inserter, ostream_iterator

using namespace std;

// Helper: print a vector with a label
void printVec(const string& label, const vector<int>& v) {
    cout << label << " [";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) cout << ", ";
        cout << v[i];
    }
    cout << "]  (size=" << v.size() << ", capacity=" << v.capacity() << ")" << endl;
}

int main() {
    cout << "============================================" << endl;
    cout << "  1D std::vector Operations Demo" << endl;
    cout << "============================================\n" << endl;

    // ──────────────────────────────────────────────
    // 1. Construction & Initialization
    // ──────────────────────────────────────────────
    cout << "--- 1. Construction & Initialization ---\n" << endl;

    // Default: empty vector
    vector<int> v1;
    printVec("v1 (default empty)", v1);

    // Fill constructor: 5 elements, all initialized to 0
    vector<int> v2(5);
    printVec("v2 (5 zeros)", v2);

    // Fill constructor with value: 5 elements, all set to 42
    vector<int> v3(5, 42);
    printVec("v3 (5 x 42)", v3);

    // Initializer list (C++11)
    vector<int> v4 = {10, 20, 30, 40, 50};
    printVec("v4 (init list)", v4);

    // Copy constructor
    vector<int> v5(v4);
    printVec("v5 (copy of v4)", v5);

    // From a range (another container's iterators)
    vector<int> v6(v4.begin() + 1, v4.begin() + 4);  // elements at index 1,2,3
    printVec("v6 (range [1,4) of v4)", v6);

    // Using iota to fill with consecutive values 0,1,2,...,9
    vector<int> v7(10);
    iota(v7.begin(), v7.end(), 0);  // fills with 0, 1, 2, ..., 9
    printVec("v7 (iota 0..9)", v7);

    cout << endl;

    // ──────────────────────────────────────────────
    // 2. Adding & Removing Elements
    // ──────────────────────────────────────────────
    cout << "--- 2. Adding & Removing Elements ---\n" << endl;

    vector<int> v = {1, 2, 3};
    printVec("initial", v);

    // push_back: add to the end — O(1) amortized
    v.push_back(4);
    v.push_back(5);
    printVec("after push_back(4,5)", v);

    // emplace_back: construct in-place at the end (avoids copy) — O(1) amortized
    v.emplace_back(6);
    printVec("after emplace_back(6)", v);

    // pop_back: remove last element — O(1)
    v.pop_back();
    printVec("after pop_back()", v);

    // clear: remove all elements — O(N)
    vector<int> temp = {99, 88, 77};
    printVec("temp before clear", temp);
    temp.clear();
    printVec("temp after clear", temp);

    cout << endl;

    // ──────────────────────────────────────────────
    // 3. Accessing Elements
    // ──────────────────────────────────────────────
    cout << "--- 3. Accessing Elements ---\n" << endl;

    printVec("v", v);

    // operator[]: no bounds checking — fastest
    cout << "v[0] = " << v[0] << ",  v[2] = " << v[2] << endl;

    // .at(): with bounds checking — throws std::out_of_range if invalid
    cout << "v.at(1) = " << v.at(1) << endl;

    // .front() and .back(): first and last element
    cout << "v.front() = " << v.front() << ",  v.back() = " << v.back() << endl;

    // .data(): raw pointer to underlying array
    int* raw = v.data();
    cout << "v.data()[3] = " << raw[3] << endl;

    cout << endl;

    // ──────────────────────────────────────────────
    // 4. Size, Capacity, and Memory
    // ──────────────────────────────────────────────
    cout << "--- 4. Size, Capacity, and Memory ---\n" << endl;

    cout << "v.size()     = " << v.size()     << "  (number of elements)" << endl;
    cout << "v.capacity() = " << v.capacity() << "  (allocated slots before realloc)" << endl;
    cout << "v.empty()    = " << (v.empty() ? "true" : "false") << endl;

    // reserve: pre-allocate capacity without changing size
    v.reserve(100);
    cout << "After reserve(100): size=" << v.size() << ", capacity=" << v.capacity() << endl;

    // shrink_to_fit: reduce capacity to match size (C++11, non-binding request)
    v.shrink_to_fit();
    cout << "After shrink_to_fit: size=" << v.size() << ", capacity=" << v.capacity() << endl;

    // resize: change size (adds default elements or truncates)
    v.resize(8, 0);  // extend to 8 elements, new ones = 0
    printVec("After resize(8, 0)", v);

    v.resize(4);  // truncate to 4 elements
    printVec("After resize(4)", v);

    cout << endl;

    // ──────────────────────────────────────────────
    // 5. Iterators & Range-based For
    // ──────────────────────────────────────────────
    cout << "--- 5. Iterators & Range-based For ---\n" << endl;

    v = {10, 20, 30, 40, 50};

    // Forward iteration with iterator
    cout << "Forward (iterator):  ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // Reverse iteration with reverse_iterator
    cout << "Reverse (rbegin):    ";
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;

    // Range-based for loop (C++11) — cleanest syntax
    cout << "Range-based for:     ";
    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;

    // Const reference to avoid copying
    cout << "Const ref for:       ";
    for (const int& x : v) {
        cout << x << " ";
    }
    cout << endl;

    // Modify in-place using reference
    for (int& x : v) {
        x *= 2;  // double each element
    }
    printVec("After doubling", v);

    cout << endl;

    // ──────────────────────────────────────────────
    // 6. Searching & Finding
    // ──────────────────────────────────────────────
    cout << "--- 6. Searching & Finding ---\n" << endl;

    v = {5, 3, 8, 1, 9, 3, 7, 3};
    printVec("v", v);

    // std::find — returns iterator to first occurrence, or v.end() if not found
    auto it = find(v.begin(), v.end(), 8);
    if (it != v.end()) {
        cout << "find(8): found at index " << (it - v.begin()) << endl;
    }

    it = find(v.begin(), v.end(), 99);
    cout << "find(99): " << (it == v.end() ? "not found" : "found") << endl;

    // std::count — count occurrences
    int cnt = count(v.begin(), v.end(), 3);
    cout << "count(3) = " << cnt << endl;

    // std::find_if — find first element satisfying a predicate
    auto itEven = find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
    if (itEven != v.end()) {
        cout << "First even element: " << *itEven << " at index " << (itEven - v.begin()) << endl;
    }

    // binary_search — requires sorted range! Returns bool only.
    vector<int> sorted_v = v;
    sort(sorted_v.begin(), sorted_v.end());
    printVec("sorted_v", sorted_v);
    cout << "binary_search(7) = " << (binary_search(sorted_v.begin(), sorted_v.end(), 7) ? "true" : "false") << endl;

    // lower_bound — iterator to first element >= value (sorted range)
    auto lb = lower_bound(sorted_v.begin(), sorted_v.end(), 5);
    cout << "lower_bound(5) → index " << (lb - sorted_v.begin()) << ", value " << *lb << endl;

    cout << endl;

    // ──────────────────────────────────────────────
    // 7. Sorting & Removing Duplicates
    // ──────────────────────────────────────────────
    cout << "--- 7. Sorting & Removing Duplicates ---\n" << endl;

    v = {5, 3, 8, 1, 9, 3, 7, 3};
    printVec("original", v);

    // sort ascending
    sort(v.begin(), v.end());
    printVec("sorted ascending", v);

    // sort descending using greater<int>
    sort(v.begin(), v.end(), greater<int>());
    printVec("sorted descending", v);

    // sort with custom comparator (by absolute value)
    vector<int> neg = {-5, 3, -1, 4, -2};
    sort(neg.begin(), neg.end(), [](int a, int b) { return abs(a) < abs(b); });
    printVec("sorted by |x|", neg);

    // Remove duplicates: sort first, then use unique + erase
    v = {5, 3, 8, 1, 9, 3, 7, 3};
    sort(v.begin(), v.end());
    // unique moves duplicates to the end, returns iterator to new logical end
    auto newEnd = unique(v.begin(), v.end());
    v.erase(newEnd, v.end());
    printVec("unique (sorted)", v);

    cout << endl;

    // ──────────────────────────────────────────────
    // 8. Insert, Erase, Swap
    // ──────────────────────────────────────────────
    cout << "--- 8. Insert, Erase, Swap ---\n" << endl;

    v = {10, 20, 30, 40, 50};
    printVec("original", v);

    // insert single element before index 2 — O(N) due to shifting
    v.insert(v.begin() + 2, 25);
    printVec("insert 25 at idx 2", v);

    // insert multiple copies
    v.insert(v.begin(), 3, 0);  // insert three 0s at the front
    printVec("insert 3x0 at front", v);

    // erase single element at index 4 — O(N)
    v.erase(v.begin() + 4);
    printVec("erase at idx 4", v);

    // erase a range [begin+1, begin+3)
    v.erase(v.begin() + 1, v.begin() + 3);
    printVec("erase range [1,3)", v);

    // swap two vectors — O(1), just swaps internal pointers
    vector<int> a = {1, 2, 3};
    vector<int> b = {9, 8, 7, 6};
    printVec("a before swap", a);
    printVec("b before swap", b);
    a.swap(b);
    printVec("a after swap", a);
    printVec("b after swap", b);

    cout << endl;

    // ──────────────────────────────────────────────
    // 9. Algorithms (accumulate, min/max, reverse, rotate)
    // ──────────────────────────────────────────────
    cout << "--- 9. Algorithms ---\n" << endl;

    v = {3, 1, 4, 1, 5, 9, 2, 6};
    printVec("v", v);

    // accumulate: sum of all elements
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "sum (accumulate) = " << sum << endl;

    // accumulate with custom op: product
    long long product = accumulate(v.begin(), v.end(), 1LL, multiplies<long long>());
    cout << "product = " << product << endl;

    // min_element / max_element
    auto minIt = min_element(v.begin(), v.end());
    auto maxIt = max_element(v.begin(), v.end());
    cout << "min = " << *minIt << " at index " << (minIt - v.begin()) << endl;
    cout << "max = " << *maxIt << " at index " << (maxIt - v.begin()) << endl;

    // reverse
    reverse(v.begin(), v.end());
    printVec("reversed", v);

    // rotate: move first 3 elements to the back
    v = {1, 2, 3, 4, 5};
    rotate(v.begin(), v.begin() + 3, v.end());
    printVec("rotate left by 3", v);  // [4, 5, 1, 2, 3]

    // fill: set all elements to a value
    fill(v.begin(), v.end(), 7);
    printVec("fill with 7", v);

    cout << "\n============================================" << endl;
    cout << "  Done." << endl;
    cout << "============================================" << endl;

    return 0;
}