A C++ Pitfall (or, respect Java)

It seems like a lot of programmers have been making fun of Java lately.  I'm also guilty of this; I teased badly about Java with a gal that just finished AP Computer Science A, who claims that she loves it.  (I regretted it later.  If you see this, sorry.)

This is not a healthy thing in general, and a reflection of contempt culture, and today, I am sharing an example of how this type of arrogance cost me.

The problem goes like this: I needed to enumerate the last $k$ elements of a std::vector in C++ in reverse order.  Thus, I did this [0]:

// vector<int> v; 
// int k; 
for (int i = v.size() - 1; i >= v.size() - k; i--) { 
    // v[i] 
}

... and it segfaulted with an access violation when $k=\texttt{v.size()}$. Why? [1]

std::vector::size is unsigned

As it turns out, std::vector::size() is unsigned.  A feature called type promotion causes v.size() - k to be evaluated as unsigned entirely, since v.size() is already unsigned.  When $k=\texttt{v.size()}$, it evaluates to an unsigned $0$.  This is fine...right?

Well, the type promotion mechanism also causes $i$ to be coerced to unsigned when performing the comparision i >= v.size() - k. Now, when $i=-1$, the comparision should stop the loop entirely, as we're no longer processing the last $k$ elements; however, type promotion converts $i$ to an unsigned integer (technically size_t, but for most modern systems it's just unsigned long).  Here, hilarity ensues, as an unsigned $-1$ does not exist, and is instead interpreted as a huge value (4,294,967,295 under 32-bit Linux! [2])  This allows the loop to continue and access v[4,294,967,295], at which point C++ just rage quits.

We can use explicit type coercions to fix the code like this:

// std::vector<int> v;
// int k; 
for (int i = (int)v.size() - 1; i >= (int)v.size() - k; i--) { 
    // v[i] 
}

... but this isn't very elegant, and may cause issues if one somehow has more than 2,147,483,647 elements (unlikely that you're still using vectors at this scale), or we can use modern C++'s std::ssize(std::vector v), which returns a signed integer and requires passing in the vector as a parameter, rather than calling on the vector itself.  This is only available in C++20:

// std::vector<int> v; 
// int k; 
for (int i = std::ssize(v) - 1; i >= std::ssize(v) - k; i--) { 
    // v[i] 
}

Either way should work.  In competitive programming, since we don't get C++20 on most platforms, the first approach is what I use.

Java

Now, how does Java avoid this issue entirely?  Its ArrayList class returns a signed integer for its size, so this issue is nonexistent. [3]

We now see why we should always be respectful of other languages; even when we joke about TerribleLanguageFactoryFactory, they do make good design decisions a surprisingly many amount of times.

[0] It's possible to use std::reverse() for it but then you have to reverse it back, and do an extra bit of math for the original index just to enumerate in reverse.  Thanks to Atri on Discord for suggesting this alternative approach.

[1] I already check for $k\gt\texttt{v.size()}$.

[2] I should probably not intimidate you by listing the 64-bit value.
[3] Although they now cannot do large containers; there's always tradeoffs necessary in the design process.