STL-Style algorithms on tuples

Question

I started writing some of the standard algorithms for tuples, here are the first few non-modifying ones

#include <functional>
#include <iostream>
#include <optional>
#include <tuple>
#include <type_traits>

template <typename Predicate, typename Tuple>
constexpr bool all_of(Predicate&& pred, Tuple&& t) noexcept {
  return std::apply(
      [&](auto&&... xs) constexpr noexcept {
        return (... && pred(std::forward<decltype(xs)>(xs)));
      },
      std::forward<decltype(t)>(t));
}

template <typename Predicate, typename Tuple>
constexpr bool any_of(Predicate&& pred, Tuple&& t) noexcept {
  return std::apply(
      [&](auto&&... xs) constexpr noexcept {
        return (... || pred(std::forward<decltype(xs)>(xs)));
      },
      std::forward<decltype(t)>(t));
}

template <typename Predicate, typename Tuple>
constexpr bool none_of(Predicate&& pred, Tuple&& t) noexcept {
  return std::apply(
      [&](auto&&... xs) constexpr noexcept {
        return !(... || pred(std::forward<decltype(xs)>(xs)));
      },
      std::forward<decltype(t)>(t));
}

template <typename Predicate, typename Tuple>
constexpr void for_each(Predicate&& f, Tuple&& t) noexcept {
  return std::apply(
      [&](auto&&... xs) constexpr noexcept {
        (..., f(std::forward<decltype(xs)>(xs)));
      },
      std::forward<decltype(t)>(t));
}

template <typename Predicate, typename Tuple, std::size_t... Is>
constexpr void for_each_n_impl(Predicate&& f, Tuple&& t,
                               std::index_sequence<Is...>) noexcept {
  return (..., f(std::get<Is>(t)));
}

template <std::size_t N, typename Predicate, typename Tuple>
constexpr void for_each_n(Predicate&& f, Tuple&& t) noexcept {
  static_assert(N <= std::tuple_size_v<std::decay_t<decltype(t)>>);
  return for_each_n_impl(std::forward<decltype(f)>(f),
                         std::forward<decltype(t)>(t),
                         std::make_index_sequence<N>());
}

template <typename Tuple, typename T>
constexpr std::size_t count(Tuple&& t, const T& value) noexcept {
  return std::apply(
      [&](auto&&... xs) constexpr noexcept {
        return (0u + ... + static_cast<std::size_t>(value == xs));
      },
      std::forward<decltype(t)>(t));
}

template <typename Predicate, typename Tuple>
constexpr std::size_t count_if(Predicate&& pred, Tuple&& t) noexcept {
  return std::apply(
      [&](auto&&... xs) constexpr noexcept {
        return (0u + ... +
                static_cast<std::size_t>(pred(std::forward<decltype(xs)>(xs))));
      },
      std::forward<decltype(t)>(t));
}

template <std::size_t N, typename TupleZero, typename TupleOne>
constexpr std::optional<std::size_t> mismatch_impl(TupleZero&& t0,
                                                   TupleOne&& t1) noexcept {
  constexpr std::size_t I = std::tuple_size_v<std::decay_t<decltype(t0)>> - N;

  if constexpr (N == 0u) {
    return std::nullopt;
  } else {
    return std::get<I>(t0) == std::get<I>(t1)
               ? mismatch_impl<N - 1u>(std::forward<decltype(t0)>(t0),
                                       std::forward<decltype(t1)>(t1))
               : std::make_optional(I);
  }
}

template <std::size_t N, typename Predicate, typename TupleZero,
          typename TupleOne>
constexpr std::optional<std::size_t> mismatch_impl(Predicate&& pred,
                                                   TupleZero&& t0,
                                                   TupleOne&& t1) noexcept {
  constexpr std::size_t I = std::tuple_size_v<std::decay_t<decltype(t0)>> - N;

  if constexpr (N == 0u) {
    return std::nullopt;
  } else {
    return pred(std::get<I>(t0), std::get<I>(t1))
               ? mismatch_impl<N - 1u>(std::forward<decltype(pred)>(pred),
                                       std::forward<decltype(t0)>(t0),
                                       std::forward<decltype(t1)>(t1))
               : std::make_optional(I);
  }
}

