C# – Most efficient data structure for implementing inheritance structure without classes

cdata structures

I have a number of types that all relate to each other in terms of them being 'derived' from one another. I'd need a way to do is relationships, which made me initially think of classes, but I realized that other than the is relationships, there would be no reason to use classes as each 'type' of data function the exact same way. I'd also thought of enums, but since there is no way to extend or inherit from enums it was a poor choice.

For context (this being my specific example):
I have a number of different kinds of resources that all are 'types' so that they can be used in conjunction with an int to denote how much of that resource is available. I have several different kinds of these resources, such as foods, metals, building materials etc. Within the food category would be something like wheat or corn; under metals would be copper, iron, gold etc. Since all of these are still just 'resources' and have no actual functionality other than typing, it seems pointless to use classes and OO inheritance.

How would I implement this kind of data type without resorting to using classes?

Best Answer

If there are no functions to inherit, composition of structs may be more favorable than class inheritance. The concept of "composition over inheritance" may apply here, see:

Popular SO Answer to this issue

Although the above examples use classes, an alternative implementation could use structs:

Composition with C structs

Related Solutions

C# – Ideal data structure/techniques for storing generic scheduler data in C#

I don't think this is too tough. What am I missing?

using System;
using System.Collections.Generic;

public class ScheduledPerson {
    public string Name {get; set;}

    public Dictionary<string, Object> Fields {
        get { return _fields; }
        set { _fields = value; }
    }
    private Dictionary<string, Object> _fields = new Dictionary<string, Object>();

    public List<Tuple<DateTime, DateTime>> Events {
        get { return _events; }
        set { _events = value; }
    }
    private List<Tuple<DateTime, DateTime>> _events = new List<Tuple<DateTime, DateTime>>();

    public ScheduledPerson(string name){
        Name = name;
    }
}

I don't see a good way to make our ScheduledPerson classes generic, as it seems the fields can be anything. I'm storing the field values as Objects, as I see nothing that requires them to be dynamics. Just make sure all field value types have a sensible ToString() implementation.

If you want Events to be a List of DateRange or of your own Event class instead of Tuple, feel free.

It then remains for you to write a separate class to render each ScheduledPerson in a table, along with figuring out all the headers from all ScheduledPerson records. It you are dealing with ten thousand people, you'll want a better solution that has all the headers stored, but for most applications, it won't be too bad to enumerate all the Fields on all the ScheduledPersons to figure out the headers.

Space Efficient Graph Data Structure – Best Implementation Methods

Well if space efficiency is all you care about then a compressed data structure would be best - but of course this isn't very efficient for access or update.....

If your graph has a relatively small number of nodes and is fairly dense (lets say at least 5% of all possible connections exist) then you may find it is more space efficient to create an adjacency matrix rather than using edge lists. This would require just one bit per possible (directed) connection, and n*n bits total where you have n nodes.

Otherwise if you need to use neighbour links then you can't easily do better than one reference per link since this is the minimum information content you need to store. If you want back-links you will need twice as many links.

There are some tricks you could try on top of this. For example, you could try sharing subsets of links ( if A and B refer to each of C, D, E then only store the list of links C,D,E once.....). However this will get complex pretty quickly and I doubt it will be worth the effort in most cases.

One other trick - assuming your graph has a reasonable number of nodes, you will certainly save space by indexing - e.g. using a 16-bit node index number rather than a full pointer / reference.

Related Topic