Transforming `std::find` into `std::ranges::find`

The last time we met, we had some fun discovering what it means to write a concept. Specifically, we derived the concept ranges::EqualityComparableWith, which allows us to describe algorithms that check for cross-type equivalence (in other words, checking that two objects with potentially different types are equivalent). Although we defined a concept, we never actually used it. That’s where today’s article comes in.

The mathematics behind concepts is so vast that we can’t cover it in a short discussion. Today, we’ll derive the C++ standard library linear search algorithm, find, as it is in the Ranges TS. There is a strong chance that this definition of find will find (ha!) its way into C++20. We will begin by defining some vital prerequisites, before looking at std::find as it is today, and then refining it so that it may resemble what we can enjoy in the Ranges TS. As with last time, there is a lot of material to cover, so make yourself that drink now: you won’t want to interrupt the flow half-way through!

Warning: this article is a direct continuation of Prepping Yourself to Conceptify Algorithms. You may be left in the dark about how and why things work if you skip the first part.

Refining and weakening concepts

When we say that we refine (or strengthen) a concept, we mean that we are applying more requirements to the concept. This makes the concept more specialised. For example, we refined WeaklyEqualityComparable so that we could define a concept that describes equivalence relations; EqualityComparable is thus a refinement over WeaklyEqualityComparable.

When we say that we weaken a concept, we mean that we are removing requirements to make it more general. I didn’t see the point in weakening concepts for a very long time, and we won’t explore the notion of weakening concepts in this article, but it does make for a central discussion in this series’ final instalment.

Linear search

A linear search takes a sequence of elements in some data structure and an item to find, and returns a position in the data structure to where the item is, or a predefined value to indicate that it isn’t in the structure. Below are examples of linear searches:

// For vectors
template <typename T>
std::ptrdiff_t find(std::vector<T> const& v, T const& value) noexcept
{
   for (auto i = std::ptrdiff_t{}; i < ranges::distance(v); ++i) {
      if (v[i] == value) {
         return i;
      }
   }

   return ranges::distance(v);
}

// For std::arrays
template <typename T, std::ptrdiff_t N>
std::ptrdiff_t find(std::array<T, N> const& a, T const& value) noexcept
{
   for (auto i = std::ptrdiff_t{}; i < ranges::distance(a); ++i) {
      if (a[i] == value) {
         return i;
      }
   }

   return ranges::distance(a);
}

// For raw arrays (yuck!)
template <typename T, std::ptrdiff_t N>
std::ptrdiff_t find(T const(& a)[N], T const& value) noexcept
{
   for (auto i = std::ptrdiff_t{}; i < N; ++i) {
      if (a[i] == value) {
         return i;
      }
   }

   return N;
}

// For array-indexed pointers with a distance (ew!)
template <typename T>
std::ptrdiff_t find(T const* const a, std::ptrdiff_t const distance, T const& value) noexcept
{
   for (auto i = std::ptrdiff_t{}; i < distance; ++i) {
      if (a[i] == value) {
         return i;
      }
   }

   return distance;
}

If you’re familiar with the span vocabulary-type, you can probably imagine how we might factorise this into a single function. A single function to handle this verbatim logic would be superb, since we can then forget about everything above.

// For vectors and arrays of all shapes and sizes!
template <typename T>
int find(gsl::span<T const> const s, T const& value) noexcept
{
   for (auto i = std::ptrdiff_t{}; i < ranges::distance(s); ++i) {
      if (s[i] == value) {
         return i;
      }
   }

   return ranges::distance(s);
}

What about linked-lists? If you took a data structures and algorithms class, you probably learnt that a singly-linked list looks somewhat like this:

// deliberately not std::forward_list, for expositional reasons
template <typename T>
struct snode {
   T value;
   snode* next = nullptr;
};

template <typename T>
struct slist {
   snode<T> head;
};

// linear search for a singly-linked list
template <typename T>
snode<T> const* find(slist<T> const& l, T const& value) noexcept
{
   for (auto const* i = &l.head; i != nullptr; i = i->next) {
      if (i->value == value) {
         return i;
      }
   }

   return nullptr;
}

