Reputation: 101
Is every "vectors" of STL deque's implementation always has the same size?
I have read The C++standard Library A Tutorial and reference 2nd, it said that deque's implementation include many blocks, I was curious that if i insert a element in the middle of the deque, will all the elements after the new inserted elements be moved backward just like vector,Or it will only move the elements in the inserted block?
Upvotes: 0
Views: 46
Answers (1)
Reputation: 16670
As Igor said, the standard doesn't mention such details. However, given that it does say that all pointers, iterators and references are invalidated, I think you can assume that it moves more than the elements in a single "block".
As an aside, given the iterator requirements for deque, all the blocks (except the first and the last one) have to be kept full. Random access iterators require constant time "increment by N", and that can't be done if you have to count how many items are in each block (or, at least, I don't see a way to do that). So that would imply that all the elements either before or after the insertion point have to be moved. (again, not just the ones in the same "block")
Upvotes: 1
Related Questions
- std::deque is contiguous memory container or not?
- Difference in size between std::vector and std::deque
- empty deque vs vector
- Does deque provide O(1) complexity when inserting on top
- will stl deque reallocate my elements (c++)?
- Why did I get deque's max_size() less than vector's max_size()?
- Why is std::deque not a vector with memory reserved before index 0?
- Vector vs Deque insertion in middle
- What's generally the size limit to switch from a vector to a deque?
- Is there a way to get deque's internal storage size as vector::capacity?