6
\$\begingroup\$

I have written the following simple find function template that does a linear search.

#include <iterator>
#include <concepts>

#include <array>
#include <random>
#include <algorithm>


template <std::input_or_output_iterator InputIt, class T>
requires ( std::equality_comparable_with<std::iter_const_reference_t<InputIt>, T> )
[[ nodiscard ]] InputIt
find( InputIt first, const InputIt last, const T& key ) noexcept
{
    auto& it { first };
    for ( ; it < last; ++it )
    {
        const auto& val { *it };
        if ( val == key ) break;
    }

    return it;
}

int main( )
{
    std::array<int, 5000> nums;

    std::random_device rand_dev { };
    std::mt19937 engine { rand_dev( ) };
    std::uniform_int_distribution dist { 1, 100 };
    std::ranges::generate( nums, [ &dist, &engine ]( ){ return dist( engine ); } );

    const int value { 42 };

    const auto it { find( std::cbegin( nums ), std::cend( nums ), value ) };

    if ( it == std::cend( nums ) )
        return EXIT_FAILURE;
    else
        return EXIT_SUCCESS;
}

A few questions:

  1. Is std::input_or_output_iterator sufficient or should I use the more refined std::input_iterator?
  2. Is the requires clause good enough? Does it need more constraints?
  3. Should I ensure the iterator type InputIt is a const_iterator type? If so then how?

Any further suggestions?

\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

Answers to your questions

  1. Is std::input_or_output_iterator sufficient or should I use the more refined std::input_iterator?

As you already suggest yourself by using the name InputIt, it should be the latter.

  1. Is the requires clause good enough? Does it need more constraints?

In principle it doesn't need constraints at all. However, the compiler will generate better error messages if you do. You have constraints on all parameters, so you don't need more. But see below.

  1. Should I ensure the iterator type InputIt is a const_iterator type? If so then how?

No. What if the caller wants to find an element with a certain value so it can then update the value? The it you return should have the same const-qualification as first. It's fine to make last const.

Remove noexcept

There is no guarantee that dereferencing the iterator, incrementing the iterator, and comparing the values pointed to by the iterators will never throw. So remove the noexcept specifier from your function.

Have a look at std::ranges::find()

Compare your function to std::ranges::find(). Apart from there being lots of overloads in the STL, the one most closely matching your function still has several differences:

  • It uses a separate type for last; this allows different type iterators to be passed, but that is fine as long as they are equality comparable.
  • It uses std::indirect_binary_predicate<std::ranges::equal_to, …> as a constraint. I am not entirely sure why, but it might handle some edge cases that your use of std::equality_comparable_with<…> doesn't.
  • It takes an optional projection function as an argument, which sometimes is useful.
  • It's constexpr but not [[nodiscard]]. You can have both.

Of course, there is also an overload that takes a range as input instead of two iterators, which is almost always much nicer to use.

Simplify the code

I would avoid the two variable declarations and simplify the code like so:

template <std::input_iterator InputIt, class T>
requires (…)
constexpr [[nodiscard]] InputIt
find(InputIt first, const InputIt last, const T& key)
{
    for (auto& it = first; it < last; ++it)
        if (*it == key)
            return it;

    return last;
}
\$\endgroup\$
0
3
\$\begingroup\$

You already have an excellent answer from @G.Sliepen, and there is pretty much no part of it that I have any quarrels with. However, I wanted to go a little bit further. And I want to particularly focus on the concepts, and not just which concepts you should use, but why.

Is std::input_or_output_iterator sufficient or should I use the more refined std::input_iterator?

std::input_or_output_iterator is just plain wrong, and std::input_iterator is dodgy.

Let’s start with the first part.

Output iterators make no sense

Output iterators are write-only. They are, as the name implies, only for outputting data… not for reading.

In fact, for many output iterators, trying to read from them will return nonsense. Take std::back_insert_iterator for example. It’s implementation will kinda look like this:

template <typename Container>
class back_insert_iterator
{
    Container* _container;

public:
    using value_type      = void;
    using difference_type = void;
    using pointer         = void;
    using reference       = void;

    using iterator_category = std::output_iterator_tag;

    using container_type = Container;

    constexpr explicit back_insert_iterator(Container& c) : _container{&c} {}

