Is this the wrong way to use std::list?

T

TBass

So I have a class:

class Client
{
unsigned int ClientID;
....
};


class MyListenSocket
{
...
AddClient( Client *pClient);
RemoveClient( unsigned int ID );
std::list<Client> m_listClients;
};


To add clients to the list, AddClient is called:

MyListenSocket::AddClient( Client *pClient )
{
m_listClients.push_back( *pClient );
}


But a client can be erased from anywhere on the list. I wrote this
function:

MyListenSocket::RemoveClient( unsigned int ID )
{
std::list<Client>::iterator it;
for( it = m_listClients.begin();
it != m_listClients.end();
++it )
{
if ( it->ClientID() == ID )
{
m_listClients.erase( it );
break;
}
}
}

The problem is that this seems to corrupt the heap in my program. I
know that the iterator is corrupted when I use the erase command, but
why would that corrupt the heap?

Is this not the way to delete an item from the middle of a list?
Should I not be using ::list for this type of purpose?

Thanks in advance,
Tom Junior
 
T

TBass

Ha! I figured it out.

I was thinking of it as the list being pointers to objects, but it's
really a container, I suppose.

This: m_listClients.erase( it );

Deleted the entire instance of the Client.

Which meant when I went to disconnect the client in next step, I was
calling bad memory. I flipped the order, and it was all good.

I'm starting to like this c++. :)
 
C

Christopher

Ha! I figured it out.

I was thinking of it as the list being pointers to objects, but it's
really a container, I suppose.

This: m_listClients.erase( it );

Deleted the entire instance of the Client.

Which meant when I went to disconnect the client in next step, I was
calling bad memory. I flipped the order, and it was all good.

I'm starting to like this c++. :)



A few problems. When you pushback you make a copy of the argument.
thus you are calling the copy constructor. Along your lines of
thinking, make a list of pointers to the object instead of a list of
objects. Then your list is pretty much a collection of handles and is
tons faster and easier to manager.

When you erase an element in the middle of iteration you need to
update the iterator with the return value of the erase call.
Currently, your erasure makes the iterator invalid at that point:

list<myobject>::iterator it = MyObjectList.begin()

while( it != MyObjectList.end() )
{
if (some condition for erasure )
{
it = MyObjectList.erase(it);
}
else
{
it++;
}
}

Also, because you want to look up clients in the container, I think a
std::map would be more appropriate than an std::list. With a map you
can look them up with a key, in your case you have one already: the
client ID.
 
S

Salt_Peter

So I have a class:

class Client
{
unsigned int ClientID;
....

};

Lets assume that the compiler generated copy ctor for Client works for
now.
class MyListenSocket
{
...
AddClient( Client *pClient);

It would be interesting to know how you are managing the pointer
above.

public:
void AddClient( const Client& client ); // much better
RemoveClient( unsigned int ID );
private:

std::list<Client> m_listClients;

};

To add clients to the list, AddClient is called:

MyListenSocket::AddClient( Client *pClient )
{
m_listClients.push_back( *pClient );

}

But a client can be erased from anywhere on the list. I wrote this
function:

MyListenSocket::RemoveClient( unsigned int ID )

void MyListenSocket::RemoveClient( const unsigned id )
{
std::list<Client>::iterator it;

for( it = m_listClients.begin();
it != m_listClients.end();
++it )
{
if ( it->ClientID() == ID )
{
m_listClients.erase( it );
break;
}
}

}

The problem is that this seems to corrupt the heap in my program. I
know that the iterator is corrupted when I use the erase command, but
why would that corrupt the heap?

The iterator is not corrupted, it gets invalidated. Your free store is
suffering from something else.
i'ld probably use a std::set instead of a std::list.
 
J

Jim Langston

TBass said:
So I have a class:

class Client
{
unsigned int ClientID;
....
};


class MyListenSocket
{
...
AddClient( Client *pClient);
RemoveClient( unsigned int ID );
std::list<Client> m_listClients;
};


To add clients to the list, AddClient is called:

MyListenSocket::AddClient( Client *pClient )
{
m_listClients.push_back( *pClient );
}


But a client can be erased from anywhere on the list. I wrote this
function:

MyListenSocket::RemoveClient( unsigned int ID )
{
std::list<Client>::iterator it;
for( it = m_listClients.begin();
it != m_listClients.end();
++it )
{
if ( it->ClientID() == ID )
{
m_listClients.erase( it );
break;
}
}
}

The problem is that this seems to corrupt the heap in my program. I
know that the iterator is corrupted when I use the erase command, but
why would that corrupt the heap?

Is this not the way to delete an item from the middle of a list?
Should I not be using ::list for this type of purpose?

As others have stated, there are a few problems with this code, or can be.

First, as stated, erase invalidates iterators. So you need to use the
algorithm:

for( it = m_listClients.begin(); it != m_listClients.end(); )
{
if ( it->ClientID() == ID )
{
it = m_listClients.erase( it );
break;
}
else
{
++it;
}
}

Second, the desturctor for the Client is not being called. Now, if clients
are creating using new, then you'll need to delete the pointer with delete.
This will also free the memory so you don't get a memory leak.

for( it = m_listClients.begin(); it != m_listClients.end(); )
{
if ( it->ClientID() == ID )
{
delete (*it);
it = m_listClients.erase( it );
break;
}
else
{
++it;
}
}

