AR7 AR7 - 1 month ago 7
C++ Question

A for loop needs to run LLONG_MAX times, but the counter variable needs to also represent signed numbers. What type do you use for the counter?

I'm hoping you can entertain this hypothetical question even though this has probably never been a problem for anyone ever.

I used to write my for loops like

for (size_t i = 0; i < container.size(); ++i)


to avoid the warnings related to comparing a signed and unsigned, but after being bitten a few too many times trying to involve
i
in operations that resulted in negative numbers, I started writing them like this, casting the size to int to also avoid that warning:

for (int i = 0; i < (int)container.size(); ++i)





Now lets say that there's a case where
container.size() > INT_MAX
and in the loop we have something like.

for (int i = 0; i < (int)container.size(); ++i) {
size_t x = 0;
while (i - x++ > INT_MIN) {
// do stuff
}
}


We need
i
to be signed, but we also need
i
to be able to represent a number larger than
INT_MAX
. I know that the super simple answer here to use
long
, but then the same problem arises eventually even if you use
long long
if you have to run your loop
> LLONG_MAX
times.

In this case, you would finally be forced into using an unsigned type for your counter variable capable of representing a number that large, but you would still need to be able to check this condition

while (i - x++ > LLONG_MIN)


how do you do it? (given you actually have some reason to run a loop 9 quintillion times).

Answer

Most containers have a size_type typedef to specify the data type that is used for indexes and sizes within the container. For example, if container is a std::vector, you would use std::vector::size_type instead of int or even size_t:

for (std::vector<type>::size_type i = 0; i < container.size(); ++i)
{
    // use container[i] as needed
}

An alternative solution is to use iterators instead of indexes, then you don't need to worry about any counter data type at all:

for (std::vector<type>::iterator iter = container.begin(); iter != container.end(); ++iter)
{
    // use *iter as needed
}

Which can be simplified using auto in C++11 and later:

for (auto iter = container.begin(); iter != container.end(); ++iter)
{
    // use *iter as needed
}

Your inner while loop doesn't really make any sense to me, but if you really need something like INT_MIN for a container, you can use std::numeric_limits to get the min/max values of the container's size_type, eg:

typedef std::vector<type>::size_type container_size_type;

for (container_size_type i = 0; i < container.size(); ++i) {
    container_size_type x = 0;
    while ((i - x++) > std::numeric_lists<container_size_type>::min()) {
        // do stuff
    }
}

It seems it would be easier to just loop between the two indexes instead:

typedef std::vector<type>::size_type container_size_type;

for (container_size_type i = 0; i < container.size(); ++i) {
    for (container_size_type j = 0; j < i; ++j) {
        // do stuff
    }
}

Or:

typedef std::vector<type>::size_type container_size_type;

for (container_size_type i = 0; i < container.size(); ++i) {
    for (container_size_type j = i; j >= 0; --j) {
        // do stuff
    }
}

Depending on which direction you want the inner loop to run.

However, either of those loops can be re-written using iterators as well (replace 'auto' with the appropriate type if you are not using C++11), eg:

for (auto iter = container.begin(); iter != container.end(); ++iter) {
    for (auto iter2 = container.begin(); iter2 != iter; ++iter2) {
        // do stuff
    }
}

for (auto iter = container.begin(); iter != container.end(); ++iter) {
    for (auto iter2 = std::vector<type>::reverse_iterator(iter); iter2 != container.rend(); ++iter2) {
        // do stuff
    }
}