Const-correctness самоидентизированных итераторов

Общая цель

Я управляю коллекцией объектов (Collection of Real как простой пример). Затем я определил итераторы в своей коллекции. Это означает: iterator, const_iterator, reverse_iterator и const_reverse_iterator. В этом примере я буду обращать внимание только на iterator и const_iterator, два других очень похожи.

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

Как я реализовал коллекцию

В этом примере мой объект в коллекции очень прост. Цель состоит в том, чтобы иметь объект вместо собственного типа:

struct Real
{
    public:
      double r;
};

Затем я определяю свою коллекцию, не задумываясь о реальном контейнере внутри:

class Collection
{
  public:
    typedef std::vector<Real>::iterator iterator;
    typedef std::vector<Real>::const_iterator const_iterator;
  private:
    std::vector<Real> data;
  public:
    Collection() : data() {}
    Collection(unsigned long int n) : data(n) {}
    Collection(unsigned long int n, const Real& x) : data(n,x) {}
    Collection::iterator       begin()       { return this->data.begin(); }
    Collection::iterator       end()         { return this->data.end(); }
    Collection::const_iterator begin() const { return this->data.begin(); }
    Collection::const_iterator end() const   { return this->data.end(); }
};

Это очень хорошо работает в этом простом примере:

int main()
{
  Collection c(5);
  double k = 1.0;
  for(Collection::iterator it = c.begin(); it != c.end(); ++it)
  {
    it->r = k;
    k *= -2.0;
  }

  std::cout << "print c with Collection::iterator" << std::endl;
  for(Collection::iterator it = c.begin(); it != c.end(); ++it)
    std::cout << it->r << std::endl;

  std::cout << "print c with Collection::const_iterator" << std::endl;
  for(Collection::const_iterator it = c.begin(); it != c.end(); ++it)
    std::cout << it->r << std::endl;

  return 0;
}

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

print with Collection::iterator
1
-2
4
-8
16
print with Collection::const_iterator
1
-2
4
-8
16

Как я реализовал фильтр

Теперь я хочу создать абстрактный фильтр, имеющий ссылку или указатель на коллекцию, имеющий итераторы и имеющий абстрактную функцию, принимающую значения через фильтр. Для этого первого шага я написал класс без итераторов:

class CollectionFilter
{
  private:
    Collection& col;
  public:
    CollectionFilter(Collection& c) : col(c) {}
    virtual ~CollectionFilter() {}
    Collection& collection() { return this->col; }
    iterator begin() { /* todo */ }
    iterator end() { /* todo */ }
    const_iterator begin() const { /* todo */ }
    const_iterator end() const { /* todo */ }
    virtual bool accept(const Real& x) const = 0;
};

Затем довольно легко создать новый фильтр, реализующий конкретное условие:

class CollectionFilterPositive : public CollectionFilter
{
  public:
    CollectionFilterPositive(Collection& c) : CollectionFilter(c) {}
    virtual ~CollectionFilterPositive() {}
    virtual bool accept(const Real& x) const { return x.r >= 0.0; }
};

Перед реализацией итераторов в фильтре у меня есть некоторые замечания/вопросы.

• Этот фильтр работает на не-const Collection&, то действительно ли нужны функции begin() const и end() const? И если да, то почему?
• Я не могу применить фильтр на const Collection&, но это явно необходимо для моей цели. Что может быть хорошим способом сделать это? Нужно ли дублировать класс CollectionFilter в классе CollectionFilterConst с очень похожим кодом? Более того, это решение довольно запутанно для пользователя, которому нужно наследовать два подобных класса.

Затем переходим к реализации итераторов. В этом примере я написал только iterator, а не const_iterator. Я добавляю это в свой класс:

