Generic / polymorphic iterators
What's the best way to implement getIterator? Depending on the condition, I want to return the appropriate iterator.
// global variables
vector<int> myVector;
set<int> mySet;
vector<int>/set<int>::iterator getIterator(bool someCondition) {
if (someCondition) return mySet.begin();
else return myVector.begin();
}
Please resist the "wise" answers like "don't use globals" etc. I just want to know if there is a way to "generalize" both set and vector iterators, this example is just created to keep things simple.
Greetings
source to share
The short answer is that you cannot. C ++ is a statically typed language. This means that the type of a function or the return value of a method is declared at compile time, not at run time.
Other languages such as Perl, for example, are dynamically typed. A Perl function can sometimes return a scalar value such as an integer. In other cases, it can return a reference (pointer) or a list or hash (a std :: vector or std :: map). But C ++ doesn't work that way.
So, if you need to write dynamically typed code, you will need to use another language other than C ++.
The only thing you can do here in C ++ is to declare this function as returning some type that can be converted to one.
For example:
class return_value {
public:
enum { vector, set} type_t;
type_t type;
std::vector<int>::iterator v_iter;
std::set<int>::iterator s_iter;
};
return_value getIterator(bool someCondition) {
// ...
}
Then your function getIterator()
creates an instance return_value
, initializing or its member v_iter
or s_iter
, and initialize the member type
either return_value::vector
, or return_value::set
so that getIterator()
the caller can check the return value and determine what type of iterator returns.
Other approaches are also possible. If, for example, the return type can be inferred from parameters getIterator()
, perhaps a statically typed solution will be implemented using templates and specialization.
source to share
Yes, iterators can be generic, but you probably need to write a wrapper class. There are several options for its implementation. Obviously, you will need to store the actual iterator inside the class, and have a way to determine which iterator it is. For example:
class MyIter {
...
private:
union {
std::vector<int>::iterator vec_iter;
std::set<int>::iterator set_iter;
}
bool is_vec_iter; /* or like in an example above, enum { vector, set} type_t; */
};
It should be pretty obvious how to build an object of this class. The interesting part is the implementation of the interface i.e. Dereferencing, incrementing, comparing iterators.
Probably a good thing to have a look at boost: iterator_facade: http://www.boost.org/doc/libs/1_53_0/libs/iterator/doc/iterator_facade.html . This is a helper pattern that implements most of the iterator operations using only a few dereferencing and traversal methods that you must provide. Even if you decide to implement everything from scratch, iterator_facade is a good place to start.
source to share
You can wrap it up and use polymorphism. Here's an example:
#include <memory>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
class GenericIterator_helper_base {
friend class GenericIterator;
public:
virtual ~GenericIterator_helper_base() = default;
virtual int operator*() = 0;
virtual void pre_inc() = 0;
};
template <typename IT>
class GenericIterator_helper_tmpl : public GenericIterator_helper_base {
public:
GenericIterator_helper_tmpl(IT &&it_) : it(it_) { }
virtual ~GenericIterator_helper_tmpl() = default;
virtual int operator*() { return *it; }
virtual void pre_inc() { ++it; }
private:
IT it;
};
class GenericIterator {
public:
template <typename T>
GenericIterator(T &&it) : helper(new GenericIterator_helper_tmpl<T>(std::move(it))) { }
int operator*() { return helper->operator*(); }
GenericIterator &operator++() { helper->pre_inc(); return *this; }
private:
std::unique_ptr<GenericIterator_helper_base> helper;
};
vector<int> myVector{1, 2};
set<int> mySet{3, 4};
GenericIterator
getIterator(bool cond) {
if (cond) {
return GenericIterator(mySet.begin());
} else {
return GenericIterator(myVector.begin());
}
}
int main() {
auto it1 = getIterator(true);
auto it2 = getIterator(false);
cout << *it1 << endl;
++it1;
cout << *it1 << endl;
cout << *it2 << endl;
++it2;
cout << *it2 << endl;
}
source to share
Assuming you actually meant to write
std::vector<int> myVector;
std::set<int> mySet;
... and you want an iterator that conditionally repeats one of the sequences, my immediate reaction is "don't do this!" First of all, I found it extremely rare that it std::set<T>
is useful for anything and for the few cases where it might be useful std::unordered_set<T>
is the best alternative. However, this is somewhat tangential.
Most importantly, the whole point of programming is to make things fast, and run-time decisions on low-level operations are about performance. You are much better off redesigning the system to drop use std::set<T>
or std::unordered_set<T>
and use consistently std::vector<T>
. If necessary, use the appropriate operations on sub-objects on the instances, which should behave like a set.
Okay, are you still reading? Didn't get it: I'm serious about the above. Think about it before moving on! There is not a very good approach to using iterators across different containers, at least not to STL iterators. STL iterators need to be fast and as a result they use separate low-level operations for each of the main operations (advance, compare, access). If you stick with this interface, you will create a performance problem: there is a reason why interfaces using the dynamically polymorphic approach use an interface Enumerable
(or something like that) that dumps all three operations into one: safe on dynamic dispatch! (so you really should really not do what below)
Ok, still read, i.e. you painted yourself in the corner. Well, there is enough rope here to hang performance, but perhaps get you out of this difficult place: as of C ++ 11, you can use union
containing class types. You just need to make sure you handle them properly during construction and demolition. You can use this to dispatch to a suitable dynamic interface without having to allocate memory:
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <vector>
#include <new>
namespace demo {
template <typename It0, typename It1>
class joint_iterator {
public:
typedef typename std::iterator_traits<It0>::value_type value_type;
typedef typename std::input_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef value_type* pointer;
typedef value_type& reference;
private:
struct dyn_base {
dyn_base() = default;
dyn_base(dyn_base const&) = default;
virtual ~dyn_base() {}
virtual bool equal(dyn_base const* other) const = 0;
virtual void increment() = 0;
virtual value_type access() = 0;
virtual int index() const = 0;
};
template <typename It, int Index>
struct dyn_it: dyn_base {
dyn_it(It it): it(it) {}
It it;
bool equal(dyn_base const* other) const override {
return this->it == static_cast<dyn_it<It, Index> const*>(other)->it;
}
void increment() override { ++this->it; }
value_type access() override { return *this->it; }
int index() const override { return Index; }
};
union it_rep{
it_rep() {}
~it_rep() {}
int dummy;
dyn_it<It0, 0> it0;
dyn_it<It1, 1> it1;
} rep;
dyn_base* it;
public:
~joint_iterator() { this->it->~dyn_base(); }
joint_iterator(joint_iterator const& other) {
if (other.it->index() == 0) {
new(&this->rep.it0) dyn_it<It0, 0>(other.rep.it0); it = &this->rep.it0;
}
else {
new(&this->rep.it1) dyn_it<It1, 1>(other.rep.it1); it = &this->rep.it1;
}
}
joint_iterator& operator=(joint_iterator const& other);
joint_iterator(It0 it0) { new(&this->rep.it0) dyn_it<It0, 0>(it0); it = &this->rep.it0; }
joint_iterator(It1 it1) { new(&this->rep.it1) dyn_it<It1, 1>(it1); it = &this->rep.it1; }
bool operator== (joint_iterator const& it) const {
return this->it->equal(it.it);
}
bool operator!= (joint_iterator const& it) const {
return !(*this == it);
}
value_type operator*() const { return this->it->access(); }
joint_iterator& operator++() { this->it->increment(); return *this; }
joint_iterator operator++(int) { joint_iterator rc(*this); this->operator++(); return rc; }
};
}
int main(int ac, char*[])
{
std::set<int> s{ 11, 12, 13, 14, 15, 16, 17, 18, 19 };
std::vector<int> v{ 21, 22, 23, 24, 25, 26, 27, 28, 29 };
typedef demo::joint_iterator<std::set<int>::iterator, std::vector<int>::iterator> joint_iterator;
std::copy(ac == 2? joint_iterator(s.begin()): joint_iterator(v.begin()),
ac == 2? joint_iterator(s.end()): joint_iterator(v.end()),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
This code is missing some method implementations (for example, the assignment operator is missing) and takes a few shortcuts about type definitions. It is not fully tested, but at least works with the latest gcc and clang. I haven't appreciated the effectiveness of this implementation (yet?), But I totally expect it - er - not great.
source to share