Cool, that’s a singly-linked list done. What about a doubly-linked list?

template <typename T>
struct dnode {
   T value;
   dnode* next = nullptr;
   dnode* prev = nullptr;
};

template <typename T>
struct dlist {
   dnode<T> head;
};

// linear search for a doubly-linked list
template <typename T>
dnode<T> const* find(dlist<T> const& l, T const& value) noexcept
{
   for (auto const* i = &l.head; i != nullptr; i = i->next) {
      if (i->value == value) {
         return i;
      }
   }

   return nullptr;
}

Hmm… That’s also verbatim text. Can we factorise it? Yes, we can.

template <template <typename> typename Node, typename T>
Node<T> const* find_impl(Node<T> const* i, T const& value) noexcept
{
   for (; i != nullptr; i = i->next) {
      if (i->value == value) {
         return i;
      }
   }

   return nullptr;
}

template <typename T>
snode const* find(slist const& l, T const& value) noexcept
{
   return find_impl(&l.head, value);
}

template <typename T>
dnode const* find(dlist const& l, T const& value) noexcept
{
   return find_impl(&l.head, value);
}

So, we’ve been able to factorise our linked-list linear search too. Let’s take a look at the algorithms side-by-side, to see if we can factorise them into one function:

template <typename T>
std::ptrdiff_t find(gsl::span<T const> const s, T const& value) noexcept
{
   for (auto i = std::ptrdiff_t{}; i < ranges::distance(s); ++i) {
      if (s[i] == value) {
         return i;
      }
   }

   return ranges::distance(s);
}

template <template <typename> typename Node, typename T>
Node<T> const* find_impl(Node<T> const* i, T const& value) noexcept
{
   for (; i != nullptr; i = i->next) {
      if (i->value == value) {
         return i;
      }
   }

   return nullptr;
}

The code is nearly the same, but not quite. Where it differs is in how we determine the end of the sequence, how we take the successor of our current element, and how we retrieve the value. While this is conceptually the same, it’s implementationally different. What about getting input from the user?

template <typename T>
std::ptrdiff_t find(std::istream& in, T const& value)
{
   auto t = T{};
   for (auto i = std::ptrdiff_t{}; in >> t;) {
      if (t == value) {
         return i;
      }
   }

   return -1; // I guess?
}

Again, similar at the concept level; and different in the implementation. This problem will arise for every container-like data structure that you design. Given the current approach, you’ll be able to factorise out textual similarities, but we’re not actually factorising all that much out. There’s still complete code redundancy here, and that’s not okay.

Fortunately, iterators offer us a way to fold all of our find implementations into a single, easy-to-understand algorithm that we’ll discuss in a bit.

Iterators

Iterators are a topic rich with mathematics. Because they are part of what makes generic programming so powerful, this topic spans multiple chapters in books on generic programming[1][2]. Informally, you might know iterators to be the ‘glue’ between algorithms and data structures. Without iterators, if there are N algorithms and M data strucutres, you can expect at most N * M algorithmic implementations. With iterators, there need only be N algorithm implementations, but there can be more (if you can optimise for a particular iterator concept).

More formally, iterators are a generalisation of pointers, and allow for abstracting how we address elements in some data structure. All iterators let us either read from an element (via a source function), write to an element (via a sink function), or both. All iterators also have a successor function, which lets us find the ‘next’ element in the structure. In C++, for some iterator i, we refer to both source and sink functions as *i, and the successor function as ++i.

Going back to our discussion of linear searches, *i will represent span[n] and n->value. ++i represents ++n (for integers) and n = n->next (for list nodes). Iterators can even abstract over our istream example! This might look strange at first, but we now have a way to factorise all of our find implementations into one generic algorithm that still concisely describes exactly what we want.

Input iterators

