Slideshow | Why Iterators Got It All Wrong

class: middle

# Why Iterators Got It All Wrong
## and what we should use instead

---
#Iterators

- part of C++ since the stone age
- modeled after pointer
- in D superseded by ranges

--
- iterators can be elements `v`

```cpp
vector<int> vec={3,2,1,3};

min_element(vec.begin(),vec.end())
          v
{ 3 , 2 , 1 , 3 }
```

--
- iterators can be borders between elements `|`

```cpp
vector<int> vec={0,0,1,1};

upper_bound(vec.begin(),vec.end(),0)
        | v
{ 0 , 0 , 1 , 1 }
```

---
# Ranges

- anything that has iterators
```cpp
for( auto it=begin(rng); it!=end(rng); ++it ){...}
```
--
- containers
```
vector
list
set
```
 * own elements
 * deep copying
         * copying copies elements in O(N)
 * deep constness
         * `const` objects implies `const` elements

--
  
- views
  
---
#Views

- reference elements
- shallow copying
  * copying copies reference in O(1)
- shallow constness
  * view object `const` independent of element `const`

```cpp
template<typename It>
struct iterator_view {
	It m_itBegin;
	It m_itEnd;
	It begin() const {
		return m_itBegin;
	}
	It end() const {
		return m_itEnd;
	}
};
```

---
#Views (2)

- more compact code

* with iterators:
```cpp
std::vector<T> vec=...;
std::sort( vec.begin(), vec.end() );
vec.erase( std::unique( vec.begin, vec.end() ), vec.end() );
```
  * with ranges:
```cpp
tc::unique_inplace(tc::sort(vec));
```

---
#Views (3): Range Adaptors

```cpp
std::vector<int> v={0,0,1,1};
auto it=find(
	v,
	0
); // first element of value 0.
```

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};
auto it=find_if(
	v,
	[](A const& a){ return a.first==0; } 
); // first element of value 0 in first
```

- related in semantics
- not at all related in syntax
- projection and search criterion lumped together

---
#Transform Adaptor

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};
auto it=find_if(
	v,
	[](A const& a){ return a.first==0; } 
); // first element of value 0 in first
```
--
- separation of projection and search criterion

```
auto trans=transform(vec, mem_fn(&pair<int,char>::first)); // {0,0,1,1}

auto it=find(trans,0); // first element of value 0 in first
```
- `vec` not modified
- `trans` referencing `vec`
- transformation lazy
  * only pay for what you dereference
  * no extra heap memory

---
#Transform Adaptor (2)

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};
find_if(
	v,
	[](A const& a){ return a.first==0; } 
)->second; // 'a' !
```
--
```
auto trans=transform(vec, mem_fn(&pair<int,char>::first)); // {0,0,1,1}

find(trans,0)->second // 'a' ?
```
--

- iterator points to `int`
- peel off `transform` to get iterator pointing to `pair<int,char>`

```cpp
find(trans,0).base()->second // 'a'!

v
{  0,      0,      1,      1    } // trans
   v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```

---
#Transform Adaptor (3)

- `find` returns iterator in role of element
- `.base()` must preserve identity of element

```cpp
find(trans,0).base()->second // 'a'

v
{  0,      0,      1,      1    } // trans
   v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```

- `upper_bound` returns iterator in role of border
- same `base()` preserves identity of border

```cpp
upper_bound(trans,0).base()

|  v
{  0,      0,      1,      1    } // trans
                |  v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```

---
#Filter Adaptor

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto filt=filter(vec, [](auto const& p){return p.second=='b';});
    // {{0,'b'},{1,'b'}}
```
--

```cpp
auto trans=transform(filt, mem_fn(&pair<int,char>::first)); // {0,1}

find(trans,0).base().base()

v
{          0    ,          1    } // trans
           v // .base()
{        {0,'b'},        {1,'b'}} // filt
           v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```
- `find` returns iterator in role of element
- result would be different without `filter`
- OK?
---
#Filter Adaptor

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto filt=filter(vec, [](auto const& p){return p.second=='b';});
    // {{0,'b'},{1,'b'}}
```

```cpp
auto trans=transform(filt, mem_fn(&pair<int,char>::first)); // {0,1}

