c++ - 比较迭代器与 ptrdiff

Question

看下面的代码

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
        }
    }
}

在第二个 for 循环中我收到错误:

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

显然我不允许将迭代器与 ptrdiff_t 进行比较。那么我怎样才能完成这个任务呢？我已尝试使用所有可用的类型转换，j 和 ptrdiff_t - 但什么都不允许。

我需要这个的原因是因为我只希望内部循环在外部循环的每次迭代中迭代容器的较小子集。

我需要这个的一个例子是冒泡排序算法的实现

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

如果您想为前向迭代器编写 bubble_sort 方法，那么它可以如下所示，如下面的演示程序所示。 ptrdiff_t 都不是必需的。

给你。

#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;
}

程序输出可能如下所示

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