Алгоритмы и представления
Алгоритмы представляют специальные функции, которые определены в модуле и выполняются над контейнерами элементов. Разберем наиболее распространенные.
Минимальный и максимальный элементы
Функции std::min_element и std::max_element возвращают минимальный и макисмальный элементы соответственно из некоторого диапазона. В качестве коллекции элементов может выступать контейнер или массив. Диапазон элементов задается начальным и конечным итераторами контейнера/массива.
#include #include #include int main() < std::vectornumbers < 1, 2, 3, 4, 5, 6, 7, 8>; std::cout
Здесь находим минимальный и максимальный элементы вектора numbers. В обоих случаях в качестве диапазона выступает весь контейнер — от итератора begin(numbers) до итератора end(numbers). Результатом каждой функции также является итератор. Потому для получения значения (максимального/минимального значения) применяем операцию разыменования: *std::min_element(. ) . Консольный вывод:
Min: 1 Max: 8
Поскольку диапазон поиска значений представляет необязательно весь контейнер, а может быть только частью контейера, ограниченной итераторами, то мы можем найти максимальное/минимальное значения на каком-то определенном диапазоне, например, от 2-го до предпоследнего элемента:
std::coutТакже для получения мин/макс. значений можно принименять функцию std::minmax_element() , которая также используется итераторы для задания диапазона поиска. Но результат возвращает в виде объекта std::pair :
#include #include #include int main() < std::vectornumbers < 1, 2, 3, 4, 5, 6, 7, 8>; const auto [min, max] = std::minmax_element(begin(numbers), end(numbers)); std::cout
STL
Все шаблонные алгоритмы работают не только со структурами данных в библиотеке, но также и с встроенными структурами данных C++. Например, все алгоритмы работают с обычными указателями.
Обработка скалярных значений
| max(a,b) | максимальное значение |
| min(a,b) | минимальное значение |
| swap(a,b) | обмен |
| gcd(a,b) | НОД |
| lcm(a,b) | НОК |
| clamp(x,low,high) | max(min(x,high),low) |
| max_element(first,last) | значение максимального элемента набора |
| min_element(first,last) | значение минимального элемента набора |
| minmax_element(first,last) | значения максимального и максимального элемента набора |
| for_each(first,last,fun) | применить к каждому элементу последовательности функциональный объект (функцию) fun |
| find(first,last,value) | поиск первого элемента, равного value |
| find_if(first,last,fun) | поиск первого элемента, для которого fun(x)==true |
| count(first,last,value) | подсчет количества элементов, равных value |
| count_if(first,last,fun) | подсчет количества элементов, для которых fun(x)==true |
| search(first1,last1, first2,last2) | поиск вхождения подпоследовательности, заданной итераторами (first2,last2) |
| search_n(first1,last1, n,value) | поиск подпоследовательности из n значений value |
| copy(first,last,where) | копирование последовательности в where |
| copy_if(first,last,where,fun) | копирование элементов в where для которых fun(x)==true |
| move(first,last,where) | перемещение последовательности в where |
| transform(first,last, where,fun) | преобразование элементов последовательности с помощью функционального объекта (функции) fun |
| transform(first1,last1, first2,where,fun) | преобразование элементов двух последовательностей, например, суммирование двух векторов a и b: vector a(n),b(n),c(n); transform(a.begin(),a.end(), b.begin(),b.end(),c.begin(),plus() |
| fill(first,last,value) | заполнение значением value |
| fill_n(where,n,value) | записать n значений value |
| iota(first,last,value) | заполнение увеличивающимися на 1 значениями, начиная с value |
| generate(first,last,fun) | заполнение результатом функционального объекта (функции) fun() |
| generate_n(where,n,fun) | записать n результатов функционального объекта (функции) fun() |
| shuffle(first,last,randgen) | перемешивание |
| remove(first,last,value) | удаление элементов, равных value, возвращается итератор на конец новой последовательности например, удаление всех 0: a.erase(remove(a.begin(), a.end(),0),a.end()) |
| remove_if(first,last,fun) | удаление элементов, для которых fun(x)==true |
| remove_copy(first,last, where,value) | копирование элементов, не равных value |
| remove_copy_if(first,last, where,fun) | копирование элементов, для которых fun(x)==false |
| replace(first,last, oldvalue,newvalue) | замена элементов, равных oldvalue на newvalue |
| replace_if(first,last, fun,newvalue) | замена элементов, для которых fun(x)==true на newvalue |
| replace_copy(first,last, where,oldvalue,newvalue) | копирование с заменой |
| replace_copy_if(first,last, where,fun,newvalue) | копирование с заменой |
| reverse(first,last) | изменение порядка элементов на обратный |
| reverse_copy(first,last,where) | копирование в обратном порядке |
| rotate(first,middle,last) | циклический сдвиг, элемент *middle становится первым |
| rotate_copy(first,middle, last,where) | копирование с циклическим сдвигом |
| partition(first,last,fun) | перемещение элементов, для которых fun(x)==true, в начало последовательности |
| stable_partition(first,last,fun) | перемещение элементов, для которых fun(x)==true, в начало последовательности с сохранением порядка в исходной последовательности |
| next_permutation(first,last) | следующая перестановка, возвращается false, если следующей перестановки не существует |
| prev_permutation(first,last) | предыдущая перестановка |
| accumulate(first,last, init,fun=plus()) | подсчет суммы элементов, можно вместо сложения указать другую бинарную функцию |
| all_of(first,last,fun) | проверка, что все элементы последовательности удовлетворяют предикату fun |
| any_of(first,last,fun) | проверка, что существует элемент последовательности, удовлетворяющий предикату fun |
| none_of(first,last,fun) | проверка, что не существует элемента последовательности, удовлетворяющего предикату fun |
Сортировка и обработка упорядоченных последовательностей, множеств (упорядоченных последовательностей без повторений)
| sort(first,last) | сортировка последовательности |
| stable_sort(first,last) | сортировка с сохранением порядка элементов с равным ключом |
| is_sorted(first,last) | проверка, что последовательность упорядочена в неубывающем порядке |
| unique(first,last) | удалить повторения элементов, возвращается итератор на конец новой последовательности |
| unique_copy(first,last,where) | копирование без повторений |
| merge(first1,last1, first2,last2,where) | слияние |
| binary_search(first,last,value) | проверка наличия значения value |
| lower_bound(first,last,value) | поиск первой позиции для вставки значения |
| upper_bound(first,last,value) | поиск последней позиции для вставки значения например, подсчет количества элементов, равных v: int k=upper_bound(a.begin(),a.end(),v) - lower_bound(a.begin(),a.end(),v); |
| includes(first1,last1, first2,last2) | проверка, что множество (first2,last2) является подмножеством множества (first1,last1) |
| set_intersection(first1, last1,first2,last2,where) | пересечение множеств |
| set_difference(first1, last1,first2,last2,where) | разность множеств |
| set_symmetric_difference(first1, last1,first2,last2,where) | симметрическая разность множеств |
| set_union(first1,last1, first2,last2,where) | объединение множеств |
| make_heap(first,last) | создать кучу из элементов последовательности |
| push_heap(first,last) | добавить значение *(last-1) к куче (first,last-1), после выполнения куча станет (first,last) |
| pop_heap(first,last) | удалить наибольшее значение из кучи (first,last) и поместить его в *(last-1), после выполнения куча станет (first,last-1) |
| sort_heap(first,last) | превратить кучу в упорядоченную последовательность |
Для аргумента where можно использовать либо итератор (указатель) на начало контейнера достаточного размера, либо back_inserter(s), который возвращает добавляющий итератор для контейнера s.
Максимальный элемент в STL Vector C++
Я решаю проблему в которой в какой то момент нужно взять элемент с максимальным значением в векторе(или в отрезке вектора) я нашел функцию max_element но оно работает медленно мне нужно чтоб я указывал аргументы как в max_element там указывается так - max_element(vectorname.begin(), vectorname.end())
Отслеживать задан 24 мая 2020 в 10:42 E_d_u_a_r_d E_d_u_a_r_d 347 3 3 серебряных знака 17 17 бронзовых знаковНу тогда делайте свой тип и храните отдельно значение максимального элемента и обновляйте при вставке. В неотсортированном массиве лучше O(N) ничего не получится. Так что используйте какую-то другую структуру данных.
24 мая 2020 в 10:46А вообще лучше задавать вопрос с общей проблемой - а то это может оказаться вопросом, какой рукой держать микроскоп, забивая гвозди, а не как забить гвоздь.
Максимальный элемент массива в C++
Здравствуйте. Подскажите, как лучше найти максимальный элемент массива на языке C++?
Андрей, возьмите первый элемент массива за максимальный. Проходите в цикле по всем элементам этого массива. Если какой-либо элемент больше max — присваиваете значение этого элемента переменной max .
#include using namespace std; int main() < int arr[10] = ; int max = arr[0]; for (int i = 0; i < 10; ++i) < if (arr[i] >max) < max = arr[i]; >> cout
А как найти четыре максимальных элемента?
Артем, сначала сортируете, а потом забираете крайние элементы.
А как найти четыре максимальных элемента?
#include using namespace std; static void quick_sort(int *arr, int low, int high) < // Алгоримт быстрой сортировки // http://ru.wikipedia.org/wiki/Быстрая_сортировка int i = low; int j = high; int x = arr[(low + high) / 2]; int temp; do < while (arr[i] < x) < ++i; >while (arr[j] > x) < --j; >if (i > while (i if (i < high) < quick_sort(arr, i, high); >> int main() < // размер массива, задается пользователем int size; cin >> size; int *list = new int [size]; // заполнить массив руками или из файла for (int i = 0; i < size; ++i) < cin >> list[i]; > // отсортировать массив по возрастанию quick_sort(list, 0, size - 1); // вывести последние 4 элемента отсортированного массива for (int i = size - 1; i > size - 5; --i) < cout return 0; > P.S. Взял алгоритм сортировки по ссылке селевита.