How to create my own generic list class?

Question

I have this :

public class CChainElement
{
    public CChainElement m_Prev, m_Next;
}

public class CChainList : IEnumerable
{
    public CChainElement m_First;

    internal void Add(CChainElement Element)
    {
        if (m_First != null)
            m_First.m_Prev = Element;

        Element.m_Next = m_First;
        m_First = Element;
    }
}

public class CEntity : CChainElement
{
}

public class CItem : CEntity
{
}

public class CTest
{
    void Test()
    {
        CChainList AllItem = new CChainList();
        CItem Item = new CItem();

        AllItem.Add(Item);

        CItem FirstItem = AllItem.m_First as CItem;
        CItem SecondItem = FirstItem.m_Next as CItem;
    }
}

And I'd like to switch to something like this :

public class CChainElement<T> where T : CChainElement<T>
{
    public T m_Prev, m_Next;
}

public class CChainList<T> : IEnumerable where T : CChainElement<T>
{
    public T m_First;

    internal void Add(T Element)
    {
        if (m_First != null)
            m_First.m_Prev = Element;

        Element.m_Next = m_First;
        m_First = Element;
    }
}

public class CEntity : CChainElement<CEntity>
{
}

public class CItem : CEntity
{
}

public class CTest
{
    void Test()
    {
        CChainList<CItem> AllItem = new CChainList<CItem>();
        CItem Item = new CItem();

        AllItem.Add(Item);

        CItem FirstItem = AllItem.m_First;  // Yeepee, no more "as CItem" ..! ;-)
        CItem SecondItem = FirstItem.m_Next;
    }
}

And I get the error that CItem can't be converted to CChainElement<CItem> .

So my question is : is there anyway to constrain public class CChainElement<T> so it'll take CItem graciously, even if it doesn't inherit directly from CChainElement ?

My goal is obviously that all classes inherited from CChainElement<T> being able to be listed with my generic list class, while avoiding the explicit cast.

Thanks in advance for any help !

EDIT: in my full project, CEntity is used for many different things as an abstraction class (ie: I can manipulate Monsters in a similar way than Items through it), so it can't be changed to be a generic CEntity<T> .