An input iterator is an iterator that can be read from. This might be from a vector of objects or some other container, or even an iterator that abstracts over an input stream (such as the character input). We may only read from an input iterator, and so only have a source function and a successor function: there is no sink function. If we wish to write to some element in a range, we need at least an output iterator.

One critical property of input iterators is that they are ‘single-pass’. That means that once you apply the successor function to an input iterator, you can never get the data that the iterator offered back. Further, all copies of said iterator become ‘invalid’, and may no longer be read from. This notion of ‘single-pass’ is relaxed in iterator concepts that refine input iterators, but because the input iterator concept is so general, it must be present to permit said generality. An iterator that abstracted over retrieving keyboard input is an example of this ‘single-pass’ axiom. Each time that you press a key is, from the algorithm’s perspective, a unique occurrence.

Examples of input iterators

std::vector<int>::const_iterator
std::istream_iterator<double>{std::cin}

What about other iterators?

If you’re familiar with the STL, then you’re probably aware of at least four other iterator concepts. While there are other iterator concepts, they are not relevant for our discussion, so we shan’t consider them today.

Ranges

One of the papers that proposing to integrate the Ranges TS with the Standard[3] defines a range to be “an iterator and a sentinel that designate the beginning and end of the computation, or an iterator and a count that the beginning and the number of elements to which the computation is applied.” We’ll properly define what a sentinel is a little bit later on, but for right now, you can think of it as an iterator delimiting the aforementioned computation: this is how Standard C++ has defined it up until the Ranges TS anyway.

We use a half-open interval notation to denote a range: [i, s) means that we can traverse from i up to s, but we can never apply a source function on s, nor may we succeed it. If i == s, then the range is empty. While i != s, it denotes the elements in some data structure spanning [i, s). We say that s is reachable from i if, and only if, we can apply the successor function a finite number of times before i == s is satisfied. Not all ranges are finite, but they’re for a future blog (if at all). Because counted ranges are not relevant to the discussion, we’ll omit them too, for brevity.

`std::find`

Now that we’re familiar with the concept of input iterators and ranges, let’s revisit our friend, find.

template <typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, T const& value)
{
   for (; first != last; ++first) {
      if (*first == value) {
         return first;
      }
   }

   return last;
}

That’s it! The algorithm is still very much the same: we provide some mechanism for determining how to end the search, a way to succeed the current position, and a way to read the data. However, the details of how to implement these for each structure are abstracted out of the algorithm. This is actually a valid implementation for std::find. If you want to just pass a data structure, and not worry about iterators, then you can overload a range-based find:

template <typename InputRange, typename T>
auto find(InputRange const& rng, T const& value)
{
   return find(ranges::begin(rng), ranges::end(rng), value);
}

The beautiful thing about this generic implementation is that provided your data structure can be generalised to be a range, these latest two iterations of find are probably valid for your purposes too. Notice that I said probably. Since this is such a general implementation for find, there need to be some rules put in place. Some requirements, that we’ll define below, by refining find.

Using the InputRange version of find is hopefully a drop-in replacement for all cases of find, provided that your data structure is also compatible with the InputIterator version. All standard containers, std::string, Boost containers, and gsl::span are compatible. If you have two pointers to an array, this is also compatible:

constexpr auto size = 10;
auto p = std::make_unique<int[]>(size);
// ...
find(p.get(), p.get() + size, 0); // of course, you'd be using span<int> in real code.

Our linked-lists, however, are not compatible (yet). They don’t have a notion of what an iterator is, but it’s fairly simple (but mechanical) to give them one. In production code, we would never implement our own list type (and we will rarely want to use a list anyway): we’d use std::forward_list or std::list, so we won’t be considering slist or dlist from here on.

We’ve already discussed the concept of an input iterator, and the Ranges TS provides that for us. To make sure that we’re not going to try and pass in something that we can’t iterate over, we ought to make our first refinement that.

template <ranges::InputIterator I, typename T>
I find(I first, I last, T const& value);

Now, silly code, such as find(0, 1, 0) won’t be allowed, because integers do not model InputIterator.

