мин n элементов с дорогим или удаленным конструктором по умолчанию
Учитывая массив v (немного СТЛ контейнер, например std::vector< double >) вообще несортированных данных (скажем, assert(std::is_same< typeof(v), V >::value);). Над элементами массива определяется оператор сравнения, скажем std::less, Вам нужно создать массив с n минимальные элементы (копия формы v), но элементы не по умолчанию (или это дорогая операция). Как это сделать с помощью СТЛ? Требуется алгоритм немодифицированной последовательности.
Первоначально рассматривается как способ решить с помощью std::back_insert_iterator, но есть некоторая путаница, как объяснено далее:
assert(!std::is_default_constructible< typename V::value_type >::value); // assume
template< class V >
V min_n_elements(typename V::const_iterator begin, typename V::const_iterator end, typename V::size_type const n)
{
assert(!(std::distance(begin, end) < n));
V result; // V result(n); not allowed
result.reserve(n);
std::partial_sort_copy(begin, end, std::back_inserter(result), /*What should be here? mb something X(result.capacity())?*/, std::less< typename V::value_type >());
return result;
}
Я хочу найти решение, оптимальное с точки зрения времени и памяти (O (1) дополнительной памяти и <= O (std::partial_sort_copy) расход времени). Всего алгоритм должен работать на следующем количестве памяти: v.size() элементы неизменяемого источника v в качестве входа и n недавно созданных элементов, все из которых являются копиями n наименьшие элементы исходного массива v, как вывод. Это все. Я думаю, что это реалистичные пределы.
Решение
РЕДАКТИРОВАТЬ: reimplemented with heap:
template< class V >
V min_n_elements(typename V::const_iterator b, typename V::const_iterator e, typename V::size_type const n) {
assert(std::distance(b, e) >= n);
V res(b, b+n);
make_heap(res.begin(), res.end());
for (auto i=b+n; i<e; ++i) {
if (*i < res.front()) {
pop_heap(res.begin(), res.end());
res.back() = *i;
push_heap(res.begin(), res.end());
}
}
return std::move(res);
}
Другие решения
Если вам не нужны отсортированные элементы, возможно, это самый простой и быстрый в использовании std::nth_element, затем std::copy,
template <class InIter, class OutIter>
min_n_elements(InIter b, InIter e, OutIter o, InIter::difference_type n) {
InIter pos = b+n;
std::nth_element(b, pos, e);
std:copy(b, pos, o);
}
std::nth_element не только находит данный элемент, но и гарантирует, что те элементы, которые меньше двух, «левее», а те, что больше, «правее».
Хотя это немного обходит реальную проблему — вместо того, чтобы фактически создавать контейнер для результатов, он просто ожидает, что пользователь создаст контейнер правильного типа, а затем предоставит итератор (например, back_insert_iterator) для установки данные в нужном месте. В то же время, я думаю, что это действительно правильно: алгоритм поиска N минимальных элементов и выбор контейнера для пункта назначения являются отдельными.
Если вы действительно хотите поместить результат в определенный тип контейнера, это не должно быть ужасно сложным:
template <class V>
V n_min_element(V::iterator b, V::iterator e) {
V::const_iterator pos = b+n;
nth_element(b, pos, e);
V ret(b, pos);
return V;
}
Пока они стоят, они изменяют (порядок элементов в) входные данные, но, учитывая, что вы сказали, что входные данные не отсортированы, я предполагаю, что их порядок не имеет значения, поэтому это должно быть допустимо. Если вы не можете сделать это, следующая возможность наверное чтобы создать коллекцию указателей, и использовать функцию сравнения, которая сравнивает данные на основе этих указателей, затем выполните nth_element для этого и, наконец, скопируйте указатели в новую коллекцию.