Чтобы понять STL, вам нужно как минимум понять некоторые аспекты C ++. Я сделаю все возможное, чтобы объяснить это. Структура обманчиво проста. Где библиотека сияет в том, как ее использование может упростить многие сложные задачи. Я собираюсь придерживаться некоторых очень простых примеров, потому что что-то еще может запутать кого-то, кто не знает C ++, и потому, что я не хочу писать роман. ;)
Сначала немного истории. STL (библиотека стандартных шаблонов) была разработана отдельно, а затем передана на рассмотрение стандартному комитету C ++, что дает им возможность перенести ее на язык. Но он не был разработан как часть стандарта C ++, и по этой причине он разработан в стиле, который сильно отличается от остальной части стандартной библиотеки C ++. Если я помню свою древнюю историю, то стандартному комитету также потребовалось немало времени, чтобы понять STL и привыкнуть к нему. Когда они впервые увидели это, они не слишком заинтересовались этим, но через некоторое время поняли, насколько мощным и продуманным он был. Так было принято в язык. Все это произошло еще в конце 1990-х годов, когда язык приближался к стандартизации ISO.
По своей сути STL обеспечивает наиболее фундаментальную функциональность, которую вы ожидаете от стандартной библиотеки: способность хранить последовательности данных и возможность обрабатывать эти последовательности.
Каждый другой язык имеет часть коллекций / контейнеров в своей стандартной библиотеке, содержащую реализации динамических массивов (известных как массивы в Java, List в C # и векторы в C ++), связанных списков, словарей и других общих структур данных.
Они также обычно предоставляют некоторые механизмы для обхода этих структур. (Перечислители или итераторы, например)
STL предоставляет те же функциональные возможности в C ++, но делает это необычно элегантно и с некоторыми интересными абстракциями.
STL четко разделен на три отдельных компонента:
- Контейнеры (как описано выше, они есть у каждого языка. Массивы, ArrayList, Dictionary, Set, LinkedList и т. Д. Любая структура данных, которая может хранить коллекцию объектов, является контейнером в C ++)
- Алгоритмы (Каждый язык также имеет их в некотором виде. Алгоритмы - это функции для обработки последовательностей элементов.) Пока предположим, что последовательность является контейнером. Это немного упрощает, но мы вернемся к этому. Алгоритмы служат широкому кругу целей: от функции
for_each(), которая позволяет применять функцию к каждому элементу в последовательности, или связанной transform(), которая применяет функцию к каждому элементу и сохраняет результат в отдельной последовательности. (очень похоже на операцию отображения в функциональных языках) или накапливать (аналогично сворачиванию в функциональных языках), но также функции сортировки или поиска и функции, которые позволяют копировать целые последовательности.
- И, наконец, клей, который связывает контейнеры и алгоритмы: итераторы. Как я уже говорил выше, последовательности (над которыми работают алгоритмы) не совсем совпадают с контейнерами. Элементы в контейнере, безусловно, представляют собой последовательность, но первые пять элементов в контейнере также являются последовательностью. Или любой другой элемент в контейнере является последовательностью. Данные, считываемые непосредственно из файлового потока, также могут рассматриваться как последовательность. Даже данные, которые генерируются на лету (скажем, последовательность Фибоначчи), могут рассматриваться как последовательность значений. Последовательности не должны отображаться в контейнер или даже в данные, которые существуют в памяти, хотя это наиболее распространенное использование.
Обратите внимание, что эти три области не перекрываются. Контейнер хранит (и владеет) данными и производит итераторы. Итераторы позволяют вам проверять, изменять и просматривать данные. А алгоритмы работают на диапазонах итераторов
Концептуально говоря, итератор имеет две функции. Он указывает на некоторые данные, и его можно перемещать в последовательности (в зависимости от типа итератора могут быть доступны разные операции перемещения. Почти все итераторы могут переходить к следующему элементу. Некоторые могут также переходить к предыдущему, а некоторые могут прыгать на произвольные расстояния назад и вперед).
Если вы знакомы с C, это будет звучать очень похоже на указатели, и это не случайно. Итераторы моделируются как обобщение указателей, и фактически указатели также являются допустимыми итераторами. Все алгоритмы STL работают как с указателями, так и с «реальными» итераторами.
Это означает, что любая последовательность данных может быть представлена парой итераторов: первый итератор указывает на первый элемент в последовательности, а второй указывает один за конец последовательности .
Это позволяет использовать довольно простой синтаксис для обхода последовательностей в цикле:
std::vector<int> container;
for (iter it = container.begin(); it != container.end(); ++it)
{
// perform some operations on the iterator (it) or the element it points to (*it)
++(*it); // increment the value the iterator points to
}
Или мы можем применить алгоритм к последовательности:
std::sort(container.begin(), container.end());
Обратите внимание, что функция сортировки не знает и не заботится о том, что она работает с вектором. Передается два итератора, и они могут быть любого типа. Это могут быть простые указатели на массив, итераторы связанного списка или любой другой допустимый тип итератора.
Мы можем немного обобщить функцию сортировки, предоставив нашу собственную функцию сравнения (любая функция, которая принимает два значения и возвращает true, если первое строго меньше другого)
// sort in descending order, by passing in a custom comparer which uses greater than instead of less than
bool greater(int lhs, int rhs) { return lhs > rhs; }
std::sort(container.begin(), container.end(), greater);
Конечно, мы могли бы также отсортировать только первые пять элементов вектора:
std::sort(container.begin(), container.begin()+5);
Функции begin () и end () - это просто вспомогательные функции для получения итераторов из контейнера. Нам не нужно использовать их напрямую.
Еще один приятный трюк в том, что потоки тоже можно обобщать в итераторы. Итак, давайте прочитаем все целые числа из файла и скопируем их в массив (массивы, конечно, простые C-типы, поэтому они не являются правильными контейнерами и не имеют итераторов. Но указатели работают нормально)
int arr[1024];
std::ifstream file("something.txt");
// (note, this assumes <= 1024 integers are read)
std::copy(std::istream_iterator<int>(file) // create an iterator pointing to the current position in the file stream
, std::istream_iterator<int>() // and our "end" iterator. When we reach the end of the stream, testing the two iterators for equality will yield true, and so the operation will halt
, arr);
Уникальная особенность STL в том, насколько он гибок и расширяем. Он полностью взаимодействует с кодом C (указатели являются легальными итераторами), его можно просто и легко расширять (вы можете писать собственные типы итераторов, если хотите. Большинство алгоритмов принимают пользовательские предикаты сравнения, как тот, который я показал выше, и вы можете определить свои собственные контейнеры, то есть каждый из трех столпов STL может быть переопределен или расширен, поэтому можно сказать, что STL является скорее стратегией проектирования, чем чем-либо еще. Вы можете написать код STL, даже если вы используете ваши собственные контейнеры, итераторы и алгоритмы. И поскольку каждый из этих трех столпов четко отделен от других, их можно заменить гораздо проще, чем в большинстве других языков, где эти три обязанности смешаны и разделены одними и теми же классами.
Алгоритм не знает , в котором, если таковые имеются, контейнер, в котором хранится последовательность, в которой он работает. Он знает только то, что переданные итераторы могут быть разыменованы для получения доступа к самим данным.
Контейнер не должен поддерживать все стандартные алгоритмы. Он просто должен иметь возможность создавать пару итераторов, и тогда все функции предоставляются бесплатно.
Сравните это, скажем, с Java, где каждый класс коллекции должен реализовывать свой собственный поиск, свой собственный вид, свое собственное все. В C ++ нам нужна только одна реализация find (). Требуется два итератора и значение для поиска, и он проходит последовательность поиска значения. И так, он работает с любым типом контейнера, даже с теми, которые я определяю сам.
Еще одна замечательная особенность STL - практически нулевая потеря производительности при его использовании. Все шаблоны C ++ подставляются во время компиляции, в результате чего получается код, который можно оптимизировать так же агрессивно, как если бы вы все вручную кодировали в C. Приведенная выше функция сортировки потеряла бы некоторую производительность, потому что я передаю ей указатель функции в качестве моего пользовательского компаратора. , который обычно не может быть встроенным, но может быть исправлен, если мы определим его так:
struct greater {
bool operator()(int lhs, int rhs) { return lhs > rhs; }
};
std::sort(container.begin(), container.end(), greater());
Теперь мы больше не передаем указатель функции, а объект. И функции-члены (такие как operator ()) могут быть встроенными. Так что эта функция сортировки будет столь же эффективной, как и все, что вы могли бы написать вручную на языке C.
И снова, даже не нужно добавлять никакой сложности к функции сортировки. На самом деле сортировка имеет две перегрузки. Тот, который принимает функцию сравнения, а другой - нет.
Функция сортировки не должна знать, передан ли ей указатель на функцию или объект. Пока синтаксис «X (a, b)» действителен, где X - это значение, которое было передано в качестве компаратора, и a, b элементы для сравнения, будет работать та же реализация функции сортировки. И поскольку мой greater объект перегружен operator (), этот синтаксис действителен как для этого объекта, так и для указателя функции, который мы передали ранее.
STL-код получает множество функциональных возможностей бесплатно, используя подобные трюки. Одна и та же реализация функции работает с очень разными типами аргументов из-за способа работы шаблонов C ++.