C++ STL list: Issue deleting things

The Chubu · *Last edited by The Chubu; 08-15-2012 at 04:47.*

Hi! I was trying to code the last exercise from here: http://www.cplusplus.com/forum/articles/12974/ (the ones about bunnies).

And I'm having issues deleting things from the linked list. Now, on this particular case I have to delete bunnies that are 10 years old so I messed around with an iterator (which I dont know what it is exactly, a pointer some element of the list I guess? ) in a for loop and the erase function.

tentlist is the list's typedef (from "type entity list" ), entlist is the entity list that currently holds bunny objects.

Code:

    for (tentlist::iterator it = entlist.begin(); it != entlist.end(); it++ )
        {
        if (it->age < 10)
            it->aging();
        else
            {
            cout << "Bunny " << it->id << " has died!" << endl;
            entlist.erase(it);
            

            }
        }

This lil' piece of code unleashes an infinite loop sadly. Repeating "Bunny 0 has died!" till the end of times.

Now, when i use the debugger the issue lies on the entlist.erase (actually, I have suspicions that it lies on my shoddy coding

). As soon as the code finds a bunny 5 years old, i call out the erase function to delete him from the list. The first time this happens (i followed it with the debugger), once the for loop tries to continue after killing its first bunny (yay!), it seems the iterator points to a non valid position because it finds some extremely low number for the bunny's ID and age repeating "Bunny -17.xxx.xxx is -17.xxx.xxx years old!" and never reaching the end of the list for some reason.

(that "Bunny xxx is xxx years old!" comes from the "aging()" method of the bunny object btw)

After that I didnt followed the debugger anymore because I suppose it increments that data up to 0 and then hangs somewhere with the "bunny 0 has died" message I talked about before.

Now, i think that the iterator doesnt "saves itself" when I use it to delete an item from the list. But if that's the case, how could I use it for erasing specific items in a list? I can't start traversing the list again just because I erased something (entlist.erase(it); and then it = entlist.begin(); then start again) I'd need to add a flag for already aged bunnies and such.

I managed to use the remove_if function from the stl list but I dont like it, its just a work around the fact that I don't know how to use the erase efectively.

Xendance · 08-15-2012, 13:10 | posts: 5,300 | Location: Funland aka Happycamp aka Finland

erase(it) returns an iterator to the current correct position in the list, now you aren't assigning the return value to anything. So I think you should do

Code:

it = entlist.erase(it);

The Chubu · 08-16-2012, 02:38 | posts: 2,541 | Location: Look out!

lol, it worked! And here I thought it would involve some complex logic.

Thanks a lot!

proliferazor · 08-17-2012, 03:08 | posts: 684

You still have a problem, you're skipping a bunny every time you delete one. When you delete your bunny using erase(it) it returns an iterator to the next bunny, so you don't want to advance it again after that iteration. So you need to remove your ++it from the for loop and only ++it if you don't delete a bunny. Also use the pre ++ operator it's the correct one ++it.

Code:

for (entlist::iterator it = entlist.begin(); it != entlist.end();  )
        {
        if (it->age < 10)
            {
            it->aging();
            ++it;
            }
        else
            {
            cout << "Bunny " << it->id << " has died!" << endl;
            it = entlist.erase(it)
            }
        }

For this reason it maybe easier to read if you just do a while loop

Code:

std::list<Bunny>::iterator it = entList.begin();
while( it != entList.end() )
    {
    if (it->age < 10)
        {
        it->aging();
        ++it;
        }
    else
        {
        cout << "Bunny " << it->id << " has died!" << endl;
        it = entlist.erase(it)
        }
    }

An iterator is an object that knows how to traverse a STL container. I think all containers in the STL can be traversed using iterators. Vector/List/Map all use iterators. So get used to doing it this way.

proliferazor · 08-17-2012, 05:55 | posts: 684

