использование std :: nth_element в собственных и связанных запросах

Question

Я учу себя c ++ и eigen за один раз, так что, возможно, это простой вопрос.

Учитывая n и 0 "<" m "<" n, и n-вектор d с плавающей точкой,Чтобы конкретизировать: </p>

VectorXf d = VectorXf::Random(n)

я хотел бы иметь m-вектор d_prim onf целых чисел, который содержит индексы всех записей d, которые меньше или равны m-й наибольшей записи d,Эффективность имеет значение.если в данных есть ничья, тогда заполнение d_prim первых m записей d, которые меньше его m-й по величине записи, вполне подходит (мне действительно нужен индекс m чисел, которые не больше, чем m ^ самая большая записьd).

Я пробовал (наивно):

float hst(VectorXf& d,int& m){
//  VectorXf d = VectorXf::Random(n);
    std::nth_element(d.data().begin(),d.data().begin()+m,d.data().end());
    return d(m);
}

, но есть две проблемы:

1. не работает
2. , даже если это сработало, мне все равно придется один раз передать (копию) d, чтобы найти индексы тех записей, которые меньше d (m).Это необходимо?

Best,

Answer 1

std::nth_element - это то, что вы хотите (вопреки тому, что я говорил ранее).Это делает частичное, так что элементы в диапазоне [first, mth) меньше, чем элементы в диапазоне [mth, last).Поэтому после выполнения nth_element все, что вам нужно сделать, скопировать первые m элементы в новый вектор.

VextorXf d = VectorXf::Random(n);
VectorXi d_prim(m);

std::nth_element(d.data().begin(), d.data.begin() + m, d.data().end());
std::copy(d.data().begin(), d.data().begin() + m, d_prim.begin());

Этот ответ содержит больше информации об алгоритмах для этого.

Answer 2

Собрав воедино ответы Дэвида Брауна и Керрека, я получил это «самое эффективное предложение»:

VectorXi hst(VectorXf& d,int& h){
    VectorXf e = d;
    VectorXi f(h); 
    int j=0;
    std::nth_element(d.data(),d.data()+h,d.data()+d.size());
    for(int i=0;i<d.size();i++){
        if(e(i)<=d(h)){
            f(j)=i;
            j++;
        if(j==h) break; 
        } 
    }
    return f;
}