Здесь мы собираемся обсудить некоторые STL, которые часто используются в соревновательном программировании. Как строка, вектор, пара, очередь, стек, набор и карта.
Что такое STL?
STL (стандартная библиотека шаблонов): STL предоставляет набор общих классов для C ++, таких как контейнеры (очередь, стек) и ассоциативные массивы (хеш-таблицы), которые можно использовать с любыми встроенными данными. -type и с любым определяемым пользователем типом данных, который поддерживает некоторые элементарные операции (такие как копирование и присваивание).
Все STL обеспечивают динамическое распределение памяти. Вектор и строка имеют непрерывное выделение памяти, а остальные имеют несмежное выделение памяти.
Итак, теперь мы должны увидеть каждый STL один за другим: -
Вектор: -
Это похоже на массив, но с динамическим непрерывным распределением памяти. Это входит в вектор библиотеки STL.
Добавляемая библиотека: - вектор (#include ‹vector›)
Объявление вектора: -
вектор ‹тип данных› имя-вектора;
здесь тип данных может быть любым встроенным типом данных (char, int, float, double) или любым типом данных, определяемым пользователем (классы, структуры).
Разница и сходство между вектором и массивом: -
Объявление массива, в котором может храниться 8 целых чисел, будет выглядеть как
int arr [8];
и если мы хотим использовать вектор вместо массива, нам просто нужно написать
vector ‹int› v; (размер указывать необязательно)
Указание размера при объявлении вектора: -
vector ‹int› v (8);
(также можно не указывать размер)
vector ‹int› v;
(Это объявление не означает, что этот вектор v будет хранить только одно целое число. Это список целых чисел с непрерывным распределением памяти).
Мы используем функцию push_back для вставки любого элемента в конец вектора.
предположим, мы написали следующий код
vector<int> v;
for(int i=0;i<8;i++){
arr[i]=i;
v.push_back(i);
}
Теперь в этом векторе v 8 целых чисел 0,1,2,3,4,5,6,7.
Разница:
Разница между вектором и массивом заключается в том, что размер в векторе не является фиксированным и может быть изменен динамически, потому что вектор имеет динамическое распределение памяти, а массив имеет статическое выделение памяти. Нам не нужно указывать размер при декларировании.
Сходство:
Сходство между вектором и массивом состоит в том, что они оба имеют непрерывное распределение памяти. Преимущество непрерывного распределения памяти состоит в том, что мы можем получить доступ к любому элементу с временной сложностью O (1), указав индекс элемента в квадратных скобках с именем вектора.
Предположим, мы хотим получить доступ к 5-му элементу в массиве, тогда мы напишем arr [4], и это будет то же самое в векторе v [4] (из-за непрерывного выделения памяти). как вектор, так и массив будут выводить 4 из-за приведенного выше кода. Но мы не можем получить доступ таким же образом в list, потому что он имеет несмежное выделение памяти. По сути, это связанный список, и временные сложности для всех операций такие же, как и у структуры данных связанного списка.
Мы можем выполнять все операции с векторами так же, как и с массивами.
Вот некоторые функции-члены, которые часто используются в векторе: -
- push_back (arg): - эта функция помещает элемент arg в конец вектора.
- pop_back (): - эта функция выталкивает элемент с конца вектора.
- back (): - эта функция возвращает последний элемент вектора.
- front (): - эта функция возвращает первый элемент вектора.
- clear (): - эта функция очищает вектор.
- size (): возвращает общее количество элементов, хранящихся в векторе.
- begin (): возвращает итератор, указывающий на первый элемент вектора.
- end (): возвращает итератор, указывающий на теоретический элемент, следующий за последним элементом.
Все вышеперечисленные функции имеют временную сложность O (1).
Пример: -
#include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int > v;
int i;
for(i=0;i<8;i++) {
v.push_back(i);
}
cout<<”First element is:- “<<v.front()<<endl;
cout<<”Last element is:- “<<v.back()<<endl;
cout<<”Elements in the vector are:- “<<endl;
for(i=0;i<v.size();i++) {
cout<<v[i]<<endl;
}
v.pop_back();
cout<<”Last element after pop_back:- “<<v.back()<<endl;
v.clear();
cout<<”Size of vector after clearing the vector:- “<<v.size();
return 0;
}
Output of the above program:-
First element is:- 0
Last element is:- 7
Elements in the vector are:-
0
1
2
3
4
5
6
7
Last element after pop_back:- 6
Size of vector after clearing the vector:- 0
Как вектор выполняет динамическое и непрерывное размещение?: -
Когда вектор объявлен, ему назначается блок памяти с фиксированной емкостью (максимальное количество элементов, которые должны храниться в этом блоке). Когда в вектор добавляется новый элемент и размер вектора превышает его емкость, то новому блоку памяти назначается большая емкость, и предыдущий блок копируется в этот новый блок памяти, а новый элемент добавляется просто после этого скопированный блок и предыдущий блок памяти освобождается. Вот как он поддерживает два вышеупомянутых свойства.
Строка: -
Последовательность символов называется String. Он также имеет непрерывное и динамическое распределение памяти и работает так же, как вектор для динамического и непрерывного распределения памяти.
Добавляемая библиотека: - строка (#include ‹string›)
Объявление строки: -
строка имя-строки;
Как объявить массив символов в C: -
char str[N+1]; ( Here N is the number of characters in the string and extra 1 for null character )
но если вы хотите использовать строку STL, мы объявим ее как.
string str; ( Here we do not need to specify the size )
Теперь мы можем использовать то же самое, что и символьный массив, но мы не можем использовать какую-либо функцию из string.h в c, потому что str является объектом строки класса, а str в объявлении символьного массива является указателем.
Для сравнения строковых объектов присваивание и конкатенация очень просты, и нам не нужно писать какую-либо функцию, для которой мы можем сравнивать их так же, как мы сравниваем целые числа.
string s1=”abc”,s2=”cde”; s1<s2 , s1==s2 , s2≥s1 any comparison will work fine but with same string object. s1+=s2; ( This concatenation will make s1=”abccde” ).
Вот некоторые из функций-членов строки: -
- length (): возвращает размер строки.
- clear (): - очищает строку
- substr (pos, len): - возвращает подстроку, начиная с pos (с индексом 0) и размером len. Если запрошенная подстрока выходит за пределы конца строки, возвращается подстрока
[pos, size()).
Пример кода: -
#include<iostream>
#include<string>
using namespace std;
int main() {
string s=”abcdefghijklmnopqrstuvwxyz”;
cout<<”Length of the String:- “<<s.length()<<endl;
cout<<”Characters in the String:- “;
for(int i=0;i<s.length();i++) {
cout<<s[i]<<’ ‘;
}
cout<<endl;
cout<<”Substring is:- “<<s.substr(23,3)<<endl;
s.clear();
cout<<s.length();
return 0;
}
Output of the above program:-
Length of the String:- 26
Characters in the String:- a b c d e f g h i j k l m n o p q r s t u v w x y z
Substring is:- xyz
Очередь
Очередь - это линейная структура данных, соответствующая принципу FIFO (первый пришел - первый ушел). Элементы будут вставлены в конец и удалены спереди.
Push and pop in queue: - Push означает вставку элемента, а Pop означает удаление элемента.
Он имеет динамическое, но несмежное выделение памяти.
Добавляемая библиотека: - очередь (#include ‹queue›)
Объявление очереди: -
queue ‹data-type› имя-очереди;
( Здесь тип данных может быть любым встроенным или определенным пользователем типом данных)
Вот некоторые функции-члены очереди stl: -
- size (): - возвращает количество элементов в очереди.
- front (): возвращает первый элемент в очереди.
- push (arg): - помещает arg в очередь.
- pop (): - выталкивает первый элемент из очереди и ничего не возвращает.
- empty (): - возвращает true, если очередь пуста, иначе false.
- back (): - возвращает последний элемент очереди.
Пример кода: -
#include<iostream>
#include<queue>
using namespace std;
int main() {
queue<int> q;
for(int i=0;i<4;i++) {
q.push(i);
}
cout<<"Size of the queue is:- "<<q.size()<<endl;
while(!q.empty()) {
cout<<"First element in the queue:- "<<q.front()<<endl;
cout<<"Last element in the queue:- "<<q.back()<<endl;
q.pop();
cout<<"Element popped"<<endl;
}
return 0;
}
Output of the above program:-
Size of the queue is:- 4
First element in the queue:- 0
Last element in the queue:- 3
Element popped
First element in the queue:- 1
Last element in the queue:- 3
Element popped
First element in the queue:- 2
Last element in the queue:- 3
Element popped
First element in the queue:- 3
Last element in the queue:- 3
Element popped
Стек: -
Стек - это структура данных, соответствующая LIFO (Last in First Out). Элементы будут вставлены в конец и удалены с конца.
Он имеет динамическое, но несмежное выделение памяти.
Добавляемая библиотека: - стек (#include ‹stack›)
Объявление стека: -
stack ‹data-type› имя-стека;
( Здесь тип данных может быть любым встроенным или определенным пользователем типом данных)
Вот некоторые функции-члены очереди stl: -
- size (): - возвращает количество элементов в стеке.
- push (arg): - помещает arg в стек.
- pop (): - извлекает первый элемент из стека и ничего не возвращает.
- empty (): - возвращает true, если стек пуст, иначе false.
- top (): возвращает элемент, который находится на вершине стека .
Пример кода: -
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int > st;
for(int i=0;i<4;i++) {
st.push(i);
}
cout<<"Size of the stack is:- "<<st.size()<<endl;
while(st.empty()==false) {
cout<<"Element at the top of the stack:- "<<st.top()<<end;
st.pop();
cout<<"Element popped"<<endl;
}
return 0;
}
Output of the above program:-
Size of the stack is:- 4
Element at the top of the stack:- 3
Element popped
Element at the top of the stack:- 2
Element popped
Element at the top of the stack:- 1
Element popped
Element at the top of the stack:- 0
Element popped
