C++ reverse iterator和eigen

Question

我一直在使用J.F. Sebastian的implementation兩個排序數組的第k個順序統計，並取得了一些成功。

基本上，該算法將長度爲la和lb的兩個排序數組A和B作爲輸入，並以log（la）+ log（lb）次返回其聯合的第k個最大元素。

但是，在我的應用程序中，在某些情況下，A將按降序排序。幸運的是，我事先知道這些情況是什麼。所以我總是可以這樣做：

（A.data()和A.data()+A.size()分別爲A.begin（）和A.end（） ）的特徵構造。

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

和情況下，A的遞減順序進行排序：

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

這工作[:)]，但看起來過於複雜[:(]和（我懷疑）效率低下，特別是因爲我需要要還原到它在結束原來的順序。

我試圖通過

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

但這會導致G ++畏縮：

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) 

，我不知道如何解決它。

但這並沒有給出預期的結果：！

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

Answer 1

您的nsmallest函數要求前4個參數的類型完全相同。

試試這個：

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) { 
... 
}