[deque.modifiers] Clarify complexity requirements on deque insertion

[RedBeard0531]

[deque.modifiers]/2 states:

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 at either the beginning or end of a deque always takes constant time and causes a single call to a constructor of T.

This is misleading since all real-world implementations of deque are only amortized constant time when inserting at the end, due to the need to grow (hopefully exponentially) the mapping array. I think there are a few possible solutions here, some of which make sense to combine:

• Replace "takes constant time and" with "only" since the "single call to the constructor of T" is redundant with stating constant time in the strict interpretation of [container.requirements.pre]/2. This avoids the use of the misleading phrase.
• Add a cross-reference to [container.requirements.pre] when stating it is constant time to give readers proper context.
• Add "amortized" before "constant time"
• Explicitly state that an amortized constant number of operations on pointers may take place. Since this is observable via the use of allocator-derived fancy-pointers, it is reasonable for this to be a normative requirement.

[jensmaurer]

Uhm, I hope you don't expect the editors to make a judgment call on the phrasing here?

@jwakely , do you feel empowered to take a pick?

[frederick-vs-ja]

This is really tricky. "Constant time" is correct for operations on elements (i.e. single construction in this case), but the wording is somehow unhelpful.

• Explicitly state that an amortized constant number of operations on pointers may take place. Since this is observable via the use of allocator-derived fancy-pointers, it is reasonable for this to be a normative requirement.

I guess there should be an LWG issue for specifying numbers of operations on "pointers", along with allocations and deallocations.

[RedBeard0531]

Uhm, I hope you don't expect the editors to make a judgment call on the phrasing here?

I thought it best to leave the editorial decisions on exact phrasing to the editors :)

If you or @jwakely would prefer, I'd be happy to open a PR with my preference, but I suspect that will end with one of you telling me how to change my PR, which would be more efficient if you just owned it.

For context if you missed it, this is fallout from the lib mailing list thread "Should std::list::reverse be O(1)" which @jwakely is involved in.

[jensmaurer]

Well, there are apparently technical questions on whether "number of operations on possibly fancy pointers from the allocator" should matter for the complexity specification. Answering such questions doesn't seem editorial.