私は、JFセバスチャンによる2つのソートされた配列のk次統計量の実装を使用しており、ある程度の成功を収めています。
基本的に、このアルゴリズムは、長さlaとlbの2つのソートされた配列AとBを入力として受け取り、それらの和集合のk番目に大きい要素をlog（la）+ log（lb）回返します。
ただし、私のアプリケーションでは、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;
}
これは[:)]動作しますが、非常に複雑に見えます[:(]と（おそらく）非効率的です。特に、最後にAを元の順序に戻す必要があるためです。
std::reverse上記を次のように置き換えようとしました
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;
}