Максимальный элемент в 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
А вообще лучше задавать вопрос с общей проблемой — а то это может оказаться вопросом, какой рукой держать микроскоп, забивая гвозди, а не как забить гвоздь.
Нахождение максимального элемента вектора
Задание, которое я выполнял:»Создать файл из N целых чисел. Найти число, повторяющееся максимальное количество раз. Если таких чисел несколько, то все из них. Сохранить эти числа в другой файл и отсортировать. Все файлы до и после обработки вывести на печать.»
Цикл по нахождению максимального элемента вектора veccount не работает, как надо. То изменяет максимум на меньшее число, то идет не по той ветке if-а. Просьба указать на ошибку или показать рабочий вариант.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
#include #include #include #include using namespace std; int main() { setlocale(LC_ALL, "RUSSIAN"); ofstream fin; ifstream fout; int n, randnum, max = 0, maxi, maxcount = 1; cin >> n; vector int> veccount(n); vector int> veckeep(n); srand(time(0)); fin.open("Task.txt"); if (!fin.is_open()) cout <"NOT OPEN"; for (int i = 0; i n; i++) { randnum = rand() % 10; cout ; fin <" "; } cout <"_________"; fin.close(); fout.open("Task.txt"); for (int i = 0; i n; i++) fout >> veckeep[i]; for (int i = 0; i n; i++) for (int j = i + 1; j n; j++) if (veckeep[j] == veckeep[i]) veccount[i]++; for (int i = 0; i n; i++) // Этот цикл работает не так { if (max veccount[i]) { max = veccount[i]; maxi = i; } else if (max = veccount[i]) { maxcount++; } } fout.close(); fin.open("Answer.txt"); if (maxcount == 1) fin [ maxi]; else for (int i = 0; i n; i++) if (veccount[i] = max) { cout [ i]; fin [ i]; } fin.close(); cout <"Проверьте файл!"; return 0; }
Алгоритмы и представления
Алгоритмы представляют специальные функции, которые определены в модуле и выполняются над контейнерами элементов. Разберем наиболее распространенные.
Минимальный и максимальный элементы
Функции 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.