Implementing Java Collection hierarchy in C++

Question

#include <iostream>
using namespace std;

template <typename T> class Iterator
{

T * ptr;

public: 

    Iterator(T * addr)
    {
        ptr=NULL;
        ptr=addr;
    }

    //not working
    //virtual Iterator * operator ++(int x);


    /*Iterator * operator ++(int x)
    {
        (this->ptr)++;
        return this;
    }*/

    T operator *()
    {
        return *ptr;
    }
};

template<typename T>
class Vector{

T * a;
public:
    Vector(size_t n)
    {
        a=new T[5];
    }
    T& operator [](int x)
    {
        return a[x];
    }
    class iterator: public Iterator<T>
    {
        public:

            iterator(T * addr): Iterator<T>(addr)
            {}

            /* not working 
            Iterator<T> * operator ++(int x)
            {
                Iterator<T>::ptr++;
                return this;
            }*/


            //working now
            iterator * operator ++(int x)
            {
                Iterator<T>::ptr++;
                return this;
            }
    };
    iterator begin()
    {
        iterator ob(&a[0]);
        return ob;
    }
};

int main()
{

Vector <char> v(5);

for(int i=0;i<5;i++)
    v[i]=i+65;

for(int i=0;i<5;i++)
    cout<<v[i]<<endl;

/*~~~~~~ What I want~~~~~~

Iterator <char> p=v.begin();    

*/

// what is working now:

Vector<char>:: iterator p=v.begin();

while(*p){
    cout<<*p<<endl;
    p++;
   }

   return 0;
}

In the above code, I want to make operator ++() in Iterator class, virtual so that in main I can use:

Iterator <char> ptr=v.begin();

rather than having to use:

Vector <char>:: iterator p=v.begin();

that is a single base class refernce with run time polymorphism to determine which ++ operator to call depending upon whether the value is a vector or list. However, when I declare it virtual in Iterator class it is not working. I have to declare it exclusively for the inner classes, but I want a single interface just like in Java. I am trying to implement the java collection hierarchy in c++ for better structure. What is going wrong? Is it happening because Iterator is a template class which makes return type Iterator also template, that is, the operator ++() function a template function? I know template functions cannot be virtual, only concrete functions can be virtual. What can be done to fix this?

Why do you want runtime polymorphism on iterator? What's the actual usage? — , May 11 '17 at 06:46
In Java, we have a single Iterator interface but in C++ we use vector:: iterator and another one for list and so on. So what I wanted to do was to make a single Iterator base class. Then use a base class reference to call different iterator implementations, for example, list has different implementation than vector. So at run time it would figure out whose iterator implementation to call depending upon what object the "Iterator" reference is pointing to. — Deepayan Ghosh, May 11 '17 at 11:48
You are not answering me. I already know you want runtime polymorphism. What I have asked is why. As in what the actual use case is. I wonder how special your use case is since concept-based, compile-time polymorphism, which we are using on daily basis, already cover most cases. — , May 11 '17 at 12:57

Zefick · Answer 1 · 2017-05-11T07:19:15.630

0

Virtual functions can be called only through a pointer. Your begin function returns not a pointer. If you fix that then you will get a lot of compilation errors related to type conversions.

You can also use a reference instead but it should be an r-value reference:

Iterator<char> &&p = v.begin();

edited May 11 '17 at 07:19

answered May 11 '17 at 07:01

Zefick

2,014
15
19

@LaurentG Yes, reference works too and it is easier to change the current code to use it. I updated the answer. – Zefick May 11 '17 at 07:20

PapaDiHatti · Answer 2 · 2017-05-11T08:55:54.723

Here is sample implementation with correct postfix increment version :

template<typename T> 

class Iterator
{
    private: 
    T* ptr;
    public:
    Iterator(T* ptr1):ptr(ptr1)
    {
    }
    virtual Iterator  operator ++(int)
    {
        Iterator result(*this);
        (this->ptr)++;
        return result;
    }
    T operator*()
    {
        return *ptr;
    }
};

template<typename T>
class Vector
{
    private:
    T* data;
    public:
    Vector()
    {
        data = new T(100);
        for(int i=0;i<100;i++)
         data[i]=i;
    }


Iterator<T> begin()
{
    return Iterator<T>(&(data[0]));
}
};

Passer By · Answer 3 · 2017-05-11T10:01:33.407

