Memory leaks from removing elements from list.

Started by
15 comments, last by iMalc 10 years, 10 months ago
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.
Advertisement
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

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

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

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

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)

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.

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
}

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.

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)

This topic is closed to new replies.

Advertisement