Полиморфные итераторы в С++

Ответ 1

Обычный подход заключается в использовании полиморфизма времени компиляции вместо полиморфизма времени выполнения; это позволяет компилятору гораздо больше возможностей для оптимизации кода с использованием итератора и, как правило, более идиоматично в современном С++.

Если вам требуется полиморфное поведение во время выполнения, возможно, проще всего инкапсулировать полиморфизм внутри самого итератора и не подвергать его внешнему воздействию. Вы можете выполнить это, используя оболочку полиморфных функций, например function, найденную в Boost, С++ TR1 и С++ 0x. Я привел пример здесь на основе итератора фильтра из одного из моих проектов хобби:

template <typename ForwardIt>
class filter_iterator
    : public std::iterator<
          std::forward_iterator_tag, 
          typename std::iterator_traits<ForwardIt>::value_type>

{
public:

    typedef typename std::iterator_traits<ForwardIt>::value_type ValueType;
    typedef typename std::function<bool(ValueType)> FunctionType;

    filter_iterator() { }

    explicit filter_iterator(ForwardIt end)
        : it_(end), end_(end) 
    {
    }

    filter_iterator(ForwardIt it, ForwardIt end, FunctionType is_filtered) 
        : it_(it), end_(end), is_filtered_(is_filtered)
    { 
        skip_filtered_elements(); 
    }

    const ValueType& operator*()  const { return it_.operator*();  }
    const ValueType* operator->() const { return it_.operator->(); }

    filter_iterator& operator++()   
    { 
        ++it_; skip_filtered_elements(); return *this; 
    }

    filter_iterator operator++(int) 
    { 
        filter_iterator it(*this); ++*this; return it; 
    }


    friend bool operator==(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return lhs.it_ == rhs.it_;
    }

    friend bool operator!=(const filter_iterator& lhs,
                           const filter_iterator& rhs)
    {
        return !(lhs == rhs);
    }

private:

    void skip_filtered_elements()
    {
        while (it_ != end_ && is_filtered_(*it_))
            std::advance(it_, 1);
    }

    ForwardIt it_;
    ForwardIt end_;

    std::function<bool(const ValueType&)> is_filtered_;
};

template <typename ForwardIt>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt end)
{
    return filter_iterator<ForwardIt>(end);
}

template <typename ForwardIt, typename Function>
filter_iterator<ForwardIt> make_filter_iterator(ForwardIt it, 
                                                ForwardIt end, 
                                                Function f)
{
    return filter_iterator<ForwardIt>(it, end, f);
}

Использование прост. Этот пример (с использованием выражения лямбда С++ 0x как тип функции) демонстрирует фильтрацию нечетных чисел из диапазона:

int main()
{
    std::array<int, 4> x = { 1, 2, 3, 4 };

    std::copy(make_filter_iterator(x.begin(), x.end(), [](int i) { return i % 2; }),
              make_filter_iterator(x.end()),
              std::ostream_iterator<int>(std::cout, " "));
}

Ответ 2

Здесь есть две проблемы:

• Синтаксис
• : STL предполагает, что итераторы предоставляют признаки (value_type, reference например), которые должны соответствовать фактическому элементу.
• семантика: итераторы должны быть скопированы.

Помните, что (в С++) итератор не является диапазоном, и поэтому операция ++ быстро становится беспорядочной, потому что вам нужно пропустить некоторые элементы, но (с традиционной реализацией) вы не можете знать, сколько элементов в вашем распоряжении...

Поэтому, если вам нужны полиморфные итераторы, которые следуют за интерфейсом GOF, вам придется отказаться от использования алгоритмов STL.

Тем не менее, вполне возможно реализовать полиморфные итераторы:

struct IterBase
{
  virtual void increment() = 0;
  virtual void decrement() = 0;

  // others
};

class Iter
{
public:
  Iter& operator++() { base->increment(); return *this; }
  Iter operator++(int) { Iter tmp(*this); base->increment(); return tmp; }

  // others

private:
  std::unique_ptr<IterBase> base;
};

И тогда вам нужно будет написать все конструкторы копирования, операторы присваивания и деструкторы, чтобы делать правильные вещи...

Без шаблонного полиморфизма, хотя это стоит того, только если ваш итератор предназначен только для использования в одном типе...

Ответ 3

Хорошее решение, которое я видел связанным с вопросом Оли Чарльверта, который не получил большого доверия (по крайней мере, не так сильно, как я думал, что это должно).

class Iterator
{
public:
    SmartPointer<IteratorImplementation> ItrPtr;

    //Delegate methods to ItrPtr
}

Затем вы можете передать Iterator по значениям и методам отложенности к содержащемуся умному указателю; Это в основном итератор, реализующий шаблон "Стратегия", и стратегия демонстрирует полиморфное поведение.

Ответ 4

Это можно сделать с помощью итератора, который содержит указатель в некоторой форме, а затем передает функциональность указателю.

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

• Не используйте shared_ptr!

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

Поэтому вам нужно клонировать каждый раз, когда вы копируете, но, к счастью, с С++ 0x вы можете просто переместить большую часть времени, а не клонировать.

Вам также нужно знать, что операции будут удалены по v-таблице для каждой итерации, что может привести к ее медленному запуску, чем если бы вы сделали полиморфические методы "макро" (и, возможно, реализовали с шаблоном, поэтому вам не нужно перепишите код).

Ответ 5

Люди говорят, что интерфейсы должны быть максимально простыми и общими. В вашем случае вы описываете необработанный указатель как нечто, что не является "возможным". Итак, я бы предположил, что ваше очевидное решение использовать интеллектуальный указатель - это самый простой и общий метод, который возможен.

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

Ответ 6

Был там. Сделано это.

Что вы можете сделать, это скрыть свой интерфейс итератора за другим итератором. Предположим, что у вас есть несколько итераторов, которые скрываются за интерфейсом IIterator.

Затем напишите другой класс, похожий на итератор, например. MyIterator, который содержит указатель на IIterator и который просто перенаправляет все вызовы на IIterator, например:

template <typename T>
class MyIterator
    {
    public:
       MyIterator() : m_iterator(nullptr) {}
       MyIterator(IIterator *it) : m_iterator(it) {}
       MyIterator &operator++()
          {
          if (m_iterator) m_iterator->operator++();
          return *this;
          }
       T &operator*() const
          {
          if (m_iterator) return m_iterator->operator*();
          else            throw an exception?
          }
    private
       IIterator *m_iterator;
    };

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