Menu
Lets say I was inserting p new elements at the 'i' th position in an std::vector<mytype> of size 'n'.
Since items in std::vector are guaranteed to use contiguous storage locations for their elements, it seems like this would take me 4 steps to do the above:
1) Possible reallocation of the vector if we are out of space, basically doubling its size. But that is a constant time operation (albeit a very large one).
2) Next there is a memcpy of elements from index 0 through i-1 from the old vector into the new one.
3) Then you copy 'p' new items being inserted at ith index.
4) Then another memcpy for all items from i+1 through n indexes from the old vector to the new vector.
Aren't all the above constant time operations? Then shouldn't insertion itself be a constant time operation? Why then is std::vector::insert linear on the number of elements inserted (copy/move construction) plus the number of elements after position (moving)?
270
Its time complexity is O(1). insert(): Inserts new elements into the vector at a particular position. ts time complexity is O(N + M) where N is the number of elements inserted and M is the number of the elements moved . pop_back(): Removes the last element from the vector.
6.1-1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; In this analysis I'm looking at end insertion, which is done with the C++ vector::push_back function.
Yes, the elements of a std::vector are guaranteed to be contiguous.
The time complexity to find an element in std::vector by linear search is O(N). It is O(log N) for std::map and O(1) for std::unordered_map . However, the complexity notation ignores constant factors.
Aren't all the above constant time operations?
No, the time complexity of memcpy and memmove is linear in the size of the block being copied or moved, because each of the k bytes being moved needs to be touched exactly once. The size of the block being moved is sizeof(T) * N, making the timing linear as well.
Even addition of an element at the end of a vector has linear complexity because of copying data on reallocation (however, adding N elements to the end of a vector has amortized linear complexity, which translates to amortized constant per-item complexity).
63
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
