How does begin() know which return type to return (const or non-const)?

Question

This works perfectly :

list<int> l;
list<int>::const_iterator it;
it = l.begin();
list<int>::iterator it2;
it2 = l.begin();

What I don't get is how the list "knows" that it must return the iterator begin() version or the const_iterator begin() const one.

I'm trying to implement iterators for my container (a trie) and I'm running into this problem. Isn't C++ supposed not to handle differentiation by return type (except when using weird tricks)?

Here is some code and the compiler error I get :

My Trie<T> is a templated trie that can contain any type. I have a Trie<int>::iter non-const iterator and a Trie<int>::const_iter const iterator. iter begin() and const_iter begin() const are declared (and defined) in the Trie class.

Trie<int> t;
Trie<int>::const_iter it;
it = t.begin();

Error :

../test/trie.cpp:181: error: no match for 'operator=' in 'it = Trie<T>::begin() [with T = int]()'
[..path..]/Trie.h:230: note: candidates are: Trie<int>::const_trie_iterator& Trie<int>::const_trie_iterator::operator=(const Trie<int>::const_trie_iterator&)

So, I believe the non-const version of begin is not used.

I contemplated creating an operator=(const Trie<T>::const_trie_iterator&) method for the non-const iterator but I don't see that in the STD lib and I would have to const_cast the iterator. What should I do?

Answer 1

In standard containers, a non-const iterator is implicitly convertible to a const_iterator. The type returned is based solely on the const-ness of the object/reference on which begin() was called, which in your case would be iterator, there is a conversion that allows the later assignment.

In particular in the 23.2.1 General Container Requirements, table 96, it says that X::iterator must be convertible to X::const_iterator.

Answer 2

list knows which kind of iterator to return because there are two begin methods defined, one for when the list is const, and one for when it isn't. The declarations might look something like this:

template<class T>
class list {
public:
    iterator<T> begin();
    const_iterator<T> begin() const;
}

In the following example, the first, non-const iterator would be returned, because the list isn't const:

void doSomething(list<int> &myList) {
    iterator<int> i = myList.begin();
    ...
}

In the next example, the list is declared as const, so the second version of begin that returns a const_iterator would be used instead:

void doSomethingElse(const list<int> &myList) {
    const_iterator<int> i = myList.begin();
    ....
}

Of course, an iterator can always be cast to a const_iterator, so you could declare i to be a const_iterator in either example, but if you try to declare i to be an iterator in the second example you'll get an error since a const_iterator can not be implicitly cast as an iterator.