accessing unallocated memory while sort from algorithm stl c++

Question

while I was going through stl today, I came across a situation where to sort my dynamically allocated array from arr[0],,..arr[n-1]. I was using command

#include<algorithm>
.
.
int *arr = new int[n]();
//loop to take user input for each arr[i]
sort(&arr[0],&arr[n])

The above command was sorting the array without any error, even if I have allocated memory up to arr[n-1].

The below command was sorting upto n-1th element.

#include<algorithm>
.
.
int *arr = new int[n]();
//loop to take user input for each arr[i]
sort(&arr[0],&arr[n-1])

How was '&arr[n]' working in the 1st code snippet.

I don't understand the problem. With n, it sorts n elements, with n-1, it sorts only n-1, ok, so what? The situation where you access n elements with only n-1 allocated is UB. — deviantfan, Nov 04 '15 at 22:25
Can't you read the documentation for `std::sort`? Is that kind of thing not allowed anymore? — juanchopanza, Nov 04 '15 at 22:32

score 2 · Answer 1 · answered Nov 04 '15 at 22:56

STL algorithms use "half-open" ranges. That means it includes the first element and works up to--but not including--the last element. Given:

std::sort(&arr[0], &arr[n]);

The sort function will sort the elements from 0 to n - 1. It will never try to look in arr[n].

In C and C++, it's legal to create a pointer to the first element beyond the end of an array, but you cannot dereference that pointer.

When you changed the call to:

std::sort(&arr[0], &arr[n-1]);

you introduced a bug, since this will ignore the last element in the array when sorting.

Using half-open ranges (or intervals) is pretty natural given that arrays are indexed from 0.

score 0 · Answer 2 · answered Nov 04 '15 at 22:26

0

Arrays are 0 indexed in C++. If you have n elements then the first index is 0 and the last is n-1.

It was working because it's undefined behavior. It can do anything. Often what happens is you just overwrite some variable on the stack with nonsense. If it's the right variable this can allow someone to overload that buffer with targeted nonsense and cause code to be executed. It's called a "buffer overrun" and you need to avoid them.

answered Nov 04 '15 at 22:26

Edward Strange

40,307
7
73
125

so the arr[n] which I am passing here, can show error sometime? – Uchiha_itachi Nov 04 '15 at 22:31
2

`&arr[n]` is not undefined behavior because `(arr) + n` is valid as long as you avoid to dereference it (see clause 5.7 in the C++ standard). Thus, using std::algorithm with C arrays is usually valid. – bjhend Nov 04 '15 at 22:38
I was confused about what's going on but unless they changed it in C++11 or up, `&arr[n]` is undefined because there IS a dereference there. They legalized it in C so maybe C++ absorbed that change. – Edward Strange Nov 04 '15 at 22:57
@Crazy Eddie: &arr[n] is the address after the last array element. It doesn't dereference anything. It's been that way since C90. – David Thornley Nov 04 '15 at 23:01
See litb's comment here: http://stackoverflow.com/questions/3144904/may-i-take-the-address-of-the-one-past-the-end-element-of-an-array/3144915#3144915 – Edward Strange Nov 04 '15 at 23:38

accessing unallocated memory while sort from algorithm stl c++

2 Answers2