Sign in to follow this  
Syerjchep

Memory leaks from removing elements from list.

Recommended Posts

Syerjchep    212
I want a dynamic container that I can add items to or remove items from and that will allocate memory automatically, unlike an array. But I also want something that I can modify the elements of, and I don't mean replace, but actually run methods and functions of the classes stored in the container. This doesn't work with an array or a list as far as I have tested.
 
Here is some test code:
 
#include <iostream>
#include <forward_list>
 
using namespace std;
 
class whoKnows
{
    private:
        int hidden;
    public:
        int getHidden();
        void setHidden(int newint);
};
 
int whoKnows::getHidden()
{
    return hidden;
}
 
void whoKnows::setHidden(int newint)
{
    hidden = newint;
}
 
int main()
{
    forward_list<whoKnows> test;
    whoKnows unknown;
 
    whoKnows twelve;
    twelve.setHidden(12);
    whoKnows thirty;
    thirty.setHidden(30);
    whoKnows six;
    six.setHidden(6);
 
    test.push_front(twelve);
    test.push_front(thirty);
    test.push_front(six);
 
    cerr<<"Showing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        unknown = *it;
        cerr<<"Class found, value: "<<unknown.getHidden()<<"\n";
    }
 
    cerr<<"Increasing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        unknown = *it;
        unknown.setHidden(unknown.getHidden()+1);
    }
 
    cerr<<"Reshowing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        unknown = *it;
        cerr<<"Class found, value: "<<unknown.getHidden()<<"\n";
    }
 
    cout<<"Done\n";
    return 0;
}
Ideally the second iteration of values would all be one more than the first time, but they are not.
A forward list would work for me, as I have a program that every frame loops though each object (begin to end) and runs a method which will modify values in that class. As long as I can remove an object at any point in the container, I don't need to access elements randomly, only from begining to end.

Share this post


Link to post
Share on other sites
Waterlimon    4398
In that example you are taking the unknown from the iterator by value.

Use a reference instead, currently you are copying it and ediring the copy. Im not sure if there are still problems with the std containers as i have little experience with them, just making sure thats not the problem.

Share this post


Link to post
Share on other sites
Syerjchep    212

Well I read a topic on a differnet forum, here: http://stackoverflow.com/questions/1718615/container-of-pointers-vs-container-of-objects-performance

And I basically added a few astricks in the right places and it seems to work now.

Too bad this will apparently decrease preformance, but I can't imagine it'd be any worse than just having an array of objects.

#include <iostream>
#include <forward_list>
 
using namespace std;
 
class whoKnows
{
    private:
        int hidden;
    public:
        int getHidden();
        void setHidden(int newint);
};
 
int whoKnows::getHidden()
{
    return hidden;
}
 
void whoKnows::setHidden(int newint)
{
    hidden = newint;
}
 
int main()
{
    forward_list<whoKnows*> test;
    whoKnows *unknown;
 
    whoKnows *twelve = new whoKnows;
    twelve->setHidden(12);
    whoKnows *thirty = new whoKnows;
    thirty->setHidden(30);
    whoKnows *six = new whoKnows;
    six->setHidden(6);
 
    test.push_front(twelve);
    test.push_front(thirty);
    test.push_front(six);
 
    cerr<<"Showing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        unknown = (*it);
        cerr<<"Class found, value: "<<unknown->getHidden()<<"\n";
    }
 
    cerr<<"Increasing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        unknown = (*it);
        unknown->setHidden(unknown->getHidden()+1);
    }
 
    cerr<<"Reshowing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        unknown = (*it);
        cerr<<"Class found, value: "<<unknown->getHidden()<<"\n";
    }
 
    cout<<"Done\n";
    return 0;
}
Edited by Syerjchep

Share this post


Link to post
Share on other sites
Jeff Cotton    109

The problem with your new code is that you have memory leaks. You aren't de-allocating the memory you allocated with the new * calls. i.e.

    whoKnows *twelve = new whoKnows;
    twelve->setHidden(12);
    whoKnows *thirty = new whoKnows;
    thirty->setHidden(30);
    whoKnows *six = new whoKnows;
    six->setHidden(6); 

