Fast/easy removal from container classes? (C++)

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Apr 24, 2006 at 13:49

Alright, suppose the following situation. You have a person class and you also have a company class. A company is a group of people so you would have a member variable list containing pointers to all the persons in the company.

Adding people to a companies list is easy. However, say a person dies (or whatever) and I need to delete him. How can I quickly and easily remove this person from every list that he is in? Simply deleting him will result in a bunch of bad pointers in lists.

Thanks in advance

12 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 24, 2006 at 14:00

And you don’t want to store a list of companies in the class Person itself because…?

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Apr 24, 2006 at 14:10

@.oisyn

And you don’t want to store a list of companies in the class Person itself because…?

Yes, that would work.

But now lets say, that people can be in other lists other than companies (eg. clubs, families, social groups, whatever) and what if the comapany (or whatever) gets removed too?

820ce9018b365a6aeba6e23847f17eda
0
geon 101 Apr 24, 2006 at 14:39

Store pointers booth ways, and inform the object in the other end if you are about to delete person/company.

You also probably want to create a base class for collections of people. That way you don’t need add specialized code for companies, families, clubs, etc.

46462f88a1670d7e9cbbfa360aa20134
0
juhnu 101 Apr 24, 2006 at 14:56

Or you might want to use a standard sql database for all this..

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Apr 24, 2006 at 15:13

@geon

Store pointers booth ways, and inform the object in the other end if you are about to delete person/company. You also probably want to create a base class for collections of people. That way you don’t need add specialized code for companies, families, clubs, etc.

Ok thanks :yes:

820ce9018b365a6aeba6e23847f17eda
0
geon 101 Apr 24, 2006 at 17:52

@juhnu

Or you might want to use a standard sql database for all this..

Not an option, since this is obviously an exercise in C++ class design. But, yes, an SQL database would be the (only?) rational solution.

6b7e1a4b42e4b47d92fdef8bf2bd8e2c
0
Jare 101 Apr 29, 2006 at 13:47

If all your containers have regular “update” functions, then in order to kill a person, you simply flag him as “dead” (but dont delete the object yet) and all containers detect and remove any dead persons during the update. Once all containers have updated, and thus have eliminated their references to that person, the dead person itself can be safely buried er… deleted. :)

How to know if all containers have updated?

a) a reference counter in the person that lists how many containers it is held into. Containers increase that reference counter in the person when the person is added to a container, and decrement the reference counter when the person is removed from a container.

b) guaranteed maximum amount of time for all containers to have run an update. This may seem quirky and error-prone, but is in fact fairly typical in one way or another. Just make sure you get the “guaranteed” part right.

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Apr 29, 2006 at 14:05

@Jare

If all your containers have regular “update” functions, then in order to kill a person, you simply flag him as “dead” (but dont delete the object yet) and all containers detect and remove any dead persons during the update. Once all containers have updated, and thus have eliminated their references to that person, the dead person itself can be safely buried er… deleted. :)

Wouldn’t an “update” require looping through each member of each container object?

I was looking for an algorithm that didn’t have any linear (or greater) dependancies.

I’m guessing the most efficient would be using a list of containers in each member and container.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Apr 29, 2006 at 14:52

@poita

Wouldn’t an “update” require looping through each member of each container object?

Aren’t you doing that anyway sooner or later, like when iterating the container to display the list of persons on the screen?

6b7e1a4b42e4b47d92fdef8bf2bd8e2c
0
Jare 101 Apr 30, 2006 at 11:16

@poita

Wouldn’t an “update” require looping through each member of each container object?

Yeah, that’s why I said “if they have such an update function”. That situation is not uncommon.

Yet another option is to have a registry of “groups”; whenever you want to kill a person, you inform this registry and it in turn notifies all the containers. If your deletes are relatively rare and you don’t mind having an additional dependency, this solution is good, clean, and doesn’t add any persistent overhead.

You can see there are many solutions to the problem, each with its own caveats and strengths, but only you know which one is better suited to your specific situation.

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Apr 30, 2006 at 12:30

@.oisyn

Aren’t you doing that anyway sooner or later, like when iterating the container to display the list of persons on the screen?

Good point… :wallbash:

I guess I wasn’t thinking straight.

Thanks Jare for your input.

Cd577ee1cb56aa2ad5645b7daa0a2830
0
eddie 101 May 03, 2006 at 04:01

Still, a good question. I love these types of discussions.