looping through an array to delete stuff

[Red Squirrel]

I tend to find various ways of doing this but thought I'd ask, what is the best or better way of doing this?

Lets say I have an array of items I want to loop through and delete items. So Either a Vector, or a C# List... I'm speaking generally here not caring about the language.

When I'm in the loop if I delete an item then it's size will change so the loop may not complete as expected.

What I normally do is loop through, adding all valid items to another array, then clear first and copy temp one over.

Now, is there a better way of doing it?

In this particular case I'm dealing with C# List object. This is my code:

		//this is used to check if anyone went offline or something, so we remove them from array
		public bool ValidateRegisteredMobs()
		{
			List<Mobile> templist = new List<Mobile>();
			
			for(int i=0;i<RegisteredMobs.Count;i++)
			{
			Mobile mob = RegisteredMobs[i] as Mobile;
			
			if(mob.NetState==null || mob.Deleted)continue;
			templist.Add(mob);
			}
		
			RegisteredMobs.Clear();
			
			RegisteredMobs = templist;
			
			templist.Clear();

			return templist.Count>=MinMembers;
		}

 

[Crusty]

Grab an enumerator from your list and use that to iterate through the list, if the current element needs to be deleted you can add them to any kind of collection really. Then once you've determined all the elements to delete, iterate through that collection and call remove on the original list for each element in the collection.

So you've got the right idea kind of, but you are creating extra work for the garbage collector. In fact, your RegisteredMobs.Clear(); is pointless, considering on the next line you change the reference to a whole new List. Instead of saving the elements you want to keep.

 

[degibson]

There's a distinction between ways that work and ways that are fast and efficient. The above works but is inefficient, for reasons mentioned by crusty, and also because of memory allocation / deallocation (depends on memory manager, naturally), pointer locality, and potentially overhead for building a brand new list (depends on implementation of List<>, but could involve the memory manager on every new item). As I understand C#, you can go ahead and add extra object copying, as well, for the RegisteredMobs = templist; line.

Crusty's suggestion of an iterator (are they called enumerators in C#?) is a good one, because you don't need a separate list, and if List<> is implemented well, it will allow deletions without making a new list. I'm sorry I can't show you the syntax-- C# isn't exactly my forte.

Edit: Forgot an and in the first sentence. First sentences are important.

 

[Red Squirrel]

Yeah kind of figured my way was unefficient. How about this?

			//this is used to check if anyone went offline or something, so we remove them from array - also to check if enough people actually registered
		public bool ValidateRegisteredMobs()
		{
			List<Mobile> todel = new List<Mobile>();
			
			foreach(Mobile mob in RegisteredMobs)
			{
				if(mob.NetState==null || mob.Deleted)todel.Add(mob);
			}		

			foreach(Mobile mob in todel)
			{
				RegisteredMobs.Remove(mob);
			}
			
			todel.Clear();

			return RegisteredMobs.Count>=MinMembers;
		}

Also is Clear() even the right function to release the memory?

 

[Crusty]

Really you can just let it be and the Garbage Collector will take care of it eventually, but if you want to you would call Dispose()

Clear() simply removes all elements from the list.

 

[lozina]

loop through the List backwards.

List<Mobile> mylist; // whatever your list is...
for (int x = mylist.size() - 1; x >= 0; x--) {
if (we_want_to_delete)
mylist.Remove(x);
}

 

[Crusty]

Originally posted by: lozina
loop through the List backwards.

List<Mobile> todel = new List<Mobile>();
for (int x = todel.size() - 1; x >= 0; x--) {
if (we_want_to_delete)
todel.Remove(x);
}

You can't do that in C#. The function declaration is List<T>.Remove(T item). So you pass it the object you are wanting to remove, not the index. The Remove function will also remove the first copy of the object it finds.

 

[imported_Dhaval00]

Originally posted by: Crusty
Really you can just let it be and the Garbage Collector will take care of it eventually, but if you want to you would call Dispose()

Clear() simply removes all elements from the list.

Ummm... there is no "Dispose()" for Generics. But you're right about letting the GC do its job.

 

[imported_Dhaval00]

Originally posted by: lozina
loop through the List backwards.

List<Mobile> mylist; // whatever your list is...
for (int x = mylist.size() - 1; x >= 0; x--) {
if (we_want_to_delete)
mylist.Remove(x);
}

Based on this, and cleaning up this logic a bit more, you can try the following:

for (Int32 i = 0; i < myList.Count; i++)
{
if (RegisteredMobs"i".NetState == null || RegisteredMobs"i".Deleted) // Access the object using List<T>'s indexer - replace double quotes with square braces.
{
myList.RemoveAt(i);
}
}

This is not tested and might require further tweaking.

 

[Red Squirrel]

Actually I've seen removeat used in such situation, only thing, would that keep a bunch of empty gaps in the array? or is there a way to "defrag" it afterwards? This does seem more efficient then the way I used.

 

[Snapster]

Originally posted by: RedSquirrel
Actually I've seen removeat used in such situation, only thing, would that keep a bunch of empty gaps in the array? or is there a way to "defrag" it afterwards? This does seem more efficient then the way I used.

As far as you are concerned it's handled under the hood:

RemoveAt on MSDN
In collections of contiguous elements, such as lists, the elements that follow the removed element move up to occupy the vacated spot. If the collection is indexed, the indexes of the elements that are moved are also updated. This behavior does not apply to collections where elements are conceptually grouped into buckets, such as a hash table.

 

[degibson]

The most efficient way I know to remove items from a list peeks at the next element during a traversal ... if the next element is supposed to be deleted, push the next element onto a queue of free nodes (ideally, Queue<Node*> in C++ -- I don't know if C# has an equally-lightweight analog), to avoid calling the memory manager (when allocating a new node, check the queue first before calling new).

This brings up the question: If you're adding and removing nodes from this list fairly often -- often enough to worry about optimizing it, why is it a list in the first place? Why not make it a hash table or tree or some other faster structure? Is it not possible to scan over trees/hash tables in C#?

 

[lozina]

Originally posted by: Crusty

Originally posted by: lozina
loop through the List backwards.

List<Mobile> todel = new List<Mobile>();
for (int x = todel.size() - 1; x >= 0; x--) {
if (we_want_to_delete)
todel.Remove(x);
}

You can't do that in C#. The function declaration is List<T>.Remove(T item). So you pass it the object you are wanting to remove, not the index. The Remove function will also remove the first copy of the object it finds.

Then it's the RemoveAt(x) method

there's a method that deletes on a specific index