Почему в стандартной библиотеке C нет хеш-таблиц? - PullRequest
47 голосов
/ 25 мая 2011

Почему отсутствует поддержка Hashtable в составе библиотеки Standard C?Есть ли какая-то конкретная причина для этого?

Ответы [ 4 ]

45 голосов
/ 25 мая 2011

C кажется необычным по сегодняшним стандартам, потому что не определены полезные структуры данных. Никто. Даже не строки - и если вы думаете, что строка C - это структура данных, нам придется не согласиться с тем, что такое «структура данных».

Если вам нравится C, тогда думайте о нем как о «чистом листе» ... все ваше приложение состоит из кода, написанного вами, и выбранных вами библиотек, а также нескольких довольно примитивных стандартных функций библиотеки, с одно или два исключения, например qsort. В наши дни люди используют C для реализации таких вещей, как Python, Ruby, Apache или ядро ​​Linux. Это проекты, которые в любом случае используют все свои собственные структуры данных, и вряд ли они будут использовать что-то вроде STL.

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

Со всеми этими библиотеками, которые делают то, что вы хотите, какой смысл добавлять хеш-таблицу в стандарт C?

39 голосов
/ 25 мая 2011

В стандартной библиотеке C нет хеш-таблицы, потому что либо:

  • никто не представил предложение рабочей группе; или
  • рабочая группа сочла это ненужным.

Так работает ISO. Предложения выдвигаются и принимаются или отклоняются.

Вы должны быть осторожны с тем, что добавляете в стандартную библиотеку, поскольку у вас есть две конфликтующие группы. Как пользователь , вы можете захотеть, чтобы каждая структура данных под солнцем была добавлена ​​в стандарт, чтобы сделать язык более полезным.

Но, как разработчик языка (кроме того, это, вероятно, люди, которые, как правило, составляют большинство различных рабочих групп, так что их мнение, вероятно, окажет большее влияние), вы не на самом деле не нужно создавать вещи, которые могут использоваться не всеми. Все, что было там, когда появился C89, было связано с тем, что основная цель состояла в том, чтобы кодифицировать существующую практику, а не вводить новые практики. С тех пор все итерации стандартов были немного более свободными в том, что они могут сделать, но обратная совместимость по-прежнему является важной проблемой.

Я тоже имею конфликты. Я бы хотел, чтобы все функции библиотек Java, C ++ или Python были в моем распоряжении в C. Конечно, это усложнит изучение всего для новичков и, как сказал один из комментаторов, возможно, сделает это любым Обезьяна кода может выкачать полезный код, уменьшив мою ценность в процессе: -)

И у меня в значительной степени есть все структуры данных, которые мне когда-либо понадобятся, из моей долгой и (в основном) прославленной карьеры. Вы не ограничены стандартной библиотекой для такого рода вещей. Существует множество сторонних инструментов, которые вы можете использовать для выполнения этой работы, и (как и я) вы также можете использовать свои собственные.

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

Это обоснование фокусируется главным образом на дополнениях, пояснениях и изменениях, внесенных в язык, как описано в базовых документах. Это не является обоснованием для языка Си в целом: Комитету было поручено кодифицировать существующий язык, а не разрабатывать новый. В этом Обосновании не делается никаких попыток защитить ранее существовавший синтаксис языка, такой как синтаксис объявлений или привязка операторов.

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

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


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

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

Эта третья, вероятно, является основной причиной, по которой библиотека не была расширена в массовом масштабе с первоначальными усилиями по стандартизации, - и тем фактом, что такое расширение из комитета, вероятно, привело бы к тому, что ANSI C был бы помечен как C2038, а не как C89 .

10 голосов
/ 25 мая 2011

Стандартная библиотека C не включает любые большие, постоянные структуры данных - ни списки, ни деревья, ни стеки, ни хеш-таблицы.

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

Обратите внимание, что стандартная библиотека C POSIX определяет общие хеш-функции: hcreate(), hsearch() и hdestroy(); и отметьте также, что их «один размер подходит всем» природа имеет тенденцию делать их неадекватными для большинства реальных случаев использования, поддерживая приведенный выше аргумент.

1 голос

Из-за отсутствия шаблонов

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

Существуют стратегии C для смягчения этой проблемы, например, игра с void *, но они теряют проверки типов времени компиляции.

GLib и gnulib - мои рекомендуемые реализации на данный момент: Быстрый способ реализовать словарь в C

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...