    // All no-ops that return *this.
    constexpr auto operator*()     -> back_inserter& { return *this; }
    constexpr auto operator++()    -> back_inserter& { return *this; }
    constexpr auto operator++(int) -> back_inserter  { return *this; }

    // Assignment is where the magic happens.
    constexpr auto operator=(typename Container::value_type const& value) -> back_inserter&
    {
        _container->push_back(value);
        return *this;
    }
    constexpr auto operator=(typename Container::value_type&& value) -> back_inserter&
    {
        _container->push_back(std::move(value));
        return *this;
    }
};

As you can see, operator* just returns a reference to the iterator, so that *it = value works. So in your find function when you basically do *it == key, you’re not actually comparing the key to any real value… you’re comparing it to the iterator. If you’re lucky, this will trigger a compile error. If you’re not so lucky, the search key will actually be comparable with the iterator and then who knows what hell will ensue.

But ignore the details and instead just consider things conceptually. What, exactly, do you think you would be comparing the key to? An output iterator is a sink; a black hole. Stuff goes in, stuff does not come out. You can’t look into the black hole, you can only throw stuff into it. *it == key is just nonsense.

So without even knowing anything about std::input_or_output_iterator, it’s obviously the wrong concept just by the name. A find function cannot work with output iterators.

std::input_or_output_iterator is mostly useless

Okay, but let’s pretend for a moment that output iterators could work. Even then, std::input_or_output_iterator is the wrong concept.

std::input_or_output_iterator is an unfortunately bad name. I mean, first of all, does it mean that it accepts any input iterators and any output iterators? Or does it only accept iterators that can do both input or output?

But it actually gets worse, because std::input_or_output_iterator will actually accept things that are neither input iterators nor output iterators!

std::input_or_output_iterator tests essentially two things:

  1. that the thing can be incremented (operator++, prefix or postfix); and
  2. that the thing can be dereferenced (unary operator*).

Now consider what you need your find algorithm to be able to do:

  1. It must be able to compare iterators (while (first != last)).
  2. It must be able to increment an iterator.
  3. It must be able to dereference an iterator.
  4. It must be able to read the value the iterator is referencing.

Of those 4 requirements, std::input_or_output_iterator only covers 2 and 3. It doesn’t even constrain a minimal input or output operator.

So what is std::input_or_output_iterator useful for then?

Well, as I said, it is not a great name. A better name might be std::very_basic_iterator_like_thingy. Okay, that’s a terrible name, too. Naming is hard.

My point is: what std::input_or_output_iterator is trying to describe is the absolute, basic, bare minimum idea of what it means to be an iterator.

So what is the point of that?

Well, if you are trying to do anything with an iterator—if you are trying to use an iterator (to do something)—that’s pretty useless. If you are trying to do anything that requires an underlying sequence, or an actual value to be pointed to by the iterator (either to be read or written to, or both), then std::input_or_output_iterator is no good to you.

But if you are trying to do something to an iterator, then this is what you need. This is for situations where you don’t even care if there is an underlying sequence, or what that sequence might look like, or what value the iterator is pointing to, if any.

For example, consider std::advance(). That function does not care about the underlying sequence, or any referenced values. All it does is operate on the iterator itself. All it does is increment a specified number of times (basically). And, lo, std::ranges::advance() is only constrained with std::input_or_output_iterator.

You are almost never doing operations just on an iterator. You are almost always using iterators to do operations on the underlying sequence, or at least some value referenced by the iterator (either reading or writing). So you will almost never find any use for std::input_or_output_iterator.

Input iteration and “finding”

Okay, but I said that even std::input_iterator is a “dodgy” choice, which seems to be contraindicated not only by the fact that std::input_iterator’s operations are enough for a find algorithm, but also by the fact that std::ranges::find() itself uses std::input_iterator. So, what am I on? Has Indi been on the bad drugs again?

Bear with me on this: there are two different meanings of “find”:

  1. “I just want to know whether the value is in the collection.”
  2. “I want to find the value in the collection, in order to do something with it (or based on its location).”

Unfortunately, prior to C++23, a single algorithm was used for both concerns.

  1. If you just wanted to check whether the value was in the collection, you’d do std::find(...) != end.
  2. If you wanted to use the value, you’d do auto p = std::find(...);, then use *p (after checking if it was valid, of course). (Or use p if you want to do something based on the value’s location.)

