Is it good form to compare against changing values in a loop in C++?

Question

No doubt some of you have seen my recent posting, all regarding the same program. I keep running into problems with it. To reiterate: still learning, not very advanced, don't understand pointers very well, not taking a class, don't understand OOP concepts at all, etc. This code just merges two sorted vectors, farray and sarray, into a single sorted vector. At least, I hope that's what it does. Tell me:

    //int num is to find the size of the original vector and
    //build up farray and sarray; not used in the merge process
    int num = original.size() 
    std::vector<int> final;

    std::vector<int>::iterator it = farray.begin();
    std::vector<int>::iterator iter = sarray.begin();

    //farray.size() == (0 thru (num / 2))
    //sarray.size() == ((num / 2) thru num)
    for (;it != farray.end() && iter != sarray.end();) {
        if (*it > *iter) {
            final.push_back(*it);
            it++;
        }    
        else
        {
            final.push_back(*iter);
            iter++;
        }

            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

I rewrote the merge part of my merge sort function so as to...well, make it work. I actually have several questions about this code:

1. Is it good form to compare against std::vector::iterators it && iter for my last two if statements if the for loop might change them on its next pass?
2. Will the values of iter and it change on this loop's last pass and screw up my code? Will putting my last if statements before the *it and *iter comparison?
3. Does the end() member function refer to the last value of whatever is calling it? It seems like it might extend past it somehow.

EDIT: I will respond to all replies tomorrow, so check back then if you want to hear more. It's past midnight. G'night.

Answer 1

1 . It's fine to compare iterators which are from the same container as a for loop condition, but this only makes sense if you are moving one or other iterators in either the increment part if the for loop statement or in the body of the for loop itself. In this for loop you compare iter against sarray.end() but the for loop never changes iter. This means that either there will be no iterations or the for loop will never terminate. Also, you probably want to use != and not < for the comparison. == and != work for all iterators, < doesn't.

            for (int i = 0; iter != sarray.end(); i++) {
                final.push_back(*iter);
            }

As iter starts where you want the loop to begin, you may want something like this:

            for (; iter != sarray.end(); ++iter) {
                final.push_back(*iter);
            }

As you're still learning (although aren't we all!), it's probably instructive to work through an algorithm like this, but you should be aware of std::merge which probably does what you want.

std::merge( farray.begin(), farray.end(), sarray.begin(), sarray.end(), std::back_inserter( final ) );

(You need to #include <iterator> and <algorithm>.)

2 . I don't see incrementing iter or it in the outer for loop invalidating the logic in the later for loops, the point in 1. aside.

3 . end() points to one past the end of a container, so you can use it for loop termination checks, but you shouldn't try to dereference an iterator which is "==" to ".end()".

Answer 2

Some general advice: You need to think about variable names. Calling your iterators 'it' and 'iter' is going to confuse you at some point. Actually, if you look closely, it already has. If 'farray' and 'sarray' are meaningful names, how about 'fiter' and 'siter'.

Also, think through what the merge sort is doing. Those last two blocks are there just to "drain" whichever iterator has some stuff left. So they don't need to be in the first loop.

I'd probably write it as (pseudocode):

while not (list1.empty and list2.empty):
    if list1.empty:
        result.push(list2.pop)
    else if list2.empty:
        result.push(list1.pop)
    else if list1.top > list2.top:
        result.push(list2.pop)
    else:
        result.push(list1.pop)

Or in somewhat rusty cargo-culted C++:

std::vector<int>::iterator fiter = farray.begin();
std::vector<int>::iterator siter = sarray.begin();

while (fiter != farray.end() || siter != sarray.end()) {
    if (fiter == farray.end())      final.push_back(*siter++);
    else if (siter == sarray.end()) final.push_back(*fiter++);
    else if (*fiter > *siter)       final.push_back(*siter++);
    else                            final.push_back(*siter++);
}

Answer 3

I didn't check your algorithm's implementation, I will just refer to your three questions:

1. Iterators are much like pointers to values of a container. It's exactly like using size_t i and then ++i in the for loop. would you feel it's problematic to compare farray[i] with sarray[i]? probably not, therefore it's OK.
2. What I see you doing in your code here, is that you just read the values of *it and *iter, you don't actually change them, therefore they won't change.
3. The end() points to an invalid place. It doesn't point to the last value, but to "after it". It's like "NULL" if you will, therefore if(iter == sarray.end()) is true, you will crash if you will write *iter, because you can't dereference an iterator which is equal to end().

Answer 4

You have a few things to think about here.

First, if you are merging two ranges you would be much better off using the std::merge function rather that rolling your own.

Your code is a little difficult to read because you use varying styles for indentation and where you out your curly braces. Pick a style & stick to it.

The first part of your for loop seems to be a correct implementation of a merge:

for (;it != farray.end() && iter != sarray.end();) {
    if (*it > *iter) {
        final.push_back(*it);
        it++;
    }    
    else
    {
        final.push_back(*iter);
        iter++;
    }

...and this should be all you need to get the job done.

The second part of your loop has a couple problems:

   for (;it != farray.end() && iter != sarray.end();) {
         :   :
            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

For one thing, the for() conditionals are written so that both it and iter must not point to the end() of their respective collection, or else the loop ends. So it can never point to sarray.end(), iter can never point to farray.end(), and neither if statement can ever fire. They are both dead (unreachable) code.

But even if they weren't dead code, they have bugs. The conditional in the for(...) breaks the loop when the iterator points to the end of the collection, but this iterator is never moved, so you have an infinite loop.

Again both of these for(...)s are uneeded dead code because the iterators can never point to the end of the vector.

Answer 5

One simple comment: why not use while (condition) instead of for(; !condition; ).

The latter construction is nonstandard and hard to understand!