This depends though on the ownership of the Client pointer. Who owns the
pointer? If your m_list_Clients is the only place you are keeping this
pointer, then m_listClients owns the pointer and needs to delete it when it
gets erased.
 
A

Andre Kostur

So I have a class:

class Client
{
unsigned int ClientID;
....
};


class MyListenSocket
{
...
AddClient( Client *pClient);
RemoveClient( unsigned int ID );
std::list<Client> m_listClients;
};


To add clients to the list, AddClient is called:

MyListenSocket::AddClient( Client *pClient )
{
m_listClients.push_back( *pClient );
}

Why is this function taking a client by pointer? Why confuse the issue?
have it take the Client by const-reference.
But a client can be erased from anywhere on the list. I wrote this
function:

MyListenSocket::RemoveClient( unsigned int ID )
{
std::list<Client>::iterator it;
for( it = m_listClients.begin();
it != m_listClients.end();
++it )
{
if ( it->ClientID() == ID )
{
m_listClients.erase( it );
break;
}
}
}

The problem is that this seems to corrupt the heap in my program. I
know that the iterator is corrupted when I use the erase command, but
why would that corrupt the heap?

Because you've got a problem somewhere else. Check your Client class to
make sure that it is properly copy constructable and assignable.
 
T

Tadeusz B. Kopec

As others have stated, there are a few problems with this code, or can
be.

First, as stated, erase invalidates iterators. So you need to use the
algorithm:

for( it = m_listClients.begin(); it != m_listClients.end(); ) {
if ( it->ClientID() == ID )
{
it = m_listClients.erase( it );
break;
}
else
{
++it;
}
}

This change makes difference only if 'it' is used after the loop and if
value 'past the erased element' is appropriate there. Quite strong
assumption.
Second, the desturctor for the Client is not being called. Now, if
clients are creating using new, then you'll need to delete the pointer
with delete. This will also free the memory so you don't get a memory
leak.

for( it = m_listClients.begin(); it != m_listClients.end(); ) {
if ( it->ClientID() == ID )
{
delete (*it);
it = m_listClients.erase( it );
break;
}
else
{
++it;
}
}

This depends though on the ownership of the Client pointer. Who owns
the pointer? If your m_list_Clients is the only place you are keeping
this pointer, then m_listClients owns the pointer and needs to delete it
when it gets erased.

There are values not objects stored in the list.
 
J

Jim Langston

Tadeusz said:
This change makes difference only if 'it' is used after the loop and
if value 'past the erased element' is appropriate there. Quite strong
assumption.

Actually, the for statement is executed until it != m_listClient.end(). If
you don't use this algorithm but ++it in the for statemnet, the iterator
becomes invalidated in the erase staement. ++it is incrementing an
invalidated iterator. What usually happens is that not all elements in the
container are visited, although it's undefined behavior so anything can
happen.

Try running this program and see what output you get.

#include <iostream>
#include <list>

main()
{
std::list<int> Data;
for ( int i = 0; i < 10; ++i )
Data.push_back(i);

for ( std::list<int>::iterator it = Data.begin(); it != Data.end();
++it )
{
std::cout << *it << "\n";
}
std::cout << "\n";
for ( std::list<int>::iterator it = Data.begin(); it != Data.end();
++it )
{
std::cout << *it << "\n";
if ( *it == 5 )
Data.erase( it );
}
}

For me, Microsoft Visual C++ .net 2003 under XP I get an access violation
reading location...
There are values not objects stored in the list.

Okay, then they don't need to be deleted. My bad on that.
 
T

Tadeusz B. Kopec

Actually, the for statement is executed until it != m_listClient.end().
If you don't use this algorithm but ++it in the for statemnet, the
iterator becomes invalidated in the erase staement. ++it is
incrementing an invalidated iterator. What usually happens is that not
all elements in the container are visited, although it's undefined
behavior so anything can happen.

After erasing break statement is executed, so no incrementation, just
leaving the loop. Yes, the value of iterator is invalid after that so it
shouldn't be used.
Try running this program and see what output you get.

#include <iostream>
#include <list>

main()
{
std::list<int> Data;
for ( int i = 0; i < 10; ++i )
Data.push_back(i);

for ( std::list<int>::iterator it = Data.begin(); it != Data.end();
++it )
{
std::cout << *it << "\n";
}
std::cout << "\n";
for ( std::list<int>::iterator it = Data.begin(); it != Data.end();
++it )
{
std::cout << *it << "\n";
if ( *it == 5 )
Data.erase( it );
}
}

For me, Microsoft Visual C++ .net 2003 under XP I get an access
violation reading location...

But to be equivalent to original code it should be
if ( *it == 5 )
{
Data.erase( it );
break;
}
and everything is fine (OK, I had to add return type to main).
 
J

Jim Langston

Tadeusz said:
After erasing break statement is executed, so no incrementation, just
leaving the loop. Yes, the value of iterator is invalid after that so
it shouldn't be used.


But to be equivalent to original code it should be
if ( *it == 5 )
{
Data.erase( it );
break;
}
and everything is fine (OK, I had to add return type to main).

Dag nab it. I missread the entire code. That's what I get for trying to
respond to a post after being up for > 24 hours.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,139
Messages
2,570,805
Members
47,356
Latest member
Tommyhotly

Latest Threads

Top