Stack Exchange
Using STL Sort within a template function?
I have tried to create a template function that does some weighted sampling within a Monte Carlo simulation.  It is below.  input_data will either be a statically-allocated array (i.e. data[33]), a dynamically-allocated array, or a vector.
template <class myType>
int init_roulette_calcs(myType &input_data, int inputlength, int *(&output_cdf), int highclassix, int weight)
{
        sort(input_data, input_data + inputlength); //where the error occurs

        //other code:
        output_cdf = new int [inputlength];
        int k = 1;
    for (int i = 0; i < inputlength; i++)
    {
        output_cdf[i] = k;
        if (i+1 < highclassix) k++;
        else    k += weight;
    }
    return output_cdf[inputlength-1];
}

The code will not compile because the template function could not deduce the argument for the call to sort.  This may be a stupid question, but what do I need to do to ensure that sort can work properly?
Error   4   error C2784: 'std::_Vb_iterator<_Alloc> std::operator 
+(_Alloc::difference_type,std::_Vb_iterator<_Alloc>)' : could not deduce template argument for 
'std::_Vb_iterator<_Alloc>' from 'int'  j:\rdm\lrgv_2011-07-21\lrgv_src\lrgv.h  398

Thanks in advance for your help.

If you put in an array, the array name is essentially a pointer to the first element, and the array name + x is the poitner to the xth element - so you have this part correct.
The problem is that this is not the case for a vector, which is why you need to use the .begin() and .end() functions to get the pointer to these locations.
You could try sorting by pulling the addresses of the dereferenced start/end elements - that might let you treat a vector the same as an array.

Thanks. I'll have to handle the vectors differently.

You should never treat an STL iterator as a raw pointer, or you code may break on some implementations.

I agree with that statement - vector implementations are defined as using contiguous memory in the standard though, so addressing them with pointer arithmetic shouldn't yield problems.  It's defintely not good practice with STL containers in general though - especially since iterators can be invalidated by container operations in midst of use.

Using contiguous memory is only the classical implementation, but by no means the definition in the standard.

Oh, thanks for the info - someone told me that in response to a post once and I guess I never double checked it :(

In your code, input_data is a reference, but sort would need it to be a pointer to the start of an array. It should be:
int init_roulette_calcs(myType input_data[], int inputlength, …

Although it would be proper STL usage to make such a template that the user can provide any kind of random access begin and end iterators instead. Thus you could later switch to a vector or any other container that sort can work on…
template <class InputIterator>
int init_roulette_calcs(InputIterator begin, InputIterator end, int *(&output_cdf), int highclassix, int weight)


Thanks for this.  Two questions: (1) That seems to work for dynamically and statically allocated arrays, but it doesn't work for stl vectors. (2) If I change the argument list to what you've suggested, will the data still be sorted when I exit the function?  I was under the impression that if I passed by value like that, the data would not remain modified after exiting the function.  That's why I was using a reference in the first place.

The first version is indeed tailored for arrays, but the second one should work with any STL container with random access, thus including vectors. Also, you have to understand what you pass by value or reference. When you pass a pointer by value, you pass a copy of the pointer, not a pointer to a copy of the array. Same for an STL container: when you pass an iterator by value, your function sees a copy of the iterator, that lets it interact with the original container, not a copy.

sort(&input_data, &input_data + inputlength);
    ^^^          ^^^    

I hope the argument you're passing is actually a reference to the first element in an array.

Can you elaborate a bit?  I tried passing in the first element of an array as the argument into the function and I got many errors.
