Wikipedia:Reference desk/Archives/Computing/2023 June 30

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 30

Weird behaviour of end() in c++ vector

Well, I don't know whether this is correct forum. But I tried Stack Overflow and they told me to read references and pointed to my bad coding practices but did not answer actual question. Problem is thaat arr.end() is behaving weirdly. Usual behaviour is that it should point after the last element, which it does before entering into if condition. But after if statements (and deletions inside it) it points to last element which is giving problems. ALso, I know dereferencing end() is undefined, but it actually is giving me last element which is weird, and I want to fix it and learn from it

[1]link to original question

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

    ll N,K;

    cin >>N >>K;    

    vector<ll> arr(N);

    for(ll i=0;i<N;++i){

        cin>>arr[i];

    }  

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

    ll cnt=0;

   

        auto itr = arr.begin();

        auto temp = arr.begin()+1;

        cout<<*arr.end();

        while(temp!=arr.end() && arr.size()!=2 && arr.size()!=3){


            cout<<" "<<*arr.end()<<" ";

            if(*temp >= *itr + K ){

                temp = arr.erase(temp);

                itr = arr.erase(itr);

                ++cnt;                                 cout<<*arr.end()<<"  ";

            }

            else{

                ++temp;

            }

        }

    cout<<cnt;

} 2409:408D:4E99:46F1:B8F9:E360:B91A:14FF (talk) 2409:408D:4E99:46F1:B8F9:E360:B91A:14FF (talk) 10:15, 30 June 2023 (UTC)

arr.end() is _not_ an iterator to the end of the array; it's an iterator to one-past-the-end-of-the array. It's illegal to deference ::end() LongHairedFop (talk) 18:28, 1 July 2023 (UTC)

I asked our computer support person and he stated that end is one past the end of the array, which contains whatever it contained when it was last used. His example was that if I had an array of 1, 2, 3, 4 and I moved the end pointer from one past 4 to one past 3, then end would be one past 3, which contains 4. I barely understand it. Does that make sense in relation to this issue? 97.82.165.112 (talk) 14:19, 7 July 2023 (UTC)

The thing you have to remember about undefined behavior is that it's allowed to do anything. That makes it easier to write an optimizing compiler, because the compiler can treat a wide range of situations any way that's fastest or most convenient. Then the burden is on the programmer to avoid these situations.

So dereferencing end() is not necessarily giving you the last element here; it might be, for example, that for whatever reason the vector is being represented in memory with the last element duplicated, and you're seeing that duplicate. I don't know why that would be faster, but it's hard to exclude that there could be a reason. In any case you just are not supposed to do that. --Trovatore (talk) 17:44, 7 July 2023 (UTC)

It occurs to me my wording was a little unfortunate here. I don't mean the compiler cares about returning the fastest result in the case of undefined behavior. I mean it doesn't care what happens in the case of undefined behavior. It only cares about getting the result fastest in the case of defined behavior, and if that means doing something that will result in nearly undectectable Heisenbugs in the undefined-behavior case, then that's what it will do. --Trovatore (talk) 18:18, 7 July 2023 (UTC)