Почему счетчик стандартного алгоритма С++ возвращает разность_типа вместо размера_t?

Алгоритм std::count() опирается на тип итератора для определения целочисленного типа, достаточно большого для представления любого размера диапазона. Возможная реализация контейнеров включает в себя файлы, сетевые потоки и т. д. Нет гарантии, что весь диапазон сразу поместится в адресное пространство процесса, поэтому std::size_t может быть слишком маленьким.

Единственный целочисленный тип, предлагаемый стандартом std::iterator_traits<>, — это std::iterator_traits<>::difference_type, который подходит для представления «расстояний» между двумя итераторами. Для итераторов, реализованных как (оболочки) указателей, этот тип — std::ptrdiff_t. В трейтах итераторов нет size_type или им подобных, так что другого выбора нет.

size_t технически не является правильным выбором, так как он может быть недостаточно большим. Итераторам разрешено перебирать «что-то», что больше любого объекта в памяти — например, файл на диске. Когда они это сделают, итератор может определить тип больше size_t как свой difference_type, если он доступен.

difference_type необходимо подписать, поскольку в контекстах, отличных от std::count, он представляет смещения между итераторами в обоих направлениях. Для итераторов с произвольным доступом it + difference является совершенно разумной операцией, даже если difference отрицательно.

iterator_traits не предлагает тип без знака. Возможно, так и должно быть, но, учитывая, что это не так, iterator_traits<InputIterator>::difference_type это лучший доступный тип.

Вопрос о том, должны ли итераторы предлагать беззнаковый тип, вероятно, связан с массовым конфликтом стилей кодирования, следует ли вообще использовать беззнаковые типы для подсчета. Я не предлагаю воспроизводить этот аргумент здесь, вы можете посмотреть его. У ptrdiff_t есть недостаток, заключающийся в том, что в некоторых системах он не может представить все допустимые различия указателей и, следовательно, не может представить все ожидаемые результаты std::count.

Насколько я могу судить, даже в C++03 стандарт фактически запрещал это, может быть, случайно. 5.7/6 говорит о том, что вычитание может привести к переполнению ptrdiff_t, как это делает C. Но в таблице 32 (требования к распределителю) сказано, что X::difference_type может представлять разницу между любыми двумя указателями, а std::allocator гарантированно использует ptrdiff_t в качестве своего difference_type (20.1.5/4). С++ 11 аналогичен. Таким образом, одна часть стандарта считает, что вычитание указателя может переполнить ptrdiff_t, а другая часть стандарта говорит, что не может.

std::count предположительно был разработан в соответствии с тем же (возможно, ошибочным) предположением, что и требования распределителя, что ptrdiff_t достаточно велико, чтобы выразить размер любого объекта, и (в общем) difference_type итератора может выражать количество итерандов между любыми двумя итераторами.

Тип возвращаемого значения — typename iterator_traits<InputIterator>::difference_type, в данном случае это ptrdiff_t.

Предположительно было выбрано difference_type, потому что максимальное количество совпадающих элементов в диапазоне было бы разностью итераторов last - first.

Первоначально std::count было:

template <class InputIterator, class EqualityComparable, class Size>
void count(InputIterator first, InputIterator last, 
           const EqualityComparable& value,
           Size& n);

В этой функции Size является параметром шаблона. Это может быть что угодно, и вы обязаны убедиться, что это правильно. Это может быть самый длинный тип на вашей платформе.

Я подозреваю, что когда новая форма:

template <class InputIterator, class EqualityComparable>
iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, 
      const EqualityComparable& value);

был добавлен iterator_traits уже существовал, поэтому повторное использование существующего типа имело то преимущество, что оно сохраняло небольшие и локализованные изменения стандарта по сравнению с добавлением еще одного typedef в iterator_traits.

Таким образом, использование iterator_traits вместо простого использования std::size_type означает, что каждый возможный итератор получает возможность указать, какой именно тип должен быть возвращен std::count. Это включает в себя пользовательские итераторы, которые считывают из сети или с диска, которые могут использовать что-то гораздо большее, чем ptrdiff_t или size_type и им подобные. (При необходимости это может быть своего рода "BigInt"). Это также означает, что пользователь не несет ответственности за вывод соответствующего типа для использования, что может быть сложно именно из-за возможности пользовательского итератора.

Хотя счетчик не может быть отрицательным, тип возвращаемого значения указан как iterator_traits<InputIterator>::difference_type, а разница между двумя итераторами может быть отрицательной.

Если бы итератор был массивом, это означало бы, что результат находится в пределах диапазона массива.

Для этого конкретного алгоритма я не могу придумать интересную причину. Тем не менее, для тех, кто использует это как компонент, это может быть интересно.

На странице сказано, что она сделает что-то эквивалентное. Таким образом, в случае массива это может сделать что-то вроде прямой разницы указателей. Это была бы довольно быстрая специализация, если бы она была применима.

difference_type обычно обозначает тип, подходящий для обозначения расстояния в массиве или подобном. Следующая формулировка взята из требований к распределителю, но всякий раз, когда в стандарте говорится о difference_type, это означает ту же концепцию:

тип, который может представлять разницу между любыми двумя указателями в модели распределения

Естественный тип для этого — ptrdiff_t.

Для size_type он говорит:

тип, который может представлять размер самого большого объекта в модели распределения.

Естественный тип здесь — size_t.

Теперь для подсчета любых элементов в диапазоне (или массиве) нужен хотя бы тип, подходящий для указания разницы last-first. Кажется наиболее естественным выбрать именно его.