Personal computing discussed

Moderators: renee, SecretSquirrel, just brew it!

 
Asin
Gerbil Team Leader
Topic Author
Posts: 292
Joined: Tue Mar 09, 2004 10:36 pm
Location: Ontario, Canada
Contact:

C++: Iterators / Going Through A Deque

Sun Nov 13, 2005 10:23 pm

This is really hurting my brain. I'm trying to figure out why the following two code segments do different things with std::deque objects.

void CardPile::addToPile (CardPile & otherPile) {
    for (std::deque<Card*>::iterator iter = otherPile.pile.begin ();
        iter != otherPile.pile.end (); iter++) {
        pile.push_back (&(otherPile.removeTopCard ()));
    } // end for
} // end addToPile

void CardPile::addToPile (CardPile & otherPile) {
    for (int i = 0; i < otherPile.size (); i++) {
        pile.push_back (&(otherPile.removeTopCard ()));
    } // end for
} // end addToPile


pile is an std::deque object. The iterator works as expected, but for some reason, the second piece of code doesn't. I'd ignore this, but the first code segment isn't using the iterator (directly), so I like to avoid losing marks as much as possible.

Thanks in advance.
 
sativa
Grand Gerbil Poohbah
Posts: 3044
Joined: Sun Apr 14, 2002 7:22 pm
Location: lafayette, la

Sun Nov 13, 2005 10:47 pm

output the value of the 'i' variable in the loop and make sure that the size() function is reporting the right size, and that the values of i make sense. it might help you figure out where things are going wrong.

 void CardPile::addToPile (CardPile & otherPile) { 
    for (int i = 0; i < otherPile.size (); i++) {
        cout << "i: " << i << endl;
        pile.push_back (&(otherPile.removeTopCard ()));
    } // end for
} // end addToPile
Last edited by sativa on Sun Nov 13, 2005 10:52 pm, edited 1 time in total.
Science is forbidden. Laboratories manufacture danger!
 
bitvector
Grand Gerbil Poohbah
Posts: 3293
Joined: Wed Jun 22, 2005 4:39 pm
Location: San Francisco, CA

Re: C++: Iterators / Going Through A Deque

Sun Nov 13, 2005 10:49 pm

Asin wrote:
pile is an std::deque object. The iterator works as expected, but for some reason, the second piece of code doesn't. I'd ignore this, but the first code segment isn't using the iterator (directly), so I like to avoid losing marks as much as possible.

Could it be because the size of otherPile is changing as you remove cards (as your for loop termination condition isn't the original size but the current size)?
 
sativa
Grand Gerbil Poohbah
Posts: 3044
Joined: Sun Apr 14, 2002 7:22 pm
Location: lafayette, la

Re: C++: Iterators / Going Through A Deque

Sun Nov 13, 2005 10:54 pm

bitvector wrote:
Asin wrote:
pile is an std::deque object. The iterator works as expected, but for some reason, the second piece of code doesn't. I'd ignore this, but the first code segment isn't using the iterator (directly), so I like to avoid losing marks as much as possible.

Could it be because the size of otherPile is changing as you remove cards (as your for loop termination condition isn't the original size but the current size)?


good call. it would be performed each time the loop is iterated.

he needs to retrieve the value of the size before entering the loop, and store that in a seperate variable.

 void CardPile::addToPile (CardPile & otherPile) { 
    int otherPileSize = otherPile.size();
    for (int i = 0; i < otherPileSize; i++) {
        pile.push_back (&(otherPile.removeTopCard ()));
    } // end for
} // end addToPile
Science is forbidden. Laboratories manufacture danger!
 
Asin
Gerbil Team Leader
Topic Author
Posts: 292
Joined: Tue Mar 09, 2004 10:36 pm
Location: Ontario, Canada
Contact:

Sun Nov 13, 2005 11:01 pm

I think that you're right bitvector. It looks like that's the problem. I would definitely explain why a trace would output only 0 and 1 for i on deques of size 3.

Thanks you two.
 
Craig P.
Gerbil Team Leader
Posts: 285
Joined: Tue Dec 31, 2002 3:12 am
Location: South Bend, IN

Wed Nov 16, 2005 12:36 am

In my experience, changing the size of a container underfoot while I'm iterating over it has caused a lot of pain.
 
UberGerbil
Grand Admiral Gerbil
Posts: 10368
Joined: Thu Jun 19, 2003 3:11 pm

Wed Nov 16, 2005 12:58 am

Craig P. wrote:
In my experience, changing the size of a container underfoot while I'm iterating over it has caused a lot of pain.
Yes, this is a classic error and it's why Java and the .NET languages (among others) have the "for each" construct to ensure you can iterate across a collection without hitting it (even if you're deleting elements or otherwise changing the collection).
 
just brew it!
Administrator
Posts: 54500
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Wed Nov 16, 2005 1:02 am

UberGerbil wrote:
Craig P. wrote:
In my experience, changing the size of a container underfoot while I'm iterating over it has caused a lot of pain.

Yes, this is a classic error and it's why Java and the .NET languages (among others) have the "for each" construct to ensure you can iterate across a collection without hitting it (even if you're deleting elements or otherwise changing the collection).

Indeed.

I've been burned by this "stupid programmer trick" a number of times myself. Probably ranks right up there with the classic "off by one" error, in terms of common programming mistakes.
Nostalgia isn't what it used to be.
 
Flying Fox
Gerbil God
Posts: 25690
Joined: Mon May 24, 2004 2:19 am
Contact:

Wed Nov 16, 2005 1:28 am

Let me see if I can add some more here.

I would say both approaches are not too good. The 2nd one we already explained why because the size of the other pile keeps changing and you are not starting the for loop from scratch every time. The 1st one works for you with the iterator because you are popping the elements in front of the iterator, which for a deque is ok becuase the iterator is not (?) bidirectional and it just so happens the iterator remains valid after you remove the element in the collection. If the collection is LIFO (only remove last available) then you are screwed.

I would argue that semantically, even the "for each" construct is misleading and may eventually lead to errors if the underlying implementation of the iterator (example: in .NET you are implementing an interface if you are creating a new collection class, and it could be a badly implemented one which is not as robust as the FCL).

Since the code is about removing elements from another collection into your own collection, to make the code more explicit you should probably not use the iterator approach at all (unless constrained by access restrictions and/or assignment instructions). If I were to write that piece of code I would do the following. The basic idea is to use the while loop and clearly express the logic as "while the otherPile still has something keep removing items from it". IMO it makes more readable code.

void CardPile::addToPile(CardPile& otherPile)
{
    while (otherPile.size() > 0)
    {
        pile.push_back(&(otherPile.removeTopCard()));
    } // end while
} // end addToPile
(In reality there can be a performance hit for this approach, but for CS assignments usually it is about logical correctness, right?)

Now, after all of us have given our input for your little assignment, how many more Folding boxen are you contributing for our effort? :wink:

Who is online

Users browsing this forum: No registered users and 1 guest
GZIP: On