You have several options to fix the problem the best is probably to use smart pointers in your container. However, if you go back to your original code you can use the iterators directly and everything should work fine. i.e.

#include <iostream>
#include <forward_list>
 
using namespace std;
 
class whoKnows
{
    private:
        int hidden;
    public:
        int getHidden();
        void setHidden(int newint);
};
 
int whoKnows::getHidden()
{
    return hidden;
}
 
void whoKnows::setHidden(int newint)
{
    hidden = newint;
}
 
int main()
{
    forward_list<whoKnows> test;
    whoKnows twelve;
    twelve.setHidden(12);
    whoKnows thirty;
    thirty.setHidden(30);
    whoKnows six;
    six.setHidden(6);
 
    test.push_front(twelve);
    test.push_front(thirty);
    test.push_front(six);
 
    cerr<<"Showing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        cerr<<"Class found, value: "<<(*it).getHidden()<<"\n";
    }
 
    cerr<<"Increasing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        (*it).setHidden((*it).getHidden()+1);
    }
 
    cerr<<"Reshowing all values.\n";
 
    for(auto it = test.begin(); it != test.end(); it++)
    {
        cerr<<"Class found, value: "<<(*it).getHidden()<<"\n";
    }
 
    cout<<"Done\n";
    return 0;
}

Share this post


Link to post
Share on other sites
Hiwas    5807

Another option is to get rid of the iterators completely using C++11 which seems viable give you are using the new auto form.

 

// If getHidden were 'const' you could change this to 'const auto&'
for(auto& it : test)
    {
        cerr<<"Class found, value: "<<it.getHidden()<<"\n";
    }
    cerr<<"Increasing all values.\n";
 
    for(auto& it : test)
    {
        it.setHidden( it.getHidden()+1 );
    }
 
    cerr<<"Reshowing all values.\n";
 
    for(auto& it : test)
    {
        cerr<<"Class found, value: "<< it.getHidden()<<"\n";
    }

 

Nice reduction in typing which usually means fewer possible errors.  Though missing the '&' reference on auto is a bugger to figure out sometimes. :)

Share this post


Link to post
Share on other sites
Syerjchep    212
So right now I'm using alleightup's suggestion and it's working well. Hopefully there isn't any memory loss, it'll be a little bit before I have the actual program ready to test and can see for myself.
 
Currently my question is how can I remove an element?
Something along the lines of this:
 
for(auto& it : lifeforms)
{
      if(it->food < 1)
            lifeforms.remove(it);
}
Does not work.
The program crashes.

How do I remove an element?
(while freeing its memory, as I only need the elements that are in the list) Edited by Syerjchep

Share this post


Link to post
Share on other sites
Hiwas    5807

Err, I probably should have changed the naming a bit so it was more clear..  The auto type in the examples I gave will become references to the dereferenced iterator.  So, 'auto& it' actually becomes 'whoKnows& it = *impliedIterator;'  I should have changed "it" to be something like "yourObjRef" since the iterator is now implied and hidden.

 

So right now I'm using alleightup's suggestion and it's working well. Hopefully there isn't any memory loss, it'll be a little bit before I have the actual program ready to test and can see for myself.
 
Currently my question is how can I remove an element?
Something along the lines of this:
 

for(auto& it : lifeforms)
{
      if(it->food < 1)
            lifeforms.remove(it);
}
Does not work.
The program crashes.

How do I remove an element?
(while freeing its memory, as I only need the elements that are in the list)

 

Given the use of std::forward_list, you are limited to pretty much a single solution for the above:

 

  lifeforms.remove_if( []( lifeform& n ){ return n.food < 1; } );

 

Sorry, you can't iterate and remove from a forward list directly, for that you need to go back to std::list.

Share this post


Link to post
Share on other sites
Syerjchep    212

Err, I probably should have changed the naming a bit so it was more clear..  The auto type in the examples I gave will become references to the dereferenced iterator.  So, 'auto& it' actually becomes 'whoKnows& it = *impliedIterator;'  I should have changed "it" to be something like "yourObjRef" since the iterator is now implied and hidden.
 

So right now I'm using alleightup's suggestion and it's working well. Hopefully there isn't any memory loss, it'll be a little bit before I have the actual program ready to test and can see for myself.
 
