Can you embed for loops (in each other) in C++

Question

I am working on a merge sort function. I got the sort down - I am trying to get my merge part finished. Assume that I am learning C++, have cursory knowledge of pointers, and don't understand all the rules of std::vector::iterator's (or std::vector's, for that matter).

Assume that num is the size of the original std::vector that have copied (std::copy) values from an array of size "int ar[num]." Assume that farray has the values of (0 to (num / 2)) and sarray has the values of ((num / 2) to num).

int num = original.size();
std::vector<int> final(num);

for (std::vector<int>::iterator it = farray.begin(); it != farray.end(); ++it) {
     for (std::vector<int>::iterator iter = sarray.begin(); iter != sarray.end(); ++iter) {
         if (*it > *iter) final.push_back(*it);
          else
               final.push_back(*iter);
     }
}

This code compiles and my latest stable build of Bloodshed Dev-C++ does not throw any warnings or errors. I don't know if this is valid, I still need to try and cout all the values of final. I just want to know if this is common, prone to errors, or just bad style. And, if so, how you would

Answer 1

It's valid... but a for loop probably isn't what you want. When you use two for loops, your inner loop keeps going back to the start every time the outer loop loops. So if your vectors contain:

farray: 10 9 8 4 3
sarray: 7 6 4 3 1

Then your final array will contain something like:

10 10 10 10 10 9 9 9 9 9 8 8 8 8 8 7 6 4 4 4 7 6 4 3 3

because you are testing every single combination, and adding the larger one to the final list. A better solution might be to remember an iterator for each list, and just use one loop. Rather than looping over a list, just go through both of them together - if sarray has the larger number, then increment your sarray iterator, and compare that with the old farray iterator. Stop your loop when both sarray and farray are empty.

vector<int> fiter = farray.begin();
vector<int> siter = sarray.begin();
vector<int> final;

// Let's traverse both farray and sarray.
// We'll want to stop this loop once we've traversed both lists.
while (fiter != farray.end() && siter != sarray.end())
{
    if (fiter == farray.end())
    {
        // we must have gone right through farray - 
        // so use the value from sarray, and go to the next one
        final.push_back(*siter);
        siter++;
    }
    else if (siter == sarray.end())
    {
        // we must have gone right through sarray - 
        // so use the value from farray, and go to the next one
        final.push_back(*fiter);
        fiter++;
    }
    else if (*siter > *fiter)
    {
        // siter is the bigger of the two - add it to the final list, and
        // go to the next sarray entry
        final.push_back(*siter);
        siter++;
    }
    else // *fiter >= *siter
    {
        // fiter is the bigger of the two - add it to the final list, and
        // go to the next farray entry
        final.push_back(*fiter);
        fiter++;
    }
}

I haven't tested it - and if this is for homework, then please try to understand what I've done, go away and write it yourself, rather than copy+paste.

Answer 2

Merge sort algorithm aside, nested for loop with iterator's is just as valid as nested for loops with two variables i and j.

Answer 3

You can nest loops of any kind (for, while, do while) as long as you don't reuse the loop variables. If you would try that it would compile but may fail miserably during runtime. Although technically allowed to use the same name for nested loop variables in modern C and C++ it is confusing and should be avoided.

It's no more or less prone to errors than a single loop except for the already mentioned problem with the reuse of loop variables.

Read more about the limits of nested loops.

Answer 4

Nesting for loops is a totally legit way to do things. For example, it's the classic "old school" way to traverse a 2D array - one loop goes down the y axis, and the other loop goes down the x axis.

Nowadays, with those kids and their for each loops and iterators and mapping functions there are arguably "better" ways to do it, (for some definition of better) but nesting loops works just fine. Using C++ or pointers doesn't change that.

Answer 5

Yes, you can do this. And yes, it is often prone to errors. In fact, writing loops is itself prone to errors, which is one argument to use the algorithms in the STL like for_each, copy and transform.

Answer 6

Yes, you can nest loops, or other statements, to pretty much whatever depth you want (within reason; there are limits, as mentioned in another answer, but they're way above what you should ever need).