class CollectionFilter
{
  public:
    class iterator
    {
      private:
        CollectionFilter*    filter;
        Collection::iterator iter;
      public:
                  iterator(CollectionFilter* f, Collection::iterator i) : filter(f), iter(i) {}
                  iterator(const iterator& i) : filter(i.filter), iter(i.iter) {}
        iterator& operator = (const iterator& i) { this->filter = i.filter; this->iter = i.iter; return *this; }
        iterator& operator ++ ()
        {
          if(this->iter != this->filter->collection().end())
          {
            do
            {
              ++this->iter;
            } while(this->iter != this->filter->collection().end() && !this->filter->accept(*this->iter));
          }
        }
        iterator operator ++ (int) { /* similar */ }
        Real& operator * () { return *this->iter; }
        Collection::iterator operator -> () { return this->iter; }
        bool operator == (const iterator& i) const { return this->iter == i.iter; }
        bool operator != (const iterator& i) const { return this->iter != i.iter; }
    };
  public:
    iterator begin()
    {
      Collection::iterator it = this->col.begin();
      if(!this->accept(*it)) ++it;
      return CollectionFilter::iterator(this,it);
    }
    iterator end()
    {
      Collection::iterator it = this->col.end();
      return CollectionFilter::iterator(this,it);
    }
};

Это также хорошо работает на этом простом примере

int main()
{
  Collection c(5);
  double k = 1.0;
  for(Collection::iterator it = c.begin(); it != c.end(); ++it)
  {
    it->r = k;
    k *= -2.0;
  }

  std::cout << "print c with CollectionFilterPositive::iterator" << std::endl;  
  CollectionFilterPositive fc(c);
  for(CollectionFilterPositive::iterator it = fc.begin(); it != fc.end(); ++it)
    std::cout << it->r << std::endl;

  return 0;
}

дает ожидаемый результат:

print with CollectionFilterPositive::iterator
1
4
16

Снова, некоторые вопросы:

3. Я совершенно не согласен с этим?
4. Я предполагаю, что мне нужно дублировать код CollectionFilter::iterator, чтобы реализовать CollectionFilter::const_iterator только с небольшими изменениями. Есть ли способ избежать дублирования этого кода (написано 8 раз, если я считаю дублированный класс CollectionFilterConst и обратные итераторы)?
5. Я не чувствую себя комфортно с константой моего кода. Вы видите некоторые проблемы?

Спасибо заранее!

Ответы

class Collection {         
    template<typename Iterator, typename Predicate>
    class filter_iterator_tmpl :
    public std::iterator<std::input_iterator_tag, typename Iterator::value_type, typename Iterator::difference_type, typename Iterator::pointer, typename Iterator::reference> {
    private:
        Iterator underlying_iterator_;
        Predicate predicate_;

    public:
        filter_iterator_tmpl& operator++() {
            do {
                ++ underlying_iterator_;
            } while(! predicate_(*underlying_iterator_));
            return *this;
        }

        typename Iterator::reference operator*() const {
            return *underlying_iterator_;
        }

        ....
    }

};

class Collection {
private:
    template<typename Iterator, typename Predicate>
    class filter_iterator_tmpl;
public:
    template<typename Predicate>
    using filter_iterator = filter_iterator_tmpl<Collection::iterator, Predicate>;

    template<typename Predicate>
    using const_filter_iterator = filter_iterator_tmpl<Collection::const_iterator, Predicate>;

    template<typename Predicate>
    filter_iterator<Predicate> begin_filter(const Predicate& pred);

    template<typename Predicate>
    const_filter_iterator<Predicate> begin_filter(const Predicate& pred) const;
}

template <typename C>
class Filter {
    static_assert(std::is_same<
                      std::decay_t<C>,
                      Collection
                  >::value, "Can only filter a Collection.");

    using collection_iterator = decltype(std::declval<C&>().begin());

    C& collection_;
public:
    Filter(C& collection) : collection_(collection) { }

    struct iterator { 
        /* TODO, use collection_iterator */
    };

    iterator begin() const { /* TODO */ };
    iterator end() const   { /* TODO */ };
};

template <typename <typename> class F, typename C>
F<C> makeFilter(C& collection) {
    return F<C>(collection);
}

auto filter = makeFilter<CollectionFilterPositive>(some_collection);