These two operations look like they’re basically the same thing, but they are very much not.

Imagine if we had two, completely separate functions: find() to actually find a value in a collection so you can use it, and contains() just to see if a value is in a collection. Now imagine we have a type that can contain a crap-ton of sequential data, but that also has a very, very fast lookup for whether certain values appear in that data. I’ll give a concrete example: imagine a type that downloads gigabytes of raw binary data from somewhere, and as it downloads, for every byte value it sees, it sets a flag in a 256 bit bitset. Now imagine you want to “find” the specific byte value 42. Consider two cases:

  1. You want to find the first instance of 42, because that signals the start of some data that you want to read.
  2. You just want to know if the value 42 appears in the data, because if it does, then you know the data is corrupt.

In the first case, you would have to do find(data, 42), which would have to do a O(n) linear search through gigabytes of data. If the 42 does not appear, or if it appears near the end, you could be waiting a while. But that’s your only option.

In the second case, you would do contains(data, 42), which would not actually have to iterate through the data at all. It could be specialized to just check that bitset, and return whether bit 42 is set. That is not only O(1), it could be many orders of magnitude faster.

(Note that as of C++23, the standard actually does finally get a contains() algorithm. Unfortunately, it is straight-up specified in terms of find(), so… blah.)

Okay, but what does this have to do with std::input_iterator?

Well, if you just want to know whether data is in a collection, then conceptually, you only need to increment and read. That’s std::input_iterator in a nutshell, so it would make sense to constrain contains() with std::input_iterator.

But if you want to actually use the value, then it doesn’t really make sense for it to be read-only. You already know what its value is… you literally specify that as key in the function arguments. If the value is found at all… then you know what it is, because you specifically searched for it. For find() to make any sense at all, you want to do more than simply read the value after finding it… you want either want to mutate the item being referenced, or you want to mutate the collection based on the position of that value. In either case, a read-only view doesn’t make sense, so std::input_iterator (which is a read-only iterator whose position has no meaning, because it is only ephemeral) doesn’t make sense.

Which means:

  1. contains() could be constrained with std::input_iterator.
  2. find() should be constrained with (at least) std::forward_iterator.

Now, let me be absolutely clear here: I am not suggesting you use std::forward_iterator to constrain your find algorithm. That is because these iterator categories are not exactly “pure”, and there are actually plausible situations where the position in an input sequence isn’t entirely meaningless, and where the value returned from the input iterator might be interesting (it may be “equal” to the key, yet still somehow unique). This is because of deeper issues, like that “equality” can be a fuzzy concept, and that the C++ standard iterator model mushes too many things together (notably access and traversal). The real world is messy.

So you should constrain your find() with std::input_iterator. Just… understand why. Understand both why std::input_iterator is the minimum constraint you need, and why it may not actually be the perfect constraint.

Is the requires clause good enough? Does it need more constraints?

So, the constraint you use is:

std::equality_comparable_with<std::iter_const_reference_t<InputIt>, T>

But (after stripping out the projection stuff) std::ranges::find() uses:

std::indirect_binary_predicate<std::ranges::equal_to, InputIt, T const*>

Why does the standard do that?

First let’s understand the difference between the two constraints. The difference really kinda boils down to:

  • “can the types be compared after removing the indirection?” (your constraint); versus
  • if the indirection is removed, can the types be compared?” (the standard’s constraint).

The difference is very subtle, but the standard’s constraint is “gentler”, because it is conditional, leaving the “how” of removing the indirection unspoken. Yours is “rougher” because it attempts to unconditionally strip away the indirection, and in a specific way.

The most obvious way the difference manifests is that, because the standard isn’t committing itself to removing the indirection in one particular way, it is able to check several different ways of removing the indirection. You just check for the validity of:

iter_const_reference_t<InputIt> == T

The standard, on the other hand, checks the validity of:

iter_value_t<InputIt>& == T const
iter_value_t<InputIt>& == T const&
iter_reference_t<InputIt> == T const
iter_reference_t<InputIt> == T const&
common_reference_t<iter_value_t<InputIt>&, iter_reference_t<InputIt>> == T const&