Chubu there are some good free video tutorials on the net for c++ such as
http://xoax.net/cpp/
http://www.youtube.com/playlist?list...0&feature=plcp
http://www.programmingvideotutorials...p-introduction

By far though the single most helpful thing I ever did was joining 3dbuzz.com as a member sponsor and doing the live c++ classes.

The Chubu · 08-18-2012, 03:50 | posts: 2,541 | Location: Look out!

Thanks! You're right. I didn't noticed it. Anyway, I've switched a lil bit the bunny object so it is more in charge of its demise.

I'll check the links but I'm more fond of reading than watching, at least on programming, already read the cplusplus.com online book a few times, and I'm having my share of theory in university atm (missed a course last year so I just started object oriented paradigm on java).

Though I'll have to read more about the standard library since cplusplus tutorial lacks on that part... I actually misunderstood the erase because I checked the cplusplus reference and it does says that has a return value (STL Linked List).

I've read that most compilers output the same code for both ++foo and foo++ when used in that context so I didn't payed much attention to it (of course that in other contexts like mathematical functions order matters a lot).

proliferazor · 08-18-2012, 06:51 | posts: 684

It is true that some compilers will optimize out i++ don't count on this though, what it does is just replace it with ++i because that is the right operator to use. In all cases in which you don't need the old value after the operation. So it's far better to think of these operators as ++i being the correct one to use 99% of the time and just using i++ when you are required to.

Print this. Wish I had one of these when I was starting out. You can buy a cardboard print of it at b&n or amazon.
http://www.ebook3000.com/C----SparkCharts-_163261.html

The Chubu · 08-20-2012, 23:59 | posts: 2,541 | Location: Look out!

Quote:

Originally Posted by proliferazor

It is true that some compilers will optimize out i++ don't count on this though

I'd be surprised if IBM's, GNU's. Microsoft's and Intel's compilers didn't.

In any case, thanks for the chart!

That one will be useful. The Cplusplus book (I printed it) has that kind of information but that chart is waaay more condensed.

Now I'll try to make up my mind about making a GameDev.com or Stackoverflow account (sometimes I learn more if I dont have a place to ask for the right answer immediately).

gamerk2 · 08-22-2012, 13:58 | posts: 2,065 | Location: Medford, NY

The gist of what was happening was the Iterator (which is basically tracking the position in the STL container, as mentioned above) was getting corrupt when you removed an element from the list.

Once you deleted am element, the Iterator was left pointing at an invalid position (think of it as a blank space being left where you removed an element from the list). So you have to advance the Iterator object after you remove an element, then ensure you don't skip a test because of the advanced iterator.

And yes, we're all guilty of doing this at one point or another.

The Chubu · *Last edited by The Chubu; 08-25-2012 at 07:16.*

Quote:

Originally Posted by gamerk2

Once you deleted am element, the Iterator was left pointing at an invalid position (think of it as a blank space being left where you removed an element from the list).

'cept that system memory isnt blank at all and I was cout'ing crap all over the console lol

Quote:

Originally Posted by gamerk2

And yes, we're all guilty of doing this at one point or another.

Like leaking memory and all the good stuff!

Anyway, I'm having another issue. Actually, I had it from the start but I was procrastinating it for a while.

So, I'd like to have a counter for total bunny ammount, and separate counters for female and male population. So I set up some statics in the bunny class.

int q for total count, int f for female count, int m for male count. Then set up the constructor to ++q always, and ++f or ++m accordingly. Thing is, counting upwards forever isn't going to work when bunnies start to die, so I set up the destructor to -- each as bunnies get deleted.

Its all fine and dandy until I notice that I delete bunny objects every now and then for doing things. Specially with lists, where I allocate new memory for a bunny with a pointer, pass the pointer's content to the list, then delete the pointer. I end up with the bunny data on the list as I want it but the destructor gets called reducing q, f and m size.

I could have a global counter in main and ++ or -- exactly when I want to, but it makes more sense that the bunny objects are the ones in charge of knowing how many they are.

