Полезные встроенные функции
Содержание
swap
swap(a, b)
обменивает значения переменных a
и b
местами.
int a = 1, b = 2;
cout << a << ' ' << b << '\n'; // выведет 1 2
swap(a, b);
cout << a << ' ' << b << '\n'; // выведет 2 1
min_element и max_element
min_element(first, last)
возвращает итератор на минимум на полуинтервале [first; last)
.
max_element(first, last)
возвращает итератор на максимум на полуинтервале [first; last)
.
Если минимумов/максимумов несколько, то возвращается первое вхождение. <syntaxhighlight="C++"> vector<int> numbers = {5, 3, 1, 2, 1}; auto it = min_element(numbers.begin(), numbers.end()); cout << *it << " " << (it - numbers.begin()) << "\n"; // выведет 1 2 </syntaxhighlight>
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
sort, unique, компараторы
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
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());
nth_element
nth_element(first, need, last)
ставит в позицию need
элемент, который был бы на этом месте после сортировки всех элементов в полуинтервале [first; last)
. first
, need
и last
- итераторы. Функция работает за линию.
next_permutation и prev_permutation
Генерируют следующую и предыдущую перестановку. Например, чтобы перебрать все уникальные перестановки в векторе a
, можно написать такой код:
sort(a.begin(), a.end());
do {
... // тело цикла
} while (next_permutation(a.begin(), a.end()));
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. Подробнее можно почитать [[1]]. Обратите внимание, что если не использовать back_inserter, код получился бы таким:
vector<int> res(vec1.size() + vec2.size());
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), res.begin());
В первом варианте код красивее, но дольше работает, так как res
расширится несколько раз. Решайте, каким методом пользоваться, опираясь на ограничения в задачах.
Автор конспекта: Егор Гутров
По всем вопросам пишите в telegram @egor_gutrov