{ }codelper
动态内存P0158

按两倍增长的数组

自己实现一个存放整数的可增长数组。
数组分别记录元素的个数（大小）和已借来内存的格数（容量）。
一开始大小为 0，容量为 1。
命令有四种。
- push x：如果大小等于容量，先把容量扩大为 2 倍（扩容 1 次），然后把 x 放到末尾。
- pop：如果为空，输出 empty。
否则取出末尾的值并输出；之后如果容量至少为 2，且大小×4 不超过容量，就把容量减半（缩容 1 次）。
- get i：输出从 0 开始数的第 i 个值。
如果 i 不小于大小，输出 out of range。
- info：输出大小和容量，用一个空格隔开。
第一行给出命令数 q，接下来 q 行每行一个命令。
每个命令按上面的规则输出一行，最后一行输出“grow 扩容次数 shrink 缩容次数”。
info 输出的容量始终是按上面的规则得到的值。
C 用 realloc 改变借来的内存块的大小，C++ 自己用变量记下容量，并用 std::vector 的 reserve 预先借好这么多。

输入
1 ≤ q ≤ 100,000，-1,000,000,000 ≤ x ≤ 1,000,000,000，0 ≤ i ≤ 100,000（整数）
输出
每个非 push 命令输出一行，最后一行“grow G shrink S”
样例 1 · stdin
9
push 4
push 8
push 15
info
get 2
pop
pop
info
get 1
stdout
3 4
15
15
8
1 2
out of range
grow 2 shrink 1
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 2 种语言题解

这道题只接受 C、C++。
自己决定借多少格、自己搬运数据是这两种语言的事；Python list、JS 数组、Java ArrayList、C# List<T>、Craykon 的列表都会自动增长（倍数因实现而异：OpenJDK 的 Java ArrayList 是 1.5 倍，.NET 的 C# List<T> 是 2 倍）。
C 的 realloc(p, newcap * sizeof *p) 会扩大或缩小内存块，原地扩不了时会搬到新位置并返回新地址。
失败时返回 NULL，旧块保持不变，所以像 v->data = realloc(v->data, ...) 这样直接覆盖会丢掉旧块。
要先单独检查返回的指针再存进去。
C++ 的 std::vector 也分别有大小 size() 和容量 capacity()，用 reserve(n) 预先扩大。
但标准只保证 reserve(n) 之后容量至少为 n，push_back 自行扩容的倍数也因标准库而异（libstdc++、libc++ 是 2 倍，MSVC 是 1.5 倍）。
所以 C++ 解答自己用变量 cap 记下本题的容量，再用 reserve(cap) 至少借这么多。
按两倍扩容使搬运很少发生，一次 push 的平均代价是 O(1)。
四个陷阱：① 每次只加 1 格，每次 push 都要搬运，总共 O(q²)，容量也和本题的答案不同。
② 大小一降到容量的一半就缩容，在边界来回 push、pop 时会反复扩容又缩容。
等到四分之一再减半，缩容后仍有一半空着。
③ C++ 中不自己记容量、直接相信 capacity()，缩容时就会出错。
reserve 不能减小容量，传入比现在小的值什么也不做。
要真正归还格子，得搬进一个 reserve 了一半的新 vector 再 swap。
shrink_to_fit() 是让容量贴合大小的（不保证执行的）请求，不是减半。
④ std::vector<int> v(1) 不是借一格，而是创建一个值为 0 的元素。
想保持为空只借格子，要用 v.reserve(1)。

C++main.cpp · 53 行
#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    // 용량은 이 문제의 규칙대로 직접 센다.    // capacity()가 돌려주는 값은 표준 라이브러리마다 다를 수 있다(reserve(n) 뒤에는 n 이상이라는 것만 약속된다).    std::size_t cap = 1;    std::vector<int> v;    v.reserve(cap);  // 크기(size)는 0인 채로 적어도 cap칸을 빌려 둔다    int grow = 0, shrink = 0;    int q;    std::cin >> q;    std::string cmd;    for (int i = 0; i < q; i++) {        std::cin >> cmd;        if (cmd == "push") {            int x;            std::cin >> x;            if (v.size() == cap) {  // 가득 찼으면 두 배로: 늘리는 때를 직접 정한다                cap *= 2;                v.reserve(cap);                grow++;            }            v.push_back(x);  // capacity()가 cap 이상이라 여기서는 다시 옮겨 담지 않는다        } else if (cmd == "pop") {            if (v.empty()) {                std::cout << "empty\n";                continue;            }            std::cout << v.back() << '\n';            v.pop_back();  // 크기만 줄고 빌린 칸은 그대로다            if (cap > 1 && v.size() * 4 <= cap) {                cap /= 2;                // reserve는 칸을 줄이지 못한다: 반만큼 빌린 새 vector에 옮겨 담고 맞바꾼다                std::vector<int> smaller;                smaller.reserve(cap);                smaller.assign(v.begin(), v.end());                v.swap(smaller);                shrink++;            }        } else if (cmd == "get") {            std::size_t k;            std::cin >> k;            if (k < v.size()) std::cout << v[k] << '\n';            else std::cout << "out of range\n";        } else {            std::cout << v.size() << ' ' << cap << '\n';        }    }    std::cout << "grow " << grow << " shrink " << shrink << '\n';}
Cmain.c · 68 行
#include <stdio.h>#include <stdlib.h>#include <string.h> /* 직접 만든 늘어나는 배열: data는 cap칸을 빌려 두고, 앞의 size칸만 쓴다 */typedef struct {    int *data;    int size, cap;    int grow, shrink;} IntVec; /* 칸 수를 newcap으로 바꾼다. realloc은 자리를 옮길 수 있어서 돌려받은 포인터를 쓴다 */static void resize(IntVec *v, int newcap) {    int *p = realloc(v->data, (size_t)newcap * sizeof *p);    if (p == NULL) {             /* 실패하면 옛 블록은 그대로 남아 있다 */        free(v->data);        exit(1);    }    v->data = p;    v->cap = newcap;} static void push(IntVec *v, int x) {    if (v->size == v->cap) {     /* 가득 찼으면 두 배로: 옮겨 담기가 드물어진다 */        resize(v, v->cap * 2);        v->grow++;    }    v->data[v->size++] = x;} /* 빈 배열이면 0, 아니면 *out에 마지막 값을 꺼내고 1 */static int pop(IntVec *v, int *out) {    if (v->size == 0) return 0;    *out = v->data[--v->size];    if (v->cap > 1 && v->size * 4 <= v->cap) {  /* 1/4 이하로 줄면 반으로 */        resize(v, v->cap / 2);        v->shrink++;    }    return 1;} int main(void) {    IntVec v = { NULL, 0, 0, 0, 0 };    resize(&v, 1);               /* 처음에 한 칸 빌려 둔다 */    int q;    scanf("%d", &q);    for (int i = 0; i < q; i++) {        char cmd[8];        int x;        scanf("%7s", cmd);        if (strcmp(cmd, "push") == 0) {            scanf("%d", &x);            push(&v, x);        } else if (strcmp(cmd, "pop") == 0) {            if (pop(&v, &x)) printf("%d\n", x);            else puts("empty");        } else if (strcmp(cmd, "get") == 0) {            scanf("%d", &x);            if (x < v.size) printf("%d\n", v.data[x]);            else puts("out of range");        } else {            printf("%d %d\n", v.size, v.cap);        }    }    printf("grow %d shrink %d\n", v.grow, v.shrink);    free(v.data);                /* 빌린 블록은 마지막에 한 번 돌려준다 */    return 0;}