The two conflicting parts of the code have the same issue, creating new object, passing it to some list, then deleting it. First one:

Code:

    for ( int i = 0; i < 5; ++i )
    {
        Entity *ptra = new Entity();
        entList.push_back(*ptra);
        delete ptra;
    }

I create 5 bunnies first as the exercise demands but that "delete ptra" is messing my counters. Then there is this one:

Code:

    for ( entList_t::iterator it = entList.begin(); it != entList.end(); ++it )
    {
        cout << "Current size of list is " << entList.size() << endl;
        Entity *ptrb = (it->replicate());
        if ( ptrb != NULL )
        {
            tempList.push_back(*ptrb);
        }
        delete ptrb;

The replicate method of the bunny object (Entity) creates a new bunny object if the conditions are appropiate (age is >2, sex is female, should also test of there are males around but cant do it with messed up counters) and returns its reference. If the conditions fails, returns NULL.

Now, both issues can be easily fixed by commenting out the delete ptra and the delete ptrb respectively (works perfectly) BUT I'm not sure why its working. Both push_back don't create a new bunny object in the lists out of the object i'm deferencing to them, or at least doesn't calls its constructor. If its the same object, it should get deleted by delete ptra and delete ptrb respectively, but it isn't the case. The (new?) bunny in the list keep existing, and the one that was originally pointed to by ptra/ptrb is deleted.

So at the start for each new bunny, one constructor is called, and one destructor is called. I end up starting with 5 bunnies and every q, f and m counter set to zero.

If I don't comment out the delete ptrb of the second piece of code, its the same situation again. A new object is created inside Entity::replicate, so q,f and m get incremented by its constructor, I put the bunny in the templist, then q,f,m get decremented immediately when delete is called.

I'm not exactly sure if I'm leaking memory by commenting out those deletes. I'd be leaking 5 bunnies at the start, and one more each time Entity::replicate is successful.

If you are wondering why I create new bunnies in a different list, its because if i added each newborn bunny at the end of the list, they would age by one year right away once i make the "ageing pass", and if i added the bunny in the beginning of the list, it would be just a dirty position-dependent solution

So I create them on a different list, and once the replicate and aging passes are done, I combine tempList with entList with list.splice (no constructor/destructors are called then).

Xendance · 08-25-2012, 13:15 | posts: 5,300 | Location: Funland aka Happycamp aka Finland

You're storing a pointer pointing to another pointer in the first part, is that intended? If you just make it like this, it'll work:

Code:

std::vector<Entity*> entList;

for(int i = 0; i < 5; ++i) {
        Entity * ptra = new Entity();
        entList.push_back(ptra);
        delete ptra;
}

proliferazor · 08-25-2012, 17:44 | posts: 684

First of all what is your vector/list? Is it Bunny or Bunny*? There is no need to mix pointers with regular variables without a reason. Without seeing your bunny class I will assume you don't need pointers. (If bunny is polymorphic or makes it's own memory using new, you do need pointers, and should store Bunny* in your vector/list) Make replicate return a Bunny. Then you do tempList.push_back(it->replicate());

If you want all your bunny objects to share counter variables make them static

Code:

class Bunny
{
protected:
	static int maleCount; // every bunny now has access to this SAME variable
	static int femaleCount;  // this one two
        int age; // every bunny has it's own age
};

int Bunny::maleCount = 0;  // must initialize static member variables outside of class
int Bunny::femaleCount = 0;

proliferazor · 08-25-2012, 17:55 | posts: 684

Quote:

Originally Posted by Xendance

You're storing a pointer pointing to another pointer in the first part, is that intended? If you just make it like this, it'll work:

Code:

std::vector<Entity*> entList;

for(int i = 0; i < 5; ++i) {
        Entity * ptra = new Entity();
        entList.push_back(ptra);
        delete ptra;
}

