矢量储备 [英] reserve of vector
问题描述
标准规定保留调用是否应将
容器的值初始化为其默认值，因此vector< intintVec;
intVec.reserve（100）将make intVec [0] = intVec [1] .... intVec [99] = 0？
谢谢
ab****@gmail.com 写道：
标准要求保留调用应将
容器的值初始化为其默认值，因此vector< intintVec;
intVec.reserve（100）会使intVec [0] = intVec [1] .... intVec [99] = 0？
实际上，size（）保持不变，因此引用这些元素是
未定义的行为。
在这种情况下，resize（）方法将增加向量并初始化
缺少元素。
最佳
Kai-Uwe Bux
2008年10月13日星期一23:08:12 -0400，Kai-Uwe Bux< jk ****** **@gmx.net>
写道：
> ab **** @ gmail.com写道：
>标准要求保留调用应将
容器的值初始化为其默认值，因此vector< intintVec;
intVec.reserve（ 100）会使intVec [0] = intVec [1] .... intVec [99] = 0？
不。实际上，size（）保持不变，因此引用这些元素是未定义的行为。
为了扩展，保留用于管理内存。如果你知道
你将要向向量中添加数千个项目，那么使用
预留来预先增加内存分配可以提高效率，
因为内存分配只增长一次 - 不太可能
几十次或几百次。
IIRC顺序添加n项向量的末尾需要O（n ^ 2）
时间。这是因为内存增长了O（n）次 - 每个k
项，比方说，k是一个常数 - 每次增长都可能涉及
复制整个向量这是平均O（n）再次。
如果你可以先保留所需的空间，顺序添加n
项是O（n）。只有一个内存重新分配，并且只有一个
复制 - 最多 - 所以它实际附加的值
决定了所花费的时间，而不是重复的内存重新分配和
复制。
还有一个方案，每个
重新分配时保留的内存加倍，这也给出了O（n），虽然它仍然比
完全预分配慢。
10月13日，9：44 * pm，Stephen Horne< sh006d3 ... @ blueyonder.co.ukwrote：
为了扩展，保留用于管理内存。如果你知道
你将要向向量中添加数千个项目，那么使用
预留来预先增加内存分配可以提高效率，
我读过那个预留（）并没有多大帮助。 （我记得从B
$ $
B B B B B B ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, class =post_quotes>
IIRC顺序将n项添加到向量的末尾需要O（n ^ 2）
时间。这是因为内存增长了O（n）次 - 每个k
项，比方说，k是一个常数 - 每次增长都可能涉及
复制整个向量这又是平均O（n）。
标准要求push_back已经摊销了常量时间;所以
实施者不能使用你描述的复杂性。
还有一种方案，其中每个保留的内存加倍
重新分配，这也给了O（n），虽然它仍然比
完全预分配慢。
如今，实施者使用50％的增长因子，据报道，使用池分配器可以更好地使用
。
Ali
Does standard mandates that the reserve call should initialize a
container''s values to its defaults, hence vector<intintVec;
intVec.reserve(100) would make intVec[0]=intVec[1]....intVec[99]=0 ?
Thanks
ab****@gmail.com wrote:
Does standard mandates that the reserve call should initialize a
container''s values to its defaults, hence vector<intintVec;
intVec.reserve(100) would make intVec[0]=intVec[1]....intVec[99]=0 ?No. In fact, size() remains unchanged so that referencing those elements is
undefined behavior.
The resize() method, in this case, will grow the vector and initialize the
missing elements.
Best
Kai-Uwe Bux
On Mon, 13 Oct 2008 23:08:12 -0400, Kai-Uwe Bux <jk********@gmx.net>
wrote:
>ab****@gmail.com wrote:
>Does standard mandates that the reserve call should initialize a
container''s values to its defaults, hence vector<intintVec;
intVec.reserve(100) would make intVec[0]=intVec[1]....intVec[99]=0 ?
No. In fact, size() remains unchanged so that referencing those elements is
undefined behavior.Just to expand on that, reserve is for managing memory. If you know
that you''re about to add thousands of items to a vector, using a
reserve to pre-grow the memory allocation can make it more efficient,
since the memory allocation only gets grown once - not potentially
dozens or hundreds of times.
IIRC sequentially adding n items to the end of a vector takes O(n^2)
time. This is because the memory gets grown O(n) times - every k
items, say, where k is a constant - and each growing can involve
copying the whole vector which is on average O(n) again.
If you can reserve the required space first, sequentially adding n
items is O(n). There is only one memory reallocation, and only one
copying - at most - so its the actual appending of values that
determines the time taken, not repeated memory reallocation and
copying.
There''s also a scheme where the reserved memory is doubled on each
reallocation, and this also gives O(n), though it''s still slower than
full preallocation.
On Oct 13, 9:44*pm, Stephen Horne <sh006d3...@blueyonder.co.ukwrote:
Just to expand on that, reserve is for managing memory. If you know
that you''re about to add thousands of items to a vector, using a
reserve to pre-grow the memory allocation can make it more efficient,I''ve read that reserve() doesn''t help much. (I remember reading from
Bjarne Stroustrup himself that he stopped calling reserve() at some
point; but cannot find any references for that.)
IIRC sequentially adding n items to the end of a vector takes O(n^2)
time. This is because the memory gets grown O(n) times - every k
items, say, where k is a constant - and each growing can involve
copying the whole vector which is on average O(n) again.The standard requires that push_back has amortized constant time; so
the implementers cannot use the complexity that you describe.
There''s also a scheme where the reserved memory is doubled on each
reallocation, and this also gives O(n), though it''s still slower than
full preallocation.Nowadays the implementers use a growth factor of 50%, which reportedly
works better with pool allocators.
Ali
这篇关于矢量储备的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
