Сравнение итератора с ptrdiff - PullRequest
Новая
       11

Сравнение итератора с ptrdiff

1 голос
/ 08 апреля 2020

Глядя на следующий код 

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

Во втором для l oop я получаю ошибку: 

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

Мне не разрешено сравнивать итератор с ptrdiff_t apperently. Итак, как я могу выполнить эту задачу? Я пытался использовать все доступные броски, как для j, так и для ptrdiff_t, но ничего не разрешено.

Причина, по которой мне это нужно, заключается в том, что я хочу, чтобы внутренний l oop перебирал только меньшее подмножество контейнер для каждой итерации внешнего l oop.

Примером, где мне это нужно, является реализация алгоритма сортировки пузырьков 

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

1 Ответ

2 голосов
/ 08 апреля 2020

Если вы хотите написать метод 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
...