Почему size_t без знака?

Question

Бьярн Страуструп написал на языке программирования C++:

Целочисленные типы без знака идеальны для применений, которые рассматривают хранилище как битовый массив. Использование unsigned вместо int для получения еще одного бита для представления положительных целых чисел почти никогда не является хорошей идеей. Попытки обеспечить положительные значения некоторых значений, объявив переменные без знака, будут, как правило, отвергнуты правилами неявного преобразования.

size_t кажется беззнаковым "чтобы получить еще один бит для представления натуральных чисел". Так было ли это ошибкой (или компромиссом), и если да, то должны ли мы минимизировать ее использование в нашем собственном коде?

Другая соответствующая статья Скотта Мейерса здесь. Подводя итог, он рекомендует не использовать unsigned в интерфейсах, независимо от того, всегда ли значение положительное или нет. Другими словами, даже если отрицательные значения не имеют смысла, не обязательно использовать unsigned.

Answer 1

size_t не подписано по историческим причинам.

В архитектуре с 16-битными указателями, такой как "маленькая" модель программирования под DOS, было бы нецелесообразно ограничивать строки 32 КБ.

По этой причине стандарт C требует (через требуемые диапазоны) ptrdiff_tподписанный аналог size_t и результирующий тип разности указателей должен составлять 17 бит.

Эти причины могут все еще применяться в некоторых частях мира встроенного программирования.

Однако они не применимы к современному 32-битному или 64-битному программированию, где гораздо более важным фактором является то, что неудачные правила неявного преобразования C и C++ превращают неподписанные типы в аттракторы ошибок, когда они используются для чисел (и следовательно, арифметические операции и сравнения величин). Оглядываясь назад, мы можем видеть, что решение принять те конкретные правила конвертации, где, например, string( "Hi" ).length() < -3 практически гарантировано, было довольно глупо и непрактично. Однако это решение означает, что в современном программировании принятие беззнаковых типов для чисел имеет серьезные недостатки и никаких преимуществ - за исключением удовлетворения чувств тех, кто находит unsigned быть самоописательным именем типа и не думать о typedef int MyType,

Подводя итог, это не было ошибкой. Это было решение по очень рациональным, практическим причинам программирования. Это не имело ничего общего с переносом ожиданий от проверенных границ языков, таких как Pascal, на C++ (что является ошибкой, но очень распространенной ошибкой, даже если некоторые из тех, кто делает это, никогда не слышали о Pascal).

Answer 2

size_t является unsigned потому что отрицательные размеры не имеют смысла.

(Из комментариев:)

Это не столько обеспечение, сколько констатация того, что есть. Когда в последний раз вы видели список размером -1? Следуйте этой логике слишком далеко, и вы обнаружите, что unsigned вообще не должно существовать, и битовые операции также не должны быть разрешены. - geekosaur

Более того: адреса, по причинам, о которых вы должны подумать, не подписаны. Размеры генерируются путем сравнения адресов; обработка адреса как подписанного сделает очень неправильную вещь, и использование значения со знаком для результата приведет к потере данных таким образом, что ваше чтение цитаты Страуструпа, очевидно, считает приемлемым, но на самом деле это не так. Возможно, вы можете объяснить, что вместо этого должен делать отрицательный адрес. - geekosaur

Answer 3

Причина, по которой типы индексов остаются без знака, заключается в симметрии с предпочтениями C и C++ для полуоткрытых интервалов. И если ваши типы индексов будут без знака, тогда удобно также иметь ваш тип размера без знака.

---

В C вы можете иметь указатель, который указывает на массив. Действительный указатель может указывать на любой элемент массива или один элемент за концом массива. Он не может указывать на один элемент перед началом массива.

int a[2] = { 0, 1 };
int * p = a;  // OK
++p;  // OK, points to the second element
++p;  // Still OK, but you cannot dereference this one.
++p;  // Nope, now you've gone too far.
p = a;
--p;  // oops!  not allowed

C++ соглашается и распространяет эту идею на итераторы.

Аргументы против неподписанных типов индексов часто приводят пример обхода массива задом наперед, и код часто выглядит так:

// WARNING:  Possibly dangerous code.
int a[size] = ...;
for (index_type i = size - 1; i >= 0; --i) { ... }

Этот код работает только если index_type подписывается, что используется в качестве аргумента, что типы индексов должны быть подписаны (и, что, по расширению, размеры должны быть подписаны).

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

// WARNING:  Bad code.
int a[size] = ...;
for (int * p = a + size - 1; p >= a; --p) { ... }

Да, теперь у нас неопределенное поведение! Игнорирование проблемы, когда size 0, у нас есть проблема в конце итерации, потому что мы генерируем недопустимый указатель, который указывает на элемент перед первым. Это неопределенное поведение, даже если мы никогда не пытаемся разыменовать этот указатель.

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

Правильное решение на основе указателей:

int a[size] = ...;
for (int * p = a + size; p != a; ) {
  --p;
  ...
}

Многие находят это тревожным, потому что декремент теперь находится в теле цикла, а не в заголовке, но это то, что происходит, когда ваш синтаксис for предназначен в основном для прямых циклов через полуоткрытые интервалы. (Обратные итераторы решают эту асимметрию, откладывая декремент.)

Теперь по аналогии решение на основе индекса становится:

