Полиморфный итератор на базе итераторов STL
От: Vain Россия google.ru
Дата: 17.11.09 19:10
Оценка:
Надо мне было сделать полиморфный итератор, т.е. чистый интерфейс для итератора, т.к. типы которые итерируются — неизвестны на стадии компиляции. Интерфейс примерно такой:
class MyBaseIterator
{
  virtual ~MyBaseIterator() = 0 {}
  virtual void start(bool asForward = true) = 0;
  virtual void step(bool asForward = true) = 0;
  virtual bool done() const = 0;
  virtual mytype getFoo() const = 0;
  virtual bool seek(int id) = 0;
};

Содержимое конечного класса стало примерно таким:
class CBlablaIterator :
  public MyBaseIterator
{
protected:
  const IterationType*                    m_IterObject;   //Класс, объект которого итерируем по базовому интерфейсу.
  IterationTypeContainer::const_iterator  m_IterObjectIt; //Итератор на контейнер-мембер внутри итерируемого объекта.
  //bool                                    m_asForward;    //Нежелательный параметр, см. далее.

  //...
};

Итерируемый объект примерно такой:
typedef std::blabla ContType; //vector, list, map, etc
class IterationType
{
  friend class CBlablaIterator;
protected:
  //..
  ContType m_IterContainer;

public:
  void CreateBlablaIterator(MyBaseIterator*& pIt) const;
  //...
};

Прочитав это, реализация на одном однонаправленном итераторе оказалась несложной:
void CBlablaIterator::start(bool asForward)
{
  ASSERT(m_IterObject);
  if(m_IterObject)
  {
    if(asForward)
    {
      m_IterObjectIt = m_IterObject->m_IterContainer.begin();
    }
    else
    {
      m_IterObjectIt = m_IterObject->m_IterContainer.rbegin().base();
    }
    //m_asForward = asForward;
  }
}

void CBlablaIterator::step(bool asForward)
{
  ASSERT(m_IterObject);
  if(m_IterObject)
  {
    if(asForward)
    {
      if(m_IterObjectIt != m_IterObject->m_IterContainer.end())
      {
        m_IterObjectIt++;
      }
    }
    else
    {
      ContType::const_reverse_iterator reverseIt = m_IterObjectIt;
      if(reverseIt != m_IterObject->m_IterContainer.rend())
      {
        reverseIt++;
        m_IterObjectIt = reverseIt.base();
      }
    }
    //m_asForward = asForward;
  }
}

Проблема возникла, когда надо было реализовать функцию done. Примерная реализация должна была быть такая:
void CBlablaIterator::done()
{
  ASSERT(m_IterObject);
  if(m_IterObject)
  {
    if(m_asForward) //Требует присутствия нежелательного параметра.
    {
      if(m_IterObjectIt != m_IterObject->m_IterContainer.end())
      {
        return false;
      }
    }
    else
    {
      ContType::const_reverse_iterator reverseIt = m_IterObjectIt;
      if(reverseIt != m_IterObject->m_IterContainer.rend())
      {
        return false;
      }
    }
  }

  return true;
}

Можно ли как-нибудь обойтись без этого m_asForward? Почему итераторы для двунаправленных контейнеров — однонаправленные?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: Полиморфный итератор на базе итераторов STL
От: _Dreamer Россия  
Дата: 18.11.09 04:17
Оценка:
Здравствуйте, Vain, Вы писали:

V>Надо мне было сделать полиморфный итератор, т.е. чистый интерфейс для итератора, т.к. типы которые итерируются — неизвестны на стадии компиляции. Интерфейс примерно такой:
V>Можно ли как-нибудь обойтись без этого m_asForward? Почему итераторы для двунаправленных контейнеров — однонаправленные?

подождите. Вы хотите начинать итерирование как с конца, так и сначала, и осуществлять его в обоих направлениях, так?
для того, чтобы начать, нужно знать, откуда, и эта информация у метода start есть.
для того, чтобы совершить итерацию, нужно знать, в какую сторону, и эта информация у метода step тоже есть.

теперь нужно выяснить, какова логика метода done.
варианта здесь я вижу 2 —
1. done() == true при достижении последнего элемента при старте с первого(и наоборот, первого при старте с последнего)
2. done() == true при невозможности итерироваться в сторону, в которую была совершена последняя итерация ( как это сделано у Вас, если раскомментировать обращения к m_asForward, обратите внимание, если на самом деле нужно другое )

и в обоих случаях, нужно знать, а что же является последним элементом для текущего процесса итерации.
на мой взгляд, простейшим вариантом как раз и будет флаг направления, можно конечно и итератор на последний элемент хранить, либо даже функтор, возвращающий итератор на последний элемент.
Re: Полиморфный итератор на базе итераторов STL
От: Erop Россия  
Дата: 18.11.09 05:42
Оценка:
Здравствуйте, Vain, Вы писали:


V>Можно ли как-нибудь обойтись без этого m_asForward? Почему итераторы для двунаправленных контейнеров — однонаправленные?

