Why does the C++ standard algorithm "count" return a difference_type instead of size_t?

Solution 1:

The std::count() algorithm relies on the iterator type to define an integral type large enough to represent any size of a range. Possible implementation of containers include files and network streams, etc. There is no guarantee that the entire range fits into the process' address space at once, so std::size_t might be too small.

The only integral type offered by the standard std::iterator_traits<> is std::iterator_traits<>::difference_type, which is suitable for representing "distances" between two iterators. For iterators implemented as (wrappers of) pointers, this type is std::ptrdiff_t. There is no size_type or the like from iterator traits, so there is no other choice.

Solution 2:

size_t is not technically the correct choice, since it might not be big enough. Iterators are permitted to iterate over "something" that is larger than any object in memory -- for example a file on disk. When they do so, the iterator can define a type larger than size_t as its difference_type, if one is available.

difference_type needs to be signed because in contexts other than std::count it represents offsets between iterators in both directions. For random access iterators, it + difference is a perfectly sensible operation even when difference is negative.

iterator_traits doesn't offer an unsigned type. Maybe it should, but given that it doesn't iterator_traits<InputIterator>::difference_type is the best type available.

The issue of whether iterators should offer an unsigned type probably relates to a massive conflict of coding styles, whether unsigned types should be used for counts at all. I don't propose to reproduce that argument here, you can look it up. ptrdiff_t does have a weakness that on some systems it cannot represent all valid pointer differences, and hence also cannot represent all expected results of std::count.

As far as I can tell, even in C++03 the standard actually forbade this, maybe by accident. 5.7/6 talks about subtraction possibly overflowing ptrdiff_t, just like C does. But table 32 (allocator requirements) says that X::difference_type can represent the difference between any two pointers, and std::allocator is guaranteed to use ptrdiff_t as its difference_type (20.1.5/4). C++11 is similar. So one part of the standard thinks that pointer subtraction can overflow ptrdiff_t, and another part of the standard says it can't.

std::count presumably was designed under the same (possibly defective) assumption as the allocator requirements, that ptrdiff_t is big enough to express the size of any object and (in general) an iterator's difference_type can express the count of iterands between any two iterators.

Solution 3:

The return type is typename iterator_traits<InputIterator>::difference_type which in this particular case happens to be ptrdiff_t.

Presumably difference_type was selected because the maximum number of matching elements in the range would be the iterator difference last - first.