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
.