Как лучше всего контролировать направление итерации? - PullRequest
Новая
       13

Как лучше всего контролировать направление итерации?

3 голосов
/ 26 января 2012

У меня есть контейнер с большими объектами, которые дорого копировать.Я должен иногда перебирать весь контейнер нормально, а иногда наоборот.После того, как я определю направление итерации, мне не нужно менять промежуточный полет, т. Е. Не требуется произвольный доступ.

Я надеюсь сделать что-то вроде этого шаблона:Это программа на C ++ 11, но я не думаю, что это действительно помогает мне здесь.Я просто не вижу лучшего способа сделать это.Спасибо за любую помощь.

Ответы [ 6 ]

6 голосов
/ 26 января 2012

Почему бы вам просто не поместить свой алгоритм в функцию шаблона? Затем тривиально вызвать его с помощью begin / end или rbegin / rend. 

template <class Iterator>
void do_stuff(Iterator first, Iterator last)
{
    // Your loop code here.
}

Или вы можете использовать лямбду (поскольку это C ++ 11) вместе с std::for_each как: 

auto loop_body = [&](int &i) { std::cout << i << std::endl; } ;

if (backward)
  std::for_each(v.rbegin(), v.rend(), loop_body);
else
  std::for_each(v.begin(), v.end(), loop_body);
6 голосов
/ 26 января 2012

Стандартные контейнеры C ++ поставляются с такими вещами, которые называются «обратными итераторами».Используйте std::vector::rbegin() и std::vector::rend(), чтобы получить итератор, который повторяет в обратном направлении вектор.C ++ 03 может сделать это легко: 

#include <iostream> 
#include <vector>  

// Use const reference to pass expensive-to-copy types
void loop_body(const int& i)
{
    std::cout << i;
}

int main( int argc, char** ) 
{ 
    // pretend this is a vector of expensive objects 
    std::vector<int> foo = {1,2,3,4,5}; 

    // calculate forward or backward iteration direction 
    bool backwards = (argc > 1); 

    if( backwards ) { 
        std::for_each(foo.rbegin(), foo.rend(), &loop_body);
    } else { 
        std::for_each(foo.begin(), foo.end(), &loop_body);
    } 
    return 0; 
}

Вы можете сделать это, используя лямбды в C ++ 11: 

#include <iostream> 
#include <vector> 

int main( int argc, char** ) 
{ 
    // pretend this is a vector of expensive objects 
    std::vector<int> foo = {1,2,3,4,5}; 

    // calculate forward or backward iteration direction 
    bool backwards = (argc > 1); 

    // Use const reference to pass expensive-to-copy types
    auto loop_body = [](const int& i)
    {
        std::cout << i;
    };

    if( backwards ) { 
        std::for_each(foo.rbegin(), foo.rend(), loop_body);
    } else { 
        std::for_each(foo.begin(), foo.end(), loop_body);
    } 
    return 0; 
}
1 голос
/ 01 августа 2013

Даже если это старый вопрос, у меня недавно была та же проблема, и я решил ее следующим образом:

Поместите это куда-нибудь: 

namespace mani {

    // an extension to std::for_each where you can choose the direction:
    template <class InputIterator, class Function> Function for_each_reverse(bool reverse, const InputIterator& first, const InputIterator& last, Function fn)
    {
        if (reverse) {
            return std::for_each(std::reverse_iterator<InputIterator>(last), std::reverse_iterator<InputIterator>(first), fn);
        }
        return std::for_each(first, last, fn);
    }

}

... тогда вы можете использовать его как простойкак это: 

auto start = ...
auto end = ...
bool reverse = ...
mani::for_each_reverse(reverse, start, end, [&](const MyItem& item) {
    ...
});

Если reverse равно false, оно будет перебирать элементы в обычном направлении.Если reverse имеет значение true, оно будет повторяться в обратном направлении по элементам.

1 голос
/ 26 января 2012 
std::vector<int>::iterator begin = foo.begin();
std::vector<int>::iterator last = foo.end();
if (last != begin)
{
    --last;
    int direction = 1;
    if( backwards )
    {
        std::swap(begin, last);
        direction = -1;
    }
    for( auto& i = begin;  ; i += direction)
    {
        // do stuff
        if (i == last)
            break;
    }
}
1 голос
/ 26 января 2012

Стандартные библиотечные контейнеры имеют как нормальные, так и обратные итераторы, что решает большую часть проблемы.

К сожалению, это разные типы, поэтому вы не можете создать одну переменную, которая может содержать обычный и обратный итераторы.

Итак, я бы обернул ваш цикл в отдельную функцию, и шаблон для работы с обоими: 

template <typename It>
void myloop(It first, It last) {
    for(It cur = first; cur != last; ++cur)
    {
        // my loop body
        cout << *cur;
    }
}

А потом назовите это так: 

if( backwards )
    myloop(foo.rbegin(), foo.rend());
else
    myloop(foo.begin(), foo.end());

Конечно, тогда вы могли бы также использовать один из стандартных библиотечных алгоритмов вместо вашего цикла: 

if( backwards )
    std::for_each(foo.rbegin(), foo.rend(), [](int item){  cout << item;});
else
    std::for_each(foo.begin(), foo.end(), [](int item){  cout << item;});

(Заметьте, я здесь для простоты использую for_each. Очень вероятно, что std::transform или std::copy может быть лучше подходит для описания того, что вы хотите сделать.

Я также использовал лямбда-выражение вместо функции myloop. Вы можете сделать и то и другое, но лямбда намного короче, а ИМО легче читать.

0 голосов
/ 26 января 2012

Что вам нужно, так это создать свою собственную обертку итератора. Я могу думать о трех подходах:

  • Тот, который действует как union двух типов итераторов; он имеет два члена итератора разных типов и флаг, выбирающий, какой из них активен.

  • Тот, который содержит один двунаправленный итератор и флаг, указывающий, работать ли в прямом или обратном направлении.

  • Какая-то общая вещь итератора с виртуальными функциями. (неэффективно, но, вероятно, написать просто)

...