Why Iterators Got It All Wrong — and what we should use instead
summary
Claim: C++ iterators mix two different semantics — elements and borders — which breaks adapter chaining (reverse, filter, transform) and makes base() ambiguous. Evidence: a 1M‑line code scan finds ~300 find uses with ≈200 acting as element pointers and ≈10–20 acting as borders, lower_bound mostly used to pick elements, upper_bound almost always used as a border. Fix: introduce distinct element/border iterator types, nullable elements, and dual base functions; implemented in the think cell range library and shown to work in practice.
AI-written summary · about
chapters (12)
- 0:00Iterators introduction
- 3:17Iterator problems
- 6:32Transform adapter issues
- 9:44Filter adapter issues
- 13:40Reverse adapter issues
- 16:52Border-element identity problem
- 18:37Iterator roles in code
- 21:50Iterator nullability
- 24:17Elements versus borders
- 26:03Binary search with nulls
- 27:50Algorithm return specs
- 30:21Summary
related talks
39mWhy Iterators Got It All Wrong
01h 13mFrom Iterators to Ranges — the Upcoming Evolution of the Standard Library
57mRange Algorithms, Views and Actions: A Comprehensive Guide
01h 28mUnderstanding the Filter View to Use It Right
01h 01mAn Overview of Standard Ranges
01h 08mFrom Numerical Cosmology to Efficient Bit Abstractions for the Standard Library
56mWhat a View! Building Your Own (Lazy) Range Adaptors (part 2 of 2)
01h 02mC++20 Ranges in Practice