Recall that in the ranges section, we briefly discussed this notion of a sentinel, and I dismissed it as a delimiting iterator. That’s not a complete definition, but it is what most C++ programmers are familiar with, and it was necessary for the discussion to advance. We’ll now approach the definiton of a sentinel more carefully.

Sentinels are a generalisation of iterators, in such a way that they delimit the end of a range. This means that while iterators may be sentinels, sentinels need not be iterators. The caveat is that the sentinel must be default-constructible, copyable, and WeaklyEqualityComparableWith the iterator whose range we wish to iterate over.

Axiomatically, given an iterator i and a sentinel s that denote the range [i, s):

i == s is well-defined
Given bool(i != s), *i is valid and [++i, s) also denotes a range.
The domain of == can change over time, such that i == s may no longer be valid. This makes for an interesting discussion, but is probably best addressed in a future blog post.

A non-iterator example of a sentinel might be a type that checks if certain data has been read from an input stream, or if the stream has failed.

Let’s refine find:

template <ranges::InputIterator I, ranges::Sentinel<I> S, typename T>
I find(I first, S last, T const& value)
{
   for (; first != last; ++first) {
      if (*first == value) {
         break;
      }
   }

   return first;
}

Notice that we changed the implementation to only return first: this is because we might not always have a last that shares a compatible type with I, and so returning last could lead to some compile-time errors at best, or strange run-time errors at worst.

Refinement Three – Adding `EqualityComparableWith`

‘Finally!’, I hear you cry. Yes, we’ll now refine find to consider the EqualityComparableWith concept that we laboured over in the last article. All iterators have a value_type and a reference type, and the Ranges TS provides us with a mechanism to extract them from conforming iterator types. Under the Ranges TS, we use ranges::value_type_t and ranges::reference_t, and when merged with C++20, they’ll likely be called std::iter_value_t and std::iter_ref_t (for various reasons). Because an iterator’s source function is supposed to return a reference to what it addresses, we will use reference_t, not value_type_t.

template <InputIterator I, Sentinel<I> S, EqualityComparableWith<reference_t<I>> T>
I find(I first, S last, T const& value);

And this stops us from committing silly mistakes like

auto v1 = std::vector<int>{0, 1, 2};
auto v2 = std::vector<std::vector<int>>{ {0, 1, 2}, {3, 4, 5} };
auto i = find(begin(v1), end(v1), v2); // An honest mistake, really

Aside – Invocables

The Invocable concept is a generalisation of function types, and includes any type that invoke can be applied to. As per the Ranges TS:

The Invocable concept specifies a relationship between a callable type … F and a set of argument types Args... which can be evaluated by the library function invoke….

In short, this means that given some function with a type F, and parameters with types Args..., Invocable will let us know whether or not the function can be invoked. For example:

void foo();
using foo_t = decltype(foo);
static_assert(ranges::Invocable<foo_t>); // okay, foo() is expected
// static_assert(ranges::Invocable<foo_t, int>); // error: foo(0) isn't possible

int rando(int, int = 0);
using rando_t = decltype(rando);
static_assert(ranges::Invocable<rando_t, int, int>); // okay, rando(0, 0) is expected
// static_assert(ranges::Invocable<rando_t, int>); // error: rando's signature is equivalent to int(int, int),
                                                   // but this checks for R(int)
// static_assert(ranges::Invocable<rando_t>); // error: rando() isn't possible
// static_assert(ranges::Invocable<rando_t, std::vector<int>>); // error: not possible

Invocable makes no assumptions on the return type of the callable, nor does it impose any axioms on what the function returns.

`RegularInvocable`

Sometimes, we can’t just rely on plain old Invocable. Semantically, an object with a type that models Invocable is free to return whatever it likes. Under these rules, square(1) is allowed to return a random number, for every call to square(1). This is great for randomisation functions and functions that get user input, but not at all strong enough for functions that should map to the same result when provided with the same input.

RegularInvocable imposes the same constraints as Invocable, but axiomatically requires that the function object be equality-preserving (the result is the same each time you pass the same parameters), and that the arguments not be modified.

