C++ operator++ overloading for template iterator of a template generic tree class

Question

I've developed a c++ tree template class for which I would like to write a custom set of iterators.

The GenericTree class iterators should be used as follows:

GenericTree<int> tree;
GenericTree<int>::iterator<PREORDER> preorder_iterator;

for(preorder_iterator = tree.begin(); preorder_iterator != tree.end(); ++preorder_iterato){
  //Do something on the node pointed by the preorder_iterator.
}

In the above example, ++preorder_iterator should call the overloaded operator++() method for the iterator class defined for the int and FORWARD types, but the code does not compile. I'm using g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2

Here is the code of the iterator class. To shorten the sample, I've substituted the GenericTree class with a vector and I've completely omitted the begin() methods source code.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

template<typename P> class GenericTree{
        public:
                vector<P> data;
                GenericTree() {}
                ~GenericTree(){}

        class PREORDER{
        };

        class POSTORDER{
        };

        // ----------------------------------------------------------------------------------
        template<typename IT> class my_iterator : public std::iterator<std::forward_iterator_tag, P> {
                private:
                        int index;
                protected:
                public:
                        my_iterator()           { index=0; }
                        ~my_iterator()  {}

                IT& operator++();
        };
// ----------------------------------------------------------------------------------
        template<> my_iterator<PREORDER>& my_iterator<PREORDER>::operator++(){
                cout << "Preorder visit of GenericTree of nodes containing int values." << endl;
                return (*this);
        }

        template<> my_iterator<POSTORDER>& my_iterator<POSTORDER>::operator++(){
                cout << "Postorder visit of GenericTree of nodes containing int values." << endl;
                return (*this);
        }
};


int main(int argc, char** argv){
        GenericTree<int> c_int;
        GenericTree<int>::my_iterator<GenericTree<int>::PREORDER> iterator_int;

        for(iterator_int = c_int.begin(); iterator_int != c_int.end(); ++iterator_int)
                ;

        GenericTree<string> c_string;
        GenericTree<string>::my_iterator<GenericTree<string>::POSTORDER> iterator_str;

        for(iterator_str = c_string.begin(); iterator_str != c_string.end(); ++iterator__str)
                ;


}

Although partial, the previous code returns the same compilation errors I get when i build the full source:

