Print bookPrint book

Приложение к главе 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
remove_if

Удаляет элементы, удовлетворяющие определенным критериям 

reverse

Изменяет порядок элементов 

unique

Удаляются последовательно повторяющиеся элементы

sort

Сортирует элементы

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

В отличие от вектора элементы дека не хранятся непрерывно: обычно это реализовано с помощью набора выделенных массивов фиксированного размера.

Хранилище дека обрабатывается автоматически, расширяясь и сужаясь по мере необходимости. Расширение дека дешевле, чем расширение вектора, потому что оно не требует копирования существующих элементов в новый участок памяти.

К элементам дека можно обращаться по индексу.

Сложность (производительность) стандартных операций над двусторонней очередью следующая:

  • произвольный доступ — постоянная O(1);
  • вставка и удаление элементов с начала и с конца — амортизированная постоянная O(1);
  • вставка и удаление элементов — линейная O(n).

Функция

Действие

front

Доступ к первому элементу 

back

Доступ к последнему элементу 

empty

Проверяет отсутствие элементов

size

Возвращает количество элементов

push_front

Вставляет элемент в начало

pop_front

Удаляет первый элемент 

push_back

Вставляет элемент в конец

pop_back

Удаляет последний элемент 

clear

Очищает дек 

insert

Вставляет элементы по итератору

erase

Удаляет элементы по итератору