www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Making containers that "go both ways"

reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Hey,
Just wanted to throw this idea out for comment.
I find I can't really decide whether a container class should be a 
struct or a class.  Struct feels right if I want minimal overhead and 
something that works more like a built-in datatype.  But class feels 
right for situations where I'm less concerned about performance, and 
also offers the additional ability to extend the basic functionality via 
subclassing.

So something I did (a while back now...) was to create some containers 
in OpenMesh/D that use mixins for all their guts, and provide both 
struct and class wrappers for them.

It seems to me like that might be the "right" way to do containers in D. 
Somewhat unfortunately, because it's more complicated than just writing 
one or the other.

Thoughts?

--bb
Jan 25 2008
next sibling parent reply janderson <askme me.com> writes:
Bill Baxter wrote:
 Hey,
 Just wanted to throw this idea out for comment.
 I find I can't really decide whether a container class should be a 

something that works more like a built-in datatype. But class feels right for situations where I'm less concerned about performance Personally I'd make it a class. Yes its going to go on the heap however the resizeable array part or whatever the container contains, will probably go on the heap anyway. , and
 also offers the additional ability to extend the basic functionality 

I think you should avoid thinking about subclassing like this. Using mixins or components is a much better idea then subclassing. Subclassing should normally be used for polymorphism.
 So something I did (a while back now...) was to create some 

both struct and class wrappers for them.
 It seems to me like that might be the "right" way to do containers in 

writing one or the other.
 Thoughts?

 --bb

This may help: http://www.artima.com/intv/goldilocks3.html
Jan 25 2008
next sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"janderson" <askme me.com> wrote in message 
news:fnem61$2054$1 digitalmars.com...

 Personally I'd make it a class.  Yes its going to go on the heap however 
 the resizeable array part or whatever the container contains, will 
 probably go on the heap anyway.

Good point. Also keep in mind that even if it's a class, it can be allocated on the stack in functions if you use 'scope x = new X()', so there's at least one heap allocation avoided.
Jan 26 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Jarrett Billingsley wrote:
 "janderson" <askme me.com> wrote in message 
 news:fnem61$2054$1 digitalmars.com...
 
 Personally I'd make it a class.  Yes its going to go on the heap however 
 the resizeable array part or whatever the container contains, will 
 probably go on the heap anyway.

Good point. Also keep in mind that even if it's a class, it can be allocated on the stack in functions if you use 'scope x = new X()', so there's at least one heap allocation avoided.

And if it's a struct it can be allocated on the heap using new if you like. I would be much more inclined to use classes for containers if they either didn't require new, or could be new'ed at point of declaration (like I think they can in Java?). This scattering of information all over the place is one of the things that annoys me most about C++. // Annoying class D { MyContainer c; // must remember to 'new' this later in constructor int[] d; // no worries, it's good. MyStructContainer e; // also no worries ... this() { c = new MyContainer; } } // This would be less annoying class D { MyContainer c = new MyContainer; ... this() {} } // Or this class D { scope MyContainer c; ... this() {} } And the second reason I think containers should be structs is because if you want to "upgrade" some existing code from using a built-in array or AA to using a custom container, it's much less headache if it's a struct-based container. Also if you want to write generic code that can handle built-in and custom containers, then it's going to be easier if your custom containers are structs. I think main important difference is the way copying is handled, but unfortunately "places where a container of type X is copied and subsequently it is assumed that X.member is a distinct pointer" is pretty difficult to grep for. Initialization is also different but you initialize things far less often than you pass them around or assign them to other variables. Initialization patterns are also easier to grep for. That's my 2c. --bb
Jan 26 2008
parent reply Yigal Chripun <yigal100 gmail.com> writes:
Bill Baxter wrote:
 Jarrett Billingsley wrote:
 "janderson" <askme me.com> wrote in message 
 news:fnem61$2054$1 digitalmars.com...

 Personally I'd make it a class.  Yes its going to go on the heap 
 however the resizeable array part or whatever the container contains, 
 will probably go on the heap anyway.

Good point. Also keep in mind that even if it's a class, it can be allocated on the stack in functions if you use 'scope x = new X()', so there's at least one heap allocation avoided.

And if it's a struct it can be allocated on the heap using new if you like. I would be much more inclined to use classes for containers if they either didn't require new, or could be new'ed at point of declaration (like I think they can in Java?). This scattering of information all over the place is one of the things that annoys me most about C++. // Annoying class D { MyContainer c; // must remember to 'new' this later in constructor int[] d; // no worries, it's good. MyStructContainer e; // also no worries ... this() { c = new MyContainer; } } // This would be less annoying class D { MyContainer c = new MyContainer; ... this() {} } // Or this class D { scope MyContainer c; ... this() {} } And the second reason I think containers should be structs is because if you want to "upgrade" some existing code from using a built-in array or AA to using a custom container, it's much less headache if it's a struct-based container. Also if you want to write generic code that can handle built-in and custom containers, then it's going to be easier if your custom containers are structs. I think main important difference is the way copying is handled, but unfortunately "places where a container of type X is copied and subsequently it is assumed that X.member is a distinct pointer" is pretty difficult to grep for. Initialization is also different but you initialize things far less often than you pass them around or assign them to other variables. Initialization patterns are also easier to grep for. That's my 2c. --bb

