How they avoid problems with concept-based overloading without explicit models (a.k.a. concept maps)

Question

As it is pointed in a number of talks and papers by Andrew Sutton, Concepts Lite proposal does have concept-based overloading feature and at the same time does not have a notion of concept map, that is template arguments are checked against concepts entirely by a compiler. Given this it is not clear how would they resolve a problem described in 2005 paper by Siek and Gregor, “Explicit model definitions are necessary”. In short the problem could be stated with the following quotation from the paper.

So, there are certain input iterator types (such as istream_iterator) that would be misclassified as forward iterators. What is the danger in this? Some algorithms dispatch based on Input_iterator vs. Forward_iterator.

(There are more examples besides iterators though.)

Yes, I'm aware of that above mentioned paper considered C++0x concepts, but the problem seems to be “generic” over concepts proposals.

Answer 1

The proposal in n3351 A Concept Design for the STL is to continue to use iterator category tags:

concept InputIterator<WeakInputIterator I> =
    EqualityComparable<I> &&
    Derived<IteratorCategory<I>, input_iterator_tag>;

In the syntax expected for inclusion into the standard per n4377 C++ Extensions for Concepts:

template<typename I>
concept bool InputIterator =
    WeakInputIterator<I>() && EqualityComparable<I>() &&
    Derived<IteratorCategory<I>, input_iterator_tag>();

From the former paper:

While C++11 makes it possible to evaluate all static requirements [...] we still need to differentiate some concepts based on their semantic requirements. The iterator category solves that problem for us.

In general, one can express semantic requirements by checking a type predicate (e.g. a nested type or constant, or a type function) that exists solely for the purpose of asserting a runtime semantic.