Removing from list recursively in C#

Question

I have the following recursive function that is used to search down a hierarchical tree and remove found objects from a list:

private List<Tag> RemoveInvalidTags(Device device, List<Tag> tags)
{
   var childDevices = device.ChildDevices.Select(c => c.ChildDevice);

   foreach (var child in childDevices)
   {
      tags.Remove(child.Tag);
      RemoveInvalidTags(child, tags);
   }

   return tags;
}

What I am expecting this to do is remove all child device tags at this level from the tags list, call the function recursively for your children, then return that list up to the previous level.

Will this pass the tags list by reference and modify the original passed list? Or should I be doing something along the lines of

validTags = CollectValidTags(child, tags);

and adding up all the returned lists?

score 3 · Accepted Answer · 2011-09-12T00:23:45.323

3

Will this pass the tags list by reference

No. The list object is passed "by value" (but see next). (ref or out is required to "pass by reference" in C#, but that is not being done here, nor does it need to be.)

and modify the original passed list?

Yes. This is because the list object is passed. And that list object is mutated. Passing a reference type (anything defined with class) never implicitly makes a copy/clone/duplicate. An object is what it is.

Now, back to "pass by value": the "value passed" is the value of the "reference" (internal, no need to concern with this): this calling strategy is better known as Call/Pass By Object Sharing in a langauge like C#. The same object is shared (just as if it were assigned to two different variables). (Value types -- a struct -- are different in that they (often) are copied/duplicated on the stack, but a List<T> is a class.)

Or should I be doing something along the lines of

It depends upon the desired semantics. Is the caller expecting the side-effects directly or indirectly? Can the mutation side-effect lead to unexpected scenarios? Make sure to document it either way. (I prefer the way that guarantees the initial object is not mutated.)

Hope that clears some things up.

Happy coding.

edited Sep 12 '11 at 00:23

answered Sep 12 '11 at 00:07

Please explain -1. I don't mind, but without an explanation it does no good. – Sep 12 '11 at 00:14
2

My only nitpick here is how you refer to the "List object" being passed by value. This is misleading at best. The object is what's sitting on the heap. The reference is passed by value, yes, but to continue to say *list object* strikes me as odd. BTW, I removed the -1 after I read it over again. I misunderstood you a bit due to the issue I mention above the first time around. – Ed S. Sep 12 '11 at 00:16
@Ed S. I hope the edits cleaned that up some. I was trying to focus on the fact than an object is ... itself, no matter by what name (variable) it goes by. It still does start a little strong though. – Sep 12 '11 at 00:20
1

+1 I find that thinking of objects being passed by value is the most useful way of thinking of `ref`. – Kirk Broadhurst Sep 12 '11 at 00:23
It's more accurate to speak of object references being passed by value. A reference-type variable holds a reference to an object, and that reference is what's being passed around, whether by value or by reference. – phoog Sep 21 '11 at 18:33

score 2 · Answer 2 · answered Sep 12 '11 at 00:54

In your code you are modifying the items in your tags parameter and passing back the modified list as your result. You want to avoid modifying lists in this way - especially inside loops where it can cause you grief in many situations.

I have a LINQ-based alternative for you.

If I understand the intent of your code you want to do something like this:

Func<Device, IEnumerable<Device>> flatten = null;
flatten = d =>
{
    return (new [] { d }).Concat(
        from c in d.ChildDevices
        from f in flatten(c)
        select f);
};

var collectedValidTags = flatten(device).Select(d => d.Tag);

var result = tags.Except(collectedValidTags).ToList();

This approach doesn't pass your list of tags around so there is no chance of modifying your original list.

Does this help?

I can't select your answer as the correct answer because it doesn't actually answer my original question, however I've given you an upvote because yours is a better solution. Cheers. — dnatoli, Sep 12 '11 at 01:38
@link664 - Totally understood. I wasn't expecting to directly answer your question, but instead to give you a clean, functional way to do what you wanted without messing around with mutable collections. — Enigmativity, Sep 12 '11 at 01:56

score 0 · Answer 3 · edited May 23 '17 at 12:00

Short answer - your code will do what you want.

Long answer - you should read descriptions of what the ref keyword does. I would suggest you read as many descriptions as possible; there are many different ways to articulate it ("I like to think of it as... ") and some will work for you whilst others won't. If you read many descriptions (from people who understand it) then some kind of understanding should gel for you.

Here's a list to get you started:

Removing from list recursively in C#

3 Answers3