Jump to content

  • Log In with Google      Sign In   
  • Create Account


Memory leaks from removing elements from list.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 13 June 2013 - 02:44 PM

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.

Sponsor:

#2 Waterlimon   Crossbones+   -  Reputation: 2417

Like
0Likes
Like

Posted 13 June 2013 - 02:57 PM

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.

o3o


#3 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 13 June 2013 - 03:02 PM

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, 13 June 2013 - 03:03 PM.


#4 EnderJSC   Members   -  Reputation: 109

Like
0Likes
Like

Posted 13 June 2013 - 03:22 PM

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;
}


#5 AllEightUp   Moderators   -  Reputation: 4158

Like
0Likes
Like

Posted 13 June 2013 - 04:30 PM

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. :)



#6 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 13 June 2013 - 07:52 PM

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, 13 June 2013 - 08:42 PM.


#7 AllEightUp   Moderators   -  Reputation: 4158

Like
0Likes
Like

Posted 13 June 2013 - 09:01 PM

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.



#8 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 13 June 2013 - 09:23 PM

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, 13 June 2013 - 09:24 PM.


#9 AllEightUp   Moderators   -  Reputation: 4158

Like
0Likes
Like

Posted 13 June 2013 - 09:36 PM

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.



#10 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 13 June 2013 - 09:45 PM

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)

#11 AllEightUp   Moderators   -  Reputation: 4158

Like
0Likes
Like

Posted 13 June 2013 - 10:02 PM

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.



#12 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 14 June 2013 - 02:09 PM

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, 14 June 2013 - 02:45 PM.


#13 iMalc   Crossbones+   -  Reputation: 2287

Like
0Likes
Like

Posted 14 June 2013 - 03:48 PM

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.


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#14 Syerjchep   Members   -  Reputation: 180

Like
0Likes
Like

Posted 14 June 2013 - 04:01 PM

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.

#15 iMalc   Crossbones+   -  Reputation: 2287

Like
0Likes
Like

Posted 14 June 2013 - 11:40 PM

 

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.


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#16 rip-off   Moderators   -  Reputation: 7962

Like
1Likes
Like

Posted 15 June 2013 - 02:27 AM

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();
}


#17 iMalc   Crossbones+   -  Reputation: 2287

Like
0Likes
Like

Posted 15 June 2013 - 03:33 AM

Good point, I should have noticed he was doing that in the original post.


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS