Каков STL?

Чтобы понять STL, вам нужно как минимум понять некоторые аспекты C ++. Я сделаю все возможное, чтобы объяснить это. Структура обманчиво проста. Где библиотека сияет в том, как ее использование может упростить многие сложные задачи. Я собираюсь остановиться на некоторых очень простых примерах, потому что что-то еще может запутать кого-то, кто не знает C ++, и потому, что я не хочу писать роман. ;)

Сначала немного истории. STL (библиотека стандартных шаблонов) была разработана отдельно, а затем передана на рассмотрение стандартному комитету C ++, что дает им возможность перенести ее на язык. Но он не был разработан как часть стандарта C ++, и по этой причине он разработан в стиле, который сильно отличается от остальной части стандартной библиотеки C ++. Если я помню свою древнюю историю, то стандартному комитету также потребовалось немало времени, чтобы понять STL и привыкнуть к нему. Когда они впервые увидели это, они не слишком заинтересовались этим, но через некоторое время поняли, насколько мощным и продуманным он был. Так было принято в язык. Все это произошло еще в конце 1990-х годов, когда язык приближался к стандартизации ISO.

По своей сути STL предоставляет наиболее фундаментальную функциональность, которую вы ожидаете от стандартной библиотеки: способность хранить последовательности данных и возможность обрабатывать эти последовательности.

Каждый другой язык имеет часть Коллекции / Контейнеры в своей стандартной библиотеке, содержащую реализации динамических массивов (известных как массивы в Java, Список в 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 в том, насколько она гибкая и расширяемая. каждая из трех опор STL может быть переопределена или расширена, поэтому можно сказать, что STL является скорее стратегией проектирования, чем чем-либо другим. Вы можете написать код STL, даже если вы используете свои собственные контейнеры, итераторы и алгоритмы. И поскольку каждый из этих трех столпов четко отделен от других, их можно поменять намного проще, чем в большинстве других языков, где эти три обязанности смешаны и разделены одними и теми же классами. каждая из трех опор 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 - элементы для сравнения, та же реализация функции сортировки будет работать. И поскольку мой больший объект перегружен operator (), этот синтаксис действителен как для этого объекта, так и для указателя функции, который мы передали ранее. STL-код получает множество функциональных возможностей бесплатно, используя подобные приемы. Одна и та же реализация функции работает с очень разными типами аргументов из-за способа работы шаблонов C ++.