Важные функции компонентов STL в C ++

Опубликовано: 5 Января, 2022

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

Наиболее часто используемые структуры данных:

  1. Вектор
  2. Куча
  3. Очередь
  4. Приоритетная очередь
  5. Установленный
  6. Список
  7. Заказанные карты
  8. Неупорядоченные карты

Контейнеры или классы контейнеров хранят объекты и данные. Всего существует семь стандартных классов контейнеров «первого класса» и три класса адаптеров контейнера и только семь файлов заголовков, которые обеспечивают доступ к этим контейнерам или адаптерам контейнера.

Примечание. Мы можем включить только одну библиотеку, то есть #include <bits / stdc ++. H>, которая включает все библиотеки STL, но в некоторых соревнованиях включение этой библиотеки может замедлить код. Чтобы решить эту проблему, мы можем добавить определенные библиотеки для доступа к определенным структурам данных STL . Также при удалении элементов необходимо следить за тем, пуста ли структура данных или нет. Вызов функции удаления для пустой структуры данных приводит к ошибке. Ниже приведены некоторые структуры данных с их иллюстрациями.

  1. Вектор : основная проблема при использовании массивов заключалась в том, что нам приходилось указывать размер. Этот недостаток преодолели векторы. Векторы внутри работают как динамически выделяемые массивы, что является основной причиной того, как мы можем добавлять элементы без указания размера вектора. Когда размер вектора становится равным емкости, емкость вектора увеличивается, и, таким образом, мы можем добавлять дополнительные элементы.

Заголовочный файл:

#include <vector>

Синтаксис:

vector<data type> variable_name;

Наиболее распространенная функция для вектора:

  1. push_back (): используется для вставки элемента в конец вектора. Для более быстрого метода используйте emplace_back ().
  2. pop_back (): используется для удаления последнего элемента из вектора.
  3. size (): возвращает размер вектора.
  4. clear (): удаляет все содержимое вектора.
  5. erase (): удаляет указанный индекс или данные.
  6. empty (): возвращает логическое значение True, если вектор пуст, иначе возвращает False.
  7. Итератор lower_bound (Iterator first, Iterator last, const val): lower_bound возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который имеет значение не меньше, чем 'val'.
  8. Итератор upper_bound (Iterator first, Iterator last, const val): upper_bound возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который имеет значение больше 'val'.

C ++

// C++ program to illustrate the
// function of vector in C++
#include <iostream>
// Header file for vector if
// <bits/stdc++.h> not included
#include <vector>
using namespace std;
// Function to print the vector
void print(vector< int > vec)
{
// vec.size() gives the size
// of the vector
for ( int i = 0; i < vec.size(); i++) {
cout << vec[i] << " " ;
}
cout << endl;
}
// Driver Code
int main()
{
// Defining a vector
vector< int > vec;
// Put all natural numbers
// from 1 to 10 in vector
for ( int i = 1; i <= 10; i++) {
vec.push_back(i);
}
cout << "Initial vector: " ;
// print the vector
print(vec);
// Size of vector
cout << "Vector size: " << vec.size() << " " ;
// Check of vector is empty
if (vec.empty() == false )
cout << "Is vector is"
<< " empty: False " ;
// Popping out 10 form the vector
vec.pop_back();
cout << "Vector after popping: " ;
print(vec);
// Deleting the first element
// from the vector using erase()
vec.erase(vec.begin());
cout << "Vector after erase"
<< " first element: " ;
print(vec);
// Clear the vector
vec.clear();
cout << "Vector after "
<< "clearing: None " ;
print(vec);
// Check if vector is empty
if (vec.empty() == true )
cout << "Is vector is"
<< " empty: True " ;
}
Выход
 Начальный вектор: 1 2 3 4 5 6 7 8 9 10 
Размер вектора: 10
Вектор пуст: Ложь
Вектор после появления: 1 2 3 4 5 6 7 8 9 
Вектор после стирания первого элемента: 2 3 4 5 6 7 8 9 
Вектор после расчистки: нет 
Вектор пуст: True