Introducing projections

Projections are easier to introduce with sort and lower_bound (kudos to Sean Parent for this example). I’ll follow up with projections and find after. We’ll read a collection of employee data from the character input, then sort them, before finding someone with the surname Smith.

struct employee {
  int id;
  std::string surname;
  std::string first_name;
  double salary;
};

auto employees = std::vector<employee>{ranges::istream_iterator<employee>{std::cin},
   ranges::default_sentinel{}};

std::sort(employees,
   [](auto const& a, auto const& b) noexcept { return a.surname < b.surname; });

std::lower_bound(employees, "Smith",
   [](auto const& value, auto const& e) noexcept { return e.surname < value; });

The problem with this approach is that the lambdas are performing the same logic, on the same types; yet they have distinct signatures. Any update to one of the lambdas very likely means that an update to the other is also required. Logically speaking, we are computing string < string, but this is orthogonal to the type system: sort expects a function that takes two employees, and lower_bound expects a function that takes a T and an employee. It would be nice if we could factorise the lambdas into a single object, but that’s not at all possible, because our algorithms require different predicates. From the algorithms’ point of view, the comparisons in std::sort and std::lower_bound respectively resemble:

if (std::invoke(pred, *lhs, *rhs)) { /* ... */ } // for std::sort
if (std::invoke(pred, *lhs, value)) { /* ... */ } // for std::lower_bound

What we want to achieve is logic that is analagous to the text:

if (lhs->surname < rhs->surname) { /* ... */ } // for std::sort
if (lhs->surname < value) { /* ... */ } // for std::lower_bound

This is where projections come in. A projection is a mapping from our iterator’s reference type to the type that we wish to perform the operation on. A projection may be anything that can be treated as though it is a unary function of the iterator’s reference type. This includes pointers-to-members of the iterator’s value type, as shown in the snippet below.

auto predicate = std::less<>{};
auto projection = &employee::surname;
ranges::sort(employees, predicate, projection);
ranges::lower_bound(employees, "Smith", predicate, projection);

Here, we are demonstrating a projection of employee::surname onto our respective algorithms. While a projection doesn’t make the comparisons literally look like our goal, the logic inside the algorithms has now been customised to resemble it.

With this, we can eliminate redundancies, and make the algorithm logic simpler. If predicate becomes std::greater<>{}, it’s reflected in both algorithms automatically, rather than us needing to remember to update both (and then verify that both are correct!).

It also makes it possible to functionally reason about your code a little bit more. If we’re just using lower_bound, we can swap the first snippet below for the second.

// (1)
ranges::lower_bound(employees, "Smith",
   [](auto const& value, auto const& e) noexcept { return e.surname < value; });
// (2)
ranges::lower_bound(employees, "Smith", std::less<>{}, &employee::surname);

C++ Reference defines lower_bound as

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

To me, the second snippet is easier to read, as we can almost read our lambda’s logic as

lower_bound on employees, where "Smith" is not less than the current employee’s surname.

Contrived? Sure. That doesn’t make it any less true, which is why I make liberal use of projections. Please don’t interpret this to mean that recommended practice suddenly becomes “use projections everywhere”. It means that if you can factorise out one or more components in multiple algorithms, then you should do so.

Projections on `find`

If we want to find a specific employee in a range of employees, based on their surname, we can’t use find, because find doesn’t let us discriminate. We have a value, and that’s that. If we want to do this today, we need to use find_if.

std::find_if(begin(employees), end(employees), [](auto const& e) noexcept {
   return e.surname == "Smith"; });

We can again use projections to stick with find, similarly to my final lower_bound example. Without further ado, let’s introduce projections to find:

template <InputIterator I, Sentinel<I> S, typename T, typename Proj = identity>
requires
   EqualityComparableWith<value_type_t<projected<I, Proj>>, T> &&
   EqualityComparableWith<reference_t<projected<I, Proj>>, T>
