Using STL Sort within a template function?

Question

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.

Armen Tsirunyan · Accepted Answer · 2011-07-22 14:00:18Z

2

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.

edited Jul 22, 2011 at 14:00

Armen Tsirunyan

134k61 gold badges336 silver badges442 bronze badges

answered Jul 22, 2011 at 13:39

John Humphreys

39.7k44 gold badges167 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Joe Over a year ago

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

Pierre Thierry Over a year ago

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

John Humphreys Over a year ago

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.

Pierre Thierry Over a year ago

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

John Humphreys Over a year ago

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

Pierre Thierry · Accepted Answer · 2011-07-22 13:38:55Z

2

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)

answered Jul 22, 2011 at 13:38

Pierre Thierry

5,1093 gold badges31 silver badges46 bronze badges

2 Comments

Joe Over a year ago

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.

Pierre Thierry Over a year ago

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.

Armen Tsirunyan · Accepted Answer · 2011-07-22 13:28:01Z

1

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

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

answered Jul 22, 2011 at 13:28

Armen Tsirunyan

134k61 gold badges336 silver badges442 bronze badges

1 Comment

Joe Over a year ago

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.

Collectives™ on Stack Overflow

Using STL Sort within a template function?

3 Answers 3

5 Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related