Armadillo, Template, and STL

[Maji]

Hi C++ experts

I'm trying to create a set intersection / union function for armadillo vectors.
Below are my functions and it works.
But it's clunky and there must be a better way.
Please mesmerize me with your super skills.

There are at least 2 problems.
First problem is, because I can't directly put the set_intersection, set_union result into a armadillo vector I have to put it in a stl vector.

Second, because I have to put it in a vector, I need the type of the vector separately specified when making a function call since I don't know how to access the type information of a vector.

Thanks for your advice!
-------------------------------------------------------
template< class Vector, class Type >
Vector vintersection( Vector first, Vector second )
{
std::vector<Type> output;
std::set_intersection(first.begin(),first.end(),second.begin(),second.end(),std::inserter(output,output.begin()));
vec result=conv_to<Vector>::from(output);
return(result);
}

template< class Vector, class Type >
Vector vunion( Vector first, Vector second )
{
std::vector<Type> output;
std::set_union(first.begin(),first.end(),second.begin(),second.end(),std::inserter(output,output.begin()));
vec result=conv_to<Vector>::from(output);
return(result);
}

// test
vec first = randu(5);
first.resize(first.n_elem+2);
first(first.n_elem-2)=99.0;
first(first.n_elem-1)=44.0;
vec second = randu(5);
second.resize(second.n_elem+2);
second(second.n_elem-2)=99.0;
second(second.n_elem-1)=44.0;
vec t2 = vintersection<vec,double>(first, second);
t2.print("t2");
vec t3 = vunion<vec,double>(first, second);
t3.print("t3");

[rollie]

Not familiar with armadillo - what happens if you do:

vec first = randu(5);
vec seconds = randu(5);
// init
vet output;
std::set_intersection(first.begin(), first.end(), second.begin(), second.end(), std::inserter(output,output.begin()));

Also, a performance note: returning a 'Vector' from your vunion and vintersection functions could be dangerous, as you are potentially copying the entire vector from the local output variable to a temporary, and finally to some vec in the calling code. Better to simply have the output as a parameter of each function (which would need to be a reference to work). Also, similarly, you can take 'const Vector & first, const Vector & second' as the inputs to both of your functions, to further cut down on potentially expensive copying of containers. If you know your vectors implement move constructors and you are using a c++11 compiler, you can ignore the return optimization.

[JLBorges]

> Also, a performance note: returning a 'Vector' from your vunion and vintersection functions could be dangerous,
> as you are potentially copying the entire vector from the local output variable to a temporary,
> and finally to some vec in the calling code.

One would expect a reasonable C++ compiler to apply RVO.
http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/



> Second, because I have to put it in a vector, I need the type of the vector separately specified
> when making a function call since I don't know how to access the type information of a vector.

If any one of these is a possibility, it would allow you to write:
vec t2 = vintersection( first, second ) ;

// armadillo vector is a C++ standard library compatible sequence container
template< typename ARMA_VECTOR_TYPE > 
ARMA_VECTOR_TYPE vintersection( ARMA_VECTOR_TYPE first, ARMA_VECTOR_TYPE second )
{
    ARMA_VECTOR_TYPE result ;
    std::set_intersection( first.begin(), first.end(), second.begin(), second.end(),
                           std::back_inserter(output) ) ;
    std::reverse( result.begin(), result.end() ) ;                       
    return result ;
}

// armadillo vector has a nested typedef 'value_type'
template< typename ARMA_VECTOR_TYPE >
ARMA_VECTOR_TYPE vintersection( ARMA_VECTOR_TYPE first, ARMA_VECTOR_TYPE second )
{
    std::vector< typename ARMA_VECTOR_TYPE::value_type > output ;
    std::set_intersection( first.begin(), first.end(), second.begin(), second.end(),
                           std::back_inserter(output) ) ;
    std::reverse( output.begin(), output.end() ) ;   
    
    ARMA_VECTOR_TYPE result = conv_to< ARMA_VECTOR_TYPE >::from(output);
    return result ;
}

// armadillo vector has just one template type parameter
template< typename T, template <typename> class ARMA_VECTOR_TYPE >
ARMA_VECTOR_TYPE<T> vintersection( ARMA_VECTOR_TYPE<T> first, ARMA_VECTOR_TYPE<T> second )
{
    std::vector<T> output ;
    std::set_intersection( first.begin(), first.end(), second.begin(), second.end(),
                           std::back_inserter(output) ) ;
    std::reverse( output.begin(), output.end() ) ;   
    
    ARMA_VECTOR_TYPE<T> result = conv_to< ARMA_VECTOR_TYPE<T> >::from(output);
    return result ;
}

[rollie]

Did some testing, and after turning on a few compiler switches I saw the benefit of the elision. Very cool! I knew some copies were optimized out, but never that it went quite that far (definitely different from what I had learned). Thanks for the article.

[Maji]

Wow thanks guys!

2nd and 3rd algorithm of JLBorges works perfectly.
You've taught me valuable skills for templates.
Specially the 3rd one. I didn't know you can do such a thing.
Awesome!

I had problem with the 1st of JLBorges and Rollie's algorithm though.
The compiler wouldn't allow for std::back_inserter or std::inserter of armadillo vector objects for some reason.
It may be the setting I have.

Anyway you guys are fantastic!
Have a nice day.

[clanmjc]

@JLBorges very nice post, #3 I myself haven't used and look forward to playing with it tomorrow.