HM203 货架提前预留

来源： 第 203 集 vector容器-预留空间

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

如果事先知道大约要装多少件货，可以先调用 reserve(n) 预留容量。单词是 reserve，不要和 reverse 搞混。

它和 resize 不同：reserve 只开辟空地，**不会初始化这些位置上的元素**，此时 size() 仍是 \(0\)，不能去访问那些还没插入的格子。resize 才会得到可访问的元素（默认填 \(0\)）。

动态扩展时，容器往往要「找更大的新空间 → 拷贝旧数据 → 释放旧空间」。每换一次底层存储，首元素的地址就会变。可以用指针记下 &v[0]（必须在至少有一个元素之后），统计地址变化次数，当作扩容次数。

请对同一规模 \(n\) 做两组实验：

1. 空货架先 reserve(n)，输出此时的 size()，以及 capacity() >= n 是否成立；再尾插 \(n\) 个整数，统计扩容次数。
2. 另一座空货架**不**预留，直接尾插同样的 \(n\) 个整数，再统计扩容次数。

不要输出未预留时扩容次数的具体值（不同实现的扩容倍数不一样），只比较「预留后的扩容次数是否不超过未预留」。

输入格式

第一行一个整数 \(n\)。

第二行 \(n\) 个整数 \(a_i\)，两组实验都按这个顺序尾插。

输出格式

共三行：

1. 两个整数：reserve 之后、尚未尾插时的 size()，以及 capacity() >= n 则为 1 否则 0。
2. 一个整数：预留后再尾插 \(n\) 次的扩容次数。
3. 一个整数：若预留组的扩容次数 \(\le\) 未预留组，输出 1，否则 0。

样例

输入 #1

8
1 2 3 4 5 6 7 8

输出 #1

0 1
1
1

输入 #2

1
42

输出 #2

0 1
1
1

说明

\(1 \le n \le 100000\)，\(|a_i| \le 10^9\)。

• reserve 之后 size 仍为 \(0\)，这和 resize(n) 会得到 \(n\) 个可访问元素不同。
• 预留足够空间后再尾插，整段过程中底层地址通常只在第一次插入时记录一次，扩容次数为 \(1\)。
• 未预留时，实现会多次换更大的空间，扩容次数一般更多；本题只比较大小关系，不要求写出那个具体次数。
• 统计地址时必须先 push_back 再取 &v[0]，空容器上取首地址是不允许的。