-1

I was solving a question related to maximum sum of adjacent elements. I solved it recursively and tried to solve using tabulation as well but didn't succeeded in that. I went on internet and found a code which was working flawlessly but there i found a case in which we were tryin to accessing a negetive index inside a vector. As far as i know, it must had given me an error but it was running fine.

code for refrence:

int maximumNonAdjacentSum(vector<int> &nums){
    int n = nums.size();
    vector<int> table(n+1,0);
    table[0] = nums[0];
    for(int i=1;i<=n; i++){
        table[i] = max(nums[i]+table[i-2],table[i-1]);
    }
    return table[n];
}
trincot
  • 317,000
  • 35
  • 244
  • 286
Hiten Vats
  • 27
  • 1
  • 2
    _"As far as i know, it must had given me an error but it was running fine."_ No, it's just _undefined behavior_, which includes that apparently. – πάντα ῥεῖ Oct 13 '22 at 10:22
  • In many cases, using code you find on the internet is like eating food you find lying in the street. – molbdnilo Oct 13 '22 at 10:24
  • The answer to question title is more like, you can write code to do it, but you can't tell what the code actually does. – hyde Oct 13 '22 at 10:34
  • A more general answer is, negative indexes are fine as long as they access the same array, that is as long as the array has valid negative indexes. This is never true with `std::vector`, but it can be true if you have a pointer to C array, which points to somewhere else than the beginning of the _actual_ array object. – hyde Oct 13 '22 at 10:35
  • Refer to [how to ask](https://stackoverflow.com/help/how-to-ask) where the first step is to *"search and then research"* and you'll find plenty of related SO posts for this. For example, [dupe1](https://stackoverflow.com/questions/47170740/c-negative-array-index) and [dupe2](https://stackoverflow.com/questions/1239938/accessing-an-array-out-of-bounds-gives-no-error-why). These things are also explained any [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Jason Oct 13 '22 at 10:37
  • Read this and think about this for a while : [No raw loops](https://belaycpp.com/2021/06/22/dont-use-raw-loops/) – Pepijn Kramer Oct 13 '22 at 11:17
  • It's indeed dependent on the container type. `std::map Map` has no problem at all with `Map[-1] = "Minus One"`. – MSalters Oct 13 '22 at 14:44

1 Answers1

2

You're probably running in Release mode, which doesn't throw a "vector subscript out of range" assertion.

For std::vector, and many other types of arrays, the operator [] takes an unsigned number, which mean signed numbers will be explicitly converted to unsigned. -1 will be 0xffffffff, -2 will be 0xfffffffe and so on.

In this case, the item you're trying to access is way beyond the actual size of the vector, but it just happens to be in readable memory region so it gives you garbage value instead of a seg fault.

thedemons
  • 1,139
  • 2
  • 9
  • 25
  • 2
    actually though the index is an unsigned number you'll actually end up with an address that is before the start of the array (though this is all undefined behaviour), e.g. if you are on a 32-bit system and your array is at address `0x0000 1000` then passing an index of `-1` returns an address of `0x0000 1000 + 0xFFFF FFFF` which overflows to `0x0000 0FFF` – Alan Birtles Oct 13 '22 at 10:56
  • 1
    Minor point: throwing a "`'vector subscript out of range'` assertion" is compiler-specific. Formally, the behavior is undefined. +1. – Pete Becker Oct 13 '22 at 12:42
  • @AlanBirtles you're right, I was actually thinking about that and opened up the assembly code to see what is the address being read and it overflow back to the address before the start of the array – thedemons Oct 14 '22 at 02:11
  • @PeteBecker thanks for the info! I didn't know about that, it would be a nightmare trying to find the bug without the assertion – thedemons Oct 14 '22 at 02:14