Const-correctness of self made iterators

Question

General goal

I manage a collection of objects (Collection of Real as simple example). Then I defined iterators on my collection. That means : iterator, const_iterator, reverse_iterator and const_reverse_iterator. In this example, I will only pay attention on iterator and const_iterator, the two others are very similar.

After that, I would like to define a filter on my collection, which keeps or not the elements with respect to a specific condition. As exemple, keep only the Real instances with a positive value. I also would like to iterate on my collection on the kept elements only.

How I implemented the collection

For this example, my object in the collection is very simple. The goal is just having an object instead of a native type :

struct Real
{
    public:
      double r;
};

Then I define my collection without having to know the real container inside :

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(); }
};

This is working very well in this simple example :

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;
}

And this program writes the expected output :

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

How I implemented the filter

Now I want to create an abstract filter, having a reference or pointer to a collection, having iterators, and having an abstract function accepting values through the filter. For this first step, I only wrote the class without the iterators :

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;
};

Then, it's quite easy to create a new filter implementing a specific condition :

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

Before implementing the iterators in the filter, I have some remarks / questions.

1. This filter works on a non-const Collection&, then, are the begin() const and end() const function really required ? And if yes, why ?
2. I can't apply the filter on a const Collection&, but it's clearly required for my goal. What could be a good way to do that ? Have I to duplicate the class CollectionFilter to a class CollectionFilterConst with a very similar code ? Moreover this solution is quite confusing for the user having to inherit from two similar classes.

Then, let's go to the implementation of the iterators. For this example, I only wrote the iterator and not the const_iterator. I add this to my class :

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);
    }
};

This is also working well on this simple example

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;
}

giving the expected output :

print with CollectionFilterPositive::iterator
1
4
16

Again, some questions :

3. Am I totally wrong with this approach ?
4. I suppose I have to duplicate the code of CollectionFilter::iterator to implement CollectionFilter::const_iterator with only small modifications. Is there a way to avoid duplication of this code (written 8 times, if I count the duplicated class CollectionFilterConst and the reverse iterators) ?
5. I don't feel comfortable with the const-correctness of my code. Do you see some problems ?

Thanks in advance !

Answer 1

I would suggest to drop the CollectionFilter class, and instead have a Collection::filter_iterator_tmpl template class, with two instantiations Collection::filter_iterator and Collection::const_filter_iterator.

Collection::filter_iterator_tmpl could be implemented like this:

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_;
        }

        ....
    }

};

Polymorphism can be added by letting Predicate be a polymorphic functionoid with a virtual bool PolymorphicPredicate::operator(Real) const function.

Collection would then define the actual filter iterators:

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;
}

Boost implements a generic "Filter Iterator" in a similar way: http://www.boost.org/doc/libs/1_46_1/libs/iterator/doc/filter_iterator.html As a standalone class, not as part of a container class.

About const-correctness: Containers in C++ (std::vector, std::map, std::string, etc) own their content objects: They create and delete them, and need to make sure that with const access to the container, you also only get const access to the content objects. They need to be implemented so as to enforce this, because the underlying pointers by which they access their allocated storage don't have this notion of ownership. This is why they need to have two versions of iterators (iterator and const_iterator). The iterators themselves don't own the object: With const access to an iterator, you cannot advance the iterator, but you still get non-const access to the object.

Questions 1/2: CollectionFilter is problematic because it does not own the objects that it provides access to, yet const/non-const access to the filter should only give const/non-const access to the object. Because it holds a reference to the Collection, and it should work for both const and non-const access to the Collection, two versions CollectionFilter and ConstCollectionFilter would then be needed with that approach.

Question 4: Once there is a split from a const-correct container object to two classes for const and non-const access, there necessarily is some code duplication. Templates avoid having to implement both versions manually. There are also some additional complications, such as comparing an iterator to an const_iterator, and constructing a const_iterator from an iterator but not the other way around...

Questions 3/5: See above.

Answer 2

1. This filter works on a non-const Collection&, then, are the begin() const and end() const function really required ? And if yes, why ?
2. I can't apply the filter on a const Collection&, but it's clearly required for my goal. What could be a good way to do that ? Have I to duplicate the class CollectionFilter to a class CollectionFilterConst with a very similar code ? Moreover this solution is quite confusing for the user having to inherit from two similar classes.

These questions are very related. Basically, does it make sense to limit your filtering to a non-const Collection? That doesn't make much semse to me. We're not modifying the CollectionFilter object at all, only the underlying Collection objects (potentially), and the functionality of the Filter is independent of whether or not the Collection is const. Put that all together, and it calls for a template:

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 */ };
};

This way, Filter<Collection>::collection_iterator is Collection::iterator and Filter<const Collection>::collection_iterator is Collection::const_iterator. And you can't do Filter<std::vector<int>>.

This sort of answers the rest of your questions as well - this is a const-correct, non-duplicated approach to filtering any collection.

To avoid the extra typing, you could also create a builder function:

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

auto filter = makeFilter<CollectionFilterPositive>(some_collection);

The const-ness of the iterators of filter will depend on the const-ness of some_collection.

I would also look into Boost.IteratorFacade for writing Filter::iterator, it'll save you some time and some headaches.