С++ условный однонаправленный итератор - программирование

С++ условный однонаправленный итератор

Я хочу добиться чего-то вроде псевдокода ниже:

string foo;  // or vector<int> foo;
auto itr = bar?  foo.begin() : foo.rbegin();
auto end = bar?  foo.end() : foo.rend();
for (  ; itr != end; ++itr) {
// SomeAction ...
}

То есть я хочу, чтобы itr был прямым или обратным итератором, в зависимости от некоторой bar условий, для сканирования в прямом или обратном направлении.

Очевидно, такой код не будет работать, так как прямой и обратный итератор имеет разный тип.

Обратите внимание, что я не хочу разбиваться на два //SomeAction, так как код, подобный //SomeAction будет дублирован.

Как я могу это сделать? Ответы с использованием С++ 11 и/или ранее являются предпочтительными.

Также, пожалуйста, уточните, если строка и вектор имеют разные решения.

4b9b3361

ОТВЕТЫ

Ответ 1

Я бы поместил логику в функцию с двумя итераторами:

<template typename Iter>
void do_stuff(Iter first, Iter last)
{
    for(; first != last; ++first)
    {
        // Do logic
    }
}

bar ? do_stuff(foo.begin(), foo.end()) : do_stuff(foo.rbegin(), foo.rend());

Ответ 2

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

Один из вариантов - перенести их использование в шаблонную функцию:

template<class Iterator> void loop(Iterator begin, Iterator end)
{
    for (auto itr = begin; itr != end; ++itr) { ... }
}

if (bar) loop(foo.begin(), foo.end());
else loop(foo.rbegin(), foo.rend());

В более новых версиях C++ (C++ 14 и новее, а не C++ 11) функция цикла может быть лямбда-выражением, используя auto в качестве типа параметра.

auto loop = [](auto begin, auto end)
{
    for (auto itr = begin; itr != end; ++itr) { ... }
};

Другой вариант, хотя и несколько более сложный, состоит в создании типа-обертки, который может содержать итератор или обратный итератор и действовать как сам итератор, по крайней мере, с операторами сравнения, приращения и разыменования.

Ответ 3

Я не хочу разбиваться на два цикла, так как код, подобный //SomeAction, будет дублирован.

Поместите действие в лямбду.

auto lambda = [&](char &val) // 'ElementType &'
{
    // ...
};

if (bar)
{
    for (auto &val : foo)
        lambda(val);
}
else
{
    for (auto it = foo.rbegin(); it != foo.rend(); it++)
        lambda(*it);
}

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

std::size_t i, end, step;
if (bar)
{
    i = 0;
    end = foo.size();
    step = 1;
}
else
{
    i = foo.size() - 1;
    end = -1;
    step = -1;
}

for (; i != end; i += step)
{
    // ...
}

Ответ 4

Один из вариантов - написать шаблон функции для цикла, который работает с любым итератором. Затем условно вызвать один экземпляр шаблона или другой. Другие ответы уже показывают примеры того, как это сделать.

Кстати, шаблон цикла может уже существовать в заголовке <algorithm> зависимости от того, что вы делаете. Вы можете использовать (но не ограничиваясь этим) либо std::for_each, std::accumulate либо std::remove например:

auto body = [captures,needed,by,some,action](char c) {
    // SomeAction ...
};
if (bar)
    std::for_each(foo.begin(),  foo.end(),  body);
else
    std::for_each(foo.rbegin(), foo.rend(), body);

Если тело цикла можно повторно использовать вне этого контекста, то вы также можете использовать именованную функцию, но только если вам не нужны захваты. С перехватами вы можете использовать именованный тип функтора, но это довольно сложный пример.

Другой вариант - использовать адаптер итератора для удаления типов. Он поставляется с небольшими затратами времени выполнения и, вероятно, здесь не нужен. Но полезно упомянуть, если у людей есть тесно связанная проблема, где она лучше подходит.

По сути, такой адаптер предназначен для шаблонного итератора, что std::function для аргумента шаблонного функтора. Это устраняет необходимость в шаблонах, которые могут быть полезны, в частности, для абстрактных интерфейсов. К сожалению, в стандартной библиотеке нет такого адаптера итератора.

Альтернативой для адаптера итератора является адаптер диапазона (также не входящий в стандартную библиотеку):

using t_erase = boost::adaptors::type_erased<>;
auto range = bar
    ? boost::make_iterator_range(foo.begin(),  foo.end())  | t_erase()
    : boost::make_iterator_range(foo.rbegin(), foo.rend()) | t_erase();
for(char c : range) {
    // SomeAction ...
}

Ответ 5

Используйте класс итератора, который абстрагирует эту функциональность.

Итератор имеет 3 основных функции:

  • инкремент
  • разыменовывают
  • Проверьте на равенство

Мы можем использовать их в качестве руководства при создании интерфейса, который абстрагирует это поведение. Этот интерфейс немного громоздок в использовании сам по себе, но мы можем использовать его для создания класса-оболочки GenericIterator, который может автоматически назначаться любому другому типу итератора.

