Comparing iterator with ptrdiff

Question

Looking at the following code

template <typename Itr>
constexpr auto foo(Itr first, Itr last)
{
    for (; first != std::prev(last); std::advance(first, 1))
    {
        for (auto j{ first }; j != (std::prev(last) - first); std::advance(j, 1)) // Error here
        {
            // Do stuff
        }
    }
}

In the second for loop I get the error:

no operator found which takes a right-hand operand of type '__int64' (or there is no acceptable conversion)

I am not allowed to compare the iterator with a ptrdiff_t apperently. So how can I accomplish this task? I have tried using every cast available, to both j and the ptrdiff_t - but nothing is allowed.

The reason I need this, is because I only want the inner loop to iterate over a smaller subset of the container for each iteration of the outer loop.

An example where I need this is in the implementation of the bubble sort algorithm

template <typename Itr>
constexpr auto bubble_sort(Itr first, Itr last)
{
    for (; first != std::prev(last); std::advance(first, 1))
    {
        auto swapped{ false };
        for (auto j{ first }; j != (std::prev(last) - first); std::advance(j, 1))
        {
            if (*j > *std::next(j)) // Pred
            {
                std::iter_swap(j, std::next(j));
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

Answer 1

If you want to write the method bubble_sort for forward iterators then it can look the following way as it is shown in the demonstrative program below. Neither ptrdiff_t is required.

Here you are.

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <ctime>

template <typename ForwardIterator>
void bubble_sort( ForwardIterator first, ForwardIterator last )
{
    for ( auto sorted = last; first != last && std::next( first ) != last; last = sorted  )
    {
        for ( auto next = sorted = first, prev = next++; next != last; ++next, ++prev )
        {
            if ( *next < *prev )
            {
                std::iter_swap( prev, next );
                sorted = next;
            }
        }
    }
}

template <typename ForwardIterator, typename Comparison>
void bubble_sort( ForwardIterator first, ForwardIterator last, Comparison cmp )
{
    for ( auto sorted = last; first != last && std::next( first ) != last; last = sorted  )
    {
        for ( auto next = sorted = first, prev = next++; next != last; ++next, ++prev )
        {
            if ( cmp( *next, *prev ) )
            {
                std::iter_swap( prev, next );
                sorted = next;
            }
        }
    }
}

int main() 
{
    const size_t N = 10;
    int a[N];

    std::srand( ( unsigned int )std::time( nullptr ) );

    for ( auto &item : a ) item = std::rand() % N;

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    bubble_sort( std::begin( a ), std::end( a ) );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    bubble_sort( std::begin( a ), std::end( a ), std::greater<>() );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

The program output might look like

1 5 4 4 0 9 7 3 3 1 
0 1 1 3 3 4 4 5 7 9 
9 7 5 4 4 3 3 1 1 0