int a[size] = ...;
for (index_type i = size; i != 0; ) {
  --i;
  ...
}

Это работает ли index_type подписан или не подписан, но выбор без знака дает код, который более точно сопоставляется с версиями идиоматического указателя и итератора. Неподписанное также означает, что, как и в случае с указателями и итераторами, мы сможем получить доступ к каждому элементу последовательности - мы не сдаем половину нашего возможного диапазона для представления бессмысленных значений. Хотя это не является практической проблемой в 64-битном мире, это может быть очень реальная проблема в 16-битном встроенном процессоре или в создании абстрактного типа контейнера для разреженных данных в огромном диапазоне, который все еще может обеспечить идентичный API в качестве родной контейнер.

Answer 4

С другой стороны...

Миф 1: std::size_t является неподписанным из-за устаревших ограничений, которые больше не применяются.

Здесь обычно упоминаются две "исторические" причины:

1. sizeof возвращается std::size_t, который был неподписан со времен С.
2. Процессоры имели меньший размер слова, поэтому было важно выжать этот дополнительный бит из диапазона.

Но ни одна из этих причин, несмотря на то, что она очень старая, на самом деле не относится к истории.

sizeof по-прежнему возвращает std::size_t который до сих пор не подписан. Если вы хотите взаимодействовать с sizeof или стандартные контейнеры библиотеки, вам придется использовать std::size_t,

Все альтернативы хуже: вы можете отключить предупреждения сравнения со знаком / без знака и предупреждения преобразования размера и надеяться, что значения всегда будут находиться в перекрывающихся диапазонах, так что вы можете игнорировать скрытые ошибки, используя пару потенциально возможных типов. Или вы можете сделать много проверок диапазона и явных преобразований. Или вы можете ввести свой собственный тип размера с помощью умных встроенных преобразований, чтобы централизовать проверку диапазона, но никакая другая библиотека не будет использовать ваш тип размера.

И хотя большинство основных вычислений выполняется на 32- и 64-разрядных процессорах, C++ все еще используется на 16-разрядных микропроцессорах во встроенных системах даже сегодня. На этих микропроцессорах часто очень полезно иметь значение размера слова, которое может представлять любое значение в вашем пространстве памяти.

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

Миф 2: Вам не нужен этот дополнительный бит. (AKA, у вас никогда не будет строки размером более 2 ГБ, если ваше адресное пространство составляет всего 4 ГБ.)

Размеры и индексы не только для памяти. Ваше адресное пространство может быть ограничено, но вы можете обрабатывать файлы, которые намного больше, чем ваше адресное пространство. И хотя у вас может не быть строки с более чем 2 ГБ, вы можете с комфортом иметь битовый набор с более чем 2 Гбит. И не забудьте виртуальные контейнеры, предназначенные для разреженных данных.

Миф 3: Вы всегда можете использовать более широкий тип со знаком.

Не всегда. Это правда, что для локальной переменной или двумя, вы можете использовать std::int64_t (при условии, что ваша система имеет один) или signed long long и, вероятно, написать вполне разумный код. (Но вам все равно понадобится несколько явных приведений и вдвое больше проверок границ, либо вам придется отключить некоторые предупреждения компилятора, которые могли бы предупредить вас об ошибках в другом месте вашего кода.)

Но что, если вы строите большую таблицу индексов? Вы действительно хотите дополнительные два или четыре байта для каждого индекса, когда вам нужен только один бит? Даже если у вас достаточно памяти и современный процессор, увеличение этой таблицы в два раза может оказать вредное влияние на локальность ссылок, а все проверки диапазона теперь выполняются в два этапа, снижая эффективность прогнозирования ветвлений. А что если у тебя нет всей этой памяти?

Миф 4: Арифметика без знака удивительна и неестественна.

Это подразумевает, что подписанная арифметика не удивительна или как-то более естественна. И, возможно, именно в мышлении с точки зрения математики все основные арифметические операции замкнуты на множестве всех целых чисел.

Но наши компьютеры не работают с целыми числами. Они работают с бесконечно малой долей целых чисел. Наша подписанная арифметика не замкнута над множеством всех целых чисел. У нас переполнение и недостаток. Для многих это так удивительно и неестественно, что они просто игнорируют это.

Это ошибка:

auto mid = (min + max) / 2;  // BUGGY

Если min а также max подписаны, сумма может переполниться, и это приводит к неопределенному поведению. Большинство из нас обычно пропускают такие ошибки, потому что мы забываем, что дополнение не закрыто для набора подписанных целых. Нам это сходит с рук, потому что наши компиляторы обычно генерируют код, который делает что-то разумное (но все же удивительно).

Если min а также max без знака, сумма может все еще переполниться, но неопределенное поведение исчезло. Вы все равно получите неправильный ответ, так что это все равно удивительно, но не более удивительно, чем с подписанными целыми.

Настоящий сюрприз без знака приходит с вычитанием: если вы вычтите большее беззнаковое целое из меньшего, то в итоге вы получите большое число. Этот результат не более удивителен, чем если бы вы поделили на 0.

Даже если вы можете исключить неподписанные типы из всех ваших API, вы все равно должны быть готовы к этим неподписанным "сюрпризам", если вы имеете дело со стандартными контейнерами, форматами файлов или проводными протоколами. Стоит ли добавлять трения в свои API, чтобы "решить" только часть проблемы?