Стандартная библиотека шаблонов (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.
• Не имеет конструктора от размера.
• Можно считывать потоковым вводом.