Стандартная библиотека шаблонов C ++ (STL) - Введение

В этом уроке вы узнаете о том, что такое STL в C ++, что он предоставляет, и обзор всех элементов STL.

STL означает стандартную библиотеку шаблонов . STL является наиболее созданными библиотеками среди всех других библиотек в C ++. Это сердце C ++. Включает в себя контейнеры, алгоритмы и итераторы.

Стандартная библиотека шаблонов C ++ (STL)

Что обеспечивает STL?

Стандартная библиотека шаблонов предоставляет алгоритмы и контейнеры . Контейнеры содержат данные, а алгоритмы оперируют данными, находящимися в контейнерах.

Целью объектно-ориентированного языка является объединение алгоритма и данных в класс, который называется объектом. STL идет противоположным путем языка ООП. Он разделяет алгоритмы и структуры данных. Целью этого является повторное использование кода. Мы хотим, чтобы один алгоритм применялся к разным контейнерам. И мы хотим, чтобы один контейнер использовал разные алгоритмы. Контейнеры имеют разные интерфейсы друг от друга. Поэтому, если мы хотим применить один алгоритм к разным контейнерам, нам нужно предоставить разные реализации для этого. Поэтому, если у нас есть N алгоритмов и M контейнеров, нам нужно предоставить N * M реализаций. Это довольно много работы и не масштабируется также.

Для решения этой проблемы библиотека STL предоставляет еще одну группу модулей под названием Iterators, Каждый контейнер должен предоставлять общий интерфейс, определенный итераторами. Итератор может перебирать каждый элемент внутри контейнера. Таким образом, алгоритм вместо работы непосредственно с контейнерами работает только на итераторах. Таким образом, алгоритм не знает, над каким контейнером он работает. Он знает только об итераторе. Это будет очень полезно для повторного использования кода вместо написания N * M реализаций (вышеупомянутый пример). Теперь нам нужно только обеспечить N + M реализаций. Это очень много применений. Если мы определим новый алгоритм, который работает на итераторе, то все существующие контейнеры могут использовать этот алгоритм. Точно так же, если мы определим новый контейнер, который обеспечивает соответствующий интерфейс итерации, тогда все существующие алгоритмы могут быть применены к этому новому контейнеру. Так что эта библиотека ST очень полезна.

Источник изображения

Контейнеры

Контейнеры последовательности

Они реализованы с массивами и связанными списками.

• Вектор : вектор - это динамический массив, растущий в одном направлении; это в конце вектора.
• Deque : Deque похож на вектор. Но deque может расти как в начале, так и в конце в обоих направлениях.
• Список : это то же самое, что и двойной связанный список. Каждый элемент в списке указывает на предыдущий и следующий элемент этого элемента.
• Прямой список : прямой список содержит только прямой указатель. Таким образом, он может проходить от начала до конца, но не от конца до начала.
• Массив : существуют ограничения для контейнерного массива. Это размер не может быть изменен.

Ассоциативные Контейнеры

Обычно они реализуются двоичными деревьями . Ключевым атрибутом ассоциативных контейнеров является то, что все элементы всегда сортируются.

• Set : Set не имеет дубликатов. Когда мы вставляем элементы в набор, все элементы автоматически сортируются. Требуется O (log (n)) время.
• Мультисеть : это так же, как набор. Но единственная разница в том, что он позволяет дубликаты также.
• Карта : иногда мы не хотим сортировать элементы по значениям. Нам интересно отсортировать их по значению ключа. Карта и Multimap содержат структуру пары ключ-значение. Карта не позволяет дублировать ключи.
• Multimap : это как карта. Но единственное отличие состоит в том, что он позволяет дублировать ключи. Важным примечанием является то, что ключи не могут быть изменены в карте и мультикарте.

Слово ассоциативный означает, связывая ключ со значением. Мы можем сказать, что set и multiset - это особый вид или map или multimap, где ключ элемента одинаков. Это причина, которую они назвали ассоциативной.

