typedef error: where to put typedef and how it should be written?

I'm writing a btree implementation class 'btree' inside a file btree.h and implemented inside btree.tem with an external iterator class 'btree_iterator' in a file btree_iterator.h implemented in a file btree_iterator.tem

Here is the (stripped down) content of btree.h:

#include "btree_iterator.h"

template <typename T> class btree 
{
 public:

  friend class btree_iterator<T>;开发者_StackOverflow中文版
  typedef btree_iterator<T> iterator;

  iterator find(const T& elem);
};

#include "btree.tem"

Now in implementing the find function, I have the following stub implementation in btree.tem:

template <typename T> iterator btree<T>::find(const T& elem) //LINE 24
{
    return NULL;
}

(I've only included lines of code that are relevant to my question)

When I compile I get the following errors:

btree.tem:24: error: expected constructor, destructor, or type conversion before 'btree'

Now I know that this has something to do with the fact that I've declared the typedef for iterator inside the class declaration and is therefore scoped only inside that block. But I've tried to put another line of typedef in btree.tem but it just won't work.

How should it be written?

Write this:

template <typename T>
typename btree<T>::iterator btree<T>::find(const T& elem) //LINE 24
{
  //;;
}

Since iterator is a nested type, you've to write btree<T>::iterator, and since it is a dependent nested type as it depends on the template argument type T, you've to use typename as well:

  typename btree<T>::iterator
//^^^^^^^^ must use it as iterator is a dependent type!

See a detailed explanation here:

• Where and why do I have to put the "template" and "typename" keywords?

Your return type is broken (there's no iterator in global scope!), and you're going to need to qualify the dependent type with typename:

template <typename T>
typename btree<T>::iterator btree<T>::find(const T& elem)
{
    return NULL;
}

iterator is a nested type within btree<T>. When you define the function you are outside the scope of the class so you need to qualify the type as typename btree<T>::iterator.

The lookup scopes in a member function definition are slightly asymmetric. Lookup for the return type is performed in the enclosing scope while arguments are looked up in the class scope. This means that while for the arguments you can use the unqualified name of the typedef, you cannot do that for the return type. For an ilustrative example:

struct test {
   typedef int integer;
   integer f( integer x );
};
// [1]                   [2]
test::integer test::f( integer x ) {
   return x;
}

The return type [1] is in the enclosing namespace scope, and in that scope integer is not defined, so you need to qualify it. On the other hand, arguments to the member function are looked up inside the class scope, so you can use the unqualified integer there.

In your particular case, because you are using a template you have the added complexity of having to add the typename before the dependent name. But the important part of the problem is that lookup for the return type is performed in the enclosing scope.