Let’s ignore all the const stuff. That means your constraint checks:

iter_reference_t<InputIt> == T

While the standard checks:

iter_value_t<InputIt>& == T
iter_value_t<InputIt>& == T&
iter_reference_t<InputIt> == T  // <- your check
iter_reference_t<InputIt> == T&
common_reference_t<iter_value_t<InputIt>&, iter_reference_t<InputIt>> == T&

So, the standard checks actually include your check… but along with others.

But what is the point of those other checks? Why do both iter_value_t<InputIt>& and iter_reference_t<InputIt>? If the underlying type of the sequence is U, then the former is U&, while the latter is… U&. Right? So, what’s the point of doing it both ways?

Well, because for some complex iterators, like proxy iterators, iter_value_t<I>& and iter_reference_t<I> may not be the same.

Take the infamous vector<bool> for example. iter_value_t<vector<bool>::iterator> is (presumably) bool. But iter_reference_t<vector<bool>::iterator is std::vector<bool>::reference.

(And, as an aside, iter_const_reference_t<vector<bool>::iterator is probably bool. Not bool const& (because that would make little sense). Just bool.)

Now, your check will still technically work, because vector<bool>::reference implicitly converts to bool. So it will convert, then you just have bool == bool, which is fine. But not all proxy iterators will do that. If vector<bool>::reference didn’t do that, and didn’t directly compare to bool, then your check would fail. But the standard’s check would still pass, because iter_value_t<vector<bool>::iterator> is bool.

So, the answer to the mystery is: proxy iterators. For any non-proxy iterator, iter_value_t<I>& and iter_reference_t<I> will probably by the same thing. For proxy iterators, all bets are off. The standard avoids specifying how the indirection is removed, so that it can be removed differently by different methods, and so long as any of them work to produce something equality-comparable with T, the check will pass.

(Note that because there is no concept that only does the indirection for one argument, the standard cheats by applying indirection to T, by making it T const*. This works fine because the indirection from a bare pointer is never going to give a proxy iterator.)

So your requires clause is not wrong, and it will work fine for any non-proxy iterator. It will also work for many, if not most, if not all, proxy iterators. But there are multiple ways to skin the indirection off of an iterator cat, and if you want to be 100% sure you’ve covered your bases, you need to check all the different methods.

Should I ensure the iterator type InputIt is a const_iterator type? If so then how?

@G.Sliepen explained why you wouldn’t want to do this with a specific example. I’ll generalize the idea: If a user gives you something they expect to get back, you shouldn’t fuck with it unnecessarily.

If a user gives you a value, or a type, and you’re going to be returning that value or type, you shouldn’t modify that value or type any more than is absolutely necessary to perform the operation of the function. Don’t add const to the type. Don’t remove const. Don’t add volatile. Don’t add 1 to the found value just for the sake of returning a higher value to lift the user’s spirits. Even if it’s technically harmless, because the user is informed by the documentation that you’re going to add 1 and they can just subtract 1 if they didn’t want that, doing that extra, unnecessary thing is just going to piss the user off.

There is no reason to add const here. If the user wants const, they can add it themselves. If they don’t want it, they could technically just remove it… but why should they need to take that extra step? It would just annoy them.

As for the second part of the question…

I am aware of no way, in general, to be sure the type you got is a const-iterator. “const_iterator” isn’t even a general concept. There is no such thing as an output const-iterator, and an input iterator is always a const-iterator because it is read-only by definition. Is a transform iterator a const-iterator? Because mutating the transformed value surely makes no sense, so in that sense it is a const-iterator… but at the same time you can just do .base() which may give you mutable access to the base data, so…?

If you really, really, really, really want to detect only const-iterators, whatever that may mean in general, there are some things you could try. Again, the idea can’t be generalized, so these checks can’t be expected to always work reliably. But you could try:

  • checking that iter_reference_t and iter_const_reference_t are the same; and
  • checking that iter_reference_t is either not an lvalue reference, or is an lvalue reference to something const.

At least for vector<bool>—the only proxy iterator I have any real experience with—this should work, because iter_reference_t<vector<bool>::const_iterator> is likely bool, which is not an lvalue reference. For the new proxy iterators we’ll be getting in C++23? 🤷🏼

Happy coding!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.