g++     prova.cpp   -o prova
prova.cpp:35:11: error: explicit specialization in non-namespace scope ‘class GenericTree<P>’
  template<> my_iterator<PREORDER>& my_iterator<PREORDER>::operator++(){
           ^
prova.cpp:35:70: error: invalid use of incomplete type ‘class GenericTree<P>::my_iterator<GenericTree<P>::PREORDER>’
  template<> my_iterator<PREORDER>& my_iterator<PREORDER>::operator++(){
                                                                      ^
prova.cpp:24:30: error: declaration of ‘class GenericTree<P>::my_iterator<GenericTree<P>::PREORDER>’
  template<typename IT> class my_iterator : public std::iterator<std::forward_iterator_tag, P> {
                              ^
prova.cpp:40:11: error: explicit specialization in non-namespace scope ‘class GenericTree<P>’
  template<> my_iterator<POSTORDER>& my_iterator<POSTORDER>::operator++(){
           ^
prova.cpp:40:72: error: invalid use of incomplete type ‘class GenericTree<P>::my_iterator<GenericTree<P>::POSTORDER>’
  template<> my_iterator<POSTORDER>& my_iterator<POSTORDER>::operator++(){
                                                                        ^
prova.cpp:24:30: error: declaration of ‘class GenericTree<P>::my_iterator<GenericTree<P>::POSTORDER>’
  template<typename IT> class my_iterator : public std::iterator<std::forward_iterator_tag, P> {
                              ^
prova.cpp: In function ‘int main(int, char**)’:
prova.cpp:51:27: error: ‘class GenericTree<int>’ has no member named ‘begin’
  for(iterator_int = c_int.begin(); iterator_int != c_int.end(); ++iterator_int)
                           ^
prova.cpp:51:58: error: ‘class GenericTree<int>’ has no member named ‘end’
  for(iterator_int = c_int.begin(); iterator_int != c_int.end(); ++iterator_int)
                                                          ^
prova.cpp:57:30: error: ‘class GenericTree<std::basic_string<char> >’ has no member named ‘begin’
  for(iterator_str = c_string.begin(); iterator_str != c_string.end(); ++iterator__str)
                              ^
prova.cpp:57:64: error: ‘class GenericTree<std::basic_string<char> >’ has no member named ‘end’
  for(iterator_str = c_string.begin(); iterator_str != c_string.end(); ++iterator__str)
                                                                ^
prova.cpp:57:73: error: ‘iterator__str’ was not declared in this scope
  for(iterator_str = c_string.begin(); iterator_str != c_string.end(); ++iterator__str)
                                                                         ^
make: *** [prova] Error 1

I cannot find the correct way to define the two template specializations of the operator++() for the PREORDER and POSTORDER type.

If I use the template<> keyword, the compiler complains that the specialization is done out of scope and I do not understand why. Moving the two template specializations out of the GenericTree class body didn't solve the problem.

Thank you in advance for your help!

f.

Move your declaration/definition of class `my_iterator` outside of `GenericTree`. — Jarod42, Aug 23 '14 at 16:56
The error say exactly what it's happen, the specialization could not be in the class scope. — NetVipeC, Aug 23 '14 at 17:19
May be related to [error-explicit-specialization-in-non-namespace-scope](http://stackoverflow.com/questions/6301966/c-nested-template-classes-error-explicit-specialization-in-non-namespace-sco?lq=1) — Jarod42, Aug 23 '14 at 17:42

Jarod42 · Answer 1 · 2014-08-23T17:52:33.597

0

Moving the iterator class outside of GenericTree and partial specialize the struct my_iterator does the job. Following compiles and may help:

namespace internal
{
    class PREORDER {};
    class POSTORDER {};

    // ------------------------------------------------------------------------------
    template<typename P, typename IT>
    class my_iterator;


    template<typename P>
    class my_iterator<P, PREORDER>
    : public std::iterator<std::forward_iterator_tag, P>
    {
    private:
        int index;
    protected:
    public:
        my_iterator () { index = 0; }

        my_iterator& operator++ () {
            std::cout << "Preorder visit of GenericTree of nodes containing int values." << std::endl;
            return (*this);
        }
    };
    // ------------------------------------------------------------------------------
    template<typename P>
    class my_iterator<P, POSTORDER>
    : public std::iterator<std::forward_iterator_tag, P>
    {
    private:
        int index;
    protected:
    public:
        my_iterator () { index = 0; }

        my_iterator& operator++ () {
            std::cout << "Postorder visit of GenericTree of nodes containing int values." << std::endl;
            return (*this);
        }
    };

}

template<typename P> class GenericTree
{
public:
    template <typename IT>
    using my_iterator = internal::my_iterator<P, IT>;
    using PREORDER = internal::PREORDER;
    using POSTORDER = internal::POSTORDER;

    std::vector<P> data;
    GenericTree () {}
    ~GenericTree () {}
};

Demo

edited Aug 23 '14 at 17:52

answered Aug 23 '14 at 17:19

Jarod42

203,559
14
181
302

but if I move the iterator class out of the GenericTree class when I instantiate an iterator to work on a tree I should pass the tree pointer/reference to the iterator to be able to walk the tree structure. If I manage to keep the iteraror class into the GenericTree one the code to be written to use both is cleare in my opinion. – faugra Aug 23 '14 at 17:29
Do you think the problem can be solved if the two calsses remain nested? – faugra Aug 23 '14 at 17:35
Not sure I understand your second comment, but I provided `typedef` inside `GenericTree` to allow same interface. And it is true that you may have to implement some methods of `my_iterator` after the definition of class `GenericTree`. – Jarod42 Aug 23 '14 at 17:36
I might be wrong here, but to use your implementation of my_iterator I should write something like: GenericTree tree_int; my_iterator iter_int(&tree). That is, I should somehow pass to iter_int a pointer o referenc to the tree it should iterate. – faugra Aug 23 '14 at 17:46
It seems it is possible to keep the classes nested if you add a dummy type to keep the inner class partially specialized. – Jarod42 Aug 23 '14 at 17:46
I've read about the dummy type to be added in order to partially specialize the method, but I couldn't figure out the correct syntax... I'll try again. – faugra Aug 23 '14 at 17:50
Thank you Jarod42, this is exactly what I was trying to obtain. Great Job! – faugra Aug 24 '14 at 17:46

C++ operator++ overloading for template iterator of a template generic tree class

1 Answers1