Why does this supposedly infinite loop program terminate?

Question

I was talking to my friend about these two pieces of code. He said the python one terminates, the C++ one doesn't.

Python:

arr = [1, 2, 3]
for i in range(len(arr)):
  arr.append(i)
print("done")

C++:

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> arr{1,2,3};
  for(int i = 0; i < arr.size(); i++){
    arr.push_back(i);
  }
  cout << "done" << endl;
  return 0;
}

I challenged that and ran it on 2 computers. The first one ran out of memory (bad alloc) because it had 4gb of ram. My mac as 12gb of ram and it was able to run and terminate just fine. I thought it wouldn't run forever because the type of size() in vector is an unsigned int. Since my mac was 64 bit, I thought that it could store 2^(64-2)=2^62 ints (which is true) but the unsigned int for the size is 32 for some reason.

Is this some bug in the C++ compiler that does not change the max_size() to be relative to the system's hardware? The overflow causes the program to terminate. Or is it for some other reason?

@Scheff: `i < arr.size()` is the condition to *continue* the loop, not the condition to stop it. — user2357112, Apr 15 '20 at 05:14
The python version precalculates `range(len(arr))` to set the number of iterations, so is finite. The C++ version appends an element to `arr`, so `arr.size()` increases with every iteration. `i` is therefore always less than `arr.size()` so the loop will will keep going (until either memory is exhausted, or `i` overflows and causes undefined behaviour after which all bets are off as to what happens). Introduce a new variable like `size = arr.size()` before the loop, and change the termination condition to `i < size` and the loop will be finite. — Peter, Apr 15 '20 at 05:15
@user2357112supportsMonica So, I assume the wrap-around -> negative `int` implicitly converted to `size_t` (probably an unsigned 64 bit type) cause the termination. [**Demo on coliru**](http://coliru.stacked-crooked.com/a/468986bdb5b04311) — Scheff's Cat, Apr 15 '20 at 05:21
*Is this some bug in the C++ compiler* -- If a C++ compiler had such a bug in a toy program like this, they may be laughed out of the compiler business. — PaulMcKenzie, Apr 15 '20 at 05:31
The size of `unsigned int` is *Implementation defined* i.e. the compiler gets to pick. Both your compilers chose 32 bits. — Caleth, Apr 15 '20 at 08:41

Bathsheba · Answer 1 · 2020-04-15T05:36:27.867

There is not a bug in your C++ compiler manifesting itself here.

int is overflowing (due to the i++), the behaviour of which is undefined. (It's feasible that you'll run out of memory on some platforms before this overflow occurs.) Note that there is no defined behaviour that will make i negative, although that is a common occurrence on machines with 2's complement signed integral types once std::numeric_limits<int>::max() is attained, and if i were -1 say then i < arr.size() would be false due to the implicit conversion of i to an unsigned type.

The Python version pre-computes range(len(arr)); that is subsequent appends do not change that initial value.

Why does this supposedly infinite loop program terminate?

1 Answers1