What you are doing here is creating a object on the heap, putting the address of it in the vector. Then deleting the object at that address. So every pointer in the vector is a dangling pointer. Pointing to invalid memory.

entList.push_back(*ptra); // the * in this line is the dereference operator

it will return the object at the address pointed to.

proliferazor · 08-25-2012, 22:33 | posts: 684

Quote:

Originally Posted by The Chubu

Now, both issues can be easily fixed by commenting out the delete ptra and the delete ptrb respectively (works perfectly) BUT I'm not sure why its working. Both push_back don't create a new bunny object in the lists out of the object i'm deferencing to them, or at least doesn't calls its constructor. If its the same object, it should get deleted by delete ptra and delete ptrb respectively, but it isn't the case. The (new?) bunny in the list keep existing, and the one that was originally pointed to by ptra/ptrb is deleted.

So at the start for each new bunny, one constructor is called, and one destructor is called. I end up starting with 5 bunnies and every q, f and m counter set to zero.

If I don't comment out the delete ptrb of the second piece of code, its the same situation again. A new object is created inside Entity::replicate, so q,f and m get incremented by its constructor, I put the bunny in the templist, then q,f,m get decremented immediately when delete is called.

I'm not exactly sure if I'm leaking memory by commenting out those deletes. I'd be leaking 5 bunnies at the start, and one more each time Entity::replicate is successful.

.

What it looks like your doing is creating a "new bunny' in your replicate method. This is on the heap. You return a pointer to it. When you do push_back your sending the object at that pointer to be copied and put in the list. Then you delete the original object on the heap. So you either need to store bunny pointers in your list to avoid creating and deleting temporary bunnies by passing by pointer. Or just live with the copying and use regular bunny variables.

The Chubu · *Last edited by The Chubu; 08-26-2012 at 00:13.*

To clarify, it is a linked list (std::list), of bunny objects, not pointers to bunny objects: typedef list<Entity> entList_t; I'm using a list cuz its easier to handle than vectors (no resizing, just add stuff, erase stuff). Bunny its not polymorphic, its a simple base class without inheritance/friendships/etc.

Quote:

Originally Posted by proliferazor

Make replicate return a Bunny. Then you do tempList.push_back(it->replicate());

You're right, returning a bunny directly sounds more reasonable. Though have in mind that replicate isn't an always-guaranteed to return a bunny method. Here is my replicate method if you want to see it:

Click to show spoiler