Currently my question is how can I remove an element?
Something along the lines of this:
 

for(auto& it : lifeforms)
{
      if(it->food < 1)
            lifeforms.remove(it);
}
Does not work.
The program crashes.

How do I remove an element?
(while freeing its memory, as I only need the elements that are in the list)

 
Given the use of std::forward_list, you are limited to pretty much a single solution for the above:
 
 
  lifeforms.remove_if( []( lifeform& n ){ return n.food < 1; } );
 
Sorry, you can't iterate and remove from a forward list directly, for that you need to go back to std::list.

So that seems like something I only need to run once per frame, and not once per organism per frame, correct?
e.g.
while(running)
{
      //do other program stuff
      for(auto& it : lifeforms)
      {
            it->doLivingStuff(); //example function, though everything here is pretty much for example
            //everything else a lifeform has to do per frame
      }
      lifeforms.remove_if( []( lifeform& n ){ return n.food < 1; } ); //remove any dead lifeforms
}
Edited by Syerjchep

Share this post


Link to post
Share on other sites
Hiwas    5807

So that seems like something I only need to run once per frame, and not once per organism per frame, correct?

e.g.
while(running)
{
      //do other program stuff
      for(auto& it : lifeforms)
      {
            it->doLivingStuff(); //example function, though everything here is pretty much for example
            //everything else a lifeform has to do per frame
      }
      lifeforms.remove_if( []( lifeform& n ){ return n.food < 1; } ); //remove any dead lifeforms
}

 

That is correct, and as such you are double iterating the list which is probably bad.  If you change to std::list, then you can rewrite as:

 

while( running )
{
  for( auto it = lifeforms.begin(); it!=lifeforms.end(); ++it )
  {
    it->doLivingStuff();
    if( it->food < 1 )
      it = lifeforms.erase( it );
  }
}

 

In this case you are back to using the actual iterators instead of hiding them, and you are using a double linked list (i.e. std::list) which allows erase to function without being a secondary iteration task.

Share this post


Link to post
Share on other sites
Syerjchep    212
It gave me compiling errors until I changed it to:
lifeforms.remove_if([](lifeform* n){ return n->food < 1; } );
I'll change to a regular list if it's a problem.
But will that cause a noticable drop in preformance?
(note that I have thousands of objects in a list each having their functions run and values modifyed and accessed per frame)

Share this post


Link to post
Share on other sites
Hiwas    5807

It gave me compiling errors until I changed it to:

lifeforms.remove_if([](lifeform* n){ return n->food < 1; } );
I'll change to a regular list if it's a problem.
But will that cause a noticable drop in preformance?
(note that I have thousands of objects in a list each having their functions run and values modifyed and accessed per frame)

 

Sorry about the typo, oops. :)

 

For the most part, you should end up with better performance given the way you are using the list.  Individual operations are a little more expensive but that is pretty much trivial and can be ignored.  You should not be worrying about the performance at this level, it is a minor issue compared to what your other functions are likely going to be doing.

Share this post


Link to post
Share on other sites
Syerjchep    212
I switched my code to use a regular list, and it's working alright.
But I guess I have a slightly different problem now: memory leaks.
I kinda figured when elements were removed from the list they weren't freed from memory, so I tried something like this:
if((*it)->food < 1)
{
     for( auto leaf = (*it)->cells.begin(); leaf!=(*it)->cells.end(); ++leaf )
          free(*leaf);
     void *old = *it;
     it = lifeforms.erase(it);
     free(old);
}
I guess how this works depends on the actual class, so I'll post what I'm using right now:
class cell;

class lifeform
{
    public:
    list<cell*> cells;
    int x,y;
    int food;
    int age;
    int pointerX,pointerY;
    int data[geneMaxLines][geneMaxArgs];

    void doFunction(int a,int b,int c,int d,int e);
    bool addCell(int newx,int newy,int newr,int newg,int newb);
};

list<lifeform*> lifeforms;

class cell
{
    public:
    int x,y;
    bool alive;
    int type;
    int r,g,b;
    int food;
    Uint32 color;
    lifeform *parent;
    int eat();
    void show();
};
This seems to cut down on the memory leaks, however I get a strage problem that the number of elements in the list is drastically differnet from the lists size, once the programs been running for a bit and many elements have been removed:
int cellCount = 0;
for( auto it = lifeforms.begin(); it!=lifeforms.end(); ++it )
      cellCount++;
