如何分配具有可变大小元素的向量(在C++中)？

Question

我编写了以下代码来接受竞争性编程网站上的测试用例.它使用input结构的向量case来同时存储给定测试用例的输入,然后一次处理一个(我省略了接受输入的循环并计算输出,因为它们与问题无关.)

#include<iostream>
#include<vector>
using namespace std;

struct case{
    int n, m;
    vector<int> jobsDone;
};

int main(){
    int testCase;
    cin>>testCase;
    vector<case> input;
    input.reserve(testCase); 

    //The rest of the code is supposed to be here
    return 0;
}

当我编写这段代码时,我意识到input.reserve(t)在元素大小可变的情况下工作(因为结构的每个实例case也有一个可变大小的向量)将是困难的.事实上,即使我没有明确写出reserve()声明,矢量仍然会保留最小数量的elemtns.

对于这种特殊情况,我对矢量有以下问题input:

• 在这种情况下,O(1)时间内的随机访问是不可能的,因为每个元素的起始位置都是未知的？
• input当无法计算每个元素的起始位置时,向量如何管理元素访问？它会将所有条目填入最大条目的大小吗？
• 我是否应该cases使用指向每个实例的指针向量来实现case？我正在考虑这个问题,因为如果向量将每个元素填充到一个大小并浪费空间,或者它保持每个元素的位置,并且随机访问在时间上不是恒定的,因此无论如何都不会使用向量.

Answer 1

每种对象类型都有固定的大小.这就是sizeof回报.甲vector本身通常具有指向对象的数组,针对空间已被分配的对象的数目,和对象的数量实际包含.这三件事的大小与向量中的元素数量无关.

例如,a vector<int>可能包含:
1)int *保存数据的地址.
2)size_t保持我们已分配空间的对象数量
3)A size_t保持向量中包含的对象数量.

无论向量中有多少个对象,这可能大约为24个字节.而这sizeof(vector<int>)将是回归.