Sentinel based find with conditional fallback to std::find

Question

I've got bored, so I decided to write a code using ancient knowledge of sentinels.

Sentinel based find

Basically what we do is put value that is needed to find at the end, and then write an endless loop. Breaking from loop happens in the body of it, so one branch (which probably won't make much, since it is a loop branch, but still) is eliminated. Requires the type to have noexcept copy assign and noexcept copy construct (in C++17, since I guess T t = value will have guaranteed copy elision).

Is there any possibilities to make this faster without compromising functionality?

#ifndef FAST_FIND_HPP
#define FAST_FIND_HPP

#include <type_traits>
#include <utility>
#include <iterator>

namespace impl
{
    template <typename BidirIt, typename T>
    BidirIt find(std::true_type, BidirIt first, BidirIt last, const T& value)
    {
        if (first == last)
        {
            return last;
        }

        auto real_last = std::prev(last);
        if (*real_last == value)
        {
            return real_last;
        }


        auto copy = *real_last;
        *real_last = value;

        auto it = first;
        for (; ; ++it)
        {
            if (*it == value)
                break;
        }

        *real_last = copy;

        if (it == real_last)
        {
            return last;
        }

        return it;

    }

    template <typename BidirIt, typename T>
    BidirIt find(std::false_type, BidirIt first, BidirIt last, const T& value)
    {
        return std::find(first, last, value);
    }
}


template <typename BidirIt, typename T>
BidirIt find(BidirIt first, BidirIt last, const T& value)
{
    return impl::find(std::integral_constant<bool, std::is_nothrow_copy_assignable<std::remove_reference_t<decltype(*first)> >::value> {}, 
        first, last, value);
    //I'd like to allow T to be different from *first

}

#endif

Usage:

#include "fast_find.hpp"
#include "randomsequence.h"
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v(10'000'000);
    random_int_generator<> gen(0, 10'000); //generate values in range
    gen(v.begin(), v.end());

    int n;
    std::cin >> n;
    auto it = find(v.begin(), v.end(), n);
    if (it != v.end())
    {
        std::cout << "Found it!\n" << *it << '\n';
    }
    else
    {
        std::cout << "Sadness\n";
    }
}

Here is the random_int_generator<>, do not review this, I posted it to make it easier for you to benchmark if needed:

#pragma once

#include <random>

template <typename T = int, class Engine = std::random_device>
class random_int_generator
{
    Engine engine;
    std::uniform_int_distribution<T> dist;
public:
    random_int_generator(T begin = 0, T end = std::numeric_limits<T>::max()) :
        dist(begin, end)
    {

    }

    template <typename OutputIt>
    void operator()(OutputIt first, OutputIt last)
    {
        while (first != last)
        {
            *first++ = dist(engine);
        }
    }

    T operator()()
    {
        return dist(engine);
    }
};

You can find current version in my github repo (it's a mess, I hope you won't mind that).

Answer 1

std::integral_constant<bool, std::is_nothrow_copy_assignable<std::remove_reference_t<decltype(*first)> >::value>

is a very complicated synonym for

std::is_nothrow_copy_assignable_t<std::remove_reference_t<decltype(*first)>>

in this context, because all the UnaryTypeTraits are defined by the standard to be "publicly and unambiguously derived" (directly or indirectly) from their BaseCharacteristic of std::true_type or std::false_type.

---

Your code returns std::prev(last) when *last == value, even if there's an instance of value prior to that in the sequence. This isn't a bug (presumably), but it's surprising enough that you should probably document it explicitly somewhere; otherwise I'd assume a function named find to have semantics exactly the same as std::find [alg.find] — i.e., "return an iterator to the first matching element".

---

Checking is_nothrow_copy_assignable<...> doesn't really buy you anything, if you aren't going to check is_nothrow_copy_constructible<...> and is_nothrow_equality_comparable<...> and is_nothrow_prefix_incrementable<...>... and so on, for all the other operations you do inside the "critical section" of your function (between the line where you blow away the old value of *real_last and the line where you restore it).

Alternatively, you could use a try/catch to make sure that you always restore the old value of *real_last. Since C++ lacks the "finally" construct that exists in languages such as Java and Python, I recommend a generic scope-guard construct such as Auto() if you find yourself doing this kind of thing very often.

---

Your code has a problem with empty ranges.