在处理向量时使用预留的好处是什么?我应该在什么时候使用它们?在这个问题上找不到明确的答案,但我认为在使用它们之前提前预留会更快。你们比我聪明怎么样?
xxe27gdn1#
如果您知道向量最终将包含多少个元素,这将非常有用-它可以帮助向量避免重复分配内存(以及不得不将数据移动到新内存)。一般来说,这可能是一个潜在的优化,你不需要担心,但它也没有害处(最坏的情况是,如果你高估了内存,你最终会浪费内存)。它可以不仅仅是一种优化的一个方面是,当您希望确保现有的迭代器不会因为添加新元素而失效时。例如,push_back()调用可能会使向量的现有迭代器失效(如果发生了重新分配),但是如果您保留了足够的元素,则可以确保重新分配不会发生,但这是一种不需要经常使用的技术。
push_back()
1cklez4t2#
它可以是...特别是如果你要在一段时间内向你的向量中添加很多元素,并且你想避免容器在用完可用的插槽时自动进行内存扩展。例如,回插(即std::vector::push_back)被视为 * 摊销 * O(1)或恒定时间处理,但那是因为如果在向量的后面进行插入,并且向量空间不足,则它必须为新的元素数组重新分配存储器,将旧元素复制到新数组中,然后它可以复制你试图插入到容器中的元素。(N)或线性时间复杂度,并且对于大向量,可能会花很多时间,使用reserve()方法允许你为向量预先分配内存,如果你知道它至少会有一定的大小,避免每次空间用完时重新分配内存,特别是当您要在某些性能关键型代码中执行反向插入时,您希望确保执行插入的时间保持为实际的O(1)复杂性-进程,并且不会为数组带来隐藏的内存重新分配。当然,复制构造函数必须是O(1)复杂性以及得到真正的O(1)整个回插过程的复杂性,但是关于由容器本身回插到向量中的实际算法,如果已经预先分配了用于该槽的存储器,则可以将其保持为已知的复杂度。
std::vector::push_back
reserve()
djp7away3#
This excellent article深入解释了deque和vector容器之间的差异。“实验2”部分显示了vector::reserve()的好处。
deque
vector
vector::reserve()
uujelgoq4#
如果你知道向量的最终大小,那么reserve是值得使用的。否则,当向量用完内部空间时,它将重新调整缓冲区的大小,这通常包括将内部缓冲区的大小加倍(或1.5倍当前大小)(如果经常这样做,可能会很昂贵)。真实的代价高昂的是调用每个元素的复制构造函数,将其从旧缓冲区复制到新缓冲区,然后调用旧缓冲区中每个元素的析构函数。如果复制构造函数的开销很大,那么它可能会成为一个问题。
s4chpxco5#
速度更快,节省内存如果你push_back另一个元素,那么一个完整的向量通常会分配两倍于它当前使用的内存--因为分配+复制的开销很大
qco9c6ql6#
不知道有没有人比你更聪明,但我想说,如果你要执行大量的插入操作,并且你已经知道或可以估计元素的总数,至少是数量级,那么你应该提前调用reserve,这样可以在良好的情况下保存大量的重新分配。
reserve
6jygbczu7#
虽然这是一个老问题,这里是我的差异实现.
#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.
看起来是有所保留的改进,但不是太多的改进。我想对于复杂的对象会有更多的改进,我不确定。欢迎任何建议,修改和评论。
bn31dyow8#
在向系统请求任何空间之前知道最终所需的总空间总是很有趣的,因此您只需请求一次空间。在其他情况下,系统可能必须将您移到一个更大的空闲区域(它是优化的,但并不总是一个自由的操作,因为需要整个数据副本)。甚至编译器也会试图帮助你,但是最好的方法是说出你所知道的(保留你的进程所需要的空间)。这就是我的想法。问候。
vhmi4jdf9#
保留还有一个优点,它与性能没有多大关系,而是与代码风格和代码清洁度有关。假设我想通过迭代对象的另一个向量来创建一个向量,如下所示:
std::vector<int> result; for (const auto& object : objects) { result.push_back(object.foo()); }
现在,显然结果的大小将与objects.size()相同,我决定预定义result的大小。最简单的方法是在构造函数中。
objects.size()
result
std::vector<int> result(objects.size());
但是现在我的其余代码无效了,因为result的大小不再是0;它是objects.size(),后续的push_back调用将增加向量的大小,因此,为了纠正这个错误,我现在必须改变构建for循环的方式,我必须使用索引并覆盖相应的内存位置。
0
push_back
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()); }
9条答案
按热度按时间xxe27gdn1#
如果您知道向量最终将包含多少个元素,这将非常有用-它可以帮助向量避免重复分配内存(以及不得不将数据移动到新内存)。
一般来说,这可能是一个潜在的优化,你不需要担心,但它也没有害处(最坏的情况是,如果你高估了内存,你最终会浪费内存)。
它可以不仅仅是一种优化的一个方面是,当您希望确保现有的迭代器不会因为添加新元素而失效时。
例如,
push_back()
调用可能会使向量的现有迭代器失效(如果发生了重新分配),但是如果您保留了足够的元素,则可以确保重新分配不会发生,但这是一种不需要经常使用的技术。1cklez4t2#
它可以是...特别是如果你要在一段时间内向你的向量中添加很多元素,并且你想避免容器在用完可用的插槽时自动进行内存扩展。
例如,回插(即
std::vector::push_back
)被视为 * 摊销 * O(1)或恒定时间处理,但那是因为如果在向量的后面进行插入,并且向量空间不足,则它必须为新的元素数组重新分配存储器,将旧元素复制到新数组中,然后它可以复制你试图插入到容器中的元素。(N)或线性时间复杂度,并且对于大向量,可能会花很多时间,使用reserve()
方法允许你为向量预先分配内存,如果你知道它至少会有一定的大小,避免每次空间用完时重新分配内存,特别是当您要在某些性能关键型代码中执行反向插入时,您希望确保执行插入的时间保持为实际的O(1)复杂性-进程,并且不会为数组带来隐藏的内存重新分配。当然,复制构造函数必须是O(1)复杂性以及得到真正的O(1)整个回插过程的复杂性,但是关于由容器本身回插到向量中的实际算法,如果已经预先分配了用于该槽的存储器,则可以将其保持为已知的复杂度。djp7away3#
This excellent article深入解释了
deque
和vector
容器之间的差异。“实验2”部分显示了vector::reserve()
的好处。uujelgoq4#
如果你知道向量的最终大小,那么reserve是值得使用的。
否则,当向量用完内部空间时,它将重新调整缓冲区的大小,这通常包括将内部缓冲区的大小加倍(或1.5倍当前大小)(如果经常这样做,可能会很昂贵)。
真实的代价高昂的是调用每个元素的复制构造函数,将其从旧缓冲区复制到新缓冲区,然后调用旧缓冲区中每个元素的析构函数。
如果复制构造函数的开销很大,那么它可能会成为一个问题。
s4chpxco5#
速度更快,节省内存
如果你push_back另一个元素,那么一个完整的向量通常会分配两倍于它当前使用的内存--因为分配+复制的开销很大
qco9c6ql6#
不知道有没有人比你更聪明,但我想说,如果你要执行大量的插入操作,并且你已经知道或可以估计元素的总数,至少是数量级,那么你应该提前调用
reserve
,这样可以在良好的情况下保存大量的重新分配。6jygbczu7#
虽然这是一个老问题,这里是我的差异实现.
当您编译并运行此程序时,它将输出:
看起来是有所保留的改进,但不是太多的改进。我想对于复杂的对象会有更多的改进,我不确定。欢迎任何建议,修改和评论。
bn31dyow8#
在向系统请求任何空间之前知道最终所需的总空间总是很有趣的,因此您只需请求一次空间。在其他情况下,系统可能必须将您移到一个更大的空闲区域(它是优化的,但并不总是一个自由的操作,因为需要整个数据副本)。甚至编译器也会试图帮助你,但是最好的方法是说出你所知道的(保留你的进程所需要的空间)。这就是我的想法。问候。
vhmi4jdf9#
保留还有一个优点,它与性能没有多大关系,而是与代码风格和代码清洁度有关。
假设我想通过迭代对象的另一个向量来创建一个向量,如下所示:
现在,显然结果的大小将与
objects.size()
相同,我决定预定义result
的大小。最简单的方法是在构造函数中。
但是现在我的其余代码无效了,因为
result
的大小不再是0
;它是objects.size()
,后续的push_back
调用将增加向量的大小,因此,为了纠正这个错误,我现在必须改变构建for循环的方式,我必须使用索引并覆盖相应的内存位置。我不喜欢这样。索引在代码中无处不在。由于[]操作符,这也更容易造成意外复制。这个例子使用整数并直接赋值给result[i],但在具有复杂数据结构的更复杂的for循环中,它可能是相关的。
回到主题,使用
reserve
可以很容易地调整第一段代码。reserve
不会改变向量的大小,只会改变容量。因此,我可以保留我的nice for循环不变。