STL sort problem

[optimumph]

I'm trying to sort an array of numbers in ascending order and don't know whats wrong with my code (I'm completely new to vectors). I should first copy the input array (data) into an STL vector, then apply STL’s sorting algorithm to the vector, and finally copy the vector back into the array.

void STLSort(int data[],int size)
{
    vector<int> a1;
    a1.reserve(size);
    for(int i=0;i<size;i++)
        a1[i]=data[i];
    sort(a1.begin(),a1.end());
    for(int i=0;i<size;i++)
        data[i]=a1[i];
}

Thanks.

[mzimmers]

The problem is that end() isn't what you think it is; I think it's a sentinel node, but in any event, it's not a valid data element. You can replace it with:

sort(a1.begin(), a1.begin() + size - 1);

I'm looking into a better way to do it, without needing to be given the size of the array.

[mzimmers]

Well, I'm out of ideas. I've created two sorts that look identical to me. One works, the other hangs. Someone smarter than I am is going to have to explain this one.

#include <vector>
#include <algorithm>

using namespace std;

void STLSort(int data[],int size)
{
	vector<int> a1;
	vector<int>::iterator last;
	a1.reserve(size);
	for(int i = 0; i < size; i++)
		a1[i] = data [i];

	last = a1.begin() + a1.size() - 1;

	sort(a1.begin(), a1.begin() + size - 1);	// works
	sort(a1.begin(), last);	// hangs

	for(int i = 0; i < size; i++)
		data[i] = a1[i];
}

int main ()
{
	int myArray[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int size = 10;

	STLSort(myArray, size);

	return 0;
}

[stereomatching]

a1.reserve(size);
for(int i = 0; i < size; i++)
a1[i] = data [i];

reserve do not same as resize, reserve only change the capacity
but not the size of the vector

besides, you don't need to calculate the position of "past the end"
just write this

std::sort(A.begin(), A.end() );

[mzimmers]

stereomatching -

Thanks for the correction. Interesting about the sort accepting a1.end; from this page:

http://www.cplusplus.com/reference/stl/vector/end/

I'd have thought that it would fail, since the 2nd parameter of sort is supposed to be the last element to sort (which is not the same as the end of a vector). But...it works.

[stereomatching]

I'd have thought that it would fail, since the 2nd parameter of sort is supposed to be the last element to sort (which is not the same as the end of a vector). But...it works.

In the world of generic programming, we need some flag to inform us "it is the end"
Past the end position is what we need to inform us "it is the end"
It is just a convenient flag in the world of GP
you could look at the implementation of find
htp://www.cplusplus.com/reference/algorithm/find/
then you would know why they choose past the end position as the flag

If there are any mistakes, please correct me
I study GP by books and Internet but not from formal courses
I can't guarantee it is 100% correct

[mzimmers]

Everything you say makes sense. I just found it odd that an algorithm that needs to be told the start and the end of the data (like sort) would expect the end to be beyond the final valid element. But, your position is supported by the results of the program, so I'm inclined to believe you're right.

[arkoenig]

Everything you say makes sense. I just found it odd that an algorithm that needs to be told the start and the end of the data (like sort) would expect the end to be beyond the final valid element. But, your position is supported by the results of the program, so I'm inclined to believe you're right.

Every STL algorithm that deals with a range expresses the range as a pair of iterators. The first iterator locates the first element in the range; the second is one past the last element.

When I say "first element" and "last element," I am generalizing that to mean "where the first/last element would be if there were one" if the sequence is empty.

There are three reasons that the second iterator points one past the last element of the range:

1) That technique allows you to express an empty range by giving the same value for the two iterators. If the second iterator pointed at the last element, you would need to have the second iterator pointing *before* the first one.

2) The technique makes it possible to use the following pattern for accessing all of the elements in the range: for (iter it = begin; it != end; ++it) { /* process an element */ } I invite you to try to figure out how you would accomplish this if "end" pointed directly to the last element rather than one before it. Be sure to handle correctly the case where there are no elements.

3) If the iterators are random-access iterators, and therefore support arithmetic, you can use end-begin to compute the number of elements in the sequence.

[arkoenig]

Interesting about the sort accepting a1.end; from this page:

http://www.cplusplus.com/reference/stl/vector/end/

I'd have thought that it would fail, since the 2nd parameter of sort is supposed to be the last element to sort (which is not the same as the end of a vector).

Where does it claim that? I couldn't find it.

[mzimmers]

Arkoenig:

Thanks for the explanation; that does make good sense. Regarding my comment above, that was based on a premise that I now know to be incorrect, namely, that the sort() expected the second argument to be the logical end of the vector, not the "real" end.

Clearly, I didn't add much to this discussion; I'll be more careful in the future.