Я разработчик Java, пытающийся изучить С++. Я много раз читал в Интернете (включая Stack Overflow), что STL - это лучшая библиотека коллекций, которую вы можете получить на любом языке. (Извините, у меня нет ссылок для этого)
Однако после изучения некоторых STL, я действительно не понимаю, что делает STL таким особенным. Не могли бы вы пролить свет на то, что отличает STL от библиотек коллекций других языков и делает его лучшей библиотекой коллекции?
Что такого хорошего в STL?
STL отлично справляется с тем, что он был задуман очень рано и все же успешно использовал парадигму обобщенного программирования С++.
Он эффективно разделяет структуры данных: vector, map,... и алгоритмы для работы с ними copy, transform,... используя шаблоны для этого.
Он аккуратно развязал проблемы и предоставил общие контейнеры с настройками настроек (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).
Это также позволило бы избежать распространенных ошибок использования неверно определенных диапазонов итераторов и поведения undefined, который был бы результатом этого...
Это не так много, что это "великая" или "лучшая библиотека коллекций, которую вы можете получить на любом языке", но у нее есть другая философия для многих других языков.
В частности, стандартная библиотека С++ использует общую парадигму программирования, а не объектно-ориентированную парадигму, которая распространена в таких языках, как Java и С#. То есть у вас есть "общее" определение того, что должно быть iterator, а затем вы можете реализовать функцию for_each или sort или max_element, которая принимает любой класс, который реализует шаблон iterator, без на самом деле нужно наследовать от какого-то базового интерфейса "Итератор" или что-то еще.
Что мне нравится в STL, насколько он прочен. Его легко расширить. Некоторые жалуются, что он маленький, не хватает многих общих алгоритмов или итераторов. Но это именно то, когда вы видите, как легко добавлять недостающие компоненты, которые вам нужны. Мало того, но маленькое красиво: у вас есть около 60 алгоритмов, несколько контейнеров и несколько итераторов; но функциональность находится в порядке продукта из них. Интерфейсы контейнеров остаются небольшими и простыми.
Поскольку он умеет писать небольшие, простые, модульные алгоритмы, легче обнаружить ошибки и дыры в ваших компонентах. Тем не менее, в то же время, так же просто, как и алгоритмы и итераторы, они необычайно надежны: ваши алгоритмы будут работать со многими существующими и еще не написанными итераторами, а ваши итераторы работают со многими существующими и все-таки- написанные алгоритмы.
Мне также нравится, насколько проста STL. У вас есть контейнеры, у вас есть итераторы, и у вас есть алгоритмы. Что это (я лежу здесь, но это то, что нужно, чтобы устроиться с библиотекой). Вы можете смешивать разные алгоритмы с разными итераторами с разными контейнерами. Правда, некоторые из них имеют ограничения, которые запрещают им работать с другими, но в целом там много, с чем можно играть.
Никлаус Вирт сказал, что программа - это алгоритмы плюс структуры данных. Это то, о чем идет STL. Если Ruby и Python являются супергероями строк, то С++ и STL являются супергероями с алгоритмами и контейнерами.
Контейнеры STL хороши, но они не сильно отличаются от других языков программирования. Что делает контейнеры STL полезными, так это то, что они прекрасно сочетаются с алгоритмами. Гибкость, обеспечиваемая стандартными алгоритмами, не имеет себе равных в других языках программирования.
Без алгоритмов только контейнеры. Контейнеры. Ничего особенного в частности.
Теперь, если вы говорите о библиотеках контейнеров только для С++, маловероятно, что вы найдете библиотеки, также используемые и протестированные, как те, которые предоставляются STL, если ничего другого, поскольку они являются стандартными.
STL прекрасно работает со встроенными типами. A std::array<int, 5> - это именно то, что - массив из 5 int s, который потребляет 20 байт на 32-битной платформе.
java.util.Arrays.asList(1, 2, 3, 4, 5), с другой стороны, возвращает ссылку на объект, содержащий ссылку на массив, содержащий ссылки на объекты Integer, содержащие int s. Да, это 3 уровня косвенности, и я не посмею предсказать, сколько байтов потребляет;)
Это не прямой ответ, но, как вы поступаете с Java, я хотел бы указать на это. По сравнению с эквивалентами Java, STL быстро действительно.
Я нашел эту страницу, демонстрируя некоторые сравнения производительности. Как правило, люди Java очень трогательны, когда речь заходит о переговорах по производительности, и заявляют, что все виды достижений происходят все время. Однако аналогичные достижения также происходят в компиляторах C/С++.
Имейте в виду, что STL на самом деле довольно старый, поэтому другие, более новые библиотеки могут иметь определенные преимущества. Учитывая возраст, его популярность является свидетельством того, насколько хорош оригинальный дизайн.
Есть четыре основные причины, по которым я бы сказал, что STL (все еще) потрясающий:
Speed STL использует шаблоны С++, что означает, что компилятор генерирует код, специально предназначенный для вашего использования библиотеки. Например, карта автоматически генерирует новый класс для реализации коллекции карт типа "ключ" для типа "значение". Накладные расходы во время выполнения отсутствуют, когда библиотека пытается определить, как эффективно хранить "ключ" и "значение" - это делается во время компиляции. Благодаря элегантному дизайну некоторые операции над некоторыми типами будут скомпилированы до отдельных инструкций по сборке (например, итератор с добавлением целых чисел).
Эффективность В классах коллекций есть понятие "распределители", которые вы можете либо предоставить себе, либо использовать предоставленные библиотекой, которые выделяют достаточно хранилища для хранения ваших данных. Никаких отступов и потерь нет. Там, где встроенный тип может быть сохранен более эффективно, существуют специализации для оптимального управления этими случаями, например. вектор bool обрабатывается как бит.
Exensibility Вы можете использовать Контейнеры (классы коллекции), Алгоритмы и Функции, предоставляемые в STL для любого подходящего типа. Если ваш тип можно сравнить, вы можете поместить его в контейнер. Если он попадает в контейнер, его можно сортировать, искать, сравнивать. Если вы предоставляете функцию типа "bool Predicate (MyType)", ее можно фильтровать и т.д.
Elegance Другие библиотеки/рамки должны реализовывать методы Sort()/Find()/Reverse() для каждого типа коллекции. STL реализует их как отдельные алгоритмы, которые принимают итераторы любой коллекции, которую вы используете, и слепо следите за этой коллекцией. Алгоритмы не заботятся, используете ли вы Vector, List, Deque, Stack, Bag, Map - они просто работают.
Ну, это что-то вроде смелого заявления... возможно, в С++ 0x, когда он наконец получает хэш-карту (в виде std:: unordered_map), она может сделать это требование, но в его текущем состоянии, ну, я этого не покупаю.
Я могу сказать вам, хотя, некоторые интересные вещи об этом, а именно, что он использует шаблоны, а не наследование, чтобы достичь своего уровня гибкости и общности. Это имеет как преимущества, так и недостатки; недостатком является то, что много кода дублируется компилятором, и любой тип динамического набора времени выполнения очень трудно достичь; однако ключевым преимуществом является то, что он невероятно быстрый. Поскольку каждая специализированная специализация действительно представляет собой отдельный отдельный класс, сгенерированный компилятором, он может быть оптимизирован для этого класса. Кроме того, многие алгоритмы STL, которые работают на контейнерах STL, имеют общие определения, но имеют специальные специализации для особых случаев, которые приводят к невероятно хорошей производительности.
STL дает вам фрагменты.
Языки и их окружения построены из небольших компонентов, иногда через конструкции языка программирования, иногда с помощью вырезания и вставки. Некоторые языки предоставляют, например, закрытую коробку - сборники Java. Вы можете делать то, что они позволяют, но горе вам, если вы хотите сделать с ними что-то экзотическое.
STL дает вам те части, которые дизайнеры использовали для создания более совершенных функций. Непосредственное отображение итераторов, алгоритмов и т.д. Дает вам абстрактный, но чрезвычайно гибкий способ рекомбинирования структур данных ядра и манипуляций любым способом, который подходит для решения вашей проблемы. Хотя дизайн Java, вероятно, попадает на отметку 90-95% для того, что вам нужно от структур данных, гибкость STL повышает ее до 99%, а абстракция итератора означает, что вы не полностью используете свои ресурсы для оставшихся 1%.
Когда вы совмещаете это с его скоростью и другими возможностями расширяемости и customizabiltiy (распределители, черты и т.д.), у вас есть отличный пакет. Я не знаю, что я бы назвал его лучшим пакетом структур данных, но, безусловно, очень хорошим.
Предупреждение: проценты полностью составлены.
Уникальный, потому что он
Что касается лучшего... Существует причина, по которой тот же подход не был (и, вероятно, не будет) когда-либо сопровождаться каким-либо другим языком, включая прямых потомков, таких как D.
Стандартный подход библиотеки С++ к коллекциям с помощью итераторов в последнее время вызвал некоторую конструктивную критику. Андрей Александреску, известный эксперт на С++, недавно начал работу над новой версией языка D, а .
Лично я считаю, что разочарование в том, что эта прекрасная работа ставится в еще один язык программирования, который сильно перекрывает существующие языки, и я сказал ему об этом!:) Я бы хотел, чтобы кто-то из его специалистов переложил руку на создание библиотеки коллекций для так называемых "современных языков", которые уже широко используются, Java и С#, которые обладают всеми возможностями, которые, по его мнению, должны быть мирового класса: понятие диапазона с непрерывным повторением уже вездесуще, но как насчет обратного итерации эффективным образом? Что относительно изменчивых коллекций? Как насчет интегрирования всего этого с Linq? и др.
Во всяком случае, дело в том, что не верите никому, кто говорит вам, что стандартный способ С++ - это священный Грааль, и это было бы лучше всего. Это всего лишь один путь среди многих и имеет хотя бы один очевидный недостаток: тот факт, что во всех стандартных алгоритмах коллекция задается двумя отдельными итераторами (начало и конец) и, следовательно, неудобно создавать операции.
Очевидно, что С++, С# и Java могут вводить столько мошеннических конкурсов, сколько вы хотите. Ключ о том, почему STL, по крайней мере, несколько отличен, заключается в том, что Java изначально была разработана и реализована без контейнеров без типов. Затем Sun решила/поняла, что люди на самом деле нуждаются в них на типизированном языке и добавили дженерики в 1.5.
Вы можете сравнить плюсы и минусы каждого из них, но относительно того, какой из трех языков имеет "самую большую" реализацию общих контейнеров - это исключительно конкурс мошенников. Величайший для чего? По мнению? У каждого из них есть лучшие библиотеки, которые создатели смогли создать, с учетом других ограничений, налагаемых языками. С++ идея генериков не работает в Java, и стирание типа будет нестандартным при типичном использовании С++.
Самое главное, вы можете использовать шаблоны для использования с использованием контейнеров switch-in/switch-out, не прибегая к ужасающему беспорядку, который является интерфейсами Java.
Если вы не видите, какое использование имеет STL, я рекомендую купить книгу "Язык программирования С++" Бьярне Страуступа. Это в значительной степени объясняет все, что есть о С++, потому что он чувак, который его создал.