template <typename TupleZero, typename TupleOne>
constexpr std::optional<std::size_t> mismatch(TupleZero&& t0,
                                              TupleOne&& t1) noexcept {
  static_assert(std::tuple_size_v<std::decay_t<decltype(t0)>> <=
                std::tuple_size_v<std::decay_t<decltype(t1)>>);
  return mismatch_impl<std::tuple_size_v<std::decay_t<decltype(t0)>>>(
      std::forward<decltype(t0)>(t0), std::forward<decltype(t1)>(t1));
}

template <typename Predicate, typename TupleZero, typename TupleOne>
constexpr std::optional<std::size_t> mismatch(Predicate&& pred, TupleZero&& t0,
                                              TupleOne&& t1) noexcept {
  static_assert(std::tuple_size_v<std::decay_t<decltype(t0)>> <=
                std::tuple_size_v<std::decay_t<decltype(t1)>>);
  return mismatch_impl<std::tuple_size_v<std::decay_t<decltype(t0)>>>(
      std::forward<decltype(pred)>(pred), std::forward<decltype(t0)>(t0),
      std::forward<decltype(t1)>(t1));
}

template <std::size_t N, typename Tuple, typename T>
constexpr std::optional<std::size_t> find_impl(Tuple&& t,
                                               const T& value) noexcept {
  constexpr std::size_t I = std::tuple_size_v<std::decay_t<decltype(t)>> - N;

  if constexpr (N == 0u) {
    return std::nullopt;
  } else {
    return std::get<I>(t) == value
               ? std::make_optional(I)
               : find_impl<N - 1u>(std::forward<decltype(t)>(t), value);
  }
}

template <typename Tuple, typename T>
constexpr std::optional<std::size_t> find(Tuple&& t, const T& value) noexcept {
  return find_impl<std::tuple_size_v<std::decay_t<decltype(t)>>>(
      std::forward<decltype(t)>(t), value);
}

template <std::size_t N, typename Predicate, typename Tuple>
constexpr std::optional<std::size_t> find_if_impl(Predicate&& pred,
                                                  Tuple&& t) noexcept {
  constexpr std::size_t I = std::tuple_size_v<std::decay_t<decltype(t)>> - N;

  if constexpr (N == 0u) {
    return std::nullopt;
  } else {
    return pred(std::get<I>(t))
               ? std::make_optional(I)
               : find_if_impl<N - 1u>(std::forward<decltype(pred)>(pred),
                                      std::forward<decltype(t)>(t));
  }
}

template <typename Predicate, typename Tuple>
constexpr std::optional<std::size_t> find_if(Predicate&& pred,
                                             Tuple&& t) noexcept {
  return find_if_impl<std::tuple_size_v<std::decay_t<decltype(t)>>>(
      std::forward<decltype(pred)>(pred), std::forward<decltype(t)>(t));
}

template <std::size_t N, typename Predicate, typename Tuple>
constexpr std::optional<std::size_t> find_if_not_impl(Predicate&& pred,
                                                      Tuple&& t) noexcept {
  constexpr std::size_t I = std::tuple_size_v<std::decay_t<decltype(t)>> - N;

  if constexpr (N == 0u) {
    return std::nullopt;
  } else {
    return pred(std::get<I>(t))
               ? find_if_not_impl<N - 1u>(std::forward<decltype(pred)>(pred),
                                          std::forward<decltype(t)>(t))
               : std::make_optional(I);
  }
}

