Похожие презентации:
Стандартная библиотека шаблонов (STL). Vector
1.
СТАНДАРТНАЯБИБЛИОТЕКА
ШАБЛОНОВ (STL)
std::vector
Школа::Кода
Олимпиадное
программирование
2020-2021 Таганрог
2.
Что из себя представляет вектор?• Класс вектора стандартной библиотеки C++ является
шаблоном класса для контейнеров
последовательности. Вектор хранит элементы заданного
типа в линейном упорядочении и обеспечивает быстрый
произвольный доступ к любому элементу. Вектор является
предпочтительным контейнером для последовательности,
когда производительность произвольного доступа имеет
уровень "Премиум".
• Иначе говоря, вектор – аналог массива.
3.
Сравнение вектора и массиваДинамический размер
Обращение к элементу
Вставка/удаление в
середину/начало
Вставка/удаление в
конец
Работа с элементами
через
Вектор
Массив
Да
O(1)
O(N)
Нет
O(1)
O(N)
O(1)
O(N)
Индекс или итератор
Индекс или указатель
4.
Почему вставка в конец вектораработает за O(1)?
1)
+
1.5)
2)
3)
4)
+
5.
Объявление вектора• Перед работой с векторами нужно подключить соответствующую
библиотеку.
• Вектор объявляется следующим образом:
vector<‘тип данных’> ‘имя вектора’;
Например:
• Объявление вектора с использованием конструкторов:
vector<‘тип данных’> ‘имя’(‘размер вектора’);
vector<‘тип данных’> ‘имя’(‘размер’, ‘стартовое значение элементов’);
Примеры:
6.
Работа с размером вектора• ‘имя вектора’.size() – возвращает текущий размер вектора.
• ‘имя вектора’.resize(‘новый размер’) – делает размер вектора равным
заданному. Значения элементов, входящих в новый размер
сохраняются.
• ‘имя вектора’.assign(‘новый размер’, ‘значение элементов’) – изменяет
размер вектора и делает все элементы равными заданному значению.
• ‘имя вектора’.clear() – очищает вектор, его размер становиться
равным 0.
• ‘имя вектора’.empty() – возвращает True, если вектор пуст, иначе –
False.
• ‘имя вектора’.reserve(‘кол-во элементов’) – резервирует память на
заданное количество элементов.
7.
Работа с элементами вектора• ‘имя вектора’[‘индекс’] – позволяет работать с элементами вектора так
же, как и с элементами массива.
• ‘имя вектора’.back() – обращается к последнему элементу вектора.
• ‘имя вектора’.front() – обращается к нулевому элементу вектора.
• ‘имя вектора’.push_back(‘значение’) – вставляет в конец вектора
заданное значение.
• ‘имя вектора’.pop_back() – удаляет последнее значение в векторе.
8.
Получение итераторов вектораИтератор – это особый тип указателя, привязанный к конкретному
контейнеру.
Итератор вектора имеет тип данных: vector<‘тип данных’>::iterator.
• ‘имя вектора’.begin() – возвращает итератор на нулевой элемент
вектора.
• ‘имя вектора’.end() – возвращает итератор за концом вектора.
• ‘имя вектора’.rbegin() – возвращает реверсивный итератор на последний
элемент вектора.
• ‘имя вектора’.rend() – возвращает реверсивный итератор перед началом
вектора.
9.
Работа с итераторами• Чтобы работать со значением элемента вектора, на который
указывает итератор, его нужно разыменовать при помощи оператора
*, который указывается перед итератором. Например:
• К итераторам вектора можно прибавлять и отнимать целые числа,
также можно вычитать из итератора итератор.
v.begin()
v.end()-3 v.begin()+4
v.rend()
v.rend()-3 v.rbegin()+2
v.end()
v
v
v.rbegin()
10.
Функции, работающие с векторами• Требуется подключение #include <algorithm>
• min_element(‘итератор на начало’,’итератор за конец’) – возвращает
итератор на наименьший элемент в заданном диапазоне.
• max_element(‘итератор на начало’,’итератор за конец’) – возвращает
итератор на набольший элемент в заданном диапазоне.
• reverse(‘итератор на начало’,’итератор за конец’) – выстраивает
элементы в заданном диапазоне в обратном порядке.
• sort(‘итератор на начало’,’итератор за конец’,’компаратор’) – сортирует
элементы в заданном диапазоне в соответствии с компаратором; в
случае его отсутствия – по возрастанию.
Для сортировки по убыванию можно использовать стандартный
компаратор greater<‘тип данных’>().
11.
КомпараторыАналог компаратора,
используемого по умолчанию
less<int>()
Компаратор, позволяющий
отсортировать числа по убыванию
остатка от деления на 7
Вызов сортировки с указанием
компаратора
12.
Строки (класс string)• Требует подключения библиотеки <string>.
• Представляет собой специфическую реализацию вектора символов
(vector<char>).
• Имеет методы, аналогичные методам вектора: assign, back, begin,
clear, empty, end, front, pop_back, push_back, rbegin, rend, resize,
reserve, size.
• Не имеет конструктора от размера.
• Можно считывать потоковым вводом.