Приложение к главе 1.1
Site: | Профильное обучение |
Course: | Информатика. 10 класс (Повышенный уровень) |
Book: | Приложение к главе 1.1 |
Printed by: | Guest user |
Date: | Saturday, 14 December 2024, 10:58 PM |
Некоторые функции для работы с типом данных вектор
Функция |
Действие |
v.size() |
Возвращает количество элементов |
v.resize(n) |
Изменяет количество элементов в векторе, новое значение становится равным n. При этом количество элементов может как уменьшиться, так и увеличиться. Если вызвать в виде v.resize(n, x), где x — значение, соответствующее типу элементов в векторе, то при увеличении количества элементов добавляемые значения будут равны x. |
v.clear() |
Очищает вектор, количество элементов становится равным 0 |
v.empty() |
Возвращает true, если вектор пуст, false — если не пуст |
v.push_back(x) |
Добавляет в конец вектора элемент x, вызывается с одним параметром, тип которого совпадает с типом элементов вектора |
v.pop_back() |
Удаляет последний элемент вектора |
v.erase(pos). v.erase(first, last) |
Удаляет один элемент, pos — итератор, указывающий на удаляемый элемент; удаляет элементы в диапазоне [first; last). |
v.insert(pos, value) v.insert(pos, value, count) v.insert(pos, first, last) |
Вставляет value перед элементом, на который указывает pos; вставляет count копий значения value перед элементом, на который указывает pos; вставляет элементы из диапазона [first, last) перед элементом, на который указывает pos |
v1.swap(v2) |
Меняет местами содержимое двух векторов |
v.begin() |
Возвращает итератор на первый элемент |
v.end() |
Возвращает итератор на элемент, следующий за последним |
v.rbegin() |
Возвращает обратный итератор на первый элемент |
v.rend() |
Возвращает обратный итератор на элемент, следующий за последним |
v.front() |
Предоставляет доступ к первому элементу |
v.back() |
Предоставляет доступ к последнему элементу |
Некоторые функции библиотеки algorithm
Функция |
Действие |
Не модифицирующие операции |
|
accumulate |
Складывает диапазон элементов |
djacent_difference |
Считает разницу между смежными элементами диапазона |
adjacent_find |
Находит два идентичных (или имеющих другое отношение) элемента, смежных друг с другом |
Count |
Возвращает количество элементов, соответствующее данному значению |
count_if |
Возвращает количество элементов, для которых предикат является истиной |
equal |
Определяет, одинаковы ли два множества элементов |
find |
Находит значение в данном диапазоне |
find_end |
Ищет последнее вхождение подпоследовательности элементов в диапазон |
find_first_of |
Ищет в множестве элементов первое вхождение любого элемента другого множества |
find_if |
Ищет первое вхождение элемента, для которого верен определенный предикат |
for_each |
Применяет функцию к диапазону элементов |
inner_product |
Считает внутренний продукт двух диапазонов элементов |
mismatch |
Находит первую позицию, в которой два диапазона различны |
partial_sum |
Считает частичную сумму диапазона элементов |
search |
Производит поиск в диапазоне элементов |
search_n |
Ищет N последовательных копий элемента в диапазоне |
Модифицирующие операции |
|
copy |
Копирует некоторый диапазон элементов в новое место |
copy_backward |
Копирует диапазон элементов в обратном порядке |
fill |
Присваивает диапазону элементов определенное значение |
fill_n |
Присваивает значение некоторому количеству элементов |
generate |
Сохраняет результат функции в диапазоне |
generate_n |
Сохраняет результат N применений функции |
iter_swap |
Меняет местами элементы, обозначенные двумя итераторами |
partition |
Делит диапазон элементов на две группы |
random_shuffle |
Случайное перемешивание элементов диапазона |
remove |
Удаляет элемент, равный определенному значению |
remove_copy |
Копирует диапазон элементов, за исключением элементов, равных определенному значению |
remove_copy_if |
Создает копию диапазона, за исключением элементов, для которых предикат является истинным |
remove_if |
Удаляет все элементы, для которых предикат является истинным |
replace |
Заменяет каждое вхождение некоторого значения в диапазоне другим значением |
replace_copy |
Копирует диапазон, заменяя определенные значения новыми |
replace_copy_if |
Копирует диапазон значений, заменяя те, для которых предикат является истинным |
replace_if |
Заменяет значения тех элементов, для которых предикат является истинным |
reverse |
Изменяет порядок следования элементов некоторого множества на обратный |
reverse_copy |
Создает копию некоторого диапазона, изменяя порядок следования элементов на обратный |
rotate |
Двигает элементы множества влево на некоторое количество позиций |
rotate_copy |
Копирует и диапазон, сдвигая все его элементы на некоторое количество позиций |
stable_partition |
Делит элементы на две группы, сохраняя их относительный порядок |
swap |
Меняет местами значения двух объектов |
swap_ranges |
Меняет местами два диапазона элементов |
transform |
Применяет функцию преобразования к диапазону элементов |
unique |
Удаляет дубликаты элементов в диапазоне |
unique_copy |
Создает копию диапазона, которая не содержит дубликатов элементов |
Сортировка |
|
nth_element |
Вставляет элемент диапазон, сохраняя упорядоченность, и проверяет, что нет элементов, для которых элемент слева больше, чем элемент справа |
partial_sort |
Сортирует первые N элементов диапазона |
partial_sort_copy |
Копирует и частично сортирует диапазон элементов |
sort |
Сортирует диапазон по возрастанию |
stable_sort |
Сортирует диапазон элементов, сохраняя относительное положение между равными элементами |
Бинарный поиск (операции для отсортированных диапазонов) |
|
binary_search |
Определяет, присутствует ли элемент в некотором диапазоне |
equal_range |
Ищет диапазон элементов, равных определенному элементу |
lower_bound |
Ищет первое место в диапазоне, в которое можно вставить значение, сохраняя упорядоченность |
upper_bound |
Ищет последнее место, куда можно вставить значения, сохраняя упорядоченность (первое место, в котором элемент больше, чем вставляемое значение) |
Слияние (операции для отсортированных диапазонов) |
|
includes |
Возвращает истину, если одно общество является подмножеством другого |
inplace_merge |
Производит слияние двух упорядоченных диапазонов, сохраняя результат в них |
merge |
Производит слияние двух упорядоченных диапазонов |
set_difference |
Считает разницу между двумя множествами |
set_intersection |
Считает пересечение двух множеств |
set_symmetric_difference |
Считает симметричную разность между двумя множествами |
set_union |
Вычисляет объединение двух множеств |
Min/Max |
|
max |
Возвращает больший из двух элементов |
max_element |
Возвращает наибольший элемент в диапазоне |
min |
Возвращает меньший из двух элементов |
min_element |
Возвращает наименьший элемент в диапазоне |
lexicographical_compare |
Возвращает истину, если один диапазон лексикографически меньше, чем другой |
next_permutation |
Получает следующую в лексикографическом порядке перестановку элементов диапазона |
prev_permutation |
Получает следующую в лексикографическом порядке перестановку элементов диапазона |
Некоторые функции для работы с типом данных список
Функция |
Действие |
front |
Доступ к первому элементу |
back |
Доступ к последнему элементу |
empty |
Проверяет отсутствие элементов |
size |
Возвращает количество элементов |
push_front |
Вставляет элемент в начало |
pop_front |
Удаляет первый элемент |
push_back |
Вставляет элемент в конец |
pop_back |
Удаляет последний элемент |
clear |
Очищает список |
erase |
Удаляет элементы |
insert |
Вставляет элементы |
resize |
Изменяет количество хранимых элементов |
merge |
Слияние двух отсортированных списков |
splice |
Перемещает элементы из другого list |
remove |
Удаляет элементы, удовлетворяющие определенным критериям |
reverse |
Изменяет порядок элементов |
unique |
Удаляются последовательно повторяющиеся элементы |
sort |
Сортирует элементы |
Некоторые функции для работы с типом данных дек
В отличие от вектора элементы дека не хранятся непрерывно: обычно это реализовано с помощью набора выделенных массивов фиксированного размера.
Хранилище дека обрабатывается автоматически, расширяясь и сужаясь по мере необходимости. Расширение дека дешевле, чем расширение вектора, потому что оно не требует копирования существующих элементов в новый участок памяти.
К элементам дека можно обращаться по индексу.
Сложность (производительность) стандартных операций над двусторонней очередью следующая:
- произвольный доступ — постоянная O(1);
- вставка и удаление элементов с начала и с конца — амортизированная постоянная O(1);
- вставка и удаление элементов — линейная O(n).
Функция |
Действие |
front |
Доступ к первому элементу |
back |
Доступ к последнему элементу |
empty |
Проверяет отсутствие элементов |
size |
Возвращает количество элементов |
push_front |
Вставляет элемент в начало |
pop_front |
Удаляет первый элемент |
push_back |
Вставляет элемент в конец |
pop_back |
Удаляет последний элемент |
clear |
Очищает дек |
insert |
Вставляет элементы по итератору |
erase |
Удаляет элементы по итератору |