Let me preface by saying, your implementation will not work as you intended. Neither will all of the other answers currently seen.

Using a pointer as the implementation of a polymorphic iterator is doomed to fail, polymorhphsm doesn't change the fact that you will have to implement all the concrete iterators that will be polymorphic.

Similar to Java (I will assume some familiarity), a global polymorphic Iterator is made possible with an interface. Now C++ don't have dedicated interfaces, what we have instead is pure virtual classes.

template<typename T>
class Iterator
{
public:
    virtual Iterator& operator++() = 0; // pure virtual
    // other methods
};

template<typename T>
class Vector
{
    class Iterator  // Vector's concrete Iterator
      : public ::Iterator<T>  // analogous to implements in Java
    {
    public:
        Iterator& operator++() override { /* implementation */ }
        // other methods...
    };
};

template<typename T>
class List
{
    class Iterator  // List's concrete Iterator
      : public ::Iterator<T>  // implements
    {
    public:
        Iterator& operator++() override { /* implementation */ }
        // other methods...
    };
};

Since polymorphism applies only to references and pointers, and references in C++ needs to be explicitly written

Vector<int> v;
List<int> l;
Iterator<int>&& rit = v.begin();
const Iterator<int>& crit = l.begin();

is how you would use Iterator.

And as a final note, polymorphism is a tool, abusing it is worse than not having it. Do take into consideration the performance penalty and weigh against the flexibility it provides.

Thank you for the answer. The last two lines about the performance, you mentioned, can you please elaborate about the performance penalties? I am new to C++ programming, I only used C++ to code data structures but never used C++ to make something compact as a single unit, so this is my first attempt, so can you please share more on the performance penalties you mentioned? Thank You.. — Deepayan Ghosh, May 11 '17 at 11:41
@DeepayanGhosh [This](http://stackoverflow.com/questions/113830/performance-penalty-for-working-with-interfaces-in-c) and [this](http://stackoverflow.com/questions/449827/virtual-functions-and-performance-c) are good starting points. There have been extensive discussions already, I won't go into the details. What I will say is a container should be suited to its needs, which is often broad since its templated. — Passer By, May 11 '17 at 12:48
Thank you for the help. Got to learn a lot from those questions. Thanks — Deepayan Ghosh, May 11 '17 at 14:11

score -1 · Accepted Answer · answered May 11 '17 at 08:37

Your code almost work. I only had to fix 3 problems in it:

ptr should be protected instead of private in Iterator class if you want to be able to access it in overriden methods of a derived class
the incrementation operator should be declared virtual Iterator<T> ...
if you want to iterate your array up to a null value, you should write a null value at the end.

So this compiles without a warning and run fine with Clang 3.4.1:

#include <iostream>
using namespace std;

template <typename T> class Iterator
{
protected:
T * ptr;

public: 

    Iterator(T * addr)
    {
        ptr=NULL;
        ptr=addr;
    }

    //not working - in fact works perfectly
    virtual Iterator<T> * operator ++(int x)
    {
        (this->ptr)++;
        return this;
    }

    T operator *()
    {
        return *ptr;
    }
};

template<typename T>
class Vector{

T * a;
public:
    Vector(size_t n)
    {
        a=new T[5];
    }
    T& operator [](int x)
    {
        return a[x];
    }
    class iterator: public Iterator<T>
    {
        public:

            iterator(T * addr): Iterator<T>(addr)
            {}

            /* not working 
            Iterator<T> * operator ++(int x)
            {
                Iterator<T>::ptr++;
                return this;
            }*/


            //working now but useless as we can use the base class version
            /*iterator * operator ++(int x)
            {
                Iterator<T>::ptr++;
                return this;
            }*/
    };
    iterator begin()
    {
        iterator ob(&a[0]);
        return ob;
    }
};

int main()
{

Vector <char> v(5);

for(int i=0;i<5;i++)
    v[i]=i+65;

for(int i=0;i<5;i++)
    cout<<v[i]<<endl;

v[5] = 0;  // set a null at the end of the vector

/*~~~~~~ What I want~~~~~~ and that works...*/

Iterator <char> p=v.begin();    



// what is working now:

//Vector<char>:: iterator p=v.begin();

while(*p){
    cout<<*p<<endl;
    p++;
   }

   return 0;
}

You can uncomment the overriden version of operator ++ in Vector class and it also works fine.

Implementing Java Collection hierarchy in C++

4 Answers4