Неупорядоченные контейнеры

Неупорядоченные контейнеры внутренне реализованы с помощью хеш-таблицы. Каждый элемент, рассчитанный с помощью хэш-функции, отображается на хеш-таблицу. Основным преимуществом является то, что если у нас есть эффективная хеш-функция, мы можем найти элементы за O (1) времени.

Это самый быстрый среди всех контейнеров.

В неупорядоченных контейнерах порядок не определен. И они могут меняться со временем.

• Неупорядоченный набор : неупорядоченный набор, который не допускает дублирование.
• Unordered Multiset : неупорядоченный набор, который позволяет дублировать элементы.
• Неупорядоченная карта : это неупорядоченное множество Парижа.
• Неупорядоченная мультикарта : неупорядоченная карта, допускающая дублирование ключей.

Контейнерные адаптеры

Наряду с контейнерами, адаптеры контейнеров также предоставляются библиотекой ST.

Контейнерные адаптеры - это не полные контейнерные классы, а классы, которые предоставляют специальный интерфейс, опирающийся на объект одного из контейнерных классов (например, deque или list) для обработки элементов. Базовый контейнер инкапсулирован таким образом, что к его элементам обращаются члены адаптера контейнера независимо от используемого базового класса контейнера.

• Стек : Стек обеспечивает операции push, pop, top для работы с ним.
• Очередь : Push, Pop, Front, Back разрешены операции над этим.
• Очередь приоритетов : это ключи предметов разного приоритета. Первый пункт всегда имеет наивысший приоритет. 

итераторы

Существует пять категорий итераторов, основанных на типах операций над ними.

1. Итератор произвольного доступа

В итераторе с произвольным доступом мы можем получить доступ к элементам в контейнере случайным образом. Здесь мы можем увеличивать, уменьшать, складывать, вычитать, а также сравнивать. Мы можем выполнить все эти операции.

Пример: Vector, deque, Array предоставляет итератор произвольного доступа.

2. Двунаправленный итератор

С помощью двунаправленного итератора мы можем увеличивать и уменьшать, но мы не можем добавлять, вычитать или сравнивать.

Пример: list, set / multiset, map / multimap предоставляют двунаправленные итераторы.

3. Вперед итератор

Прямой итератор может быть только увеличен, но не может быть уменьшен.

Пример: forword_list

Оставшиеся «неупорядоченные контейнеры» они предоставляют как минимум «прямые итераторы». А также шанс на рост «двунаправленных итераторов». Это зависит от реализации STL.

4. Входной Итератор

Входной итератор используется для чтения и обработки значений во время итерации вперед. Мы можем только читать, но не писать.

5. Выходной Итератор

Используется для вывода значений. Мы можем писать, но не читать. И входной итератор и выходной итератор могут двигаться только вперед. Они не могут двигаться назад.

Итератор Адаптер (Предопределенный Итератор)

Это специальный, более мощный итератор.

• Вставить итератор
• Потоковый итератор
• Обратный итератор
• Переместить итератор

Алгоритмы

Алгоритмы в основном циклы. Алгоритмы всегда обрабатывают диапазоны полуоткрытым способом. Это означает, что он будет включать первый элемент, но не будет включать последний элемент.

Немодифицирующие алгоритмы

• Count: функция Count подсчитывает количество элементов в некотором диапазоне данных.
• Min и max: элементы Max возвращают первое максимальное число, min возвращает минимальное число.
• Линейный поиск: если данные не отсортированы, выполняется поиск элемента и возвращается первое совпадение.
• Двоичный поиск: при сортировке данных выполняется поиск элемента и возвращается первое совпадение
• Сравнение диапазонов: используется для сравнения двух векторов / списка… .etc
• Атрибуты проверки: в этом порядке сортируются различные атрибуты проверки, удовлетворяется ли любое из этих условий или нет, и т. Д. ... Мы изучим все это в следующих модулях.

Алгоритмы модификации (Алгоритмы изменения значения)

