Хороший вопрос! Есть несколько причин, по которым вы можете захотеть это сделать.
Для начала, не все языки программирования поставляются со всеми хорошими структурами данных, которые вы, возможно, захотите использовать. Например, C не имеет встроенных библиотек для любых структур данных (хотя у него есть bsearch и qsort для массивов), поэтому, если вы хотите использовать связанный список, ha sh таблица, et c. в C вам нужно либо создать его самостоятельно, либо использовать пользовательскую стороннюю библиотеку.
Другие языки (например, JavaScript) имеют встроенную поддержку некоторых, но не всех типов структур данных. Например, нет встроенной поддержки JavaScript для связанных списков или двоичных деревьев поиска. И я не знаю какого-либо основного языка программирования, который имеет встроенную библиотеку для попыток , хотя, пожалуйста, дайте мне знать, если это не так!
В приведенных выше примерах указаны места, где отсутствие поддержки, точка, для некоторых структур данных потребует от вас написать свою собственную. Но есть и другие причины, по которым вы можете захотеть реализовать свои собственные структуры данных.
Важная из них - эффективность. Поставьте себя на место человека, который должен реализовать динамический c массив, ha sh таблицу и двоичное дерево поиска для определенного языка программирования. Вы не можете знать, каким рабочим процессам люди будут подвергать ваши структуры данных. Собираются ли они делать массу операций вставки и удаления или в основном будут запрашивать информацию? Например, если вы пишете тип двоичного дерева поиска, в котором часто встречаются вставки и удаления, вы, вероятно, захотите посмотреть что-то вроде красного / черного дерева, но если вставки и удаления редки, тогда дерево AVL будет работать много. лучше. Но вы не можете знать это заранее, потому что вам нужно написать одну реализацию, которая выдержит испытание временем и будет хорошо работать для всех приложений. Это может посоветовать вам выбрать «разумный» выбор, который хорошо работает во многих приложениях, но не требует жесткой настройки производительности для вашего конкретного c приложения. Поэтому создание пользовательской структуры данных может позволить вам воспользоваться преимуществами конкретной структуры решаемой проблемы.
В некоторых случаях спецификация языка делает невозможным или затруднительным использование быстрых реализаций данных. структуры как языковой стандарт. Например, C ++ требует, чтобы его ассоциативные контейнеры позволяли удалять и вставлять элементы без нарушения каких-либо итераторов в них. Это делает значительно более сложным / неэффективным реализацию этих контейнеров с такими типами, как B-деревья, которые на самом деле могут работать немного лучше, чем обычные деревья двоичного поиска из-за эффектов кешей. Точно так же реализация неупорядоченных контейнеров имеет интерфейс, который предполагает цепное хеширование, что не обязательно соответствует тому, как вы хотели бы реализовать таблицу ha sh. Вот почему, например, существуют альтернативы Google стандартным контейнерам , которые оптимизированы для использования пользовательских структур данных, которые не легко вписываются в языковую структуру.
Еще одна причина, по которой библиотеки могут не предоставление самых быстрых контейнеров было бы проблемой при предоставлении простого интерфейса. Например, cuckoo hashing - это несколько недавняя схема хеширования, которая имеет отличную производительность на практике и гарантирует эффективный поиск в худшем случае. Но для того, чтобы хэширование с кукушкой работало, вам нужна возможность выбирать несколько ha sh функций для данного типа данных. В большинстве языков программирования существует концепция, согласно которой каждый тип данных имеет функцию «a» ha sh (std::hash<T>, Object.hashCode, __hash__, и т.д. c.), Что несовместимо с этой идеей. В принципе, языки могут требовать от пользователей написания семейств функций ha sh с мыслью о том, что будет много разных хешей для выбора для каждого объекта, но это усложняет логистику написания собственных пользовательских типов. Предоставив программисту возможность писать семейства функций ha sh для типов, которые в этом нуждаются, язык остается простым.
И, наконец, в пространстве есть просто инновации. Все время изобретаются новые структуры данных, а языки часто медленно растут и изменяются. Недавно было проведено множество исследований новых более быстрых деревьев двоичного поиска (посмотрите деревья WAVL в качестве примера) или новых стратегий хеширования (хеширование с кукушкой и «Швейцарская таблица», разработанная Google), а также разработчиков языков и разработчикам не всегда удается поспевать за ними. чтобы получить лучшую производительность с помощью собственных реализаций ».
Есть еще одна причина, о которой я могу думать, и это« узнать, как работают язык и структура данных ». Иногда стоит создавать собственные типы данных только для того, чтобы отточить свои навыки, и вы часто найдете действительно умные методы в структурах данных, когда вы это сделаете!
При всем вышесказанном я бы не рекомендовал использовать по умолчанию кодирование собственной версии структуры данных каждый раз, когда она вам нужна. Версии библиотеки обычно являются довольно безопасным выбором, если вы не ищете дополнительную производительность или вам не хватает некоторых функций, которые вам нужны. Но, надеюсь, это поможет вам лучше понять, почему вам стоит отказаться от хорошо протестированных инструментов по умолчанию и создать свои собственные.
Надеюсь, это поможет!