I can't always tempList.push_back(it->replicate()). Replicate is called for every bunny, and the bunny needs to be able to return nothing if they're unable to replicate. Unless I make it return some boolean (if its true, push the bunny, if its false, don't push anything).

Quote:

Originally Posted by proliferazor

If you want all your bunny objects to share counter variables make them static

Umm... Well, I think i'm explaining myself again but yeah, as i said, i did exactly that, three static counters, handled by the constructors/destructors of the bunny class. Though they're public for now, so I can check them out easily from main.

Quote:

Originally Posted by proliferazor

What it looks like your doing is creating a "new bunny' in your replicate method. This is on the heap. You return a pointer to it. When you do push_back your sending the object at that pointer to be copied and put in the list. Then you delete the original object on the heap. So you either need to store bunny pointers in your list to avoid creating and deleting temporary bunnies by passing by pointer. Or just live with the copying and use regular bunny variables.

Aha, this is what i wanted to know. So list is copying the bunny. Hm, a list of bunny pointers seems... pointless

I'd be doing what xendance thought i was doing (pointer to pointer to pointer to...).

So, if i dont call delete (so the destructor doesn't gets called and my counters remain accurate) on ptra/ptrb, i'm leaking a bunny object in the heap while I have its copy on the list right? These are my destructor and constructor :

Click to show spoiler

Seems like having those handling the counters is a bad idea. How could I have the bunny class in charge of the counters (that need to be modified each time a bunny is created/deleted) without using the constructor/destructor? I'd like it to be an "automatic" thing, main doesn't has to keep track of the counters, they are handled by the bunny objects.

In short, either I leave the constructor/destructor as they are, and avoid using new like if it was the plague, or I find out a new independent way of counting bunnies...

proliferazor · 08-26-2012, 02:17 | posts: 684

You are misinterpreting what a std::list<Bunny*> is. Really simple if you do

Code:

// your list is Bunny*
Entity *ptrb = (it->replicate());
        if ( ptrb != NULL )
        {
            tempList.push_back(ptrb);
        }

Then you're golden every pointer in the list is valid. All you have to do to access your bunny is
// access member or method
(*it)->
or
// this is a dereferenced object you can use . operator on it now
(*(*it))

When you erase your bunny from the list you also call delete on the pointer.

delete (*it);
it = list.erase(it);

Doing it this way only one bunny will be created on the heap and destroyed. Not a single bunny will be copied, and no temporaries made. This is generally the way you would do it with anything more than a simple data type.

Because you have to use pointers to prevent copying, getting polymorphic behavior ( and use things like interfaces/inheritance ect...) , you should get used to putting pointers to objects in a std::vector / std::list.

With c++11 you can put your bunnies in a unique_ptr and it will delete your heap memory automatically. That is optional of course.

Using ctor and dtor to handle the counting is fine. That is proper. It is messing up because of your memory management. You can be guaranteed the ctor and dtor will run (when you don't leak). In fact it's good that you are getting messed up counters because that is evidence of you leaking memory and can help you track it down.

Another little thing is you don't have to use the char 'F' to compare this is what enums are for

make an enum ( this is c++11 enum style )

enum class SEX : char
{
MALE = 0,
FEMALE,
};

then use SEX::MALE for comparison

class Bunny
{
SEX mSex;
Bunny()
{
// your code
mSex = SEX::MALE;
}
};

if ( mSex == SEX::MALE )
// Bunny is male
else
// bunny is female

The Chubu · *Last edited by The Chubu; 08-26-2012 at 03:06.*

All right, all right! I'll use a list of pointers. I just don't like so much deferencing

PD: I had a deja vu with this thread

EDIT: I thought about using an enum but just for two values seemed like too much. I will have to use them if I implement the mutant bunny (has no sex, its just a mutant). Enum is better anyway because what could happen if 'X' made it into the sex attribute? Or an 'f' instead of 'F' ? With enums I only have the expected values that I know.

proliferazor · 08-26-2012, 03:20 | posts: 684

Quote:

Originally Posted by The Chubu

All right, all right! I'll use a list of pointers. I just don't like so much deferencing

PD: I had a deja vu with this thread

EDIT: I thought about using an enum but just for two values seemed like too much. I will have to use them if I implement the mutant bunny (has no sex, its just a mutant). Enum is better anyway because what could happen if 'X' made it into the sex attribute? Or an 'f' instead of 'F' ? With enums I only have the expected values that I know.

Now you can have a hermaphrodite bunny too! ( replicate always returns a bunny (though occasionally a mutant

)

If you really want to understand this memory management thing, it's all about the stack and the heap. Using new in c++ creates an object on the heap and returns a pointer to it. This object will live for the life of the program until you call delete on a pointer that points to it. Objects on the stack get deleted at the end of the scope ( function, object ect..) .

So if you want a bunny to live until you want to kill it pointers are the only way. You will make a huge leap in your skills when you read up on the stack and heap. You'll never understand c++ until you do. It's one of those ahah! Moments.

The Chubu · *Last edited by The Chubu; 08-26-2012 at 07:55.*

Quote:

Originally Posted by proliferazor

Now you can have a hermaphrodite bunny too! ( replicate always returns a bunny (though occasionally a mutant

)

Fun for the whole family!

Quote:

Originally Posted by proliferazor

If you really want to understand this memory management thing, it's all about the stack and the heap.

That's exactly what i'm trying to do. If it wasn't the case, i'd be practicing Java

I'm off to read about heap and stack memory...