@Cuong Le : I'd just like to remove the need for the "as CItem". It's not that important, but if I can do it with just a few changes in my list classes, that'd be nice. There's also another bonus : strong typing of elements, so I won't mess up what I'm adding to my list (ie: couldn't add anymore a CEntity to a CItem list). — ManuTOO, Sep 25 '12 at 07:30
.NET `List`s are not actually linked lists (that's `LinkedList`), they are secretly arrays that get expanded as they fill. This has performance implications. Also, unless you do it as an exercise, what could this possibly accomplish? If you want "strong typing", just make a `List`? Or is re-implementing a linked list the point? — Superbest, Sep 25 '12 at 09:06
@Superbest: 1) adding & removing elements to my list is 11 times faster than using LinkedList ; 2) I can remove element during a foreach loop (maybe it's possible with LinkedList, I didn't try) ; I know exactly what's in the code & what it does, so I don't have any surprise (like having a code which is 11 times slower than expected ;) ). Globally, I use the all purpose classes of C# (or any other language for that matter) only when performance & memory consumption aren't an issue. [...] — ManuTOO, Sep 25 '12 at 09:44
[...] I 1st got into turning my classes into generics coz I thought it'd be cleaner & easier & give slightly better performances to avoid the `as` all the time. — ManuTOO, Sep 25 '12 at 09:45
Just did a try to type only `CChainList` (to get strong typing when adding element to a list) and adding/remove elements became 4 times slower... damn C# ... >_ — ManuTOO, Sep 25 '12 at 12:08
So your goal is to out-optimize Microsoft's C#/.NET development team on the implementation of one of the most basic, fundamental concepts in computer science? Please pardon my skepticism. Can you provide some reproducible examples for that performance claim? And of course you can `foreach` through `LinkedList`, it implements `IEnumerable`, but that's moot since you should probably use the faster `List` instead (http://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist). — Superbest, Sep 25 '12 at 17:28
Moreover, note that the MSDN article for `List` (http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx) also states: "*It is to your advantage to use the type-specific implementation of the List class instead of using the ArrayList class or writing a strongly typed wrapper collection yourself. The reason is your implementation must do what the .NET Framework does for you already, and the common language runtime can share Microsoft intermediate language code and metadata, which your implementation cannot.*" — Superbest, Sep 25 '12 at 17:33
@Superbest: I wrote "I can remove element during a foreach loop", the important part isn't "foreach", it's what is written before... ;) You need 15 minutes to set-up a optimization test protocol. You should create one for yourself, and you'll learn tons of stuff. For the little I saw so far, C# is inherently slow, and in some cases extremely slow, like in that case of "one of the most basic, fundamental concepts in computer science". The reason is simple : C# libs are generic purposes oriented, with ease of use as one of main goals. That gives a lot of room for optimizations for specific use. — ManuTOO, Sep 26 '12 at 03:56
Hint to set-up a optimization test protocol : test by running the final .exe out of any dev environment, and not within debugger coz it often doesn't reflect the final actual result. — ManuTOO, Sep 26 '12 at 04:09
I know how to test performance. As the person making the performance claim, I'd expect you to say how you measured that, rather than sit here and try to guess on my own what your test was. — Superbest, Sep 26 '12 at 16:17
I did `LinkedListNode Node = LlEnt.AddFirst(Entity); LlEnt.Remove(Node);` which is 11x times slower than the equivalent with my own classes ; I tried to pre-create the node, it was then "only" 2.3 times slower than my version (and it's less convenient in that case & uses more memory in all cases). The only upside is that the 2nd case (ie: with node pre-created) is faster than my version using generics to strongly type my class list. — ManuTOO, Sep 27 '12 at 03:07

Alex Gelman · Answer 1 · 2012-09-25T07:53:47.480

0

CChainElement should not be generic. The only thing that should turn to a generic is CChainList.

public class CChainElement
{
    public CChainElement m_Prev, m_Next;
}

public class CChainList<T> : IEnumerable
   where T : CChainElement
{
    public T m_First;

    internal void Add(T Element)
    {
        if (m_First != null)
            m_First.m_Prev = Element;

        Element.m_Next = m_First;
        m_First = Element;
    }
}

public class CEntity : CChainElement
{
}

public class CItem : CEntity
{
}

public class CTest
{
    void Test()
    {
        CChainList<CItem> AllItem = new CChainList<CItem>();
        CItem Item = new CItem();

        AllItem.Add(Item);

        CItem FirstItem = AllItem.m_First;
        CItem SecondItem = FirstItem.m_Next;
    }
}

edited Sep 25 '12 at 07:53

answered Sep 25 '12 at 07:29

Alex Gelman

534
3
11

This doesn't work. Without `CEntity : CChainElement` the code will no longer compile because `m_prev` and `m_next` are not members of `CEntity`. Even with that, `m_prev` and `m_next` are incorrectly of type `CEntity` instead of `CItem` when you use a `CChainList`. – verdesmarald Sep 25 '12 at 07:41
There's nothing wrong with the test class, your proposed solution just doesn't do what the OP wants. – verdesmarald Sep 25 '12 at 07:45
the constraint on T at `CChainElement where T : CChainElement` actually works on CEntity (I think, I didn't test at 100%), coz it inherits from CChainElement ; the issue starts with CItem, coz it doesn't inherit from CChainElement . Moreover, boxing adds more stuff than it removes (ie: having to access the actual item through element.item is less convenient than the `as CItem` cast), and it's less efficient (use more memory & more new calls). Thanks for the try anyway, though ! :) – ManuTOO Sep 25 '12 at 07:55
This still doesn't work, with a non-generic CChainElement, `m_Prev` and `m_Next` are of type `CChainElement` not `CItem`, so `CItem SecondItem = FirstItem.m_Next;` won't compile. You should really try compiling stuff before you claim it works! – verdesmarald Sep 25 '12 at 07:59

verdesmarald · Answer 2 · 2012-09-25T08:31:00.227

Well, this is a fun little problem. You need to make these changes:

public class CEntity<T> : CChainElement<T> where T : CChainElement<T> { ... }

public class CItem : CEntity<CItem> { ... }

Then this will work the way you want:

var allItems = new CChainList<CItem> { new CItem(), new CItem() };

// Both of these are now of type Item.
var firstItem = allItems.m_First;
var secondItem = firstItem.m_Next;

Another option is to make ChainElement a generic interface:

public interface IChainElement<T> where T : IChainElement<T>
{
    T Previous { get; set; }
    T Next { get; set; }
}

But then you will have to explicitly add the properties to each class you want to put in the list:

public class Entity { }

public class Item : Entity, IChainElement<Item>
{
    public Item Previous { get; set; }
    public Item Next { get; set; }
}

Either way you end up needing to modify all the classes you want to use in your list.

As an aside, you might want to use a better set of naming conventions. Prefacing all your class names with C, naming parameters and locals with InitialCapitals and public fields starting with m_ make your code pretty hard to read! I would recommend something like this:

public class ChainElement<T> where T : ChainElement<T>
{
    public T Previous { get; set; }
    public T Next { get; set; }
}

public class ChainList<T> : IEnumerable where T : ChainElement<T>
{
    public T First { get; private set; }

    public void Add(T element)
    {
        if (First != null)
            First.Previous = element;

        element.Next = First;
        First = element;
    }

    public IEnumerator GetEnumerator() { throw new NotImplementedException(); }
}

public class Entity<T> : ChainElement<T> where T : ChainElement<T> { }

public class Item : Entity<Item> { }

Your solution works for the sample case of my question above, but unfortunately, it doesn't work with my full project, as CEntity is a base shared between many stuff, and can't be Generic. (PS: sorry for my naming convention, I'm old & coming from C++ ! ;) ) — ManuTOO, Sep 25 '12 at 08:12
I don't know a way to make this work without any casts and without making `CEntity` generic. Sorry. — verdesmarald, Sep 25 '12 at 08:17

How to create my own generic list class?

2 Answers2