implementing const_iterator and iterator

[flopbucket]

Hi,

For the learning experience, I am building a replacement for std::map.
I built a templated red-black tree, etc., and all the basic stuff is
working well. I implemented basic iterators and operator++, etc., and
begin(), end(), and it works as a drop in for std::map if you stick to
the methods I have implemented.

Anyway, I decided to go and add const_iterator support, thinking that
it would be simple, but I ran into a confusing error and hoped some of
the experts here could help. Please read the full post since what I am
showing here is my working end result, but I have questions about its
implementation.

Basically, I have a tree_iterator that takes a pointer to a node class.
It is something like this:

template<class T, class R>
class tree_iterator_base
{
public:
tree_iterator_base(Node<T> *t)
: iter_(t)
{
}

operator tree_iterator_base<T, const R>()
{
return tree_iterator_base<T, const R>(this->iter_);
}

.......
}


The Node class has standard tree stuff, left, right, etc. It is also
templated and is instantiated with a std:air type class for working
as a map replacement.

Here are my typedefs for my iterators and basic other types:

typedef pair<Key, Value> pair_type;
typedef Node<pair_type> node_type;
typedef tree_iterator_base<pair_type, pair_type> iterator;
typedef tree_iterator_base<pair_type, const pair_type> const_iterator;

At first, my iterator typedefs only had one template parameter. it was
"pair_type" for the normal iterator and "const pair_type" for the
const_iterator. More on this later.

Now, I had a find method:

typename btree::iterator find(const Key& key)
{
node_type *n = find...(key); // find key
.....
return iterator(n);
}


all worked great with regular iterators, but then I tried:

mymap::const_iterator x = tree.find(...);

Then I get compile error saying it can not convert between
iterator<pair> and iterator<const pair>, since find returns
iterator<pair> and const_iterator is defined as iterator<const pair>.
This makes sense and I understand that, so I added the conversion
operator to my iterator class which can convert an iterator<pair> to a
iterator<const pair>. (I also have const version of find that does
return const_iterator but that doesn't come into play here since it is
a non-const map instantiation where a const_iterator is wanted).

I added the second template parameter to the iterator class because I
though I would use one as the return type and the other as the data
type, and the iterator class would use the second parameter to specify
the return type (i.e. const pair_type operator*() vs pair_type
operator*()). Now that I think of it, I am not sure I need the two
parameters actually now that the conversion operator is there.

It all seems to be working correctly now, but I felt a bit funny with
this solution. I began looking more that the gnu libstdc++
implementation and I could not find any conversion operators on their
iterators (bits/stl_tree.h) so I am curious how they manage it. I
don't see any major differences in their iterator typedefs.

Thanks for any tips on how this could be improved. I guess I am
probably missing something simple I can't seem to figure out.

 

[flopbucket]

Thanks for any tips on how this could be improved. I guess I am

probably missing something simple I can't seem to figure out.

Nevermind... I must have had a brain disorder. A second constructor
taking const T for the iterator provides implicit conversion.

Thanks