2. Стек : это структура данных «последний пришел - первый ушел» (LIFO). Его можно реализовать с помощью массивов, связанных списков и векторов. Некоторые проблемы, такие как реверсирование элемента или строки, проверка скобок, печать следующего большего элемента, постфиксного выражения и т. Д., Могут быть выполнены с использованием класса стека, вместо того, чтобы делать все функции, которые мы можем использовать его встроенными функциями.
Заголовочный файл:

#include <stack>

Синтаксис:

stack<data_type> variable_name;

Наиболее распространенная функция для стека:

  1. push (): используется для перемещения элемента наверх стека.
  2. pop (): удаляет верхний элемент стека, но не возвращает его.
  3. top (): возвращает верхний элемент стека.
  4. empty (): возвращает логическое значение, т. е. True, если стек пуст, иначе возвращает false.
  5. size (): возвращает размер стека.

C ++

// C++ program to illustrate the
// function of stack in C++
#include <iostream>
// Header file for stack
#include <stack>
using namespace std;
// Function to print the stack
void print(stack< char > s)
{
// Loops runs till stack
// becomes empty
while (s.empty() == false ) {
// Prints the top element
cout << s.top() << " " ;
// Now pops the same top element
s.pop();
}
cout << " " ;
}
// Driver Code
int main()
{
// Given char array
char array[]
= { 'G' , 'E' , 'E' , 'K' ,
'S' , 'F' , 'O' , 'R' , 'G' ,
'E' , 'E' , 'K' , 'S' };
// Defining stack
stack< char > s;
// Check if stack is empty
if (s.empty() == true ) {
cout << "Stack is currently Empty"
<< " " ;
}
else {
cout << "Stack is not empty"
<< " " ;
}
// Push elements in stack
for ( int i = sizeof (array) / sizeof (array[0]) - 1;
i >= 0; i--) {
s.push(array[i]);
}
// Size of stack
cout << "Size of stack: "
<< s.size() << " " ;
// Content of stack
cout << "Stack initially: " ;
print(s);
// Returning the top
// element of the stack
cout << "Top element: "
<< s.top() << " " ;
// Popping the top
// element in stack
s.pop();
cout << "Stack after 1"
<< "pop operation: " ;
print(s);
// Now checking the top element
cout << "Top element after popping: "
<< s.top() << " " ;
// Size of stack
cout << "Size of stack"
<< "after popping: "
<< s.size() << " " ;
// Again checking if the
// stack is empty
if (s.empty() == true ) {
cout << "Stack is currently Empty"
<< " " ;
}
else {
cout << "Stack is not empty"
<< " " ;
}
return 0;
}
Выход
 Стек в настоящее время пуст
Размер стопки: 13
Исходный стек: GEEKSFORGEEKS 
Верхний элемент: G
Стек после операции 1pop: EEKSFORGEEKS 
Верхний элемент после всплывающего окна: E
Размер стопки после выталкивания: 12
Стек не пуст

3. Очередь: это структура данных «первым пришел - первым обслужен» (FIFO). Причина, по которой мы требуем, чтобы очереди использовали много практического применения принципа «первым пришел - первым обслужен», и когда данные не нужно обрабатывать на ранней стадии. Например, в очереди на покупку билетов на спектакль тот, кто первым встает в очередь, получает билет первым. Он может быть реализован с использованием массивов, связанных списков и векторов, как и стеки. Некоторые приложения очереди включают обход порядка уровней в деревьях и графах, при совместном использовании ресурсов и т. Д.
Заголовочный файл:

#include <queue>

Синтаксис:

queue<Data Type> variable_name;

Наиболее распространенная функция fo Queue:

  1. push (): используется для перемещения элемента в конец очереди
  2. pop (): удаляет передний элемент очереди, но не возвращает его.
  3. front (): возвращает передний элемент очереди или элемент, который стоит первым в строке.
  4. empty (): возвращает логическое значение, то есть True, если очередь пуста, иначе возвращает false
  5. back (): возвращает последний элемент очереди.
  6. size (): возвращает размер очереди.

C ++