int difference = ((signed int)lifeforms.size())-cellCount;
Difference fluctuates rapidly, itll be in the thousands one frame and then tens the next.

Note that if I go back to just inserting the:
lifeforms.remove_if([](lifeform* n){ return n->food < 1; } );
the difference stops doing that.
Memory leaks occur with both methods, if I don't include free statements. Edited by Syerjchep

Share this post


Link to post
Share on other sites
iMalc    2466

Why do you have a list of pointers to cells anyway, why not just a list of cells?

Why are you using free? You must 'delete' what you 'new'. As this is clearly C++ code, you should not be using malloc or free.

Why do you have a void pointer? Those are very very seldom useful in C++. Call delete through a pointer to the right type, or base class type.

 

Those are the obvious problems to fix first.

Share this post


Link to post
Share on other sites
Syerjchep    212

Why do you have a list of pointers to cells anyway, why not just a list of cells?

Read the OP.
That was the origional problem.
I needed to modify the elements of the list and run functions on them.
If I used pointers then I'd just get a COPY of the object, and the modifications would not stick.

Why are you using free? You must 'delete' what you 'new'. As this is clearly C++ code, you should not be using malloc or free.

Crashes the program.
I try "delete &old;" after the erase and it doesn't work.
I've tried a few other things as well.

Why do you have a void pointer? Those are very very seldom useful in C++. Call delete through a pointer to the right type, or base class type.

Doesn't seem to make a difference.

Those are the obvious problems to fix first.

Can't really fix problems concerning how "common" or "correct" something is if the program doesn't even stay open.
At least with the things I was doing it was working, it just had a huge memory leak.

Share this post


Link to post
Share on other sites
iMalc    2466

 

Why do you have a list of pointers to cells anyway, why not just a list of cells?

Read the OP.
That was the origional problem.
I needed to modify the elements of the list and run functions on them.
If I used pointers then I'd just get a COPY of the object, and the modifications would not stick.
 

Why are you using free? You must 'delete' what you 'new'. As this is clearly C++ code, you should not be using malloc or free.

Crashes the program.
I try "delete &old;" after the erase and it doesn't work.
I've tried a few other things as well.

Why do you have a void pointer? Those are very very seldom useful in C++. Call delete through a pointer to the right type, or base class type.

Doesn't seem to make a difference.

Those are the obvious problems to fix first.

Can't really fix problems concerning how "common" or "correct" something is if the program doesn't even stay open.
At least with the things I was doing it was working, it just had a huge memory leak.

 

Oh now I see what you meant earlier. You were in fact mistaken right from your very first post. You can of course modify items in a list, and no I certainly don't mean "replace". You can make whatever changes to the items in a list that you like. Same for a vector. This is good news because it means you probably can forget about storing pointers to objects afterall, and have the containers manage the memory for you.

Post the code for whatever "tests" you did if you want to find out what led to your incorrect conclusion.

 

You are using delete wrong. You can't delete the address of a local or other variable, you must pass just the pointer varible itself to delete.

There are on if's or but's about it either. If you allocated using 'new' then you MUST destroy using 'delete', end of story.

Deleting through a pointer to the correct type or base type will indeed make a very big difference. It will mean that it actually works, instead of causing memory leaks and all sorts of other nasties like you are having.

 

These are not merely suggestions, like telling you that you could replace a division with a shift or something trivial and unimportant like that. These are vital corrections. You will not get a correctly functioning program without doing so, and you will not fix your memory leaks.

Failing to match new and delete, or new[] and delete[], is precisely what is probably causing the leaks to begin with.

 

If you don't understand the advice, then ask more questions, or post code so that we can see what you are doing wrong.

Share this post


Link to post
Share on other sites
rip-off    10976
If you want to modify a value in a container, don't copy the dereferenced iterator into another value. Either use the arrow operator, or bind the dereferenced iterator to a reference:
for (auto it = c.begin() ; it != c.end() ; ++i) {
    it-> frobnicate();
    // Or ...
    Example &example = *it;
    example.foo();
    example.bar();
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this