GenericIterator: готовое решение общего назначения

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

int main() {
    bool iterate_forward;
    std::cin >> iterate_forward; 

    std::vector<int> values { 1, 2, 3 };

    GenericIterator<int&> begin, end; 

    if(iterate_forward) {
        begin = values.begin(); 
        end = values.end(); 
    } else {
        begin = values.rbegin();
        end = values.rend(); 
    }

    // Print out the values
    for(; begin != end; ++begin) {
        std::cout << *begin << " ";
    }
}

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

Замечания по производительности GenericIterator

С точки зрения функциональности GenericIterator предоставляет вам все, что вы могли бы попросить. Это легкий; и это удобно; и его легко изменить, если ваш код должен читать из std::list или чего-то другого, кроме вектора.

Однако из-за фундаментальных ограничений полиморфизма во время выполнения компилятору значительно сложнее встроить вызовы виртуальных методов. Это означает, что GenericIterator несет больше накладных расходов во время выполнения, чем другие решения.

Хорошая идея отдавать предпочтение статическому полиморфизму и шаблонам по сравнению с полиморфизмом во время выполнения, когда это возможно. Если вы можете сделать это, используйте что-то вроде решения Mark B, которое в конечном итоге будет более производительным.

аппендикс

Определение интерфейса итератора. Этот класс используется для реализации GenericIterator. GenericIterator содержит указатель на IteratorBase, который используется для достижения полиморфизма во время выполнения. Благодаря методу clone() GenericIterator остается копируемым и подвижным, как и ожидалось.

template <class Value>
class IteratorBase
{
   public:
    virtual Value         operator*() const                     = 0;
    virtual IteratorBase& operator++()                          = 0;
    virtual bool          operator!=(IteratorBase const&) const = 0;
    virtual bool          operator==(IteratorBase const&) const = 0;

    // We need this function for making copies of the iterator
    virtual IteratorBase* clone() const = 0;
    virtual ~IteratorBase()             = default;
};

Конкретный класс, реализующий IteratorBase. Этот класс реализует поведение, определенное в IteratorBase. Содержащийся в нем итератор является фактическим итератором, возвращаемым коллекцией, для которой вы выполняете итерацию. В вашем случае это будет либо std::vector::iterator либо std::vector::reverse_iterator.

template <class Iter, class Value>
class IteratorDerived : public IteratorBase<Value>
{
    Iter it;

   public:
    IteratorDerived() = default;
    IteratorDerived(Iter it) : it(it) {}
    IteratorDerived(IteratorDerived const&) = default;
    IteratorDerived(IteratorDerived&&)      = default;

    Value                operator*() const override { return *it; }
    IteratorBase<Value>& operator++() override
    {
        ++it;
        return *this;
    }

    bool operator!=(IteratorBase<Value> const& other) const override
    {
        auto* derived = dynamic_cast<IteratorDerived const*>(&other);
        return derived == nullptr || it != derived->it;
    }
    bool operator==(IteratorBase<Value> const& other) const override
    {
        auto* derived = dynamic_cast<IteratorDerived const*>(&other);
        return derived != nullptr && it == derived->it;
    }
    IteratorBase<Value>* clone() const override
    {
        return new IteratorDerived(*this);
    }
};

Реализация GenericIterator. Это фактическая реализация GenericIterator, основанная на IteratorBase и IteratorDerived. Любой итератор, данный GenericIterator в соответствующий IteratorDerived, который затем назначается указателю IteratorBase.

template <class Value>
class GenericIterator
{
    std::unique_ptr<IteratorBase<Value>> iterator;

   public:
    using value_type = typename std::remove_reference<Value>::type; 
    using reference = Value;

    GenericIterator() = default;
    GenericIterator(GenericIterator const& it) : iterator(it.iterator->clone())
    {
    }
    GenericIterator(GenericIterator&&) = default;

    // Creates a GenericIterator from an IteratorBase
    explicit GenericIterator(IteratorBase<Value> const& it)
      : iterator(it.clone())
    {
    }

    // Creates a GenericIterator from an IteratorDerived
    template <class Iter>
    explicit GenericIterator(IteratorDerived<Iter, Value> const& it)
      : iterator(it.clone())
    {
    }

    // Creates a GenericIterator by wrapping another Iter
    template <class Iter>
    GenericIterator(Iter it) : iterator(new IteratorDerived<Iter, Value>(it))
    {
    }

    GenericIterator& operator=(GenericIterator const& it)
    {
        iterator = std::unique_ptr<IteratorBase<Value>>(it.iterator->clone());
        return *this;
    }
    GenericIterator& operator=(GenericIterator&&) = default;

    Value            operator*() const { return *(*iterator); }
    GenericIterator& operator++()
    {
        ++(*iterator);
        return *this;
    }
    void operator++(int) {
        ++(*iterator);
    }

    bool operator==(GenericIterator const& other) const
    {
        return *iterator == *other.iterator;
    }
    bool operator!=(GenericIterator const& other) const
    {
        return *iterator != *other.iterator;
    }
};