Is there a "smart" way to break out of nested loops?

Question

(Right now I'm mostly using C#. Ideas in other languages are welcome, but please translate them to C# if you can, and be explicit.)

Something I come across time and time again is a nested loop, searching through some 2D array to find an element (typically some object), which then has to be manipulated. So of course, once you find that object, you should break out of both loops so you don't needlessly continue the search for something you already found (especially in nested loops which can traversing exponentially huge arrays).

The following code is currently my preferred way of doing it:

Obj O = null;
bool KeepLooping = true;

for (int j = 0; j < height && KeepLooping; j++)
{
    for (int i = 0; i < width; i++)
    {
        if (ObjArray[i, j] != null && ObjArray[i, j].property == search_value)
        {
            O = ObjArray[i, j]; // you found it, now remember it
            KeepLooping = false; // clear the flag so the outer loop will break too
            break;
        }
    }
}

Thanks to Erik Funkenbusch, it becomes much more elegant if we do this:

Obj O = null;
for (int j = 0; j < height && O == null; j++) // much, much better idea to check O for null in the outer loop
{
    for (int i = 0; i < width; i++)
    {
        if (ObjArray[i, j] != null && ObjArray[i, j].property == search_value)
        {
            O = ObjArray[i, j]; // you found it, now remember it
            break;
        }
    }
}

No more need for that pesky extra boolean!

Nevertheless, the search for alternative or better solutions goes on. Over the years I've tried many other ways, but find them not that great for one reason or another:

1. Set j (the outer-loop iterator) to a value above height, which will trigger it to break automatically. Not ideal because sometimes you want to remember the i and j values where you found it.
2. Use foreach on the 2D array. Not ideal since foreach won't let you manipulate the collection (delete or add to it, which very typically is the reason I search for the object anyway).
3. Just put the 2 loops in a function that does nothing but find and return O. return effectively breaks both loops. Many times this is okay, but not always. I do this for very generic searches, but there are also quite a lot of "group searches" where I want to collectivize the traversing. In those cases, I find 2 or more objects (sometimes within the same 2D array), remember them, and only then break out of both loops.
4. Use a goto? (Whoa, could this be the only legit use of a goto? It's surprisingly more readable than the KeepLooping flag, especially if we have 3 or more loops.) Not ideal because coworkers will scream bloody murder. And in C#, will there be correct garbage cleanup after the goto?
5. Throw a custom exception? idk, i've never tried it, but it looks less readable than my currently preferred way.
6. Once you've found the right object, do all your object manipulation inside the inner loop, and then return; This could get messy fast. Sometimes the object manipulation involves its own loops.

There is also a very clever 7th way, thanks to User_PWY:

int size = width*height; // save this so you dont have to keep remultiplying it every iteration
for (int i = 0; i < size; i++)
{
   int x = i % width; // ingenious method here
   int y = i / width; // ingenious method here

   O = ObjArray[x, y];

   if (O != null)
       break; // woohoo!
}

This effectively compacts the 2D array into one for loop for iteration. However, some criticism has pointed out that the mod and division operators are pretty slow in comparison to just i++ or j++, so it could be slower (remember we are dealing with 2D arrays of who-knows-what size). Like i commented, there should be a way to get the division and remainder in one operation because I'm pretty sure the x86 assembly code has DIV opcodes that store the quotient and remainder in separate registers, all in one DIV instruction. But how to do/use that in C#, idk.

It would be nice if C# allowed you to name loops, such as L1 and L2, and then do something like L1.break(); regardless of which loop you're inside. Alas...it cannot be done in this language. (Could there be some secret way of doing this using macros?) Is there ever gonna be a C# 6.0 with this feature implemented?

Edit: in my opinion, I judge solutions on their elegance and speed. Remember we are dealing with nested loops, which can get exponentially huge. An extra operation or comparison could make a difference.

Okay, well, tell me your preferred way, especially if it's something not listed here.

Answer 1

goto is a perfectly fine solution for this, Microsoft even recommends it:

The goto statement transfers the program control directly to a labeled statement.

A common use of goto is to transfer control to a specific switch-case label or the default label in a switch statement.

The goto statement is also useful to get out of deeply nested loops.

As for your question about object destruction, once you are out of scope for a scoped object the garbage collector should mark it for destruction, but I can't say for sure whether the behavior is the same if you use, for example, a using directive around your for loop and goto out of it as opposed to exiting scope normally.

Answer 2

Refactoring to avoid deep nesting, possibly with cleaver usage of LINQ is probably better solution.

Goto is possible for this case (and this is essentially only case to use it) if you can't come up with better approach. Setting flag with readable name will likely cause less questions/screaming.

Do not

• use exceptions for flow controls
• change loop variables. Figuring out what happens is very hard in this case. I'd bet most people will accept goto as much better approach.

Answer 3

for (int i = 0; i < width*height; i++)
{
   int x=i%width
      ,y=i/width;
   //dostuff
}

I like this way of access to 2d array.

comment 1)
There were many comments worrying that mod(%) operator could be costly, but this is integer operation we are talking about and I think that it should make no difference other solution.

comment 2)
about the macro. I couldn't find the code but managed to produce one briefly.

