Полезные встроенные функции
Содержание
swap
swap(a, b)
обменивает значения переменных a
и b
местами.
1 int a = 1, b = 2;
2 cout << a << ' ' << b << '\n'; // выведет 1 2
3 swap(a, b);
4 cout << a << ' ' << b << '\n'; // выведет 2 1
min_element и max_element
min_element(first, last)
возвращает итератор на минимум на полуинтервале [first; last)
.
max_element(first, last)
возвращает итератор на максимум на полуинтервале [first; last)
.
Если минимумов/максимумов несколько, то возвращается первое вхождение.
vector<int> numbers = {5, 3, 1, 2, 1};
auto it = min_element(numbers.begin(), numbers.end());
cout << *it << " " << (it - numbers.begin()) << "\n"; // выведет 1 2
nth_element
nth_element(first, need, last)
ставит в позицию need
элемент, который был бы на этом месте после сортировки всех элементов в полуинтервале [first; last)
. first
, need
и last
- итераторы. Функция работает за линию.
sort и компараторы
sort(first, last)
сортирует полуинтервал [first; lasst)
.
vector<int> a = {5, 2, 10, 11, 2, 3};
sort(a.begin(), a.end()); // сортируем весь вектор
for (int x : a) {
cout << x << " ";
}
cout << "\n";
// будет выведено 2 2 3 5 10 11
Функция sort
может принимать третий параметр - компаратор. Компаратор - это функция, которая принимает два объекта и возвращает true
, если первый строго меньше второго, и false
иначе.
Допустим, нам хотелось бы отсортировать числа по возрастанию их последней цифры, а при совпадении — по самому значению. Тогда мы могли бы написать следующий код:
bool cmp(int a, int b) {
return make_pair(a % 10, a) < make_pair(b % 10, b);
}
// это внутри main
vector<int> a = {30, 32, 12, 7, 15};
sort(a.begin(), a.end(), cmp);
for (int x : a) {
cout << x << " ";
}
cout << "\n";
// будет выведено 30 12 32 15 7
stable_sort
TODO
unique
unique(first, last)
принимает полуинтервал и удаляет все последовательные повторения элементов в нём. Функция возвращает итератор на конец полуинтервала, соответствующему уникализированным элементам. Значения элементов, которые следуют после этого полуинтервала, становятся неопределёнными. Поэтому рекомендуется использовать функцию unique
, например, вместе с функцией resize
.
vector<int> a = {5, 5, 5, 1, 5, 4, 4, 7, 1};
a.resize(unique(a.begin(), a.end()) - a.begin());
for (int x : a) {
cout << x << " ";
}
cout << "\n";
// будет выведено 5 1 5 4 7 1
Если нужно удалить все повторения элементов (не только соседних), то нужно сначала отсортировать их. Это делается так:
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
merge
merge(first1, last1, first2, last2, d_first) сливает два отсортированных полуинтервала [first1; last1)
и [first2; last2)
в один, начиная с d_first
и возвращает итератор на следующий за последним элемент.
back_inserter
Стандартная задача: слить отсортированные векторы vec1
, vec2
в вектор res
. Можно реализовать так:
vector<int> res;
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(res));
Здесь используется back_inserter
. Подробнее можно почитать тут.
Если не использовать back_inserter, код получился бы таким:
vector<int> res(vec1.size() + vec2.size());
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), res.begin());
В первом варианте код красивее, но дольше работает, так как res
расширится несколько раз. Решайте, каким методом пользоваться, опираясь на ограничения в задачах.
reverse
reverse(first, last)
переворачивает полуинтервал [first; last)
(элементы идут в обратном порядке).
vector<int> a = {5, 2, 3, 10, 17};
reverse(a.begin(), a.begin() + 3);
for (int x : a) {
cout << x << " ";
}
cout << "\n";
// будет выведено 3 2 5 10 17
rotate
rotate(first, n_first, last)
переставляет элементы в полуинтервале [first; last)
так, что элемент n_first
становится первым, а n_first - 1
- последним.
Например, циклический сдвиг вектора v
влево можно реализовать так:
rotate(v.begin(), v.begin() + 1, v.end());
next_permutation и prev_permutation
Генерируют следующую и предыдущую перестановку. Например, чтобы перебрать все уникальные перестановки в векторе a
, можно написать такой код:
sort(a.begin(), a.end());
do {
... // тело цикла
} while (next_permutation(a.begin(), a.end()));
lower_bound, upper_bound, binary_search
Все эти функции принимают полуинтервал [first; last)
и значение value
. Полуинтервал должен быть упорядочен по отношению element < value
(сначала те элементы, которые удовлетворяют этому, потом остальные).
lower_bound
- возвращает указатель на первый элемент, больший или равный value
.
upper_bound
- возвращает указатель на первый элемент, строго больший value
.
binary_search
— возвращает, присутствует ли value
на этом полуинтервале.
vector<int> a = {1, 5, 5, 6, 7, 10};
auto it1 = lower_bound(a.begin(), a.end(), 5);
cout << (it1 - a.begin()) << "\n"; // выведет 1
auto it2 = upper_bound(a.begin(), a.end(), 5);
cout << *it2 << "\n"; // выведет 6
if (binary_search(a.begin(), a.end(), 7)) {
cout << "There is an element = 7\n"; // это будет выведено
}
Внимание!
Не используйте lower_bound
, upper_bound
, binary_search
вместе с set
/map
! Они будут работать за линейное время. Используйте их собственные функции: set::lower_bound
(вызывается как s.lower_bound(elem)
) и так далее.
fill
fill(first, last, value)
присваивает значение value
всем элементов полуинтервала [first; last)
.
copy
copy(first, last, d_first)
копирует элементы полуинтервала [first; last)
в диапазон, начиная с d_first
.
Автор конспекта: Егор Гутров
По всем вопросам пишите в telegram @egor_gutrov