Array and Vector

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    // Suppose we will read n numbers and build their prefix sums.
9
    int n = 10;
10
    vector<int> a;            // size = 0, capacity = 0
11
    a.reserve(n);             // Ensure at least n capacity; size still 0
12
13
    // Push numbers 1..n
14
    for (int i = 1; i <= n; ++i) {
15
        a.push_back(i);       // amortized O(1)
16
    }
17
18
    // Show size and capacity
19
    cout << "size=" << a.size() << " capacity=" << a.capacity() << "\n";
20
21
    // Build prefix sums into another vector using resize (we want n elements constructed)
22
    vector<long long> pref;
23
    pref.resize(n, 0);        // logical size becomes n, all elements initialized to 0
24
    for (int i = 0; i < n; ++i) {
25
        pref[i] = (i == 0 ? 0LL : pref[i-1]) + a[i];
26
    }
27
28
    cout << "prefix sums: ";
29
    for (int i = 0; i < n; ++i) cout << pref[i] << (i+1==n?'\n':' ');
30
31
    // Demonstrate at() vs operator[]
32
    try {
33
        cout << "a.at(3)=" << a.at(3) << "\n";      // bounds-checked
34
        // cout << a.at(100) << "\n";               // would throw out_of_range
35
    } catch (const out_of_range &e) {
36
        cout << "out_of_range: " << e.what() << "\n";
37
    }
38
39
    // Erase last 3 elements using pop_back
40
    for (int k = 0; k < 3; ++k) a.pop_back(); // O(1) each
41
    cout << "after pop_back x3, size=" << a.size() << " capacity=" << a.capacity() << "\n";
42
43
    // If memory is tight and we won't push more, we can request shrink
44
    a.shrink_to_fit(); // non-binding; may reduce capacity
45
    cout << "after shrink_to_fit, size=" << a.size() << " capacity=" << a.capacity() << "\n";
46
47
    return 0;
48
}
49

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute a simple 2D operation: sum of 4-neighbors for each cell.
5
// Shows both nested vectors and a flat representation.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int R = 4, C = 5;
12
13
    // Approach 1: vector<vector<int>> (easy, but rows are discontiguous)
14
    vector<vector<int>> grid(R, vector<int>(C, 1)); // fill with 1s
15
16
    auto in_bounds = [&](int r, int c){ return 0 <= r && r < R && 0 <= c && c < C; };
17
18
    vector<vector<int>> neigh_sum1(R, vector<int>(C, 0));
19
    for (int r = 0; r < R; ++r) {
20
        for (int c = 0; c < C; ++c) {
21
            int s = 0;
22
            const int dr[4] = {-1, 1, 0, 0};
23
            const int dc[4] = {0, 0, -1, 1};
24
            for (int k = 0; k < 4; ++k) {
25
                int nr = r + dr[k], nc = c + dc[k];
26
                if (in_bounds(nr, nc)) s += grid[nr][nc];
27
            }
28
            neigh_sum1[r][c] = s;
29
        }
30
    }
31
32
    // Approach 2: flat vector with row-major indexing (contiguous, cache-friendly)
33
    vector<int> flat(R * C, 1);
34
    auto idx = [&](int r, int c){ return r * C + c; };
35
36
    vector<int> neigh_sum2(R * C, 0);
37
    for (int r = 0; r < R; ++r) {
38
        for (int c = 0; c < C; ++c) {
39
            int s = 0;
40
            if (r-1 >= 0) s += flat[idx(r-1, c)];
41
            if (r+1 <  R) s += flat[idx(r+1, c)];
42
            if (c-1 >= 0) s += flat[idx(r, c-1)];
43
            if (c+1 <  C) s += flat[idx(r, c+1)];
44
            neigh_sum2[idx(r, c)] = s;
45
        }
46
    }
47
48
    // Print one cell from each to show same result
49
    cout << "neigh_sum1[2][3]=" << neigh_sum1[2][3] << "\n";
50
    cout << "neigh_sum2[2,3]=" << neigh_sum2[idx(2,3)] << "\n";
51
52
    return 0;
53
}
54

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Build compressed ranks for an array and support mapping and inverse mapping.
5
6
int main() {
7
    ios::sync_with_stdio(false);
8
    cin.tie(nullptr);
9
10
    vector<long long> a = {1000, -5, 1000, 42, 42, 7};
11
12
    // 1) Build sorted unique values U
13
    vector<long long> U = a;
14
    sort(U.begin(), U.end());
15
    U.erase(unique(U.begin(), U.end()), U.end()); // now strictly increasing
16
17
    // 2) Map each element to its rank with lower_bound (binary search)
18
    vector<int> rank_of(a.size());
19
    for (size_t i = 0; i < a.size(); ++i) {
20
        int r = int(lower_bound(U.begin(), U.end(), a[i]) - U.begin());
21
        rank_of[i] = r; // 0..U.size()-1
22
    }
23
24
    // 3) Optionally, build inverse mapping: from rank to value is just U[r]
25
26
    // Print results
27
    cout << "unique values (U): ";
28
    for (auto x : U) cout << x << ' '; cout << "\n";
29
    cout << "ranks: ";
30
    for (auto r : rank_of) cout << r << ' '; cout << "\n";
31
32
    // Example query: compress and decompress a value
33
    long long x = 42;
34
    int rx = int(lower_bound(U.begin(), U.end(), x) - U.begin());
35
    cout << "x=42 -> rank=" << rx << ", inverse(U[rank])=" << U[rx] << "\n";
36
37
    // After compression, you can build Fenwick/segment trees with size = U.size()
38
39
    return 0;
40
}
41

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    vector<int> v;
9
    v.reserve(1); // start small to observe growth
10
11
    const int N = 32; // small demo size; grow and watch capacity and data pointer
12
    const int* last_ptr = v.data();
13
14
    for (int i = 0; i < N; ++i) {
15
        v.push_back(i);
16
        const int* cur_ptr = v.data();
17
        if (cur_ptr != last_ptr) {
18
            cout << "reallocated: size=" << v.size() << " capacity=" << v.capacity() << "\n";
19
            last_ptr = cur_ptr;
20
        }
21
    }
22
23
    // Demonstrate iterator invalidation
24
    // WARNING: This is just to illustrate; do not use invalid iterators in practice.
25
    // Acquire an iterator, then cause possible reallocation, then reacquire.
26
    auto it = v.begin();
27
    size_t idx = it - v.begin();
28
    v.push_back(999); // may reallocate -> 'it' potentially invalid now
29
    it = v.begin() + idx; // reacquire using index
30
    cout << "value at original index after growth=" << *it << "\n";
31
32
    // Show shrink_to_fit possibly reducing capacity
33
    size_t old_cap = v.capacity();
34
    v.erase(v.begin() + 5, v.end()); // keep only first 5 elements
35
    v.shrink_to_fit(); // request capacity reduction
36
    cout << "after shrink: size=" << v.size() << " capacity=" << v.capacity() << " (was " << old_cap << ")\n";
37
38
    return 0;
39
}
40