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.
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
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.
Collection&
, then, are the begin() const
and end() const
function really required ? And if yes, why ?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 :
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) ?Thanks in advance !
An iterator can either be a constant or a non-constant/regular iterator.
In C, C++, and D, all data types, including those defined by the user, can be declared const , and const-correctness dictates that all variables or objects should be declared as such unless they need to be modified.
The const keyword allows you to specify whether or not a variable is modifiable. You can use const to prevent modifications to variables and const pointers and const references prevent changing the data pointed to (or referenced).
reference operator*() const { return *m_ptr; } pointer operator->() { return m_ptr; } // Prefix increment Iterator& operator++() { m_ptr++; return *this; } // Postfix increment Iterator operator++(int) { Iterator tmp = *this; ++(*this); return tmp; } friend bool operator== (const Iterator& a, const Iterator& b) { ...
- This filter works on a non-
const
Collection&
, then, are thebegin() const
andend() const
function really required ? And if yes, why ?- 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 theclass CollectionFilter
to aclass 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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With