Что является настолько большим о STL? [закрытый]
14 ответов
Что такого замечательного в STL?
STL хорош тем, что был задуман очень рано и все же преуспел в использовании общей парадигмы программирования C ++ довольно эффективно.
Он эффективно разделил структуры данных: вектор , карту , ... и алгоритмы для работы с ними копия , преобразование , ... используя для этого шаблоны.
Он аккуратно разделил проблемы и предоставил общие контейнеры с крючками настройки (параметры шаблона Comparator и Allocator ).
Результат очень элегантен (принцип DRY) и очень эффективен благодаря оптимизации компилятора, поэтому вряд ли сгенерированные вручную алгоритмы для данного контейнера будут лучше.
Это также означает, что он легко расширяемый: вы можете создать свой собственный контейнер с желаемым интерфейсом, если он предоставляет STL-совместимые итераторы, вы сможете использовать с ним алгоритмы STL!
А благодаря использованию трейтов вы даже можете применять алгоритмы к C-массиву с помощью простых указателей! Поговорим об обратной совместимости!
Тем не менее, это могло (возможно) быть лучше ...
Что не так уж хорошо в STL?
Меня действительно бесит, что всегда приходится использовать итераторы, я бы действительно встал за возможность написать: std :: foreach (myVector, [] (int x) {return x + 1;}); , потому что посмотрим правде в глаза, в большинстве случаев вы хотите перебирать все контейнер...
Но что еще хуже, из-за этого:
set<int> mySet = /**/;
set<int>::const_iterator it = std::find(mySet.begin(), mySet.end(), 1005); // [1]
set<int>::const_iterator it = mySet.find(1005); // [2]
[1] и [2] выполняются совершенно по-разному, в результате чего [1] имеет сложность O (n), а [2] имеет сложность O (log n)! Проблема здесь в том, что итераторы слишком много абстрагируют.
Я не имею в виду, что итераторы недостойны, я просто имею в виду, что предоставление интерфейса исключительно с точки зрения итераторов было плохим выбором.
Я предпочитаю идею представлений контейнерам, например, посмотрите, что было сделано с Boost.MPL . С представлением вы манипулируете своим контейнером с помощью (ленивого) слоя преобразования. Это создает очень эффективные структуры, которые позволяют отфильтровывать одни элементы, преобразовывать другие и т. Д.
Объединение представлений и идей проверки концепции , я думаю, дало бы много лучший интерфейс для алгоритмов STL (и решите эту проблему find , lower_bound , upper_bound , equal_range ).
Это также позволило бы избежать типичных ошибок, связанных с использованием плохо определенных диапазонов итераторов и неопределенного поведения, которое из-за этого ...
Что мне нравится в STL, так это его надежность. Его легко продлить. Некоторые жалуются, что он маленький, в нем отсутствуют многие распространенные алгоритмы или итераторы. Но это именно тогда, когда вы видите, как легко добавить недостающие компоненты, которые вам нужны. Мало того, маленький - это красиво: у вас есть около 60 алгоритмов, несколько контейнеров и несколько итераторов; но функциональность находится в том порядке, в котором они указаны. Интерфейсы контейнеров остаются небольшими и простыми.
Так как это мода писать небольшие, простые, модульные алгоритмы, становится легче обнаруживать ошибки и дыры в ваших компонентах. Тем не менее, в то же время, какими бы простыми ни были алгоритмы и итераторы, они необычайно надежны: ваши алгоритмы будут работать со многими существующими и еще не написанными итераторами, а ваши итераторы работают со многими существующими и еще не написанными. написанные алгоритмы.
Мне также нравится, насколько прост в STL. У вас есть контейнеры, итераторы и алгоритмы. Вот и все (я лежу здесь, но это то, что нужно, чтобы освоиться с библиотекой). Вы можете смешивать разные алгоритмы с разными итераторами с разными контейнерами. Правда, у некоторых из них есть ограничения, которые запрещают им работать с другими, но в целом есть с чем поиграть.
Никлаус Вирт сказал, что программа - это алгоритмы плюс структуры данных. Именно об этом и идет речь в STL. Если Ruby и Python - супергерои строк, то C ++ и STL - супергерои алгоритмов и контейнеров.
Контейнеры STL хороши, но они не сильно отличаются от других языков программирования. Что делает контейнеры STL полезными, так это то, что они прекрасно сочетаются с алгоритмами. Гибкость, обеспечиваемая стандартными алгоритмами, не имеет себе равных в других языках программирования.
Без алгоритмов контейнеры - это просто так. Контейнеры. Ничего особенного.
Теперь, если вы говорите о библиотеках контейнеров только для C ++, маловероятно, что вы найдете библиотеки, используемые и протестированные так же хорошо, как те, которые предоставляются STL, если ничто иное, потому что они являются стандартными.
Дело не столько в том, что это «отличная» или «лучшая библиотека коллекций, которую вы можете получить на * любом * языке», но у нее есть философия, отличная от многих других языков.
В частности, стандартная библиотека C ++ использует парадигму общего программирования , а не объектно-ориентированную парадигму, которая является общей для таких языков, как Java и C #. То есть у вас есть «общее» определение того, каким должен быть итератор , а затем вы можете реализовать функцию for_each или sort или max_element , который принимает любой класс, реализующий шаблон итератор , без фактического наследования от некоторого базового интерфейса «Iterator» или чего-то еще.
Это не прямой ответ, но, поскольку вы пришли с Java, я хотел бы указать на это. По сравнению с эквивалентами Java, STL действительно быстр.
Я нашел эту страницу , на которой показаны некоторые сравнения производительности. Обычно люди, занимающиеся Java, очень щепетильны, когда речь заходит о производительности, и утверждают, что все виды достижений происходят постоянно. Однако аналогичные достижения происходят и в компиляторах C / C ++.
Имейте в виду, что STL на самом деле довольно старый, поэтому другие, более новые библиотеки могут иметь определенные преимущества. Учитывая возраст, его популярность свидетельствует о том, насколько хорош был оригинальный дизайн.
Я бы сказал, что STL (по-прежнему) великолепен по четырем основным причинам:
Скорость STL использует шаблоны C ++, что означает, что компилятор генерирует код, специально предназначенный для ваше использование библиотеки. Например, map автоматически сгенерирует новый класс для реализации коллекции карт типа «ключ» к типу «значение». Отсутствуют накладные расходы времени выполнения, когда библиотека пытается решить, как эффективно хранить «ключ» и «значение» - это делается во время компиляции. Из-за элегантного дизайна некоторые операции с некоторыми типами будут компилироваться до отдельных инструкций сборки (например, итератор на основе целого числа приращения).
Эффективность Классы коллекций имеют понятие «распределителей», которые вы можете предоставить самостоятельно или использовать предоставленные библиотекой, которые выделяют только достаточно памяти для хранения ваших данных. Нет ни прокладки, ни потерь. Там, где встроенный тип может храниться более эффективно, существуют специализации для оптимальной обработки этих случаев, например вектор bool обрабатывается как битовое поле.
Расширяемость Вы можете использовать Контейнеры (классы коллекций), Алгоритмы и Функции, представленные в STL, для любого подходящего типа. Если ваш тип можно сравнить, вы можете положить его в контейнер.Если он попадает в контейнер, его можно сортировать, искать, сравнивать. Если вы предоставляете такую функцию, как 'bool Predicate (MyType)', ее можно фильтровать и т. Д.
Elegance В других библиотеках / фреймворках необходимо реализовать Sort () / Find () / Reverse () для каждого типа коллекции. STL реализует их как отдельные алгоритмы, которые принимают итераторы любой коллекции, которую вы используете , и оперируют этой коллекцией вслепую. Алгоритмам все равно, используете ли вы Vector, List, Deque, Stack, Bag, Map - они просто работают.
Прежде всего, вы можете использовать шаблоны для включения / выключения контейнеров, не прибегая к ужасающему беспорядку, который представляет собой интерфейсы Java.
Подход стандартной библиотеки C ++ к коллекциям с помощью итераторов в последнее время подвергся некоторой конструктивной критике. Андрей Александреску, известный эксперт по C ++, недавно начал работу над новой версией языка, называемого D, и описывает свой опыт разработки коллекций, поддерживающих его, в этой статье .
Лично меня расстраивает то, что такого рода отличная работа воплощается в еще одном языке программирования, который сильно пересекается с существующими языками, и я ему об этом сказал! :) Я бы хотел, чтобы кто-нибудь из его опытных специалистов обратился к созданию библиотеки коллекций для так называемых "современных языков", которые уже широко используются, Java и C #, которая имеет все возможности, которые, по его мнению, необходимы для мирового класса: понятие диапазона с прямой итерацией уже повсеместно, но как насчет обратной итерации, представленной эффективным образом? А как насчет изменяемых коллекций? А как насчет плавной интеграции всего этого с Linq? и т.д.
В любом случае, суть в следующем: не верьте никому, кто говорит вам, что стандартный способ C ++ - это Святой Грааль, лучший из возможных. Это всего лишь один из многих способов и имеет по крайней мере один очевидный недостаток: тот факт, что во всех стандартных алгоритмах коллекция определяется двумя отдельными итераторами (начало и конец) и, следовательно, неудобна для составления операций.
Очевидно, что C ++, C # и Java могут участвовать в любом количестве состязаний по ссоре, сколько вы захотите. Ключ к разгадке того, почему STL, по крайней мере, в некоторой степени хорош, заключается в том, что Java изначально проектировалась и реализовывалась без типобезопасных контейнеров. Затем Sun решила / поняла, что люди действительно нуждаются в них в типизированном языке, и добавила обобщения в 1.5.
Вы можете сравнить плюсы и минусы каждого из них, но вопрос о том, какой из трех языков имеет «лучшую» реализацию универсальных контейнеров, - это сплошной розыгрыш. Наибольшее для чего? По чьему мнению? В каждом из них есть лучшие библиотеки, которые удалось придумать создателям, с учетом других ограничений, налагаемых языками. Идея универсальных шаблонов C ++ не работает в Java, и стирание типов было бы нестандартным при типичном использовании C ++.
Если вы не видите, как используется STL, я рекомендую купить книгу Бьярна Страуструпа «Язык программирования C ++». Это в значительной степени объясняет все, что есть о C ++, потому что он чувак, который его создал.
STL прекрасно работает со встроенными типами. std :: array и есть массив из 5 int s, который занимает 20 байтов на 32-битной платформе.
java.util.Arrays.asList (1, 2, 3, 4, 5) , с другой стороны, возвращает ссылку на объект, содержащий ссылку на массив, содержащий ссылки на объекты Integer, содержащие int с. Да, это 3 уровня косвенного обращения, и я не осмеливаюсь предсказать, сколько байтов они потребляют;)
Что ж, это довольно смелое заявление ... возможно, в C ++ 0x, когда он наконец получает хеш-карту (в форме std: : unordered_map), он может сделать такое заявление, но в его нынешнем состоянии я на это не куплюсь.
Тем не менее, я могу рассказать вам кое-что интересное о нем, а именно то, что он использует шаблоны, а не наследование для достижения своего уровня гибкости и универсальности. У этого есть как преимущества, так и недостатки; Недостатком является то, что компилятор дублирует большой объем кода, и очень трудно добиться какой-либо динамической типизации во время выполнения; однако ключевым преимуществом является то, что это невероятно быстро. Поскольку каждая специализация шаблона на самом деле представляет собой отдельный класс, созданный компилятором, он может быть оптимизирован для этого класса. Кроме того, многие алгоритмы STL, работающие с контейнерами STL, имеют общие определения, но имеют специализации для особых случаев, что приводит к невероятно хорошей производительности.
Уникален, поскольку
- фокусируется на базовых алгоритмах, а не на предоставлении готовых решений для конкретных проблем приложений.
- использует уникальные возможности C ++ для реализации этих алгоритмов.
Что касается лучшего ... Есть причина, по которой тот же подход не использовался (и, вероятно, не будет) когда-либо применен ни в одном другом языке, включая прямых потомков, таких как D.
STL дает вам детали.
Языки и их среды создаются из более мелких компонентов, иногда с помощью конструкций языка программирования, иногда с помощью вырезания и вставки. Некоторые языки предоставляют вам запечатанную коробку - например, коллекции Java. Вы можете делать то, что они позволяют, но горе вам, если вы хотите сделать с ними что-то экзотическое.
STL дает вам элементы, которые дизайнеры использовали для создания более продвинутой функциональности. Непосредственное раскрытие итераторов, алгоритмов и т. Д. Дает вам абстрактный, но очень гибкий способ рекомбинации основных структур данных и манипуляций любым способом, подходящим для решения вашей проблемы. В то время как дизайн Java, вероятно, достигает отметки 90-95% для того, что вам нужно от структур данных, гибкость STL повышает его, возможно, до 99%, а абстракция итератора означает, что вы не полностью один на оставшийся 1%.
Если вы объедините это с его скоростью и другими расширяемыми и настраиваемыми функциями (распределителями, трейтами и т. Д.), Вы получите отличный пакет. Не знаю, можно ли назвать его лучшим пакетом структур данных, но, безусловно, очень хорошим.
Предупреждение: проценты полностью рассчитаны.