Почему стандартный алгоритм С++ "count" возвращает ptrdiff_t вместо size_t?

Ответ 1

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

Единственным интегральным типом, предлагаемым стандартом std::iterator_traits<>, является std::iterator_traits<>::difference_type, который подходит для представления "расстояний" между двумя итераторами. Для итераторов, реализованных как (обертки) указателей, этот тип std::ptrdiff_t. Не существует size_type или тому подобного из свойств итератора, поэтому другого выбора нет.

Ответ 2

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

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

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

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

Насколько я могу судить, даже в С++ 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 может выражать счет итераций между любыми двумя итераторами.

Ответ 3

Возвращаемый тип typename iterator_traits<InputIterator>::difference_type, который в данном случае бывает ptrdiff_t.

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

Ответ 4

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

Ответ 5

Первоначально 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" ). Это также означает, что пользователь не несет ответственности за вывод соответствующего типа для использования, хотя это может быть сложно, именно из-за возможности пользовательского итератора.

Ответ 6

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

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

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

Ответ 7

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

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

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

В size_type говорится:

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

Естественным типом здесь является size_t.

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