microsoft / microsoft/STL

`<algorithm>`: Re-evaluate iterator unwrapping design

Open
#1,760 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
Dominant language
C++
Stars
11.1k
Forks
1.7k
Avg merge
4d 15h
Merged PRs (30d)
22

Description

We have facilities in the STL for unwrapping checked/safe iterators into unchecked iterators which can be rewrapped back into the original iterator type. These facilities are used by the trusted code in the STL to avoid the costs of redundant checking. During the last big design overhaul of the unwrapping machinery we were looking ahead to algorithms taking iterator/sentinel pairs, so they're well supported, but actual range types not so much. We do have some helper functions we formed while writing range algorithms after observing repeated patterns:

https://github.com/microsoft/STL/blob/2d890fdadde44bdb8eced76f29803ce2ecbe0378/stl/inc/algorithm#L206-L291

it would be nice to reconsider the design of the unwrapping story in the full context of Ranges. For instance, some range algorithms use range._Unchecked_begin() and range._Unchecked_end() to directly obtain an unchecked iterator/sentinel pair from a range, which then need to be rewrapped on return. Rewrapping currently requires a wrapped iterator to use as a target, which is awkward for these algorithms which need to call range.begin() (possibly twice!) to obtain such a wrapped iterator. Such subrange rewrapping could probably be more efficient if ranges could support it directly via an extension point.

Contributor guide

Open the contributing guide

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.

Research direction

Start by reviewing the range-algorithm helper functions in stl/inc/algorithm around the linked lines, then trace how _Unchecked_begin(), _Unchecked_end(), and iterator rewrapping are used. Compare the current iterator/sentinel handling with actual range support. Done means a coherent Ranges-aware unwrapping design and agreed extension point are documented or implemented.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
devtools
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.