Полезные встроенные функции

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>

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)) и так далее.

---

Автор конспекта: Егор Гутров

По всем вопросам пишите в telegram @egor_gutrov