template <typename Predicate, typename Tuple>
constexpr std::optional<std::size_t> find_if_not(Predicate&& pred,
                                                 Tuple&& t) noexcept {
  return find_if_not_impl<std::tuple_size_v<std::decay_t<decltype(t)>>>(
      std::forward<decltype(pred)>(pred), std::forward<decltype(t)>(t));
}

Some tests:

auto print = [](auto x) { std::cout << x << '\n'; };

constexpr auto id = [](auto x) constexpr noexcept { return x; };

int main() {
  static_assert(all_of(id, std::make_tuple(true, true, true)), "assert 0");
  static_assert(any_of(id, std::make_tuple(false, false, true)), "assert 1");
  static_assert(none_of(id, std::make_tuple(false, false, false)), "assert 2");

  for_each(print, std::make_tuple(1, 2, 3));
  for_each_n<2u>(print, std::make_tuple(1, 2, 3));
  static_assert(count(std::make_tuple(true, true, true), true) == 3u,
                "assert 3");
  static_assert(count_if(id, std::make_tuple(false, false, false)) == 0u,
                "assert 4");
  static_assert(
      mismatch(std::make_tuple(1, 2, 3), std::make_tuple(1, 3, 3)).value() ==
          1u,
      "assert 5");
  static_assert(mismatch(std::equal_to<int>{}, std::make_tuple(1, 2, 3),
                         std::make_tuple(1, 2, 4))
                        .value() == 2u,
                "assert 6");
  static_assert(find(std::make_tuple(1, 2, 3), 3).value() == 2u, "assert 7");
  static_assert(find_if([](auto x) constexpr noexcept { return x == 2; },
                        std::make_tuple(1, 2, 3))
                        .value() == 1u,
                "assert 8");
  static_assert(find_if_not([](auto x) constexpr noexcept { return x != 1; },
                            std::make_tuple(1, 2, 3))
                        .value() == 0u,
                "assert 9");
}

Instead of iterators to the elements in a sequence, optional index values are returned based on whether or not the tuple elements satisfied the criteria. I'd like some feedback on the implementation, in particular I was wondering if there is a way around that ugly "impl"-pattern (namespaces are one option). I am also not checking whether or not tuple element types posses different operators, e.g. equality, which can lead to some nasty errors.

Answer 1

Well, it's workable. There are just a few things:

1. You mark most of your functions unconditionally noexcept. Woe befall anyone passing a callable which might throw. Or if comparing does so. Yes, fixing that is tedious if you don't use an evil macro.

2. You should be aware that predicates are generally allowed to return anything they want, as long as it can be contextually converted to bool. Unless you like brittle code, when you don't use a construct doing that contextual conversion, do an explicit cast.

3. One uses decltype(t) for forwarding in lambdas for a simple reason: The argument-type doesn't have a known name yet. If it has a simple name, that's doing things the hard way.

4. You don't leverage your own functions to implement the rest. Some examples for inspiration:

   template <typename Predicate, typename Tuple>
   constexpr bool none_of(Predicate&& pred, Tuple&& t) noexcept {
       return all_of(std::not_fn(std::ref(pred)), std::forward<Tuple>(t));
   }
   
   template <typename Predicate, typename Tuple>
   constexpr bool any_of(Predicate&& pred, Tuple&& t) noexcept {
       return !none_of(pred, std::forward<Tuple>(t));
   }
   
   template <typename Predicate, typename Tuple>
   constexpr std::size_t count_if(Predicate&& pred, Tuple&& t) noexcept {
       std::size_t r = 0;
       for_each(
           [&](auto&& x){ r += (bool)pred(std::forward<decltype(x)>(x)); },
           std::forward<Tuple>(t)
       );
   }
   
   template <typename Tuple, typename T>
   constexpr std::size_t count(Tuple&& t, const T& value) noexcept {
       return count_if([&](auto&& x){ return value == x; }, std::forward<Tuple>(t));
   }
   

5. Consider rewriting your for_each_n() in terms of a generic static_for().