#define FOR2DARRAY(WIDTH,HEIGHT) 
    \for (int i = 0, x = 0,y = 0; i < (WIDTH)*(HEIGHT); i++, x=i%(WIDTH),y=i/(HEIGHT))

Answer 4

Not very much different, but I prefer to use the boolean flag in this way:

Obj O = null;
bool found = false;

for (int j = 0; j < height; j++)
{
    for (int i = 0; i < width; i++)
    {
        if (ObjArray[i, j] != null && ObjArray[i, j].property = search_value)
        {
            O = ObjArray[i, j]; // you found it, now remember it
            found = true; // clear the flag so the outer loop will break too
            break;
        }
    }
    if (found) break;
}

if (!found)
{
    // The loop finished with no values found
}
else
{
    // Do stuff here with the value found
}

Answer 5

Try this:

Obj O = ObjArray.Cast<Obj>().FirstOrDefault(obj => obj != null && obj.property == search_value);

This converts the 2D array of Obj into an IEnumerable<Obj> and gives you the first one that matches your conditions. If none of them match, Obj O is set to null.

Check it out here: https://dotnetfiddle.net/dQTJbU

Answer 6

Maybe I missed it in your list of options, but why can't you refactor the search into a method that returns your object?

private object FindObject(....)
{
    for (int j = 0; j < height && KeepLooping; j++)
    {
        for (int i = 0; i < width; i++)
        {
            if (ObjArray[i, j] != null && ObjArray[i, j].property = search_value)
            {
                return ObjArray[i, j]; // you found it, now remember it
            }
        }
    }
    return null;
} 

Answer 7

There are many many ways to do this. In your example, I would do it like this:

Obj O = null;

for (int j = 0; j < height && O == null; j++)
{
    for (int i = 0; i < width; i++)
    {
        if (ObjArray[i, j] != null && ObjArray[i, j].property == search_value)
        {
            O = ObjArray[i, j]; // you found it, now remember it
            break;
        }
    }
}

The KeepLooping variable is unnecessary in this case, and thus the simple break statement works very elegantly.

You could actually even simplify this more:

Obj O = null;

for (int j = 0; j < height && O == null; j++)
{
    for (int i = 0; i < width && O == null; i++)
    {
        if (ObjArray[i, j] != null && ObjArray[i, j].property == search_value)
            O = ObjArray[i, j]; // you found it, now remember it
    }
}

Now, the break isn't even required.

Of course this may not work for all situations, but often you can utilize the result type as a state value.

FYI, the issue with modifying the collection in a foreach isn't really a problem if you do it correctly. For instance:

// Assumes ObjArray is [,] and not [][]
foreach (int item in ObjArray.ToList()) // makes a copy to iterate over
{
    if (item != null && item.property == search_value) {
        ObjArray[0,0] = item; // I can now modify this for no reason
        break;
    }
}