More C++ Idioms/Tag Dispatching

Tag dispatch

Intent

Simplify writing multiple SFINAE-constrained overloads.

Motivation

Tag dispatching is a useful complement to enable_if. It can also be used in conjunction with trailing return type and decltype, which uses expression SFINAE.

It is most useful when you have multiple overloads for the same function, and they all have conditions for when they can be called. With just enable_if, you have to test for not just the overloads condition, but also the negation of all other overloads' conditions, lest you get overload ambiguity. Tag dispatch will help reduce the mess:

Solution

namespace detail
{
    // tags for dispatching
    struct pick_3{};
    struct pick_2 : public pick_3{};
    struct pick_1 : public pick_2{};
    constexpr pick_1 selector{};

	// first choice - member preferred if exists
	template <typename Cont, typename Op>
	auto remove_if(pick_1, Cont& cont, Op&& op)
		-> decltype(cont.remove_if(std::forward<Op>(op)), void())
	{
		cont.remove_if(std::forward<Op>(op));
	}
	
	// second choice - erase remove idiom
	template <typename Cont, typename Op>
	auto remove_if(pick_2, Cont& cont, Op&& op)
		-> decltype(cont.erase(std::remove_if(std::begin(cont), std::end(cont), std::forward<Op>(op)), std::end(cont)), void())
	{
		cont.erase(std::remove_if(std::begin(cont), std::end(cont), std::forward<Op>(op)), std::end(cont));
	}
	
	// last choice - manual looping
	template <typename Cont, typename Op>
	void remove_if(pick_3, Cont& cont, Op&& op)
	{
		auto it = std::begin(cont);
        auto end = std::end(cont);
		while (it != end)
		{
			if (std::invoke_r<bool>(std::forward<Op>(op), *it))
				it = cont.erase(it);
			else
				++it;
		}
	}
}

template <typename Cont, typename Op>
auto remove_if(Cont& cont, Op&& op)
{
	detail::remove_if(detail::selector, cont, std::forward<Op>(op));
}

This works because exact match is a better match than a base class, which in turn is a better match than base of base, etc. Tag dispatch can also be used when the tag carries useful information, not just a preference ordering. For example, one can dispatch on typename std::iterator_traits<It>::iterator_category() and have different algorithms for std::random_access_iterators and std::forward_iterators.

C++20

C++20 added concepts and requires statements, which entirely eliminates the need for tag dispatching where the constraints include both A and A && B or both A and A || B for some A and B explicitly or in the definitions of concepts. The following code implements std::advance as an example.

namespace std
{
    // Input iterator overload
    constexpr void __advance(auto& __it, auto __n)
    {
        // If __n is negative, infinite loop
        // Undefined behavior as no observable side effects
        while (__n != 0)
        {
            --__n;
            ++__it;
        }
    }
    // Bidirectional iterator overload
    // Concept-constrained overload preferred so no problem
    constexpr void __advance(std::bidirectional_iterator auto& __it, auto __n)
    {
        if (__n < 0)
        {
            while (__n != 0)
            {
                ++__n;
                --__it;
            }
        }
        else
        {
            while (__n != 0)
            {
                --__n;
                ++__it;
            }
        }
    }
    // Random access iterator overload
    // std::random_access_iterator subsumes std::bidirectional_iterator so no problem
    constexpr void __advance(std::random_access_iterator auto& __it, auto __n)
    {
        __it += move(__n);
    }
    
    template <class _Ip, class _Np>
    constexpr void advance(_Ip& __it, _Np __n)
    {
        __advance(__it, move(__n));
    }
}