Generic STL iterator in polymorphism

Question

I'm kinda new to C++, I have an abstract class (pure virtual) which 2 classes inherits from it. Each derived class holds similar data, only in different STL container (array vs map) I'm overloading the operators of the base class in order to perform, for example, addition of the STL elements. I want to be able to iterate over the elements of the STL, regardless of what type it is.

I've searched for a few days now on generic iterators, and stuff like that, but couldn't find anything.

I don't have too much code to share, as I was unable to do anything. I thought maybe to have my base class hold a template variable which would represent the STL container and then get its iterator in the operator, but again, not sure how to.

protected:
    template<class T>
    T gStlContainer;

and then accessing

gStlContainer::iterator<double> it;

obviously didn't work.

Any suggestions? Thanks!

EDIT: I'm editing to try and explain better using an example. I'm overloading the + operator in the base (abstract) class, what I want it to do is iterate over each element of the STL container, and add it to another element, for example, Say I have this arrays as STL

arr = [0,1,2,3] // Say it's stored in Derived2 class
arr = [4,5,6,7] // Say it's stored in Derived3 class

These arrays are each stored inside one of the derived classes. When I'm doing

Derived1 = Derived2 + Derived3;

then Derived1 would hold

arr = [4,6,8,10]

Hope it's a bit more clear now. The issues is that it won't always be an array, it can be combining array and map for example. That's why I need the generic iterator, or some solution.

Thanks!

Answer 1

Dynamic polymorphism works reasonable for objects but it works really badly for algorithms. For algorithms you are much better off using static polymorphism. If you feel you want to have a system of containers supporting operator+() between them, just make sure they somehow refer to a namespace and define a suitable operator+() in this namespace. For example, you could use std::vector<T, A> with an allocator A inheriting from something in a namespace with the operators. Below is an example of this approach.

The idea is basically to have namespaces implementing suitable operators. For example, addable implements operator+() and printable implements operator<<(). Neither of these namespaces is looked at unless a type somehow refers to them, e.g. by inheriting from a type in this namespace or by using a template argument of a type inheriting of one of these types. This look mechanism is called argument dependent look-up. So, both of these namespaces provide an empty struct tag {}; which will cost nothing when being inherited from.

To get hold of a container referring somehow to these namespaces the code below just creates an allocator class templates which derives from both of these types. This allocator is then used with std::vector<T, A> and std::list<T, A> to create a type alias to easily create the corresponding containers. To show everything is nicely working main() just demonstrates the use of the operators.

The code below takes advantage of C++ 2011 in several places to make the notation a bit shorter. The principle works with C++ 2003 as well. Primarily the use of type aliases and initializer-lists won't work.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

namespace addable
{
    struct tag {};

    template <typename T0, typename T1>
    T0 operator+ (T0 const& c0, T1 const& c1)
    {
        T0 rc;
        std::transform(c0.begin(), c0.end(),
                       c1.begin(),
                       std::back_inserter(rc),
                       std::plus<typename T0::value_type>());
        return rc;
    }
}

namespace printable
{
    struct tag {};
    template <typename T, typename = typename T::value_type>
    std::ostream&
    operator<< (std::ostream& out, T const& value)
    {
        out << "[";
        if (!value.empty()) {
            std::copy(value.begin(), value.end() - 1,
                      std::ostream_iterator<typename T::value_type>(out, ", "));
            out << value.back();
        }
        return out << "]";
    }
}

template <typename T>
struct my_allocator
    : addable::tag
    , printable::tag
    , std::allocator<T>
{
};

template <typename T>
using my_vector = std::vector<T, my_allocator<T>>;
template <typename T>
using my_list   = std::vector<T, my_allocator<T>>;

int main()
{
    my_vector<int> v({ 1, 2, 3, 4 });
    my_list<int>   l({ 2, 3, 4, 5 });
    my_vector<int> rc = v + l;

    std::cout << v << " + " << l << " = " << (v + l) << "\n";
}

Answer 2

The plain answer is: you can't, at least not with the iterators of the STL.

Iterators are typically built as templates, and the compiler creates a new type for each template specialization. You can think of a vector::iterator as being like VectorFloatIterator and a map::iterator as a MapFloatIterator.

They are unrelated types - not even through inheritance - that just happen to have similar interfaces, and, of course, C++ is not duck typed. You can't pass a VectorFloatIterator to a function expecting a MapFloatIterator when the two types are totally unrelated.

This even applies to using the standard algorithms - for example the for_each algorithm is templated, so the compiler will create something like a for_each_vector_float_iterator and a for_each_map_float_iterator function that can't be used with each other.

It's helpful to think of the types being generated at compile time. Your operation of passing a different type to a function happens at run time, when it's too late. You can only use the "genericization" (yes, I made that word up) features of templates in C++ at compile time.

That being said, @Luchian Grigore has the most recognized answer to the issue: specialize operator+ to handle any of the various types that might show up in an addition statement. Is it a pain? Yeah, a bit.

That being said, boost::any is what you're looking for for your use case - they are STL-like containers that handle any types by not using templates to handle varied types.

Answer 3

You're looking at the problem from the wrong point of view. You could do this, but why would you? Your base class shouldn't implement the method if it's supposed to behave differently, but should delegate the logic to the derived classes.

class Base
{
public:
    virtual ~Base() {}
    virtual void iterate() = 0;
};

class Derived : Base
{
public:
    virtual void iterate() { /*iterate through vector or map or whatever*/ }
};

Answer 4

C++ doesn't have generic iterators, but it does have template functions that can be written to operate on any type of iterator. To add all the elements in a container, there's already an algorithm for you. Read about std::accumulate.