11

As a result of this question from a few days ago there are a few things that have been bugging me about the complexity requirements for std::deque::push_back/push_front vs the actual std::deque implementations out in the wild.

The upshot of the previous question was that these operations are required to have O(1) worst case complexity. I verified that this was indeed the case in c++11:

from 23.3.3.4 deque modifiers, refering to insert, push/emplace front/back

Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances to the beginning and end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a constructor of T.

This is combined with the O(1) complexity requirement for indexing, via operator[] etc.

The issue is that implementations don't strictly satisfy these requirements.

In terms of both msvc and gcc the std::deque implementation is a blocked data structure, consisting of a dynamic array of pointers to (fixed size) blocks, where each block stores a number of data elements.

In the worst case, push_back/front etc could require an extra block to be allocated (which is fine - fixed size allocation is O(1)), but it could also require that the dynamic array of block pointers be resized - this is not fine, since this is O(m) where m is the number of blocks, which at the end of the day is O(n).

Obviously this is still amortised O(1) complexity and since generally m << n it's going to be pretty fast in practice. But it seems there's an issue with conformance?

As a further point, I don't see how you can design a data structure that strictly satisfies both the O(1) complexity for both push_back/front etc and operator[]. You could have a linked-list of block pointers, but this doesn't give you the desired operator[] behaviour. Can it actually be done?

Community
  • 1
  • 1
Darren Engwirda
  • 6,915
  • 4
  • 26
  • 42
  • related (but not really answered either): http://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl – Nate Kohl Dec 01 '11 at 02:06
  • @NateKohl: yes exactly - and the answers to that question seem to confirm that you can't strictly satisfy all of the complexity requirements... – Darren Engwirda Dec 01 '11 at 02:10

2 Answers2

4

In the C++11 FDIS, we can read:

23.2.3 Sequence containers [sequence.reqmts]

16/ Table 101 lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time.

Where Table 101 is named Optional sequence container operations and lists deque for the push_back and push_front operations.

Therefore, it seems more like a slight omission in the paragraph you cited. Perhaps worth a Defect Report ?

Note that the single call to a constructor still holds.

Community
  • 1
  • 1
Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • This issue actually seems to be creating a bit of discussion lately, see for instance: http://stackoverflow.com/questions/8627373/what-data-structure-exactly-are-deques-in-c/8628035#8628035 and http://stackoverflow.com/questions/8631531/what-does-constant-complexity-really-mean-time-count-of-copies-moves – Darren Engwirda Dec 26 '11 at 04:49
  • @DarrenEngwirda: thanks for the pointers :) I think the real issue is that no-one knows how to implement a `deque` that would satisfy the Standard requirements, only approximations... and I don't know either. The Random Access / O(1) push / Preservation of References trilogy is just unmanageable as far as I am concerned, even with amortized O(1) push. – Matthieu M. Dec 27 '11 at 17:16
  • 1
    The standard reference in this answer is somewhat misleading, as it is not the only place where complexity is constrained. By the very same clause one could read that indexing a `std::vector` is only required to take **amortized** constant time, but elsewhere it is made clear that this case really has to be constant time for any individual instance. Similarly for `std::deque::push_front`the detailed entry (23.3.3.4:3 in my copy) says **always takes constant time** as cited in OP, and this clearly seems to override what is said in 23.2.3:16. – Marc van Leeuwen Oct 15 '17 at 09:16
0

I suspect that the reallocation of the block pointers is done with a geometrically increasing size - this is a common trick for std::vector. I think this is technically O(log m) but as you point out m << n, so as a practical matter it doesn't affect the real-world results.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • 1
    I know what you mean, but the standard doesn't really allow much room to move, requiring that constant time is *always* achieved. Maybe the standard could be revised? – Darren Engwirda Dec 01 '11 at 01:54
  • 2
    Actually, the geometric growth makes it *amortized* O(1) (like `vector`). – Matthieu M. Dec 01 '11 at 08:04