find(trans,0).base().base()

v
{          0    ,          1    } // trans
           v // .base()
{        {0,'b'},        {1,'b'}} // filt
           v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```
- `find` returns iterator in role of element
- irrelevant: result would be different without `filter`
- important: `.base()` preserves identity of element
---

#Filter Adaptor (2)

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto filt=filter(vec, [](auto const& p){return p.second=='b';});
    // {{0,'b'},{1,'b'}}
```

```cpp
auto trans=transform(filt, mem_fn(&pair<int,char>::first)); // {0,1}

upper_bound(trans,0).base().base()

|      v
{          0    ,          1    } // trans
                    |      v // .base()
{        {0,'b'},        {1,'b'}} // filt
                        |  v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```
- `.base()` preserves identity of element
- OK?
---
#Filter Adaptor (2)

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto filt=filter(vec, [](auto const& p){return p.second=='b';});
    // {{0,'b'},{1,'b'}}
```

```cpp
auto trans=transform(filt, mem_fn(&pair<int,char>::first)); // {0,1}

upper_bound(trans,0).base().base()

|      v
{          0    ,          1    } // trans
                    |      v // .base()
{        {0,'b'},        {1,'b'}} // filt
                |???????|  v // .base()
{{0,'a'},{0,'b'},{1,'a'},{1,'b'}} // vec
```
- `.base()` preserves identity of element
- identity of border not preservable
- `filter(...).base()` ambiguous if iterator in role of border

--
- THEN DON'T CALL IT, DUMBA** !!!

---
# Reverse Adaptor

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto rev=reverse(vec); // {{1,'b'},{1,'a'},{0,'b'},{0,'a'}}
```

```cpp
auto trans=transform(rev, mem_fn(&pair<int,char>::first)); // {1,1,0,0}

find(trans,0).base().base()

v
{  1    ,  1    ,  0    ,  0    } // trans
                   v         // .base()
{{1,'b'},{1,'a'},{0,'b'},{0,'a'}} // rev
                   v         // .base()
        {{0,'a'},{0,'b'},{1,'a'},{1,'b'}}; // vec
```

- `.base()` must preserve identity of element

---
# Reverse Adaptor

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto rev=reverse(vec); // {{1,'b'},{1,'a'},{0,'b'},{0,'a'}}
```

```cpp
auto trans=transform(rev, mem_fn(&pair<int,char>::first)); // {1,1,0,0}

lower_bound(trans,0,std::greater<>()).base().base()

v
{  1    ,  1    ,  0    ,  0    } // trans
                   v         // .base()
{{1,'b'},{1,'a'},{0,'b'},{0,'a'}} // rev
                   v         // .base()
        {{0,'a'},{0,'b'},{1,'a'},{1,'b'}}; // vec
```
- `.base()` must preserve identity of element

---
# Reverse Adaptor

```cpp
vector<pair<int,char>> vec={{0,'a'},{0,'b'},{1,'a'},{1,'b'}};

auto rev=reverse(vec); // {{1,'b'},{1,'a'},{0,'b'},{0,'a'}}
```

```cpp
auto trans=transform(rev, mem_fn(&pair<int,char>::first)); // {1,1,0,0}

lower_bound(trans,0,std::greater<>()).base().base()

|  v
{  1    ,  1    ,  0    ,  0    } // trans
                |  v         // .base()
{{1,'b'},{1,'a'},{0,'b'},{0,'a'}} // rev
                   v    |  v // .base()
        {{0,'a'},{0,'b'},{1,'a'},{1,'b'}}; // vec
