Hello everyone,
Quoted from GotW #54 about redundant allocation in vector and deque. What makes me confused is "because none of the allocations are redundant". I think it means,
The context is about adding new elements at the end, not about insert elements at any arbitrary location (e.g. in the middle), right?
1. For deque, when allocating memory for new elements at the end, no need to reallocate, i.e. allocate new space, copy old elements to new space and free old memory -- so no redundant allocation for existing component again;
2. For vector, when allocating memory for new elements at the end, when capacity == current size, need to reallocate, i.e. allocate new space, copy old elements to new space and free old memory -- so redundant allocation for existing components again.
My understanding correct?
http://www.gotw.ca/gotw/054.htm
--------------------
3. A deque is easier to use, and inherently more efficient for growth, than a vector. The only operations supplied by vector that deque doesn't have are capacity() and reserve() -- and that's because deque doesn't need them! For vector, calling reserve() before a large number of push_back()s can eliminate reallocating ever-larger versions of the same buffer every time it finds out that the current one isn't big enough after all. A deque has no such problem, and having a deque::reserve() before a large number of push_back()s would not eliminate any allocations (or any other work) because none of the allocations are redundant; the deque has to allocate the same number of extra pages whether it does it all at once or as elements are actually appended.
--------------------
thanks in advance,
George
Quoted from GotW #54 about redundant allocation in vector and deque. What makes me confused is "because none of the allocations are redundant". I think it means,
The context is about adding new elements at the end, not about insert elements at any arbitrary location (e.g. in the middle), right?
1. For deque, when allocating memory for new elements at the end, no need to reallocate, i.e. allocate new space, copy old elements to new space and free old memory -- so no redundant allocation for existing component again;
2. For vector, when allocating memory for new elements at the end, when capacity == current size, need to reallocate, i.e. allocate new space, copy old elements to new space and free old memory -- so redundant allocation for existing components again.
My understanding correct?
http://www.gotw.ca/gotw/054.htm
--------------------
3. A deque is easier to use, and inherently more efficient for growth, than a vector. The only operations supplied by vector that deque doesn't have are capacity() and reserve() -- and that's because deque doesn't need them! For vector, calling reserve() before a large number of push_back()s can eliminate reallocating ever-larger versions of the same buffer every time it finds out that the current one isn't big enough after all. A deque has no such problem, and having a deque::reserve() before a large number of push_back()s would not eliminate any allocations (or any other work) because none of the allocations are redundant; the deque has to allocate the same number of extra pages whether it does it all at once or as elements are actually appended.
--------------------
thanks in advance,
George