std::vector vs std::array vs 普通数组

Question

我举办在线编程竞赛，程序的速度就是一切。随着时间的推移，我遇到了 3 种在 C++ 中使用数组概念的方法。比赛的问题通常需要我们创建一个给定大小的动态数组。所以它只是根据输入一次性创建动态数组，我们不会再次调整数组大小。

标准::向量

矢量看起来最花哨，每个人都喜欢它们。但是几天前，其中一个问题在使用向量时给了我 TIME_LIMIT_EXCEEDED 错误。
当我用普通数组实现相同的逻辑时，程序提交成功。
在研究中，我发现使用该push_back()功能比正常使用需要很长时间arr[i]=x;

我对它的性能了解不多。但它看起来是一种更好的处理数组的方式。

我使用动态分配int *arr=new int[given_size];然后正常使用数组。
将数组作为参数传递并不像向量那么简单，但这没什么大不了的。

除此之外，有时我还必须使用 2D 数组，但我总是不确定什么是最快的方法。vector<vector<int>>在某些论坛上被认为很慢，因此使用多维指针也是如此。所以我喜欢使用一个带有 typedef 函数的一维数组来处理它的索引，但是当我必须将一行传递给一个函数时它会变得复杂。

论坛中的大多数答案都基于 OP 试图做的事情，这给出了不同的答案。我想知道的是，使用哪种方法来获得最大速度/效率是最好的和长期的。

Answer 1

与 arr[i]=x; 相比，push_back 需要很长时间。

抱歉，您在这里表明您缺乏向量经验，因为您的示例做了两件不同的事情。

您正在比较类似此代码的内容

vector<int> vec;       // vector created with size zero
for (...)
    vec.push_back(x);  // vector size increases

用这个代码

int arr[N];
for (...)
    arr[i] = x;

不同之处在于，在第一种情况下，向量的大小为 0，并且随着您向其中添加项目，其大小会增加（这需要额外的时间），但在第二种情况下，数组以最终大小开始。对于数组，这是必须的，但是对于向量，您可以选择。如果你知道向量的最终大小是多少，你应该像这样编码

vector<int> vec(N); // vector created at size N, note use () not []
for (...)
    vec[i] = x;

那是您应该与数组代码进行比较以提高效率的代码，

您可能还想研究向量的resize和reserve方法。向量（如果没有别的）比数组灵活得多。