```

- `.base()` must preserve identity of element
- `.base()` must also preserve identity of border

**!!! the same base() cannot do both !!!**

---
#Reverse Adaptor - how come?

```cpp
struct reverse_adaptor {
  struct iterator {
    BaseIt m_it;
    operator++() { --m_it; }
    operator--() { ++m_it; }
    operator*() { return *(m_it-1); } // why?
  };
  begin() { return iterator{m_base.end()}; }
  end() { return iterator{m_base.begin()}; }
};
```
--
- `iterator` at `begin()` stores `m_it=m_base.end()`
  * may be dereferenced
  * must return `*(m_base.end()-1)`

--
- `iterator` at `end()` stores `m_it=m_base.begin()`
  * won't be dereferenced

--
- decrementing `iterator` to `end()-1` makes `m_it=m_base.begin()+1`
  * returns `*(m_base.begin()+1-1)` - OK!

---
#Reverse Adaptor - how come?

```cpp
struct reverse_adaptor {
  struct iterator {
    BaseIt m_it;
    operator++() { --m_it; }
    operator--() { ++m_it; }
    operator*() { return *(m_it-1); }
    base() { return m_it-1; } // correct for element
    base() { return m_it; } // correct for border
  };
  begin() { return iterator{m_base.end()}; }
  end() { return iterator{m_base.begin()}; }
};
```

- element _after_ border in `reverse` sequence is element _before_ border in original sequence

---
#Scope of Problem: Order

```
        | v
{ b , c , a , d }
          v // .base()
        { a , b , c , d }
```

- adaptor changes order of elements

--
   * `base()` of element well-defined
   * `base()` of border in general undefined
   * example: `sort` adaptor

--
- `reverse` adaptor
   * exceptional: everything changes sides
   * `base()` of border well-defined, but different from `base()` of element

---
#Scope of Problem: Removal

```
          |   v
    { b ,     d }
        |???| v // .base()
{ a , b , c , d }
```

- adaptor removes elements

--
   * elements may collapse into border
   * `base()` of element well-defined
   * `base()` of border ambiguous
   * ex.: `filter`, `sorted_intersection`, `sorted_difference`

---
#Scope of Problem: Adding

```
        | v
{ a , b , c , d }
        | // .base()
{ a ,         d }
```

- adaptor adds elements

--
   * elements appear that were not present in base
   * `base()` of border well-defined
   * `base()` of element in general undefined
   * ex.: `sorted_union`

---
#What do we do?

- Separate functions `border_base` and `element_base`
  * (+) small change
  * (-) no safety against wrong choice

--
- Separate concepts Border and Element
  * (-) big change: no more iterator (at least in user code)
  * (+) `base()` always does right thing

** Q: Do Iterators really have assigned roles Border/Element? **

- Hypothesis tested against our codebase (~1M LOC)

---
#Border vs Element

** Q: Do Iterators really have assigned roles Border/Element? **

- Hypothesis tested against our codebase (~1M LOC)
- `find`
  * 201 single match
       * 1 border role
       * 1 incremented to get border after
       * others element role
  * 98 first match
       * 7 border role
       * 5 incremented to get border after
       * others element role
---
#Border vs Element (2)

** Q: Do Iterators really have assigned roles Border/Element? **

- Hypothesis tested against our codebase (~1M LOC)
- `find_if`
  * 67 single match
       * all element role
  * 75 first match
       * 3 border role
       * others element role

---
#Border vs Element (3)

** Q: Do Iterators really have assigned roles Border/Element? **

- Hypothesis tested against our codebase (~1M LOC)
- `lower_bound`
  * 2 no further use of predicate
       * border role
  * 89 use predicate to find single match
       * all element role
  * 19 use predicate to find first match
       * all element role
--
- `upper_bound`
  * 24 total
       * 17 border role
       * 7 decremented to get element before

--
**-> Iterator instances have distinct roles Border/Element**

---
#Iterators were always ugly

- `begin()` and `end()` asymmetric
  * can dereference `begin()`
  * cannot dereference `end()`

```cpp
  begin            end
    v   v   v   v   v
  { a , b , c , d }
```

--
- elements and borders are symmetric

```cpp
begin            end
  | v | v | v | v |
  { a , b , c , d }
```

---
#Iterators were always ugly (2)

```cpp
auto it=find(rng, t);
if(it!=end(rng)) {...}
```

- `end()`'s meaning depends on role
  * if border, border after all elements
  * if element, magic value to say "none"

--
- have to mention rng twice
  * cannot write range expression inline

--
- why not
```cpp
if( auto it=find(rng, t) ) {...}
```

**-> Introduce Border and Element concepts!**

---
#Border Concept

```cpp
begin            end
  | v | v | v | v |
  { a , b , c , d }
