я бы хотел std::partial_sort_copy()
массив, но с использованием пользовательской функции компаратора. Дело в том, что эта функция использует как ценности сравниваемых ячеек массива и их индексы.
Ради обсуждения, предположим, что моя функция comaprison что-то вроде
template <typename T>
bool myCompare(size_t lhs_index, const T& lhs, size_t rhs_index, const T& rhs) {
T lhs_compound = lhs * (lhs_index % 2 ? -1 : 1);
T rhs_compound = rhs * (lhs_index % 2 ? -1 : 1);
return (lhs_compound <= rhs_compound);
}
(Я могу сделать его более надуманным, если хотите …)
Сначала я подумал об использовании объекта сравнения, который принимает pair<size_t, T>
s — но это не сработает, поскольку это означает, что мой вывод будет массивом таких пар, и я не хочу этого. На самом деле мне нужно ничего не материализовать — так что нет массивов пар, индексов или чего-либо подобного.
Что мне делать вместо этого?
Нечто подобное может помочь.
Он создает массив индексов, затем сортирует этот массив в соответствии с компаратором (с косвенным обращением к исходному массиву):
template <typename IT, typename Comp>
struct MyCmp
{
explicit Cmp(const IT it, Comp& comp) : it(it), comp(comp) {}
bool operator (std::size_t lhs, std::size_t rhs) const
{
return comp(lhs, *(it + lhs), rhs, *(it + rhs));
}
const IT it;
Comp comp;
};
template<typename IT, typename IT2, typename Comp>
void mypartialsort(IT begin, IT end, IT2 dbegin, IT2 dend, Comp comp)
{
std::vector<size_t> indexes;
for (size_t i = 0, size = end - begin; i != size; ++i) {
indexes.push_back(i);
}
MyCmp<IT, Comp> mycomp(begin, comp);
const std::size_t min_size = std::min(end - begin, dend - dbegin);
std::partial_sort(v.begin(), v.begin() + d, v.end(), mycomp);
for (std::size_t i = 0; i != min_size; ++i, ++dbegin) {
*dbegin = *(begin + v[i]);
}
}
Других решений пока нет …