1

I'm trying to adapt this c++ implementation of the famous kth element of two sorted array algorithm to my application (where the second array is sorted in increasing order). Now, I can see two solutions:

  1. replace the iterator to the elements of B (the second array) by a reverse_iterator,
  2. try to do it manually, e.g. replace the increments to the pointers of B by decrements.

Now, I started by trying 2) not so much out of liking but because I'm not so good with using reverse_iterator. However, the "solution" I have doesn't work. I was wondering how one should change the code of J.F. Sebastian to use a reverse iterator for the second array?

#include <cmath>
#include <ctime>
#include <functional>
#include <fstream>
#include <iostream>
#include <iterator>
#include <limits>
#include <vector>
#include <random>
#include <inttypes.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <numeric>

#define SIZE(a) (sizeof(a)/sizeof(*a))
#define NDEBUG 

using namespace std;
template<class RandomAccessIterator, class Compare>
typename std::iterator_traits<RandomAccessIterator>::value_type
nsmallest_iter(RandomAccessIterator firsta,RandomAccessIterator lasta,RandomAccessIterator firstb,RandomAccessIterator lastb,size_t n,Compare less){//https://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element-in-the-union-of-two-sorted-arrays/11698659#11698659 
    assert(std::is_sorted(firsta,lasta,less) && std::is_sorted(firstb,lastb,less));
    const float x_0=*firsta,x_1=*lastb;
    std::cout << x_0 << std::endl; 
    std::cout << x_1 << std::endl;
    for(;;){
        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){
            if(less(*(firstb+midb),*(firsta+mida))){
                firstb+=(midb+1);
                n-=(midb+1);
            } else {
                firsta+=(mida+1);
                n-=(mida+1);
            }
        } else {
            if(less(*(firstb+midb),*(firsta+mida))){
                lasta=(firsta+mida);
            } else {
                lastb=(firstb+midb);
            }
        }
    }
}

Relevant part of the main:

const int n=*nr,m=*mr,k=*kr-1;
int i;
float x[n];
srand (time(NULL));
for(i=0;i<n;i++)   x[i]=rand();
std::sort(x,x+m,std::greater<float>());
std::sort(x+m,x+n);
*vr=nsmallest_iter(x,x+m,x+m+1,x+n-1,n-2-k,std::greater<float>());
Community
  • 1
  • 1
user189035
  • 5,589
  • 13
  • 52
  • 112

1 Answers1

1

With reverse iterators, you need only some little adjustments to the code shown in the link you provided:

template<class RandomAccessIterator1, typename RandomAccessIterator2, class Compare>
typename std::iterator_traits<RandomAccessIterator1>::value_type
nsmallest_iter(RandomAccessIterator1 firsta, RandomAccessIterator1 lasta,
               RandomAccessIterator2 firstb, RandomAccessIterator2 lastb,
               size_t n,
               Compare less) {
   ...
}

and

int v = nsmallest_iter(
      a, a + SIZE(a),
      std::reverse_iterator<int*>(b + SIZE(b)), std::reverse_iterator<int*>(b),
      SIZE(a)+SIZE(b)-1-i,
      std::greater<int>());
Community
  • 1
  • 1