// C++ program to illustrate the
// function of vector in C++
#include <iostream>
// Header file for queue
#include <queue>
using namespace std;
// Function to print the queue
void print(queue< char > q)
{
for ( int i = 0; i < q.size(); i++) {
// Printing the front element
cout << q.front() << " " ;
// Popping the front element
q.pop();
}
cout << " " ;
}
// Driver Code
int main()
{
// Given array
char array[]
= { 'G' , 'E' , 'E' , 'K' , 'S' };
// Defining queue
queue< char > q;
if (q.empty() == true ) {
cout << "Queue is empty " ;
}
for ( int i = 0; i < 5; i++) {
q.push(array[i]);
}
cout << "Queue Initally: " ;
print(q);
// Front element
cout << "Front element: "
<< q.front() << " " ;
// Back element
cout << "Back Element: "
<< q.back() << " " ;
// Size of queue
cout << "Size of queue: "
<< q.size() << " " ;
// Empty
if (q.empty() == false ) {
cout << "Queue is not empty " ;
}
return 0;
}
Выход
 Очередь пуста
Очередь изначально: GEE 
Передний элемент: G
Задний элемент: S
Размер очереди: 5
Очередь не пуста

4.Приоритетная очередь : эта структура данных аналогична очередям, но порядок выхода определяется приоритетом, установленным пользователем. Основные функции включают получение элемента с наивысшим приоритетом, вставку, удаление элемента с наивысшим приоритетом или уменьшение приоритета. Структура данных Используются кучи, а не BST, как в BST, создание деревьев обходится дороже, чем кучи, а сложность куч лучше. Кроме того, кучи предоставляют свойство полного двоичного дерева и порядка кучи, удовлетворяющее всем свойствам очереди приоритетов. Очередь приоритетов имеет 2 варианта: минимальная куча и максимальная куча.
Сложные задачи, такие как поиск k наибольших или наименьших элементов, объединение k несортированных массивов, алгоритм кратчайшего пути Дейкстры, код Хаффмана для сжатия, алгоритм Прима и т. Д., Могут быть легко реализованы.
Заголовочный файл:

#include <queue>

Синтаксис:

Min Priority Queue: priority_queue<Data Type> variable_name; 
Max Priority Queue: priority_queue <Data Type, vector, greater> variable_name;

Наиболее распространенная функция очереди приоритетов:

  1. push (): используется для добавления элемента в очередь.
  2. pop (): удаляет элемент с наивысшим приоритетом очереди, но не возвращает его. Удаляет элемент с максимальным приоритетом в максимальной куче, иначе удаляет минимальный элемент
  3. size (): возвращает размер очереди.
  4. empty (): возвращает логическое значение, т. е. истина, если очередь пуста, иначе возвращает ложь.
  5. top (): возвращает верхний элемент очереди. В очереди с максимальным приоритетом он возвращает максимум, а в очереди с минимальным приоритетом возвращает минимальное значение.

C ++

