How to remove an element in NumericVector for a recursion using R and Rcpp

Question

i was trying to learn more about how to use Rcpp package for R. So i started testing basic sorting algorithms using Rcpp. I was starting at Hadley Wickham tutorial here.

I successfully implemented insertion sort recursively this way:

library(Rcpp)

vetor<-sample(100)
vetor
cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
        double aux;
        int i;

        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }

        return vetor;
        }
    ")

But the function ask for 2 arguments, then i tried this way:

cppFunction("
    NumericVector insertionsortRC(NumericVector vetor) {
        int n = vetor.size();

        double aux;
        int i;

        if(n>1) {
            vetor.erase(n-1);
            insertionsortRC(vetor);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }

        return vetor;
        }
    ")

I think erase was not a good idea here, it seem that i erase the element from memory and cant recover it later, after the recursion call. I thought also that the problem could be on vetor.erase(n-1); line, tried vetor.erase(n); and it compiled, but didn't work at all.

With vetor.erase(n); i got the following error in R:

insertionsortRC(vetor) * Error in `/usr/lib/R/bin/exec/R': malloc(): memory corruption: 0x098db548 *

with vetor.erase(n-1); it got a strange output:

insertionsortRC(vetor) [1] 3.607393e-313 3.300000e+01 3.100000e+01 8.600000e+01 2.500000e+01 7.000000e+01 [7] 4.000000e+01 8.800000e+01 8.100000e+01 1.300000e+01 8.500000e+01 8.700000e+01 [13] 3.900000e+01 6.000000e+01 6.400000e+01 1.000000e+01 8.200000e+01 8.900000e+01 [19] 1.400000e+01 6.600000e+01 3.600000e+01 1.500000e+01 9.600000e+01 2.600000e+01 [25] 4.000000e+00 5.400000e+01 2.900000e+01 8.300000e+01 5.500000e+01 6.800000e+01 [31] 9.100000e+01 6.000000e+00 1.000000e+02 5.100000e+01 7.000000e+00 5.300000e+01 [37] 9.900000e+01 6.500000e+01 2.300000e+01 9.400000e+01 5.700000e+01 9.000000e+01 [43] 3.200000e+01 4.700000e+01 1.600000e+01 5.000000e+01 2.800000e+01 3.000000e+00 [49] 9.800000e+01 1.100000e+01 1.800000e+01 7.600000e+01 6.300000e+01 7.700000e+01 [55] 7.400000e+01 4.900000e+01 8.000000e+00 9.700000e+01 1.200000e+01 2.700000e+01 [61] 3.500000e+01 7.900000e+01 8.000000e+01 2.000000e+01 6.700000e+01 9.300000e+01 [67] 5.000000e+00 5.600000e+01 9.000000e+00 3.700000e+01 2.400000e+01 9.200000e+01 [73] 6.900000e+01 3.800000e+01 4.400000e+01 1.700000e+01 4.600000e+01 4.300000e+01 [79] 3.400000e+01 1.900000e+01 2.000000e+00 9.500000e+01 7.200000e+01 1.000000e+00 [85] 6.100000e+01 4.100000e+01 6.200000e+01 2.200000e+01 4.200000e+01 2.100000e+01 [91] 8.400000e+01 4.800000e+01 7.800000e+01 7.300000e+01 3.000000e+01 5.900000e+01 [97] 5.800000e+01 5.200000e+01 7.500000e+01

Could someone tell me if: 01. Is it possible to implement this code, like this, using Rcpp and R, calling the function with only one argument, the vector of data? 02. How to do it correctly?

Answer 1

Briefly:

1. The good news is that you have your compilation working.

2. The not-so-good news is the segfault. Likely a logic error in your code.

3. In general, adding or removing to NumericVector etc is a bad idea. These are shallow types which directly connect to the R memory of the same object ("no copies"). This means extending or removing is costly. Consider using an STL std::vector<double>. All this is documented.

Answer 2

A few things:

vetor.erase(n) is undefined behavior. The first index is 0, the last is n-1. erase does not do bounds check because everybody would have to pay the price. Instead it assumes, as it is common in the C++ world that the function is used correctly.

Learn about std::sort. it is likely to be more efficient than home backed sort implementation, especially insertion sort.

Rcpp vectors have a sort method. So a NumericVectorcan sort itself.

Learn about attributes, i.e. with the Rcpp-attributes vignette, this is simpler to use and this will give you a way to deal with default arguments.

Answer 3

Try: vector.erase(vector.begin()+desiredElement)

That should take care of your problem.

The NumericVector type seems to be related to std::vector at least in the way it handles insertion and removal of data, which means that you have to use iterators (However, I am not an Rcpp guru).

Brian