Полезные встроенные функции: различия между версиями
м (added tags) |
м |
||
Строка 19: | Строка 19: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === | + | ===nth_element=== |
− | <code> | + | <code>nth_element(first, need, last)</code> ставит в позицию <code>need</code> элемент, который был бы на этом месте после сортировки всех элементов в полуинтервале <code>[first; last)</code>. <code>first</code>, <code>need</code> и <code>last</code> - итераторы. Функция работает за линию. |
− | < | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | / | ||
− | |||
− | ===sort | + | ===sort и компараторы=== |
<code>sort(first, last)</code> сортирует полуинтервал <code>[first; lasst)</code>. | <code>sort(first, last)</code> сортирует полуинтервал <code>[first; lasst)</code>. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Строка 60: | Строка 51: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | ===stable_sort=== | ||
+ | TODO | ||
+ | |||
+ | ===unique=== | ||
<code>unique(first, last)</code> принимает полуинтервал и удаляет все последовательные повторения элементов в нём. Функция возвращает итератор на конец полуинтервала, соответствующему уникализированным элементам. Значения элементов, которые следуют после этого полуинтервала, становятся неопределёнными. Поэтому рекомендуется использовать функцию <code>unique</code>, например, вместе с функцией <code>resize</code>. | <code>unique(first, last)</code> принимает полуинтервал и удаляет все последовательные повторения элементов в нём. Функция возвращает итератор на конец полуинтервала, соответствующему уникализированным элементам. Значения элементов, которые следуют после этого полуинтервала, становятся неопределёнными. Поэтому рекомендуется использовать функцию <code>unique</code>, например, вместе с функцией <code>resize</code>. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Строка 75: | Строка 70: | ||
a.resize(unique(a.begin(), a.end()) - a.begin()); | a.resize(unique(a.begin(), a.end()) - a.begin()); | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===merge=== | ===merge=== | ||
merge(first1, last1, first2, last2, d_first) сливает два отсортированных полуинтервала <code>[first1; last1)</code> и <code>[first2; last2)</code> в один, начиная с <code>d_first</code> и возвращает итератор на следующий за последним элемент. | merge(first1, last1, first2, last2, d_first) сливает два отсортированных полуинтервала <code>[first1; last1)</code> и <code>[first2; last2)</code> в один, начиная с <code>d_first</code> и возвращает итератор на следующий за последним элемент. | ||
+ | |||
===back_inserter=== | ===back_inserter=== | ||
Стандартная задача: слить отсортированные векторы <code>vec1</code>, <code>vec2</code> в вектор <code>res</code>. Можно реализовать так: | Стандартная задача: слить отсортированные векторы <code>vec1</code>, <code>vec2</code> в вектор <code>res</code>. Можно реализовать так: | ||
Строка 93: | Строка 80: | ||
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(res)); | merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(res)); | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Здесь используется back_inserter. Подробнее можно почитать | + | Здесь используется back_inserter. Подробнее можно почитать [http://www.cplusplus.com/reference/iterator/back_insert_iterator/ тут]. |
Обратите внимание, что если не использовать back_inserter, код получился бы таким: | Обратите внимание, что если не использовать back_inserter, код получился бы таким: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Строка 100: | Строка 87: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
В первом варианте код красивее, но дольше работает, так как <code>res</code> расширится несколько раз. Решайте, каким методом пользоваться, опираясь на ограничения в задачах. | В первом варианте код красивее, но дольше работает, так как <code>res</code> расширится несколько раз. Решайте, каким методом пользоваться, опираясь на ограничения в задачах. | ||
+ | |||
+ | ===reverse=== | ||
+ | <code>reverse(first, last)</code> переворачивает полуинтервал <code>[first; last)</code> (элементы идут в обратном порядке). | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | 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 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===rotate=== | ||
+ | <code>rotate(first, n_first, last)</code> переставляет элементы в полуинтервале <code>[first; last)</code> так, что элемент <code>n_first</code> становится первым, а <code>n_first - 1</code> - последним. | ||
+ | Например, циклический сдвиг вектора <code>v</code> влево можно реализовать так: | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | rotate(v.begin(), v.begin() + 1, v.end()); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===next_permutation и prev_permutation=== | ||
+ | Генерируют следующую и предыдущую перестановку. Например, чтобы перебрать все уникальные перестановки в векторе <code>a</code>, можно написать такой код: | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | sort(a.begin(), a.end()); | ||
+ | do { | ||
+ | ... // тело цикла | ||
+ | } while (next_permutation(a.begin(), a.end())); | ||
+ | </syntaxhighlight> | ||
+ | |||
{{Автор|Егор Гутров|egor_gutrov}} | {{Автор|Егор Гутров|egor_gutrov}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] | ||
[[Категория:C++ и STL]] | [[Категория:C++ и STL]] |
Версия 09:55, 28 сентября 2019
Содержание
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()));
Автор конспекта: Егор Гутров
По всем вопросам пишите в telegram @egor_gutrov