// C++ program to illustrate the
// function of priority queue in C++
#include <iostream>
// Header file for priority
// queue, both MIN and MAX
#include <queue>
using namespace std;
// Function to print the
// min priority queue
void print_min(
priority_queue< int , vector< int >, greater< int > > q)
{
while (q.empty() == false )
{
// Print the front
// element(MINIMUM)
cout << q.top() << " " ;
// Pop the minimum
q.pop();
}
cout << " " ;
}
// Function to print the
// min priority queue
void print_max(priority_queue< int > q)
{
while (q.empty() == false )
{
// Print the front
// element(MAXIMUM)
cout << q.top() << " " ;
// Pop the maximum
q.pop();
}
cout << " " ;
}
// Driver Code
int main()
{
// MIN priority queue
priority_queue< int > max_pq;
// MAX priority_queue
priority_queue< int , vector< int >, greater< int > > min_pq;
// Is queue empty
if (min_pq.empty() == true )
cout << "MIN priority "
<< "queue is empty " ;
if (max_pq.empty() == true )
cout << "MAX priority"
<< " queue is empty " ;
cout << " " ;
for ( int i = 1; i <= 10; i++)
{
min_pq.push(i);
max_pq.push(i);
}
cout << "MIN priority queue: " ;
print_min(min_pq);
cout << "MAX priority queue: " ;
print_max(max_pq);
cout << " " ;
// Size
cout << "Size of min pq: " << min_pq.size() << " " ;
cout << "Size of max pq: " << max_pq.size() << " " ;
cout << " " ;
// Top element
cout << "Top of min pq: " << min_pq.top() << " " ;
cout << "Top of max pq: " << max_pq.top() << " " ;
cout << " " ;
// Pop the front element
min_pq.pop();
max_pq.pop();
// Queus after popping
cout << "MIN priority "
<< "queue after pop: " ;
print_min(min_pq);
cout << "MAX priority "
<< "queue after pop: " ;
print_max(max_pq);
cout << " " ;
// Size after popping
cout << "Size of min pq: " << min_pq.size() << " " ;
cout << "Size of max pq: " << max_pq.size() << " " ;
cout << " " ;
// Is queue empty
if (min_pq.empty() == false )
cout << "MIN priority "
<< " queue is not empty " ;
if (max_pq.empty() == false )
cout << "MAX priority queue"
<< " is not empty " ;
}
Выход
 Очередь с приоритетом MIN пуста
Очередь с максимальным приоритетом пуста

Очередь с приоритетом MIN: 1 2 3 4 5 6 7 8 9 10 
Очередь с максимальным приоритетом: 10 9 8 7 6 5 4 3 2 1 

Размер min pq: 10
Размер макс. Упаковки: 10

Вершина мин. Pq: 1
Максимум максимального pq: 10

Очередь с приоритетом MIN после pop: 2 3 4 5 6 7 8 9 10 
Очередь с максимальным приоритетом после pop: 9 8 7 6 5 4 3 2 1 

Размер min pq: 9
Размер макс. Упаковки: 9

Очередь с приоритетом MIN не пуста
Очередь с максимальным приоритетом не пуста

4. Набор : Наборы - это ассоциативные контейнеры, в которых каждый элемент уникален. Элементы не могут быть изменены после вставки в набор. Набор игнорирует повторяющиеся значения, и все элементы хранятся в отсортированном порядке. Эта структура данных особенно полезна, когда входящие элементы необходимо отсортировать, а модификация не требуется.
Наборы могут хранить элементы в двух порядках: в порядке возрастания или убывания.
Заголовочный файл:

#include <set> 

Синтаксис:

Increasing order: set<Data type> variable_name;
Decreasing order :set<Data type, greater<Data type> > variable_name; 

Наиболее распространенная функция для набора:

  1. insert (): эта функция используется для вставки нового элемента в Set.
  2. begin (): эта функция возвращает итератор к первому элементу в наборе.
  3. end (): возвращает итератор к теоретическому элементу, который следует за последним элементом в наборе.
  4. size (): возвращает общий размер набора.
  5. find (): возвращает итератор к искомому элементу, если он присутствует. Если нет, то до конца отдаёт итератор.
  6. count (): возвращает количество вхождений в наборе. 1, если присутствует, иначе 0.
  7. empty (): возвращает логическое значение, т. е. истина, если пусто, иначе ложь.

5. Список: списки хранят данные в несмежном порядке. Элементы списка могут быть разбросаны по разным частям памяти. Доступ к любому конкретному индексу становится дорогостоящим, поскольку необходимо выполнить переход от известного индекса к этому конкретному индексу, следовательно, работает медленнее, чем вектор. Также допустимы списки нулевого размера.
Заголовочный файл:

#include <list> 

Синтаксис:

list<Data Type> variable_name;

Список наиболее распространенных функций fo:

  1. push_front (element): вставляет новый элемент element в начало списка.
  2. push_back (element): вставляет новый элемент element в конец списка.
  3. pop_front (): удаляет первый элемент списка.
  4. pop_back
Статьи C++ Олимпиады по программированию Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Онлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024
Как добавить деньги на свой аккаунт в Steam и начать покупать игры и контент
12 Января, 2024