c++ reverse iterator and eigen

Question

I have been using J.F. Sebastian's implementation of the kth order statistic of two sorted arrays with some success.

Basically, this algorithm takes as input two sorted arrays A and B of length la and lb and returns the k^th largest element of their union in log(la)+log(lb) times.

However, in my application, in some case A will be sorted in decreasing order. Fortunately, i know in advance what these cases are. So i can always do:

(A.data() and A.data()+A.size() are eigen-constructs for A.begin() and A.end() respectively).

if(normal case){               
   sol=nsmallest(A.data(),A.data()+A.size(),B.data(),B.data()+B.size(),k,std::less<float>());
   std::cout << sol << std::endl;
}

and cases where the A's are sorted in decreasing order:

if(case with reverted sorted A){
   std::reverse(A.data(),A.data()+A.size());                    
   sol=nsmallest(A.data(),A.data()+A.size(),B.data(),B.data()+B.size(),k,std::less<float>());
   std::cout << sol << std::endl;
}

This works [ :) ] but looks overly complicated [ :( ] and (i suspect) inefficient, specially because i need to revert A to it's original order at the end.

I've tried to replace std::reverse above by

typedef std::vector<float>::iterator iter_int;

....

iter_int begin (x.segment(0,i).data());                                                         
iter_int end (x.segment(0,i).data()+x.segment(0,i).size());                                              
std::reverse_iterator<iter_int> rev_end(begin);     
std::reverse_iterator<iter_int> rev_iterator(end);

but this causes g++ to cringe:

error: no matching function for call to ‘nsmallest(std::reverse_iterator<__gnu_cxx::__normal_iterator<float*, std::vector<float> > >&, std::reverse_iterator<__gnu_cxx::__normal_iterator<float*, std::vector<float> > >&, Eigen::PlainObjectBase<Eigen::Matrix<float, -0x00000000000000001, 1> >::Scalar*, Eigen::PlainObjectBase<Eigen::Matrix<float, -0x00000000000000001, 1> >::Scalar*, int&, std::less<float>)’
nosix.cpp:62:93: note: candidate is:
nosix.cpp:19:5: note: template<class RandomIterator, class Compare> typename std::iterator_traits<_InputIterator>::value_type nsmallest(RandomIterator, RandomIterator, RandomIterator, RandomIterator, std::size_t, Compare)

and i don't know how to fix it.

but this doesn't give the expect result :!

#include <algorithm>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <cassert>
#include <iterator>

#include <Eigen/Dense>
using namespace Eigen;
using Eigen::VectorXf;
using Eigen::VectorXi;
typedef std::vector<float>::iterator iter_int;   
template<class RandomIterator,class Compare>
typename std::iterator_traits<RandomIterator>::value_type
nsmallest(RandomIterator firsta,RandomIterator lasta,RandomIterator firstb,RandomIterator lastb,size_t n,Compare less) {
    assert(n<static_cast<size_t>((lasta-firsta)+(lastb-firstb)));
    if (firsta==lasta) return *(firstb+n);
    if (firstb==lastb) return *(firsta+n);

    size_t mida=(lasta-firsta)/2;
    size_t midb=(lastb-firstb)/2;
    if ((mida+midb)<n)
        return less(*(firstb+midb),*(firsta+mida))?
        nsmallest(firsta,lasta,firstb+midb+1,lastb,n-(midb+1),less):
        nsmallest(firsta+mida+1,lasta,firstb,lastb,n-(mida+1),less);
    else
        return less(*(firstb+midb),*(firsta+mida))?
        nsmallest(firsta,firsta+mida,firstb,lastb,n,less):
        nsmallest(firsta,lasta,firstb,firstb+midb,n,less);
}
int main(){  
    int p,q,n,k,l;
    float sol;
    std::cout << "enter p " << std::endl;
    std::cin >> p; 
    std::cout << "enter q " << std::endl;
    std::cin >> q;
    n=p+q;
    std::cout  << " enter k (>=) " << std::min(p,q) << " & <= " << n-1 << std::endl;
    std::cin >> k;

    srand(time(NULL));
    VectorXf v1=VectorXf::Random(p);
    srand(time(NULL));
    VectorXf v2=VectorXf::Random(q);
    VectorXf v3(n);
    v3 << v1, v2; //eigen-concatenation of vectors
    std::sort(v3.data(),v3.data()+v3.size()); 
    std::sort(v1.data(),v1.data()+v1.size(),std::greater<float>());
    std::sort(v2.data(),v2.data()+v2.size());
    //this gives the intended result:
    std::reverse(v1.data(),v1.data()+v1.size());   
    //this doesn't :(
    /*
    iter_int begin (v1.data()); 
    iter_int end (v1.data()+v1.size());  
    std::reverse_iterator<iter_int> rev_end(begin); 
    std::reverse_iterator<iter_int> rev_iterator(end); 
    sol=nsmallest(rev_iterator,rev_end,v2.data(),v2.data()+v2.size(),k,std::less<float>()); 
    /**/
    sol=nsmallest(v1.data(),v1.data()+v1.size(),v2.data(),v2.data()+v2.size(),k,std::less<float>());
    //if it works, these two should return the same.
    std::cout << sol << std::endl;  
    std::cout << v3(k) << std::endl;
    return 0;  
}

score 3 · Accepted Answer · answered Jul 28 '12 at 20:59

3

Your nsmallest function requires that the first 4 parameters be of exactly the same type.

Try this instead:

template<class RandomIteratorA, class RandomIteratorB, class Compare>
typename std::iterator_traits<RandomIteratorA>::value_type
nsmallest(RandomIteratorA firsta,RandomIteratorA lasta,RandomIteratorB firstb,RandomIteratorB lastb,size_t n,Compare less) {
...
}

answered Jul 28 '12 at 20:59

JoeG

12,994
1
38
63

Awesome: it works on the small example above (i'll be forever clueless as to these more advanced c++ structures but your patch fixed it for me). – user189035 Jul 28 '12 at 21:08

c++ reverse iterator and eigen

1 Answers1