Программисты :- Что это за библиотека STL?
STL :- Попробуйте узнать обо мне, я знаю, что вы меня полюбите 😚.
PS: Я не собираюсь ничего усложнять, я напишу только то, что необходимо для использования, а не буду пугать вас супер гиковскими вещами.
Итак, как следует из названия, Standard Template Library — это простая библиотека шаблонов некоторых действительно крутых и полезных вещей, она дает вам возможность реализовать вещи без реализации метаданных 💥.
Это как лапша, в которую нужно только добавить кипяток и все готово.
Что же это за вещи, которые делают его таким полезным и крутым. Давайте разберемся.
Итак, STL состоит из четырех компонентов, которые придают ему такую мощь.
-
Контейнеры
(Это ящики для хранения наших данных). -
Алгоритмы
(Это готовые методы и функции, такие как sort(), search().
которые действуют на контейнеры. Да, вам не нужно писать всю логику
сортировки или любого другого метода, если вы используете эту библиотеку.
она дает вам готовый шаблон, помните) -
Функция
-
Итераторы
(Они используются для последовательной итерации данных)
Не впадайте в панику ❗
Здесь мы изучим все очень просто, что определенно поможет вам начать самостоятельно.
Контейнеры
Контейнеры — это не что иное, как коробка, в которой хранятся ваши данные. В STL есть 4 типа коробок или контейнеров. У этих контейнеров есть свои разновидности. Давайте проверим эти коробки и их разновидности!
->1 . Последовательные контейнеры
(Довольно простое объяснение, они хранят данные в последовательном порядке, вы знаете это поведение из массивов)
-> Векторы
-> Список
-> Декеши
-> Массивы
-> Forward List
->2. Адаптеры контейнеров
(Они похожи на последовательные контейнеры, отличается только интерфейс)
-> Очередь
-> Очередь приоритетов
-> Стеки
->3. Ассоциативный контейнер
(Отлично работает, когда у вас есть отсортированные данные, дает o(nlogn) сложность)
-> Карта
-> Multimap
-> Наборы
-> Мультинаборы
->4. Неупорядоченный ассоциативный контейнер
(Аналогично ассоциативным контейнерам, но мы используем его, когда у нас есть несортированные данные)
-> Неупорядоченная карта
-> Неупорядоченная мультикарточка
-> Неупорядоченные множества
-> Неупорядоченные мультимножества
Да, вот и все, я знаю, вы, наверное, думаете, что это такое 😕 но,
доверьтесь процессу, мои дорогие программисты 💖.
Теперь давайте узнаем их поближе
🎃 Последовательные контейнеры
Векторы
Это смежные контейнеры, которые обрабатывают данные динамически. Они изменяют свои размеры при выполнении любых операций, таких как удаление, вставка или что-то еще. Вам не нужно заранее определять размер, как это делается в массивах.
Функции из компонента Algorithms, которые мы можем использовать для работы с векторами, следующие
begin() — возвращает итератор, указывающий на первый элемент в векторе
end() — возвращает итератор, указывающий на теоретический элемент, следующий за последним элементом вектора.
sort(arr.begin(), arr.end()) — сортирует массив
и т.д;
Существует множество функций, которые вы можете использовать в соответствии с вашими потребностями.
Инициализировать вектор можно следующим образом.
vector<int> vector_name;
vector <pair,<int,int>> vector_name;
Списки
Это последовательные компоненты для несвязных данных. Они позволяют нам вставлять и выталкивать данные сзади и спереди. Хранят только одни данные в блоке. Очень похож на двусвязный список. Список хранит информацию о следующем и предыдущем элементах.
list<int> list_name;
Погуглите о его методах.
Deques
Это очереди с двойным окончанием. Они допускают противоречие и расширение с обоих концов.
Теперь вы, наверное, думаете, что это то же самое, что и список, верно?
Так вот, ответ — нет, потому что список хранит только одни данные в одном блоке памяти, а deques хранит несколько элементов в одном блоке памяти.
deque<int> deque_name;
Я предполагаю, что вы уже знаете о массивах, поэтому я пропускаю это.
Передовые списки
Это также последовательные компоненты для несмежных данных. В них хранятся только одни данные в блоке. Очень похожи на односвязный список. Прямой список отслеживает местоположение только следующего элемента, а не предыдущего.
forward_list<int> forwardList_name;
🎃 Контейнеры Адаптеры
Стеки
Это довольно удивительно, это похоже на то, когда вы кладете вещи друг на друга. Например, колода карт, лежащая на столе, или стопка тарелок на кухне. Если вы хотите взять вторую тарелку снизу, вам нужно убрать другие тарелки, которые лежат сверху нужной вам тарелки.
Так проявляется поведение LIFO — Last in, First Out.
Это не позволит вам получить доступ к элементу напрямую, вам нужно получить доступ к верхним элементам, что означает только последовательный переход.
Некоторые классные операции — pop(), push().
stack<int> stack_name;
Очередь
Очередь, в которой вы стоите, когда вы хотите заказать билеты на фильм Marvel 🎥 или когда вы стоите в очереди в любимом ресторане. Это и есть очередь. Элементы вставляются сзади (в конце) и удаляются спереди.
«Кто первым заходит, тот первым выходит» — FIFO — First in, First Out (первый вошел, первый вышел).
queue<int> queue_name;
Очереди с приоритетом
Использует свойства стеков и очередей и хранит данные в отсортированном не возрастающем порядке. Приоритет отдается наибольшему элементу. Поэтому, если вы вставите 20,6,99,77,0 в эту очередь, она будет хранить ее как 99,77,20,6,0.
priority_queue<int>priorityQueue_name
//default, stores data in descending order - max heap
priority_queue <int, vector<int>, greater<int>> g = gq;
//greater<int> is comparator here, for ascending order -min heap
_Ах!!! Обожаю эти ассоциативные и неупорядоченные ассоциативные контейнеры 💗 _
🎃 Ассоциативные контейнеры
Временная сложность каждого ассоциативного контейнера равна O(nlogn)
Карта
Таким образом, Map больше похожа на объект в CPP. Да, давайте почитаем вместе со мной.
Map хранит отсортированные данные в виде пары ключ-значение, как и объекты. Сортировка происходит путем сравнения ключей.
Она никогда не позволяет хранить дубликаты данных. Все данные в карте идентичны друг другу.
map<int,int> map_name;
map<pair<int,int>,int>map_name;
Multimap
Эта карта похожа на карту, но ее отличие от карты заключается в следующем,
Multimap может хранить дубликаты значений.
Set
Хранит данные подобно массивам, но его отличительной особенностью является то, что он хранит данные в отсортированном виде и в нем нельзя хранить дубликаты элементов.
set<int>set_name;
Multiset
Этот набор похож на Set, но единственное, что отличает его от Set, это то, что,
Multiset может хранить дубликаты значений.
🎃 Неупорядоченные ассоциативные контейнеры
Неупорядоченная карта
Это то же самое, что и map, она хранит уникальные данные в паре ключ-значение, но, как следует из названия, неупорядоченная, она не хранит данные в отсортированном виде.
unordered_map<int,int> unorderedMap_name;
unordered_map<pair<int,int>,int>unorderedMap_name;
Неупорядоченная мультикарта
Это то же самое, что и Multimap, она хранит данные в паре ключ-значение, но, как следует из названия, неупорядоченная, она не хранит данные в отсортированном виде, а также позволяет хранить дубликаты элементов.
Неупорядоченное множество
Хранит уникальные элементы данных, но, как следует из названия, неупорядоченное множество не хранит данные в отсортированном виде. В нем используется хэширование (о хэшировании я расскажу в другой статье), временная сложность этого метода составляет O(1).
unordered_set<int> unorderedSet_name;
Неупорядоченный мультисет
Это то же самое, что и Multiset, но, как следует из названия, неупорядоченный, он не хранит данные в отсортированном виде, а также позволяет хранить дубликаты элементов.
Вот и все.
Этой информации достаточно для начала, об алгоритмах STL вы можете прочитать в моем следующем посте.