[deque.modifiers] Clarify complexity requirements on deque insertion
@jwakely is already working on this.
Since Mar 12, 2025.
- 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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.