• Копировать: копирует все из одного контейнера в другой.
• Переместить: перемещает предметы из одного места в другое.
• Преобразование: преобразовывает данные с определенной операцией. А затем сохраните результаты в другом месте.
• Обмен: обмен данными между двумя местами. Это также называется двусторонним копированием.
• Заполнить: Заполнение используется для заполнения данных определенными значениями.
• Заменить: заменить существующее значение в контейнере другим значением.
• Удалить: Удалить может удалить любой элемент в зависимости от условия.

Алгоритмы изменения порядка

Они изменяют порядок элементов в контейнере, но не обязательно сами элементы.

• Реверс: полностью изменить данные.
• Повернуть: вращает данные от начала вектора до конца вектора.
• Перестановка: следующая перестановка приводит к лексикографически следующей большей перестановке. Предыдущая перестановка результатов лексикографически следующая небольшая перестановка.
• Перемешать: случайным образом переставить элементы. Поменяйте местами каждый элемент со случайно выбранным элементом.

Алгоритмы сортировки

Алгоритмы сортировки являются широко используемыми алгоритмами в программировании.

Алгоритмы сортировки требуют итераторов произвольного доступа. Таким образом, эта опция ограничивает наши параметры контейнерами вектор, deque, контейнерный массив, собственный массив. Список и неупорядоченные контейнеры не могут быть отсортированы. И ассоциативный контейнер в любом случае не нуждается в сортировке.

Функция Sort () напрямую сортирует по умолчанию. Некоторые другие случаи также в этом. Мы изучим это в следующих уроках.

Частичная сортировка: иногда нам не нужно сортировать все элементы. В этом случае мы используем эту частичную сортировку, например, верхние 5 элементов или как минимум 10 таких элементов.

Алгоритмы кучи

Куча имеет два свойства: первый элемент всегда больше, а добавление / удаление занимает время O (log (n)).

Алгоритмы кучи часто используются для реализации приоритетной очереди. Это четыре важных алгоритма кучи.

• Make_heap: создает новую кучу для данного контейнера.
• Pop_heap: он удаляет самый большой элемент из кучи, для этого он делает две вещи, меняет местами первый и последний элементы кучи и затем выполняет кучи для удовлетворения условий кучи.
• Push_heap: добавить новый элемент в кучу.
• Sort_heap: сортировка кучи по заданной куче.

Алгоритмы сортированных данных

 Это алгоритмы, которые требуют предварительной сортировки данных.

• Бинарный поиск: проверяет данные в диапазоне данных. В результате возвращается логическое значение.
• Слияние: Операция слияния делает два диапазона отсортированных данных в один диапазон больших отсортированных данных.
• Операции над множествами: объединение множеств, пересечение множеств, разность множеств, симметричная разность - все это операции над множествами.

Численные алгоритмы

Числовые алгоритмы определены в числовом заголовке, а не в заголовке алгоритма.

• Накопить: накапливает данные в заданном диапазоне о данной операции.
• Внутренний продукт: для расчета внутреннего продукта двух диапазонов данных.
• Частичная сумма: Частичная сумма вычисляет частичную сумму заданного диапазона данных и сохраняет в другом месте.
• Смежное различие: вычисляет разницу между соседними предметами и магазинами в другом месте.

Причины использования стандартной библиотеки шаблонов C ++ (STL)

• Повторное использование кода. Вместо реализации большого количества кода мы просто используем его повторно.
• Эффективность (быстро и использовать меньше ресурсов). По этой причине современный компилятор C ++ обычно настроен на оптимизацию под стандартную библиотеку C ++.
• Точная, менее глючная.
• Краткий, читаемый код; уменьшенный поток управления.
• Стандартизация, гарантированная доступность.
• Ролевая модель написания библиотеки.
• Хорошее знание структур данных и алгоритмов.

Прокомментируйте ниже, если у вас есть вопросы или вы нашли какую-либо информацию неверной в приведенном выше руководстве для стандартной библиотеки шаблонов на C ++.