How to use two functions, one returning iterator, the other returning const_iterator

Question

So I have a function called find, which has two versions:

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

and the other is the const_iterator version:

template <typename T> 
typename btree<T>::const_iterator btree<T>::find(const T& elem) const
{
    //Implementation
}

In my test file when I do

btree<char>::iterator it = myTree.find('M');

Everything works fine, however when I use the const_iterator version:

btree<char>::const_iterator it = myTree.find('M');

It gives me the error

error: conversion from 'btree_iterator' to non-scalar type 'const_btree_iterator' requested

Which obviously means that find is only ever using the iterator (non const) version. I know that C++ is supposed to call the const_iterator version automatically - if I had done everything right. So the question is, what might I be doing wrong?

The iterator classes are:

class btree_iterator and class const_btree_iterator which is just a copy paste of btree_iterator with the names changed

Here are the full source code:
btree_iterator.h (includes const_btree_iterator) http://pastebin.com/zQnj9DxA
btree.h http://pastebin.com/9U5AXmtV
btree.tem http://pastebin.com/U9uV3uXj

Answer 1

All the standard containers implement conversion of non-const to const iterators (as specified in the requirements for the Container concept):

The type of iterator used to iterate through a container's elements. The iterator's value type is expected to be the container's value type. A conversion from the iterator type to the const iterator type must exist.

You need conversion constructor like so:

class btree_iterator;
class const_btree_iterator
{
       // ....
       public:
              const_btree_iterator(const btree_iterator& rhs) { /* .... */ }
//optionally: const_btree_iterator& operator=(const btree_iterator& rhs) { /* .... */ }
};

I threw in the assignment operator too but I suppose it is redundant

Answer 2

The important bit here is that overload resolution is performed based only on the arguments to the function and not the result. In your particular case you have two different overloads and the difference is that the implicit this is constant in one of them, that overload will be picked up whenever static type of the object or reference on which the method is called is constant.

If you want to force dispatch to the constant overload, you can obtain a const reference and then call on that reference:

btree<char> const & r = myTree;
btree<char>::const_iterator it = r.find('M');

You should avoid this construct in real code, even if you use it for testing purposes. The reason is that the const and non-const overloads should have the same semantics and thus the behavior should be the same.

Also note that in standard containers, there is an implicit conversion from iterator to const iterator to support using const_iterators directly on non-const containers. You should do the same, that is, if you provide an implicit conversion from iterator to const_iterator, then you can just write:

btree<char>::const_iterator it = myTree.find('M');

... and it will work (will not test the find method, but will allow you to verify the const_iterator behavior)