I find(I first, S last, T const& value, Proj proj = Proj{})
{
   for (; first != last; ++first) {
      if (ranges::invoke(std::ref(proj), *first) == value) {
         break;
      }
   }

   return first;
}

Well, this is a bit of a mouthful. We introduce an (apparently) unconstrained type called Proj and set the default type to be identity, which is a function object that returns whatever it is passed (no copying involved). The type projected is a convenience-type that checks that I can be read from, and that Proj models RegularInvocable. Since we want proj to be invisible except when necessary, we give it a default value.

proj has a signature equivalent to auto&&(reference_t<I>), which means that it takes a dereferenced iterator and returns an arbitrary type, so we must invoke it to get back whatever we plan to compare against value. Note that the auto&& return type means that we can’t pass a function with a void return type.

Whew! We’ve come a long way since our first iteration of find, all the way at the top. We’ve looked at so much, and you’re forgiven if you thought that this was the end of the road but we have one last stop….

Intermission the Second

Just like our first intermission, this second one revolves around invocable concepts. This time, we consider Predicate and Relation. Predicate refines RegularInvocable such that the return type of the invocable object models Boolean.

A Relation is a Predicate that takes exactly two types that are somehow ‘related’, similarly to how EqualityComparableWith ‘relates’ types. In fact, EqualityComparableWith<T1, T2> describes a Relation for two types T1 and T2 on ==.

The requires-expression we established in the last section is quite verbose, has redundancy, and is error-prone. Fortunately, there’s a concept called IndirectRelation, which is simpler to read than our mouthy friend, and also checks some things that beyond the scope of our discussion. Tim Song hosts a HTML-based version of the Ranges TS, where you can read it, if you’re interested. There are two caveats to using IndirectRelation:

It’s not imposing an equivalence relation. equal_to ensures that there is an equivalence relation, but IndirectRelation imposes no such requirement. This is useful to know when implementing other algorithms that need IndirectRelation.
It requires two input iterator-like types, so we need to hand it a T const* rather than plain-old T. This might seem like a misnomer, since our relation is proj(*i) == value, so one iterator type and a T looks better. You might be right in thinking this for find, but there are other algorithms – such as find_end and equal– that require types to model IndirectRelation and provide two input iterator-like types. Since this is a convenience concept, and because pointers model InputIterator, having two IndirectRelation concepts is a bit redundant.

template <InputIterator I, Sentinel<I> S, typename T, typename Proj = identity>
requires
   IndirectRelation<equal_to<>, projected<I, Proj>, T const*>
I find(I first, S last, T const& value, Proj proj = Proj{});

And we’ve now finished transforming std::find into what std::ranges::find should look like!

I thought the Ranges TS was about, you know, ranges

It is! Everything that we’ve just discussed is to do with finding elements in some range. What you might be expecting are range-based algorithms, similar to the range-for statement. We’ve pretty much run out of time, but since we’ve done most of the derivation above, there’s not much left to do for a range-based find.

template <InputRange Rng, typename T, typename Proj = identity>
requires
   IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, T const*>
safe_iterator_t<Rng> find(Rng&& rng, T const& value, Proj proj = Proj{})
{
   return find(ranges::begin(rng), ranges::end(rng), value, std::ref(proj));
}

InputRange subsumes (read: absorbs) both InputIterator and Sentinel<InputIterator>, and we’re left with a type called Rng. Because Rng isn’t an iterator type, we can’t directly apply it to projected: we first need to extract its iterator type (which is a required type-name by InputRange) and apply that instead.

The safe_iterator_t is a wrapper that says “hey, what you get back might actually be dangling. You do the unsafe stuff, it’s not my responsibility”. This in turn, lets us pass both lvalues and rvalues to our range-based find. After that, it’s simply a case of calling our iterator-based overload.

Yes, this will be shipping as an overload for std::ranges::find.

Conclusion

