template nested classes and compilation error: no match for operator!=

[nomentero]

Hi everybody,

I'm trying to create a matrix class. This class has a nested class called linear_t (which represents both columns and rows) and linear_t has another nested class called iterator_t.

Here is the code:

////////////////////////////////////////////////////////

template <typename T>
class matrix_t
{
public:
        // ...

        class linear_t;

        typedef linear_t row_t;

        typedef linear_t col_t;
};

////////////////////////////////////////////////////////

template <typename T>
class matrix_t<T>::linear_t
{
public:
        // ...

        class iterator_t;
};

////////////////////////////////////////////////////////

template <typename T>
class matrix_t<T>::linear_t::iterator_t
{
public:
        // ...
};

////////////////////////////////////////////////////////

template <typename T>
inline bool operator!= (
        typename matrix_t<T>::linear_t::iterator_t& it_i,
        typename matrix_t<T>::linear_t::iterator_t& it_j
        )
{
        return true; // just to allow compiling
}

I get a compilation error when I try to use the operator!= from the main function. It seems the compiler cannot find the implementation, but I don't understand the reason.

Here is the error:

main.cpp: In function `int main(int, char**)':
main.cpp:10: error: no match for 'operator!=' in 'it_1 != it_2'

And here is the fragment of code where the operator is invoked:

        matrix_t<double> m;
        matrix_t<double>::row_t r;
        matrix_t<double>::row_t::iterator_t it_1, it_2;

        if (it_1 != it_2)
        {
                // ...
        }

I don't understand what is the problem. Any help or suggestion will be more than welcomed.

Thanks

[nomentero]

What is more, there is no compilation errors if I invoke the operator!= method in the following way:

        if ( operator!= <double> (it_1,it_2) )
        {
                // ...
        }

I cannot understand why in the first post the invokation is failing.

[Disch]

That is very strange. I have the same problem over here.

I can get around it by making the operator overload part of the iterator class rather than a global function (which is my preferred style). So I guess this is a solution:

template <typename T>
class matrix_t<T>::linear_t::iterator_t
{
public:
    inline bool operator != (const matrix_t<T>::linear_t::iterator_t& r) const
    {
        return true;
    }
     // ...
};

As for why this error is happening, I don't have the first idea. What's even more baffling... if you make a friend declaration:

template <typename T>
class matrix_t<T>::linear_t::iterator_t
{
public:
    friend bool operator != (
        const matrix_t<T>::linear_t::iterator_t& it_i,
        const matrix_t<T>::linear_t::iterator_t& it_j
        );
        // ...
};

////////////////////////////////////////////////////////

template <typename T>
inline bool operator!= (
        const typename matrix_t<T>::linear_t::iterator_t& it_i,
        const typename matrix_t<T>::linear_t::iterator_t& it_j
        )
{
        return true; // just to allow compiling
}

Now it turns into a linker error instead! So it finds the friend declaration in the class, but still doesn't find the global function.

Very very strange. I don't know why it's doing that.

[jsmith]

What compiler are you using?

According to
http://www.devx.com/cplus/10MinuteSolution/30302/1954

the correct declaration is

template <typename T>
struct matrix_t<T>::linear_t::iterator_t
{
    friend bool operator !=<T> (
        const matrix_t<T>::linear_t::iterator_t&,
        const matrix_t<T>::linear_t::iterator_t&
        );

};

but neither GCC 4.x nor Comeau online compiler compile this successfully, however
GCC 3.x does like it.

[nomentero]

Hi,

First of all, thanks to all of you for your replies.

jsmith, I'm using g++ 3.4.5. But the initial problem is not the friend declaration. The original problem is that the compiler cannot find the implementation of the operator!= () if I declare it as a global function (not as a member function) as I commented in the first post.

[jsmith]

This is actually a headache-inducing problem. I discussed this with a colleague over lunch.

The problem is that the compiler is not able to deduce T from the invocation site.

Why? Let's reduce the problem size a bit:

template <typename T>
struct matrix_t
{
        struct iterator_t
        {
        };
};

template< typename T >
void foo (
        typename matrix_t<T>::iterator_t,
        typename matrix_t<T>::iterator_t 
        )
{
}

int main() {
        matrix_t<double>::iterator_t it_1, it_2;
        foo( it_1, it_2 );
}

The above code still has the same problem.

Let's say you had a specialization:

template<>
class matrix_t<int> {
   typedef int iterator_t;
};

Now, what is T in the following code?

int main() {
        matrix_t<int>::iterator_t it_1, it_2;
        foo( it_1, it_2 );
}

(Since matrix_t<int>::iterator is simply a typedef for int at that point,
it can't deduce T.)

[nomentero]

jsmith, thanks very much for your latest post. Your example is very clear. Does anybody know how to solve it?
Thanks in advance

[Disch]

I solved it in my first post.

Just make the function a member of iterator:

template <typename T>
class matrix_t<T>::linear_t::iterator_t
{
public:
    inline bool operator != (const matrix_t<T>::linear_t::iterator_t& r) const
    {
        return true;
    }
     // ...
};

[nomentero]

Yes, but I also want to define some algorithms (apart of the != or == operators) like for example:

template <typename T, typename Cmp>
T max_element (
   typename matrix_t<T>::iterator_t  it_i, 
   typename matrix_t<T>::iterator_t  it_j,
   Cmp cmp)
{

}

And in that case I don't think it is a good idea to define it as a member function (adding the Cmp template parameter to the class)

[jsmith]

There isn't a solution AFAIK except for Disch's -- you have to make them members that are
declared and implemented in the class.

Is not std::max_element() good enough? Do you really need to specialize?

[nomentero]

Sorry for my insistence but I think there is something else. For example, when using the STL, we usually do things like this:

map<char,int>::iterator it;

I think inheritance could be a possible solution (I don know if it is used in the STL) but we could do something like this (please, read the first post to understand the following fragment of code):

template <typename T>
class base_iterator_t
{
   // ...
};

template <typename T>
class matrix_t<T>::linear_t::iterator_t : public base_iterator_t<T>
{
   // ...
};

This solution presents two disadvantages:
1. inheritance implies less performance
2. each function requires two versions (see the following example for the operator!= method)

template <typename T>
inline bool operator!= (typename matrix_t<T>::linear_t::iterator_t& it_i, typename matrix_t<T>::linear_t::iterator_t& it_j)
{
   // here comes the implementation...
}

template <typename T>
inline bool operator!= (base_iterator_t<T>& it_i,base_iterator_t<T>& it_j)
{
   return operator!= <T> ((typename matrix_t<T>::linear_t::iterator_t&)it_i, (typename matrix_t<T>::linear_t::iterator_t&)it_j);
}

[nomentero]

Ok, this is an easier way (in fact, this is a simplification of what I've seen for std::vector):

template <typename T>
class base_iterator_t
{
   // ...
};

template <typename T>
class matrix_t<T>::linear_t
{
public:
   typedef base_iterator_t<T>  iterator_t;
   // ...
};

[guestgulkan]

In regard to the original problem:
Here is an extract from the book "C++ templates the complete guide" concerning template argument deduction:

Complex type declarations are built from more elementary constructs (pointer, reference, array, and function declarators; pointer-to-member declarators; template-ids; and so forth), and the matching process proceeds from the top-level construct and recurses through the composing elements. It is fair to say that most type declaration constructs can be matched in this way, and these are called deduced contexts. However, a few constructs are not deduced contexts:

Qualified type names. A type name like Q<T>::X will never be used to deduce a template parameter T, for example.