Branchless binary search insertion

branchless_binary_search.h

/*
 * This function inserts first in [first+1, first+8), which is a
 * sorted sequence.
 */
template<typename RandomAccessIterator, typename Compare=std::less<>>
auto front_insert8(RandomAccessIterator first, Compare compare={}) const
    -> void
{
    auto it = first;
    it += compare(it[4], *first) << 2;
    it += compare(it[2], *first) << 1;
    it += compare(it[1], *first) << 0;

    switch (std::distance(first, it))
    {
        // rotate_left rotates the sequence beginning at the passed
        // iterator by N positions to the left
    
        case 1: rotate_left<2>(first); break;
        case 2: rotate_left<3>(first); break;
        case 3: rotate_left<4>(first); break;
        case 4: rotate_left<5>(first); break;
        case 5: rotate_left<6>(first); break;
        case 6: rotate_left<7>(first); break;
        case 7: rotate_left<8>(first); break;
        default: break;
    }
}