the way it's done in other oop languages like java, c#, etc: there's a hierarchy of interfaces and separate implementations. so as a user i use for example : List<Type> variable = new SomeImplClass(); if i have a function that iterates over a list of stuff i don't need to know what implementation was chosen i just rely on the interface. also functions should use the most general interface that suits the problem. so i can use a func(container con, other params... ) in order to do similar with structs you need to use template functions and you don't have a way to insure that all containers have that same base "container" interface (isn't the new c++ standard tries to solve it with concepts?). also if i have different container types that creates overhead in the executable size (code duplication). -- Yigal
Jan 26 2008
parent Yigal Chripun <yigal100 gmail.com> writes:
Yigal Chripun wrote:
 Bill Baxter wrote:
 Jarrett Billingsley wrote:
 "janderson" <askme me.com> wrote in message 
 news:fnem61$2054$1 digitalmars.com...

 Personally I'd make it a class.  Yes its going to go on the heap 
 however the resizeable array part or whatever the container 
 contains, will probably go on the heap anyway.

Good point. Also keep in mind that even if it's a class, it can be allocated on the stack in functions if you use 'scope x = new X()', so there's at least one heap allocation avoided.

And if it's a struct it can be allocated on the heap using new if you like. I would be much more inclined to use classes for containers if they either didn't require new, or could be new'ed at point of declaration (like I think they can in Java?). This scattering of information all over the place is one of the things that annoys me most about C++. // Annoying class D { MyContainer c; // must remember to 'new' this later in constructor int[] d; // no worries, it's good. MyStructContainer e; // also no worries ... this() { c = new MyContainer; } } // This would be less annoying class D { MyContainer c = new MyContainer; ... this() {} } // Or this class D { scope MyContainer c; ... this() {} } And the second reason I think containers should be structs is because if you want to "upgrade" some existing code from using a built-in array or AA to using a custom container, it's much less headache if it's a struct-based container. Also if you want to write generic code that can handle built-in and custom containers, then it's going to be easier if your custom containers are structs. I think main important difference is the way copying is handled, but unfortunately "places where a container of type X is copied and subsequently it is assumed that X.member is a distinct pointer" is pretty difficult to grep for. Initialization is also different but you initialize things far less often than you pass them around or assign them to other variables. Initialization patterns are also easier to grep for. That's my 2c. --bb

the way it's done in other oop languages like java, c#, etc: there's a hierarchy of interfaces and separate implementations. so as a user i use for example : List<Type> variable = new SomeImplClass(); if i have a function that iterates over a list of stuff i don't need to know what implementation was chosen i just rely on the interface. also functions should use the most general interface that suits the problem. so i can use a func(container con, other params... ) in order to do similar with structs you need to use template functions and you don't have a way to insure that all containers have that same base "container" interface (isn't the new c++ standard tries to solve it with concepts?). also if i have different container types that creates overhead in the executable size (code duplication). -- Yigal

Also, you can design with run-time polymorphism but when necessary go back to the STL style of compile-time polymorphism. If you define a final scope class you get (almost) a struct (only without manual memory management). scope puts your class on the stack, and final makes its methods non-virtual. so you get almost all the performance benefits of structs. You could put that on the class definition itself, but I think that should be better used at the client side which should know what s/he prefers. i.e. an application developer would probably use it as is (like in Java/C#), and more advanced users of the library could decide for themselves what kind of overhead tradeoffs are suitable for their code (stack vs. heap; runtime vs. compile-time polymorphism...). -- Yigal
Jan 27 2008
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
janderson wrote:
 Bill Baxter wrote:
  > Hey,
  > Just wanted to throw this idea out for comment.
  > I find I can't really decide whether a container class should be a 
 struct or a class.  Struct feels right if I want minimal overhead and 
 something that works more like a built-in datatype.  But class feels 
 right for situations where I'm less concerned about performance
 
 
 Personally I'd make it a class.  Yes its going to go on the heap however 
 the resizeable array part or whatever the container contains, will 
 probably go on the heap anyway.
 
 , and
  > also offers the additional ability to extend the basic functionality 
 via subclassing.
 
 I think you should avoid thinking about subclassing like this.  Using 
 mixins or components is a much better idea then subclassing. Subclassing 
 should normally be used for polymorphism.

Yeh, I don't actually ever do that myself, but I hear that some people do, at least in other languages. That's why I mentioned it. Anyway, if I subclass Container to attach some additional info it, or do something slightly different, but still pass it to the original Container-using code how would that that not constitute subclassing for polymorphism? But it's strange you say "make it a class" and then turn around and say "but don't use the main property of classes that distinguish them from structs". If you want to discourage subclassing of containers, what could be better than making them structs so that it's actually impossible?
  > So something I did (a while back now...) was to create some 
 containers in OpenMesh/D that use mixins for all their guts, and provide 
 both struct and class wrappers for them.
  >
  > It seems to me like that might be the "right" way to do containers in 
 D. Somewhat unfortunately, because it's more complicated than just 
 writing one or the other.

 This may help:
 http://www.artima.com/intv/goldilocks3.html

Not really. He's talking about C++, where classes and structs are the same thing. """ Bjarne Stroustrup: My rule of thumb is that you should have a real class with an interface and a hidden representation if and only if you can consider an invariant for the class. """ The distinction he's making is between making everything public vs having private data members with API functions to do all the manipulation. That choice applies equally to either structs or classes in D. --bb
Jan 26 2008
next sibling parent janderson <askme me.com> writes:
Bill Baxter wrote:
 janderson wrote:
 Bill Baxter wrote:
  > Hey,
  > Just wanted to throw this idea out for comment.
  > I find I can't really decide whether a container class should be a 
 struct or a class.  Struct feels right if I want minimal overhead and 
 something that works more like a built-in datatype.  But class feels 
 right for situations where I'm less concerned about performance


 Personally I'd make it a class.  Yes its going to go on the heap 
 however the resizeable array part or whatever the container contains, 
 will probably go on the heap anyway.

 , and
  > also offers the additional ability to extend the basic 
 functionality via subclassing.

 I think you should avoid thinking about subclassing like this.  Using 
 mixins or components is a much better idea then subclassing. 
 Subclassing should normally be used for polymorphism.

Yeh, I don't actually ever do that myself, but I hear that some people do, at least in other languages. That's why I mentioned it. Anyway, if I subclass Container to attach some additional info it, or do something slightly different, but still pass it to the original Container-using code how would that that not constitute subclassing for polymorphism? But it's strange you say "make it a class" and then turn around and say "but don't use the main property of classes that distinguish them from structs". If you want to discourage subclassing of containers, what could be better than making them structs so that it's actually impossible?

A good point.
 
 
  > So something I did (a while back now...) was to create some 
 containers in OpenMesh/D that use mixins for all their guts, and 
 provide both struct and class wrappers for them.
  >
  > It seems to me like that might be the "right" way to do containers 
 in D. Somewhat unfortunately, because it's more complicated than just 
 writing one or the other.

 This may help:
 http://www.artima.com/intv/goldilocks3.html

Not really. He's talking about C++, where classes and structs are the same thing. """ Bjarne Stroustrup: My rule of thumb is that you should have a real class with an interface and a hidden representation if and only if you can consider an invariant for the class. """ The distinction he's making is between making everything public vs having private data members with API functions to do all the manipulation. That choice applies equally to either structs or classes in D.

I guess I'm still thinking C++. I still see struts as privative data types where all the members are public and classes as more complex datatypes which validates itself.
 
 --bb

Jan 26 2008
prev sibling parent janderson <askme me.com> writes:
Bill Baxter wrote:
 janderson wrote:
 Bill Baxter wrote:
  > Hey,
  > Just wanted to throw this idea out for comment.
  > I find I can't really decide whether a container class should be 


something that works more like a built-in datatype. But class feels right for situations where I'm less concerned about performance
 Personally I'd make it a class.  Yes its going to go on the heap 


will probably go on the heap anyway.
 , and
  > also offers the additional ability to extend the basic 


 I think you should avoid thinking about subclassing like this. 


Subclassing should normally be used for polymorphism.
 Yeh, I don't actually ever do that myself, but I hear that some 

Anyway, if I subclass Container to attach some additional info it, or do something slightly different, but still pass it to the original Container-using code how would that that not constitute subclassing for polymorphism? Polymorphism has to do with virtual functions. You change the definition of the object. Its better to do: class Container {} class A { Container C; } then class A : public Container { } In the case of a container you probably don't want to change it's shape. That is of course unless your writing something like a C# control container.
 But it's strange you say "make it a class" and then turn around and 

from structs". If you want to discourage subclassing of containers, what could be better than making them structs so that it's actually impossible?
  > So something I did (a while back now...) was to create some 


both struct and class wrappers for them.
  >
  > It seems to me like that might be the "right" way to do 


than just writing one or the other.
 This may help:
 http://www.artima.com/intv/goldilocks3.html

Not really. He's talking about C++, where classes and structs are

 """
 Bjarne Stroustrup: My rule of thumb is that you should have a real 

can consider an invariant for the class.
 """
 The distinction he's making is between making everything public vs 

manipulation. That choice applies equally to either structs or classes in D.
 --bb

Jan 26 2008
prev sibling parent Henning Hasemann <hhasemann web.de> writes:
No real thought but I did something similar some time ago:
http://www.leetless.de/indiana-parts/index.html (See "Algorithm")
This is not the recent source code version I still work on an svn repo
and a new website so let me know before you want to use it in
production.

Henning

-- 
GPG Public Key:
http://gpg-keyserver.de/pks/lookup?op=get&search=0xDDD6D36D41911851
Jan 27 2008