using std::nth_element in eigen and a related interrogation

Question

I'm teaching myself c++ and eigen in one go, so maybe this is an easy question.

Given n and 0 "<" m "<" n, and an n-vector d of floats. To make it concrete:

VectorXf d = VectorXf::Random(n)

i would like to have a m-vector d_prim onf integers that contains the indexes of all the entries of d that are smaller or equal than the m-th largest entry of d. Efficiency matters. if there are draws in the data, then filling d_prim the first m entries of d that are smaller than its m-th largest entry is fine (i really need the index of m numbers that are not larger than the m^th largest entry of d).

I've tried (naively):

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);
}

but there is two problems with it:

1. it doesn't work
2. even if it did work, i still have to pass over (a copy) of d once to find the indices of those entries that are smaller than d(m). Is this necessary?

Best,

Answer 1

std::nth_element is what you want (contrary to what I said before). It does a partial so that the elements in the range [first, mth) are less than those in the range [mth, last). So after running nth_element all you have to do copy the first m elements to the new vector.

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());

This answer has more info on algorithms to do this.

Answer 2

Putting together David Brown's and Kerrek SB answers i got this as "the most efficient proposal":

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;
}