Но лично мне больше понравился бы немного другой интерфейс: 
template<typename T> 
struct ISequenceIterator{
    virtual ~ISequenceIterator() = 0 {}
    virtual bool seek(int id) = 0;
    virtual bool seekRelative(int id) = 0;
    virtual bool step() = 0;
    virtual bool isDone() = 0;

    virtual const T& get() = 0;
  
    virtual ISequenceIterator* getReverseIterator() = 0;

}

и иметь две НЕЗАВИСИМЫЕ реализации для прямого итератора и для обратного.
Можно, даже, легко, довольно, сделать это всё шаблонным.
Ну, типа как-то так: 
template<typename TContainer> struct REndRBeginGetter;

template<typename TContainer>
struct EndBeginGetter {
    typedef typename TContainer::iterator iterator;
    typedef typename TContainer::const_iterator const_iterator;

    typedef REndRBeginGetter<TContainer> TRGetter;

    static iterator begin( TContainer& cnt ) { return cnt.begin(); }
    static const_iterator begin( const TContainer& cnt ) { return cnt.begin(); }
    static iterator end( TContainer& cnt ) { return cnt.end(); }
    static const_iterator end( const TContainer& cnt ) { return cnt.end(); }
};

template<typename TContainer>
struct REndRBeginGetter {
    typedef typename TContainer::reverse_iterator iterator;
    typedef typename TContainer::const_reverse_iterator const_iterator;

    typedef EndBeginGetter<TContainer> TRGetter;

    static iterator begin( TContainer& cnt ) { return cnt.rbegin(); }
    static const_iterator begin( const TContainer& cnt ) { return cnt.rbegin(); }
    static iterator end( TContainer& cnt ) { return cnt.rend(); }
    static const_iterator end( const TContainer& cnt ) { return cnt.rend(); }
};

template<typename TContainer, 
    typename TGetter = EndBeginGetter<TContainer>, 
    typename T = typename TIterator::value_type>
class CSequenceIterator : public ISequenceIterator<T> {
public:
   typedef typename TGetter::const_iterator TIterator;
   //  конструкторы от TContainer, TIterator и т. д. и операторы присваивания по вкусу

    virtual bool seek(int id) {  return pos = begin(), seekRelative( id ); } // или как-нибудь, более корректно
    virtual bool seekRelative(int id); // тупо реализуешь через стандартные алгоритмы на итераторе
    virtual bool step() { return ++pos != end(); }
    virtual bool isDone() { return pos != end(); }

    virtual const T& get() { return *pos; }
  
    virtual ISequenceIterator* getReverseIterator(); // тут, например, зовёшь new подходящий конструктор 
        //    класса CSequenceIterator<TContainer, typename TGetter::TRGetter, T>
private:
    const TContainer& cont;
    TIterator pos;

    TIterator end() const { return TGetter::end( cont ); }
    TIterator begin() const { return TGetter::begin( cont ); }
};
ну и не заморачиваться особо. Правда при этом могут быть проблемы с владением.
То есть, если у тебя от чего-то есть проблемы с размножением объектов-итераторов, то можно воспользоваться следующим трюком
Автор: Erop
Дата: 06.03.08
...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: Полиморфный итератор на базе итераторов STL
От: Adriano  
Дата: 18.11.09 12:52
Оценка:
Здравствуйте, Vain, Вы писали:

V>Надо мне было сделать полиморфный итератор, т.е. чистый интерфейс для итератора, т.к. типы которые итерируются — неизвестны на стадии компиляции. Интерфейс примерно такой:

Почитай здесь(все, 1-15), Александреску уже все давно придумал
Re: Полиморфный итератор на базе итераторов STL
От: Sni4ok  
Дата: 18.11.09 13:50
Оценка:
Здравствуйте, Vain, Вы писали:

V>Надо мне было сделать полиморфный итератор, т.е. чистый интерфейс для итератора, т.к. типы которые итерируются — неизвестны на стадии компиляции. Интерфейс примерно такой:
V>
V>class MyBaseIterator
V>{
V>  virtual ~MyBaseIterator() = 0 {}
V>  virtual void start(bool asForward = true) = 0;
V>  virtual void step(bool asForward = true) = 0;
V>  virtual bool done() const = 0;
V>  virtual mytype getFoo() const = 0;
V>  virtual bool seek(int id) = 0;
V>};
V>



чёто слишком сложно, создайте базовый класс с чисто виртуальными функциями которые необходимы для данного типа итератора, а дальше в обёртке над boost::iterator_facade просто их вызывайте, например для самого простого последовательного итератора будет нечто такое:

struct iterator_base{
    virtual void increment() = 0;
    virtual hz_chto& dereference() const = 0;
    virtual bool equal(const iterator_base& other) const = 0;
    virtual ~iterator_base(){}
};
class iterator : public boost::iterator_facade<iterator, hz_chto, boost::forward_traversal_tag>{
    friend class boost::iterator_core_access;
    boost::shared_ptr<iterator_base> ptr;
    void increment(){
        return ptr->increment();
    }
    hz_chto& dereference() const{ 
        return ptr->dereference();
    }
    bool equal(const iterator& other) const{
        return ptr->equal(*other.ptr);
    }
public:
    iterator(iterator_base* ptr) : ptr(ptr){
    }
};
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.