c++ 在vector中使用reserve()有什么好处?

u0njafvf  于 2023-05-20  发布在  其他
关注(0)|答案(9)|浏览(116)

在处理向量时使用reserve有什么好处。我应该什么时候使用它?我找不到一个明确的答案,但我认为它是更快,当你提前预订之前使用它们。

njthzxwz

njthzxwz1#

如果您知道向量最终将包含多少元素,这将非常有用-它可以帮助向量避免重复分配内存(以及必须将数据移动到新内存)。
一般来说,这可能是一个潜在的优化,你不需要担心,但它也不是有害的(在最坏的情况下,你最终浪费内存,如果你高估)。
当您希望确保现有迭代器不会因添加新元素而失效时,它可能不仅仅是一种优化。
例如,push_back()调用可能会使向量的现有迭代器无效(如果发生重新分配)。但是,如果您保留了足够的元素,则可以确保不会发生重新分配。这是一种不需要经常使用的技术。

42fyovps

42fyovps2#

This excellent article深入解释了dequevector容器之间的差异。“实验2”部分显示了vector::reserve()的好处。

h22fl7wq

h22fl7wq3#

它可以是。。特别是如果你要添加大量的元素到你的向量随着时间的推移,你想避免自动内存扩展,容器将使当它用完可用的插槽。
例如,向后插入(即std::vector::push_back)被认为是一个 ammortized O(1)或常数时间的过程,但这是因为如果在向量的后面进行插入,并且向量空间不足,则必须为新的元素数组重新分配内存,将旧元素复制到新数组中,然后它可以将您试图插入的元素复制到容器中。这个过程的复杂度是O(N),或者说线性时间复杂度,对于一个大的向量,可能需要相当多的时间。使用reserve()方法可以让你为向量预先分配内存,如果你知道它至少有一定的大小,避免每次空间耗尽时重新分配内存,特别是如果你要在一些性能关键的代码中进行反向插入,你想确保插入的时间保持实际的O(1)复杂度。并且不会导致数组的一些隐藏的内存重新分配。当然,你的复制构造函数也必须是O(1)复杂度,才能在整个反向插入过程中获得真正的O(1)复杂度,但是关于容器本身反向插入向量的实际算法,如果槽的内存已经预先分配,你可以保持它的已知复杂度。

z9gpfhce

z9gpfhce4#

如果你知道向量的最终大小,那么reserve是值得使用的。
否则,每当向量用完内部空间时,它将重新调整缓冲区的大小。这通常需要将内部缓冲区的大小加倍(或1.5倍当前大小)(如果您经常这样做,可能会很昂贵)。
真实的昂贵的部分是对每个元素调用复制构造函数,将其从旧缓冲区复制到新缓冲区,然后对旧缓冲区中的每个元素调用析构函数。
如果复制构造函数的开销很大,那么这可能是一个问题。

zsbz8rwp

zsbz8rwp5#

速度更快,节省内存
如果你push_back另一个元素,那么一个完整的vector通常会分配双倍的内存,因为allocate + copy的开销很大

csbfibhn

csbfibhn6#

我不知道有没有比你更聪明的人,但我会说,如果你要执行大量的插入操作,并且你已经知道或可以估计元素的总数,至少是数量级,你应该提前调用reserve。在良好的情况下,它可以为您节省大量的重新分配。

htzpubme

htzpubme7#

虽然这是一个老问题,这里是我的实现的差异.

#include <iostream>
#include <chrono>
#include <vector>

using namespace std;

int main(){
    vector<int> v1;
    chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
    for(int i = 0; i < 1000000; ++i){
        v1.push_back(1);
    }
    chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
    chrono::duration<double> time_first = chrono::duration_cast<chrono::duration<double>>(t2-t1);
    cout << "Time for 1000000 insertion without reserve: " << time_first.count() * 1000 << " miliseconds." << endl;

    vector<int> v2;
    v2.reserve(1000000);
    chrono::steady_clock::time_point t3 = chrono::steady_clock::now();
    for(int i = 0; i < 1000000; ++i){
        v2.push_back(1);
    }
    chrono::steady_clock::time_point t4 = chrono::steady_clock::now();
    chrono::duration<double> time_second = chrono::duration_cast<chrono::duration<double>>(t4-t3);
    cout << "Time for 1000000 insertion with reserve: " << time_second.count() * 1000 << " miliseconds." << endl;
    return 0;
}

当你编译并运行这个程序时,它会输出:

Time for 1000000 insertion without reserve: 24.5573 miliseconds.

Time for 1000000 insertion with reserve: 17.1771 miliseconds.

似乎有所改善,但没有太大的改善。我认为对于复杂的物体会有更多的改进,我不确定。欢迎任何建议、修改和评论。

ut6juiuv

ut6juiuv8#

在向系统请求任何空间之前,知道最终所需的总空间总是很有趣的,所以您只需要一次空间。在其他情况下,系统可能必须将您移动到更大的空闲区域(它是优化的,但并不总是空闲操作,因为需要整个数据副本)。即使编译器也会尝试帮助你,但最好的方法是告诉你所知道的(保留你的进程所需的总空间)。我是这么想的你好。

cwtwac6a

cwtwac6a9#

保留还有一个优点,它与性能没有太大关系,而是与代码风格和代码整洁度有关。
假设我想通过迭代对象的另一个向量来创建一个向量。类似于以下内容:

std::vector<int> result;
for (const auto& object : objects) {
  result.push_back(object.foo());
}

现在,显然result的大小将与objects.size()相同,我决定预定义result的大小。
最简单的方法是在构造函数中。

std::vector<int> result(objects.size());

但是现在我的代码的其余部分无效了,因为result的大小不再是0了;它是objects.size()。随后的push_back调用将增加向量的大小。所以,为了纠正这个错误,我现在必须改变我构造for循环的方式。我必须使用索引并覆盖相应的内存位置。

std::vector<int> result(objects.size());
for (int i = 0; i < objects.size(); ++i) {
  result[i] = objects[i].foo();
}

我不喜欢这样。索引在代码中到处都是。由于[]运算符的存在,这也更容易产生意外的副本。这个例子使用整数并直接将值赋值给result[i],但在具有复杂数据结构的更复杂的for循环中,它可能是相关的。
回到主题,使用reserve调整第一个代码非常容易。reserve不会改变向量的大小,而只会改变容量。因此,我可以保持nice for循环不变。

std::vector<int> result;
result.reserve(objects.size());

for (const auto& object : objects) {
  result.push_back(object.foo());
}

相关问题