6. Anyway, for_each_n() should either more closely follow the standard-library, by making n a runtime-argument (then best implement in terms of all_of()), or get a different name, like for_first_n().

7. mismatch() and find() have completely separate implementations for using a predicate and not using one. Why?
   The case without predicate is trivially implemented by cooking up the appropriate predicate and delegating.

8. Why does mismatch() expect the first tuple to not be longer than the second?
   That restriction is baffling, and will be vexing for any user.

9. mismatch() can also be easily implemented in terms of static_for(). Though should you maybe skip elements which cannot be compared?

10. find() is unusable if any tuple-member is not comparable to your needle / cannot be fed to your lambda. Shouldn't those members just be skipped?

11. find_if_not() should delegate to find_if() using std::not_fn().

12. As you wanted to get around the need for helper-functions, let me emphasize yet again that leveraging all the related functions you build and the standard-library helps there.

Answer 2

Looks good to me!

I'm pretty sure you don't need the constexpr noexcept clutter on all your lambdas: lambdas are at least constexpr(auto) and I think also noexcept(auto).

It is surprising, but I think technically reasonable, for you to take Pred&& pred by forwarding reference and then not forward it when you call it. This means that you can take either const or non-const predicates (always by reference), and call them with the appropriate constness, but always as an lvalue. Personally I would probably take const Pred& pred and screw anyone trying to pass in a mutable lambda; or take Pred pred and screw anyone trying to pass in an expensive-to-copy lambda without std::ref. Your way seems better, with the only downside being that it looks like a misuse of perfect forwarding until the reader studies it really hard. Perhaps a block comment is in order.

---

I can technically break your count by passing in types whose operator== returns a type which is BooleanLike but happens to have a wacky conversion to size_t. It would be better for you to explicitly cast the result of value == xs to bool before doing anything else with it:

template<class Tuple, class T>
constexpr size_t count(Tuple&& t, const T& value) noexcept {
  return std::apply(
      [&](auto&&... xs) {
        return (0 + ... + size_t(bool(value == xs)));
      },
      std::forward<decltype(t)>(t));
}

Stylistically I think your 0u was unnecessarily confusing: If you just mean "zero" and don't care about the type, then 0 is fine. If you're trying to avoid surprising implicit type-conversions and do all the math in size_t, then size_t(0) would be best.

---

It's interesting that your mismatch is the one function you didn't do with either std::apply or fold-expressions.

You seem to have forgotten that std::forward<T>(t) is the more common way to write std::forward<decltype(t)>(t) when T is known.

template <typename TupleZero, typename TupleOne>
constexpr std::optional<std::size_t> mismatch(TupleZero&& t0,
                                              TupleOne&& t1) noexcept {
  static_assert(std::tuple_size_v<std::decay_t<decltype(t0)>> <=
                std::tuple_size_v<std::decay_t<decltype(t1)>>);
  return mismatch_impl<std::tuple_size_v<std::decay_t<decltype(t0)>>>(
      std::forward<decltype(t0)>(t0), std::forward<decltype(t1)>(t1));
}

I would write this as:

template<class T0, class T1>
constexpr std::optional<size_t> mismatch(T0&& t0, T1&& t1) noexcept {
  constexpr size_t N = std::tuple_size_v<std::decay_t<T0>>;
  static_assert(N <= std::tuple_size_v<std::decay_t<T1>>);
  return mismatch_impl<N>(std::forward<T0>(t0), std::forward<T1>(t1));
}

And I would maybe look for a way to write it in terms of

size_t result = 0;
FOREACH...(
   [&]() {
       if (result == 0)
           if (std::get<Is>(t0) == std::get<Is>(t1))
               result = I + 1;
   }() ...
)
if (result != 0) {
    return result - 1;
}
return std::nullopt;

instead of the recursion you've got. But the FOREACH... part would have to use a helper function anyway to generate the Is; I don't think there's any way to coerce std::apply to do what you want here.