вектор c ++ с максимально N равными позициями элементов
Могу ли я получить позиции максимум N элементов (равных максимальных элементов), используя предопределенную функцию в STL?
Решение, о котором я подумал:
vector<int> maxN(vector<int> original){
vector<int> result;
auto pt = max_element(original.begin(),original.end());
int max = *pt;
while(*pt == max){
result.push_back(distance(original.begin(),pt));
*pt = 0;//assumed that all the elements in original are greater than 0
pt = max_element(original.begin(),original.end());
}
return result;
}
Должен быть более элегантный способ сделать это.
Решение
Найдя элемент max, сделайте еще один линейный проход по вектору, чтобы найти все подходящие элементы. Установка в 0 не требуется при этом. Исходный вектор передается по значению, поэтому установщик в 0 не был виден вызывающей стороне. Это делает для очень четкой реализации:
vector<int> maxN(vector<int> original){
vector<int> result;
if (original.empty()) return result;
const int max = *(max_element(original.begin(), original.end()));
for (int i = 0; i < original.size(); ++i) {
if (original[i] == max) result.push_back(i);
}
return result;
}
Более важно реализовать понятный и поддерживаемый код, чем пытаться извлечь максимальное повторное использование из библиотеки C ++.
Если ваша цель состоит в том, чтобы не использовать явный цикл над переданным исходным вектором, а использовать какой-то стандартный алгоритм шаблона C ++, я рекомендую создать вспомогательный итератор, чтобы помочь вам восстановить индекс.
struct indexer {
int i_;
indexer (int i = 0) : i_(i) {}
indexer & operator ++ () { ++i_; return *this; }
indexer operator ++ (int) { ++i_; return i_ - 1; }
int operator * () const { return i_; }
bool operator != (indexer rhs) const { return i_ != rhs.i_; }
//... whatever else is required for copy_if
};
Затем вы можете вызвать copy_if с простой лямбда и итератором обратной вставки:
copy_if(indexer(), indexer(original.size()), back_inserter(result),
[&](int i) -> bool { return original[i] == max; });
Однако это более неясно, чем простой цикл, представленный выше.
Другие решения
Это зависит от ваших точных требований:
std::max_element дает вам максимальный элемент. std::copy_if может использоваться для копирования всех элементов, равных максимальному (и ограничения максимального количества, если требуется, например, с использованием лямбды).
std::nth_element частично сортирует диапазон (например, ваш вектор), так что первые n записей равны или меньше всего, что следует. Первые n элементов сами не отсортированы. И это не стабильный раздел.
std::partial_sort дает то же самое, но первые n элементов отсортированы. Опять не стабильный раздел / сортировка.
скомбинировать std::nth_element + std::stable_partition + std::stable_sort если вам нужен стабильный выбор первых n элементов, и вы хотите, чтобы они стабильно сортировались.
Как вариант (можете проверить на cpp.sh)
#include <iostream>
#include <vector>
int main ()
{
std::vector<int>elems = {10, 20, 10, 30, 5, 30, 8, 30, 18, 12};
for(size_t i=0; i<elems.size()-1; i++)
{
if(elems[i+1] > elems[i]) { elems.erase(elems.begin()+i); i=-1;}
else if(elems[i+1] < elems[i]) { elems.erase(elems.begin()+i+1); i=-1;}
}
return 0;
}
Вы можете украсить свой оригинал индексами, использовать N-й элементный подход и снова удалить индексы (тестирование cpp.sh):
template<typename T, typename less = std::greater<T>>
std::vector<int> max_indices(
int N,
const std::vector<T> &original,
less predicate = less())
{
auto decorated = with_indices(original);
// the gist of the problem
const auto nth = std::next(begin(decorated), N);
std::nth_element(begin(decorated), nth, end(decorated),
with_indices(predicate));
std::sort(begin(decorated), nth,
with_indices(predicate));
decorated.erase(nth, end(decorated));
return indices(decorated);
}int main()
{
std::vector<int> values{ {1, 2, 3 , 4, 5, 6, 7, 8, 9, 10} };
auto m = max_indices(4, values);
assert(4u == m.size());
assert(9 == m[0]);
assert(8 == m[1]);
assert(7 == m[2]);
assert(6 == m[3]);
return 0;
}
Где эти функции выполняют декорирование / декорирование:
template<typename T>
std::vector<std::pair<T, int>> with_indices(const std::vector<T> &original)
{
std::vector< std::pair<T, int> > decorated;
std::transform(begin(original), end(original), std::back_inserter(decorated),
[index = 0](T t) mutable {
return std::make_pair(t, index++);
});
return decorated;
}
template<typename T>
std::vector<int> indices(const std::vector<std::pair<T, int>> &original)
{
std::vector<int> undecorated;
std::transform(begin(original), end(original), std::back_inserter(undecorated),
[](auto p) mutable {
return p.second;
});
return undecorated;
}
template<typename Function>
auto with_indices(Function f)
{
return [&](auto... args) {
return f(args.first...);
};
}
detector