cplusplus / cplusplus/draft

[deque.modifiers] Clarify complexity requirements on deque insertion

Open
#7,732 4 comments 0 reactions 1 assignee View on GitHub

@jwakely is already working on this.

Since Mar 12, 2025.

not-editorial
Dominant language
TeX
Stars
221
Forks
813
Avg merge
16h 4m
Merged PRs (30d)
36

Description

[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.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.