Concepts introduce a new way to write iterators. New iterators will provide concept maps that state what concepts they model, e.g.,
concept_map InputIterator<my_new_file_iterator> {
typedef char value_type;
typedef const char& reference;
typedef const char* pointer;
typedef long difference_type;
};
However, there are a great number of iterators in the world that were designed before concepts ever came to play. These iterators use the existing iterator_traits mechanism to establish that they model particular concepts, e.g.,
template<>
struct iterator_traits<my_old_file_iterator> {
typedef input_iterator_tag iterator_category;
typedef char value_type;
typedef const char& reference;
typedef const char* pointer;
typedef long difference_type;
}
The success of concepts in C++ will depend greatly on their ability to retain backward compatibility. For iterators, that means that my_old_file_iterator should with the ConceptC++ Standard Library algorithms and containers. The user should not have to write a concept map to make this happen, because writing those concept maps would become a reason not to embrace concepts. For instance, we’d like to be able to pass my_old_file_iterator instances into the copy algorithm, which looks like this:
template<InputIterator InIter, OutputIterator<InIter::reference> OutIter>
OutIter copy(InIter first, InIter last, OutIter out) {
while (first != last)
*out++ = *first++;
return out;
}
// This should work!
std::vector<int> values;
copy(my_old_file_iterator<int>("ints.txt"), my_old_file_iterator(),
back_inserter(values));
Fortunately, we can write “backward-compatibility” concept maps that make “old-style” iterators based on iterator_traits work with algorithms that use concepts. The trick is to first find a safe way to determine if a type provides iterator_traits. We can do this with an implicit concept:
auto concept IteratorTraits<typename Iter> {
typename category = iterator_traits<Iter>::iterator_category;
typename value_type = iterator_traits<Iter>::value_type;
typename reference = iterator_traits<Iter>::reference;
typename pointer = iterator_traits<Iter>::pointer;
typename difference_type = iterator_traits<Iter>::difference_type;
}
The next step is the most interesting. We are going to write a very general concept map for InputIterator that accepts any type so long as that type has suitable iterator_traits with an appropriate iterator_category:
template<typename Iter>
where IteratorTraits<Iter> &&
Convertible<IteratorTraits<Iter>::category, input_iterator_tag>
concept_map InputIterator<Iter> late_check {
typedef IteratorTraits<Iter>::value_type value_type;
typedef IteratorTraits<Iter>::reference reference;
typedef IteratorTraits<Iter>::pointer pointer;
typedef IteratorTraits<Iter>::difference_type difference_type;
}
By examining IteratorTraits (and, thus, iterator_traits), we determine whether the user has stated that this is an (old-style) iterator. For these iterators, the concept map provides the necessary typedefs for the associated types. That late_check keyword tells the compiler to delay type-checking of the concept map until it is instantiated; otherwise, the compiler would produce errors (because Iter doesn’t necessarily have dereference or increment operators, for instance). Note that late_check isn’t yet implemented in ConceptGCC: to get things to work now, remove late_check, then put a ! after typename in the template header. In any case, our call to copy() succeeds, because concept map lookup will find and match this concept map template. This is how the ConceptGCC Standard Library has provided backward compatibility, and it works very well.
We also have to worry about compatibility in the other direction, so that new-style iterators (those which won’t work with iterator_traits) can still be used algorithms that are based on iterator_traits. For instance, many have written templates for the oft-needed copy_if() algorithm that is–tragically–not present in the C++ Standard Library:
template<typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator
copy_if(InputIterator first, InputIterator last, OutputIterator out, Predicate pred) {
for (; first != last; ++first)
if (pred(*first))
*out++ = *first;
return out;
}
// We want this to work, too!
std::vector<int> nonzeroes;
copy_if(my_new_file_iterator<int>("ints.txt"), my_new_file_iterator(),
back_inserter(nonzeroes), is_non_zero());
my_new_file_iterator does provide an iterator_traits, and the primary definition of iterator_traits isn’t likely to work, either. Are we stuck upgrading our copy_if implementation to use concepts? Thankfully, no: we can write a partial specialization of iterator_traits that adapts new-style iterators for use with “old-style” generic algorithms:
template<InputIterator Iter>
struct iterator_traits<Iter> {
typedef input_iterator_tag iterator_category;
typedef InputIterator<Iter>::value_type value_type;
typedef InputIterator<Iter>::reference reference;
typedef InputIterator<Iter>::pointer pointer;
typedef InputIterator<Iter>::difference_type difference_type;
}
See how we’ve performed essentially the inverse operation to the concept map above? Whenever iterator_traits is given a model of InputIterator, it will extract the associated types from the InputIterator concept map, making them available for algorithms using iterator_traits. Better yet, it exposes an appropriate iterator_category, so that algorithms using tag dispatching will still work. By providing more of these iterator_traits partial specializations (for ForwardIterator, BidirectionalIterator, and RandomAccessIterator), we can make all new-style iterators available to old-style generic algorithms.
Interestingly enough, these concept-based partial specializations of iterator_traits even work within constrained templates. For instance, we could add a where clauses to existing generic algorithms, but still rely on iterator_traits to access associated types:
template<typename Iter, typename Pred<
where InputIterator<Iter> && Predicate<InputIterator<Iter>::reference>
typename std::iterator_traits<Iter>::difference_type
count_if(Iter first, Iter last, Pred pred) {
typename std::iterator_traits<Iter>::difference_type n = 0;
for (; first != last; ++first)
if (pred(*first))
++n;
return n;
}
The best thing about that implementation of count_if is that it’s a fully-working, concept-constrained template. However, if you take away the where clause (say, by creating a WHERE macro), it becomes a fully-working, unconstrained C++03 template. So a single implementation works both with and without concepts.
Before we run off and implement all of our ConceptC++ code with traits (which concepts were support to eliminate!), David Abrahams has found a better way to write algorithms that work both with and without concepts. David has improved the Boost Concept Check Library with macros and tools that will help us write code that works well with and without concepts support.
Backward compatibility is one of the most important aspects of concepts, as it is crucial for the widespread acceptance of this new language feature. Fortunately, concepts are up to the task, and with a little bit of effort we are able to seamlessly support iterators and algorithms, both old and new, with a single, coherent language feature.
