Почему стандартный алгоритм C++ "count" возвращает тип_разницы вместо size_t?
Почему тип возврата std::count difference_type итераторов (часто ptrdiff_t).
Поскольку счет никогда не может быть отрицательным, не size_t технически правильный выбор? А что, если счет превышает диапазон ptrdiff_t поскольку теоретически возможный размер массива может быть size_t?
РЕДАКТИРОВАТЬ: Пока нет подходящего ответа о том, почему функция возвращает ptrdiff_t, Некоторое объяснение, полученное из ответов ниже, заключается в том, что iterator_traits<InputIterator>::difference_type который является общим и может быть чем угодно. До этого момента это имеет смысл. Есть случаи, когда количество может превышать size_t, Однако по-прежнему не имеет смысла, почему возвращаемый тип typedef ptrdiff_t iterator_traits<InputIterator>::difference_type для стандартных итераторов вместо typedef size_t iterator_traits<InputIterator>::difference_type,
7 ответов
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так же, как и С. Но в таблице 32 (требования к распределителям) сказано, что X::difference_type может представлять разницу между любыми двумя указателями, и std::allocator гарантированно использовать ptrdiff_t как его difference_type (20.1.5/4). C++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, Кажется наиболее естественным выбрать именно этот.
Если бы итератор был массивом, это означало бы, что результат находится в пределах диапазона массива.
Для этого конкретного алгоритма я не могу придумать причину, которая интересна. Для тех, кто использует это как компонент, это может быть интересно.
Страница действительно говорит, что она сделала бы что-то эквивалентное. Так что для массива это может сделать что-то вроде прямой разницы указателей. Это было бы довольно быстрой специализацией, если бы это было применимо.