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 


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.


 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



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



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


 

 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 

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 




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?

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. 

container.



 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
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