Today, we made lots of progress. We first established why iterators are a powerful tool that aid our efforts to refactor algorithms that perform the same operation, but require different implementations, into a single, general algorithm. Next, we generalised the concept of a delimiting iterator to a sentinel, which determines when we’ve reached the end of a range. Following on, we applied EqualityComparableWith, because it seemed appropriate at the time.

We then made our first detour to explore what RegularInvocable means, and then applied that knowledge to further generalise our application of *i through the use of projections. After a second detour to learn about predicates and relations, we simplified our use of the projection even further.

Where to from here?

Both the previous article and this one are expositional for the concluding discussion, where I chronicle how I refine std::accumulate so that it might end up in C++23. Given that there’s a lot of history and maths behind the design of the Palo Alto Report, the Ranges TS, and what’s (hopefully) going to work its way into C++20, I couldn’t just start there. It’s very important that you actually understand what is happening in the revised algorithms found in namespace std::ranges, and more importantly, why the decisions made are so, before continuing on to something novel and completely unreviewed (as far as I’m aware, there haven’t been any committee discussions on numeric algorithms, and it’s a non-trivial task to refine them).

CppCon 2018 class

Although I’ve written this three-part series to talk about my ideas for conceptifying accumulate, now is probably as good a time as any to mention that I’m teaching a class at CppCon 2018, titled Generic Programming 2.0 with Concepts and Ranges. If you find the contents of this series interesting, and can make it to Bellevue for the end of September, you will probably enjoy this class.

Even if you don’t think the class is for you, you should definitely consider attending the conference! Conferences – especially CppCon – are a great way to network with engineers working on cool technologies (that you might use or one day use), a great way to promote your company, and of course, to learn about what speakers wish to share. If you’d like to present on a main track at a conference one day, CppCon also has lightning talks (which span for up to fifteen minutes), and open-content sessions (which span between thirty and ninety minutes). They’re a great way for you to practice with minimal pressure, and usually spark very interesting discussions.

RSS Feed

It’s 2018, and I’ve just learnt about what RSS is (I first heard about it in 2009 or 2010). I’ve set up an RSS feed in case you wish to follow more of my blog posts.

Comments and feedback

I haven’t yet set up Disqus for this site. If you’d like to discuss what you’ve read here, please head to this GitHub issue. I’m always open to feedback!

Acknowledgements

I would like to thank Arien Judge, Callum Howard, Duncan McBain, Gordon Brown, Kate Gregory, Matt Stark, Nicole Mazzuca, Shafik Yaghmour, Sy Brand, and Tristan Brindle for taking the time out to review this article.

Transforming std::find into std::ranges::find

Christopher Di Bella's Personal Website

Transforming `std::find` into `std::ranges::find`

Refining and weakening concepts

Linear search

Iterators

Input iterators

Examples of input iterators

What about other iterators?

Ranges

`std::find`

Refinement One – Locking Down Input Iterators

Refinement Two – Introducing Sentinels

Refinement Three – Adding `EqualityComparableWith`

Aside – Invocables

`RegularInvocable`

Refinement Four – Projections

Introducing projections

Projections on `find`

Intermission the Second

Fifth and final refinement – indirect relations

I thought the Ranges TS was about, you know, ranges

Conclusion

Where to from here?

CppCon 2018 class

RSS Feed

Comments and feedback

Acknowledgements

Transforming std::find into std::ranges::find

Refining and weakening concepts

Linear search

Iterators

Input iterators

Examples of input iterators

What about other iterators?

Ranges

std::find

Refinement One – Locking Down Input Iterators

Refinement Two – Introducing Sentinels

Refinement Three – Adding EqualityComparableWith

Aside – Invocables

RegularInvocable

Refinement Four – Projections

Introducing projections

Projections on find

Intermission the Second

Fifth and final refinement – indirect relations

I thought the Ranges TS was about, you know, ranges

Conclusion

Where to from here?

CppCon 2018 class

RSS Feed

Comments and feedback

Acknowledgements

Transforming `std::find` into `std::ranges::find`

`std::find`

Refinement Three – Adding `EqualityComparableWith`

`RegularInvocable`

Projections on `find`