c++ - Passing beginning and ending positions of an array

Question

I see that many functions require the beginning and ending positions of an array/vector. I have two doubts, one in arrays and the second in vectors:

1. This code

#include<iostream>
using namespace std;

int main(){

int arr[4] = {5, 3, 4, 7};
sort(begin(arr), end(arr));
for(int& x : arr) cout << x << " ";
return 0;
}

is fine as .begin() and .end() return the pointers to the first and last elements of the array respectively (btw please correct me if I am wrong anywhere).

But please explain how this code works:

#include<iostream>
using namespace std;

int main(){
int arr[4] = {5, 3, 4, 7};
sort(arr, arr + 4);
for(int& x : arr) cout << x << " ";
return 0;
}

---

2. I understand if you want to sort (or perform any other function on) the whole vector, you can use .begin() and .end().

But what if you want to sort only a portion of the vector? Like the vector between left position L and right position R. How would you do that by using .begin and .end only (without slicing the vector)?

Thanks a lot!

question from:https://stackoverflow.com/questions/66047956/passing-beginning-and-ending-positions-of-an-array

Answer 1

In your first example you should have written.

sort(begin(arr), end(arr));

because int[] is a builtin-type (from C) and does not have any member-function. There exists overloads of std::begin() and std::end() suitable for T[] as shown above.

In C, using just the name of an array is an expression that decays to the beginning of this array. For example, in:

int arr[4] = {5, 3, 4, 7};
int *p = arr;

p is a pointer initialised with the address of the first element in the array. It is equivalent to

int *p = &(arr[0]);

Moreover, in C, there exists something called pointer-arithmetic. This means that you can increment, decrement, compute the difference... with pointers. Here, p+4 means the pointer which relates to the fourth element after the one pointed-to by p; in this specific example, it is just after the end of your array. So, back to your second example, arr is equivalent to begin(arr) and arr+4 is equivalent to end(arr).

We should not know any details about the exact nature of the iterators returned by std::begin() and std::end(); the only thing we know is that they behave as metaphors of pointers, in order to tell where an element is, to move to the next element... But when the storage for these elements is a contiguous portion of memory (like T[], std::array<T>, std::vector<T>...), internaly they are nothing more than pointers (we should not know... but we know ;^) Moreover, in this specific contiguous storage case, a plain-true-real pointer is the perfect metaphor for a pointer... That's why std::sort() that was designed with iterators in mind also works with simple pointers as arr and arr+4.

You might be puzzled by the fact that the end position points-to a non-existing element (right after the last element in the array). This is a convention for many algorithms: we specify a half-open interval, the first bound is included, the second bound is excluded. So the algorithm will never access this one-step-too-far element; it will stop just before reaching it. This is consistent with the classical for() loop: imagine you want five iterations, you will write for(int i=0; i<5; ++i) to specify 0 and 5 as bounds, but you will actually use the values 0, 1, 2, 3, 4 but NOT 5.

When it comes to sorting just a portion of the array, you can use arithmetic on pointers or on iterators.

std::sort(std::begin(arr)+L, std::end(arr)-R);
std::sort(arr+L, arr+4-R);

assuming L and R are the number of elements you don't want to sort on each extremity of the array.