```

- Border `|` : like Iterator but
  * cannot be dereferenced
  * if not at begin, has `element_before()`
  * if not at end, has `element_after()`

--
- range `begin()` and `end()` are borders

--
- all iterators going into `<algorithm>` are borders
  * begin or end of input range

--
- all output iterators are borders
  * begin or end of output

--
- iterators returned from `<algorithm>`
  * depends on algorithm

---
#Border Concept (2)

- returned iterators are borders:

```cpp
mismatch                           // end of matching prefix
search                             // begin of matching range
lower_bound                        // begin of equal range
upper_bound                        // end of equal range
equal_range                        // lower and upper bound together
partition_point/[stable_]partition // border between first part
                                   // and second part
unique                             // end of compacted range
```

---
#Element Concept

```cpp
begin            end
  | v | v | v | v |
  { a , b , c , d }
```

- Element `v` : like Iterator but
  * never `end()`, cannot `++` beyond last element
  * has `border_before()`/`border_after()`
- following algorithms return element:
```cpp
[max_|min_]element // max/min element of a range 
```

- `range_of_elements` utility to get all elements inside borders
```cpp
for_each( range_of_elements(range), [&]( auto element ){...} );
```

---
#Element Concept (2)

- make Element nullable
  * compatible with pointer: pointer satisfies Element concept
  * contextually convertible to bool
  * `null` state reached through value initialization `Element{}`
  * functions returning Element return `null` instead of `.end()`

```cpp
Element elem{}; // null element
assert(!elem);

if( auto it=find_unique(rng, t) ) {...}
```

---
#Element Concept (3)

- let programmer encode her intent

--
- `std::find[_if]` gets refined to
```cpp
tc::find_unique[_if] -> Element
tc::find_first[_if] -> Element
tc::find_last[_if] -> Element
tc::trim_left[_if] -> Border
tc::trim_right[_if] -> Border
```

* `std::lower_bound` gets refined to
```cpp
tc::binary_find_unique -> Element
tc::binary_find_first -> Element
tc::binary_find_last -> Element
tc::lower_bound -> Border
```

* can always use `border_before()`/`border_after()` to convert Element to Border

--
- `_unique` functions assert single match

---
#Algorithm Return Specification

```
if( auto it=find_unique(rng, t) ) {...}
```

- want to mention `rng` only once
  * can write range expression inline

--
- let programmer write intent
  * algorithms get template parameter to control return value

--
- algorithm returning border

```cpp
// return border
lower_bound<return_border> -> border

// return view beginning/ending at border
lower_bound<return_take> -> view
lower_bound<return_drop> -> view

// return border's adjacent element
lower_bound<return_element_after> -> element
upper_bound<return_element_before> -> element
```

---
#Algorithm Return Spec. (2)

- algorithm returning element

```cpp
// return element, which may not be there
find<return_element_or_null>

// return element, which must be there
find<return_element>

// return element's adjacent border [or alternative if not there]
find<return_border_before[_or_begin|_or_end]>
find<return_border_after[_or_begin|_or_end]>

// return view beginning/ending adjacent to element
// [or alternative if not there]
find<return_take_before[_or_empty|_or_all]>
find<return_take_after[_or_empty|_or_all]>
find<return_drop_before[_or_empty|_or_all]>
find<return_drop_after[_or_empty|_or_all]>
```

---
#Return Spec. Implementation

```cpp
template< typename Rng >
struct return_take_before_or_empty {
  template<typename It>
  static auto pack_element(It it, Rng&& rng) noexcept {
    return tc::take(std::forward<Rng>(rng), it);
  }
  static auto pack_no_element(Rng&& rng) noexcept {
    return tc::take(std::forward<Rng>(rng), boost::begin(rng));
  }
};
```

---
#Conclusion

- Iterator modeled after pointers
  * low level machine concept
- Element and Border stronger semantics
  * intent already in programmer's head
  * express intent in code
  * needed for correctness of important range functions
- think-cell range library https://github.com/think-cell/think-cell-library
  * Element nullable
  * algorithm refinements
  * return specifications
- still missing
  * Border not dereferencable
  * no implicit conversion Element->Border

THANK YOU!

Share