#include <vector>

// `data` is used as a plain fixed-size block of memory: we never call its
// own pop_back or push_back, we manage size and capacity ourselves.
class Vector {
public:
    std::vector<int> data;
    int capacity;
    int size;
    int copies = 0;

    Vector(const std::vector<int>& block, int size)
        : data(block), capacity((int)block.size()), size(size) {}

    // The caller makes sure size > 0 before popping.
    void popBack() {
        size--;
        if (size * 4 <= capacity && capacity >= 4) {
            std::vector<int> smaller(capacity / 2);
            for (int i = 0; i < size; i++) {
                smaller[i] = data[i];
                copies++;
            }
            data = smaller;
            capacity = (int)smaller.size();
        }
    }

    int popMany(int pops) {
        for (int k = 0; k < pops; k++) {
            popBack();
        }
        return copies;
    }
};
More from Dynamic Arrays
