Talk:cpp/container/deque
"Insertion or removal of elements at the end or beginning - constant O(1)"
I have to put this into question. Looking at the C++17 draft (N4567), Table 100 lists optional operations (like push_{front,back} for sequence containers as amortized constant time, but of course, a lot of the operations listed are trivially constant time. The actual deque section says insert/erase at the beginning/end are constant time; the section deque.modifiers also specifies the front/back insert as constant time in the complexity subsection, also less specific about erase; not mention of amortisation anywhere, nonetheless.
However, I can not think of any data structure that would implement these time complexities. Having surfed the net for answers, I have not come across anything suitable.
The "vector of vectors" approach is where the data structure maintains a (first-level) vector of constant sized (second-level) vectors, but eventually the first-level vector will have to be resized in order to add more second-level vectors. The number of second-level vectors necessary to hold N data entries is N / s where s = size(second-level vector), which is still linear in N; so when the first-order vector needs to resize, it will invoke a linear time move of the second-level vectors (N / s time), so this approach only gives amortised constant time insertion.
The Boost implementation of deque only gives amortised constant time insertion, I have not dared look through the libstdc++, libc++ or MSVCRT. Could someone perhaps clear this up for me? --Ybab321 (talk) 15:38, 28 March 2016 (PDT)
- 23.2.1[container.requirements.general]/2: "All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [ Example: the copy constructor of type vector <vector<int> > has linear complexity, even though the complexity of copying each contained vector<int> is itself linear. — end example ]". Rebucketing the first-level hashtable (or resizing the first-level vector in your case) does not perform any operations on the contained objects. --Cubbi (talk) 18:23, 28 March 2016 (PDT)
[edit] insertion invalidation
The current draft N4659 says at 26.3.8.4 [deque.modifers/1]
"An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque."
I'm not sure if/when this changed at all.
KarlM (talk) 13:34, 12 October 2017 (PDT)
- that's how it's always been (that's kinda the point of a deque). Here it is described at std::deque::insert. No need to clutter the front page though. --Cubbi (talk) 13:39, 12 October 2017 (PDT)
