Design to have an optional data member; is it any good?

F

Ferdi Smit

I wanted to provide a template class with an optional data member. The
most natural way to do this was to implement a member for a given
template parameter, and in the case of 'void', then not.

I came up with the following, and I'm wondering if the design is any
good. Perhaps I'm overcomplicating things? Or is it ok?

// First we use a helper class that we can specialize on 'void'
template <typename T>
struct DataContainer {
// I'm aware of the problems when T is a reference, but this can
// be easily solved, either with traits, or another
// specialization
typedef T& reference_type;
T contained_;
};

// The empty class for void
template <>
struct DataContainer<void> {
typedef void reference_type;
};


// Make use of empty base class optimization to save space in
// the case of 'void'
template <typename vertex_value_type>
class Vertex : private DataContainer<vertex_value_type> {
public:
// A 'void' argument ctor
Vertex() {}

// a templated ctor taking a data argument
// SFINAE+the other overload make this work for T=void
template <typename T>
Vertex(const T& d) {
// we can't use the initializer list here, since
// the base class is dependent, and so contained_
// is not looked up, unless we qualify it. (?)
this->contained_ = d;
}

// when called in the case of 'void' this will error, which
// is good. Otherwise it works fine as the function definition
// will not be checked before use (because template class)
// and the declaration is syntactically fine.
typename DataContainer<vertex_value_type>::reference_type
data() {
return this->contained_;
}

~Vertex() {}
};


--
Regards,

Ferdi Smit (M.Sc.)
Email: (e-mail address removed)
Room: C0.07 Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands
 
V

Victor Bazarov

Ferdi said:
I wanted to provide a template class with an optional data member. The
most natural way to do this was to implement a member for a given
template parameter, and in the case of 'void', then not.

I came up with the following, and I'm wondering if the design is any
good. Perhaps I'm overcomplicating things? Or is it ok?

I am wondering what would be the application of it? How would you use it?
I understand the need to store something and get it back, and have the
typedef, and so on, but what would be the meaning of 'Vertex<void>'? What
use do you derive from it?

I realise that having different data contents based on the template
argument is a valid approach (and I've seen if not written some of that),
but what would be the point of *not* having data? Wouldn't you rather
// First we use a helper class that we can specialize on 'void'
template <typename T>
struct DataContainer {
// I'm aware of the problems when T is a reference, but this can
// be easily solved, either with traits, or another
// specialization
typedef T& reference_type;
T contained_;
};

// The empty class for void
template <>
struct DataContainer<void> {
typedef void reference_type;
};


// Make use of empty base class optimization to save space in
// the case of 'void'
template <typename vertex_value_type>
class Vertex : private DataContainer<vertex_value_type> {
public:
// A 'void' argument ctor
Vertex() {}

// a templated ctor taking a data argument
// SFINAE+the other overload make this work for T=void
template <typename T>
Vertex(const T& d) {
// we can't use the initializer list here, since
// the base class is dependent, and so contained_
// is not looked up, unless we qualify it. (?)
this->contained_ = d;
}

// when called in the case of 'void' this will error, which
// is good. Otherwise it works fine as the function definition
// will not be checked before use (because template class)
// and the declaration is syntactically fine.
typename DataContainer<vertex_value_type>::reference_type
data() {
return this->contained_;
}

~Vertex() {}
};

V
 
K

Kai-Uwe Bux

Victor said:
I am wondering what would be the application of it? How would you use it?
I understand the need to store something and get it back, and have the
typedef, and so on, but what would be the meaning of 'Vertex<void>'? What
use do you derive from it?

I realise that having different data contents based on the template
argument is a valid approach (and I've seen if not written some of that),
but what would be the point of *not* having data? Wouldn't you rather
simply undefined 'DataContainer<void>'? I mean, declare it but don't
provide the definition...
[snip]

I ran into that recently: I implemented a class template for labelled graphs

template < typename VertexLabel, typename EdgeLabel >
class graph {
...
};

Somewhere inside you would have node types like

struct vertex_node {
...
VertexLabel the_label;
...
};

Now, it makes perfect sense to consider graphs that are not labelled or have
only labels for the vertices. In that case, you want to be able to pass a
type that has no values as a template parameter. Thus, I defined, very much
like the OP,

struct empty {};

and the program gracefully deals with stuff like graph<empty,int>.


To the OP: It turns out, that an empty class is even more useful if you make
it compatible with standard container types and streams. Thus I actually
did this:

struct empty {};

std::eek:stream & operator<< ( std::eek:stream & ostr, empty const & e ) {
return( ostr << '#' );
}

std::istream & operator>> ( std::istream & istr, empty & e ) {
char chr;
istr >> chr;
if ( chr != '#' ) {
istr.setstate( std::ios_base::failbit );
}
return( istr );
}

bool operator== ( empty a, empty b ) {
return( true );
}

bool operator!= ( empty a, empty b ) {
return( false );
}

bool operator< ( empty a, empty b ) {
return( false );
}

bool operator<= ( empty a, empty b ) {
return( true );
}

bool operator> ( empty a, empty b ) {
return( false );
}

bool operator>= ( empty a, empty b ) {
return( true );
}


Best

Kai-Uwe Bux
 
F

Ferdi Smit

Victor said:
I am wondering what would be the application of it? How would you use it?
I understand the need to store something and get it back, and have the
typedef, and so on, but what would be the meaning of 'Vertex<void>'? What
use do you derive from it?

I've been experimenting with Boost Graph for some weeks now, and it
doesn't quite suit our needs in a natural way (it's too complicated to
make non-trivial extensions). Therefore I decided to implement a simple,
but still somewhat general graph class myself. Now the nodes and edges
may contain data items, but not neccesarily. When using larger graphs
you wouldn't want the overhead of some default data member. I also don't
want to specialize the entire graph class for empty data members; first
of all because it would require 4 seperate combinations, and secondly
it's tedious to maintain seperate implementations while the basics are
the same. I simplified the code here to make it more readable in the
newsgroup. The external property map approach for data caused more
problems than it solved... so internal data is prefered.
I realise that having different data contents based on the template
argument is a valid approach (and I've seen if not written some of that),
but what would be the point of *not* having data? Wouldn't you rather
simply undefined 'DataContainer<void>'? I mean, declare it but don't
provide the definition...

That's what I'm wondering about: is there an easier way. I tend to over
complicate C++ code after a day of work... I'm not exactly sure what you
mean here? I do want people to actually use Vertex<void>, it's not just
a safe-guard against someone trying to instantiate the class with void
as a template argument. I do have the nagging feeling I'm having one
redundant level of indirection at the moment. Any thoughts?

--
Regards,

Ferdi Smit (M.Sc.)
Email: (e-mail address removed)
Room: C0.07 Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands
 
F

Ferdi Smit

Kai-Uwe Bux said:
I ran into that recently: I implemented a class template for labelled graphs

I love reinventing the wheel ;) This is my case exactly...
Now, it makes perfect sense to consider graphs that are not labelled or have
only labels for the vertices. In that case, you want to be able to pass a
type that has no values as a template parameter. Thus, I defined, very much
like the OP,

struct empty {};

This is useful. One thing tho: are you sure that no extra space is used?
When I tried to have an empty class as data member, it still took up
extra space (gcc4, empty vertex was just as big as a vertex containing
an int). However, even if so, I could use an empty struct and derive
from that. Not directly tho, because you can't derive from ie. int or
float. So basically I'm back to square one then, using a wrapper for the
passed in type, specialized to be empty for void ?


--
Regards,

Ferdi Smit (M.Sc.)
Email: (e-mail address removed)
Room: C0.07 Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands
 
V

Victor Bazarov

Ferdi said:
[...] I do want people to actually use Vertex<void>, it's not just
a safe-guard against someone trying to instantiate the class with void
as a template argument. I do have the nagging feeling I'm having one
redundant level of indirection at the moment. Any thoughts?

If so, if Vertex<void> is legal in your system, then I think you're doing
it right. You need DataContainer (I would probably call it DataWrapper)
to derive from. It is going to contribute sizeof(T) when T is not void
and in your design, if used as a base class, DataContainer<void> is not
going to contribute to the total size of the derived class. I suppose
your Vertex template does have other members and possibly other base
classes...

As to Kai-Uwe's suggestion about 'empty', you don't have to store it, you
just need to specialise your DataContainer on it.

V
 
K

Kai-Uwe Bux

Ferdi said:
I love reinventing the wheel ;) This is my case exactly...


This is useful. One thing tho: are you sure that no extra space is used?
When I tried to have an empty class as data member, it still took up
extra space (gcc4, empty vertex was just as big as a vertex containing
an int). However, even if so, I could use an empty struct and derive
from that. Not directly tho, because you can't derive from ie. int or
float. So basically I'm back to square one then, using a wrapper for the
passed in type, specialized to be empty for void ?

I did not measure the size. I think there is no requirement for these empty
classes to be optimized away. And I am not even sure if that is allowed
when they are used as data members.

Also, keep in mind that your effort might be entirely in vain anyway: after
all you are going to create vertex and edge nodes dynamically. Chances are
that dynamic allocation of memory for objects restricts the available sizes
to multiples of 16 or even 32 bytes in which case your specialization might
not pay off at all.



Best

Kai-Uwe Bux
 
V

Victor Bazarov

Kai-Uwe Bux said:
[..] I think there is no requirement for these empty
classes to be optimized away. And I am not even sure if that is allowed
when they are used as data members.

They can only have size 0 if they are base class subobjects. If they are
stand-alone (data members as well), they have size at least 1.
Also, keep in mind that your effort might be entirely in vain anyway: after
all you are going to create vertex and edge nodes dynamically. Chances are
that dynamic allocation of memory for objects restricts the available sizes
to multiples of 16 or even 32 bytes in which case your specialization might
not pay off at all.

If they are created in an array, and by tens of thousands at a time, it
might...

V
 
K

Kai-Uwe Bux

Ferdi said:
Kai-Uwe Bux wrote: [snip]
struct empty {};

This is useful. One thing tho: are you sure that no extra space is used?
When I tried to have an empty class as data member, it still took up
extra space (gcc4, empty vertex was just as big as a vertex containing
an int). However, even if so, I could use an empty struct and derive
from that. Not directly tho, because you can't derive from ie. int or
float. So basically I'm back to square one then, using a wrapper for the
passed in type, specialized to be empty for void ?

Ok, so what about something like this:

template < typename T >
struct empty_eliminator {

T data;

};

struct empty {};

template <>
class empty_eliminator< empty > {

static empty data;

};


Now you do

template < typename VertexLabel >
struct Vertex : public empty_eliminator< VertexLabel > {
...
};

And you should be able to use the data field transparently inside
Vertex<empty> and Vertex<int>. The only drawback is that name lookup via
this->data will probably not work. Maybe this idea needs a little bit of
polishing.


Best

Kai-Uwe Bux
 
G

Greg

Victor said:
Kai-Uwe Bux said:
[..] I think there is no requirement for these empty
classes to be optimized away. And I am not even sure if that is allowed
when they are used as data members.

They can only have size 0 if they are base class subobjects. If they are
stand-alone (data members as well), they have size at least 1.
Also, keep in mind that your effort might be entirely in vain anyway: after
all you are going to create vertex and edge nodes dynamically. Chances are
that dynamic allocation of memory for objects restricts the available sizes
to multiples of 16 or even 32 bytes in which case your specialization might
not pay off at all.

If they are created in an array, and by tens of thousands at a time, it
might...

In other words, the only way to enjoy the savings of a zero-sized
object is to first create a non-zero sized object to hold it. I'm
thinking that I could profitably apply a similar technique and offer
every reader of comp.lang.c++ a free car, which I would deliver as soon
as I had received $50,000 to cover the cost of the key. In both cases,
the deal is not a great as it may first seem, and the savings (if any,
in the case of the "free" car) is only incremental and not absolute in
its nature.

Greg
 
F

Ferdi Smit

Kai-Uwe Bux said:
Ok, so what about something like this:

template < typename T >
struct empty_eliminator {

T data;

};

struct empty {};

template <>
class empty_eliminator< empty > {

static empty data;

};


Now you do

template < typename VertexLabel >
struct Vertex : public empty_eliminator< VertexLabel > {
...
};

And you should be able to use the data field transparently inside
Vertex<empty> and Vertex<int>. The only drawback is that name lookup via
this->data will probably not work. Maybe this idea needs a little bit of
polishing.

Sorry for the delay, I went home for the weekend ;)

I came up with the follwing now, basically what you said:

#include <iostream>


struct empty {};

template <typename T>
struct DataWrapper {
typedef T reference_type;
T data_;
};

template <>
struct DataWrapper<empty> {
typedef void reference_type;
};


template <typename Label>
struct Graph {
Graph() {}
~Graph() {}

struct Vertex : private DataWrapper<Label> {
Vertex() {}
explicit Vertex(const Label& data) {
this->data_ = data;
}
~Vertex() {}

int mandatory_data_;
};
};


int main() {
empty empty_object;
typedef Graph<int> IGraph;
typedef Graph<empty> EGraph;
typedef Graph<void> VGraph;

IGraph g1;
EGraph g2;
VGraph g3;

IGraph::Vertex v1(1);
EGraph::Vertex v2;

// Error: invalid use of 'void' (original problem with the 'void' method)
// VGraph::Vertex v3;

// error: ‘struct Graph<empty>::Vertex’ has no member named data_
// Nobody will do this anyway
// EGraph::Vertex v4(empty_object);

// Error: no matching function call
// EGraph::Vertex(1);

std::cout << "sizeof(Graph<int>::Vertex) = " <<
sizeof(IGraph::Vertex) << std::endl;
std::cout << "sizeof(Graph<empty>::Vertex) = " <<
sizeof(EGraph::Vertex) << std::endl;

// Output with (gcc 4.0.1 20050727 (Red Hat 4.0.1-5)):
// sizeof(Graph<int>::Vertex) = 8
// sizeof(Graph<empty>::Vertex) = 4
}


It works nicely this way. I don't need a templated ctor anymore, as
forming a reference to 'empty' is no problem at all. As far as i know
the definition is not checked until instantiation, so the missing member
will only show up when you try to instantiate it with empty. Something
one shouldn't do anyway, so perhaps it's best to make it's ctor private.
And due to inheritance the space is (probably) really saved. It's all a
little bit more simple now; one template function less. Thanks for the
advice :)

--
Regards,

Ferdi Smit (M.Sc.)
Email: (e-mail address removed)
Room: C0.07 Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands
 
F

Ferdi Smit

Ferdi said:
I came up with the follwing now, basically what you said:
Code:
 [/QUOTE]

I forgot the get() method of course, so to be complete... :

// in vertex
         typename DataWrapper<Label>::reference_type
         get() {
             return this->data_;
         }

// in main
     v1.get();

// error: ‘struct Graph<empty>::Vertex’ has no member named ‘data_’
// error: return-statement with a value, in function returning 'void'
//  v2.get();


-- 
Regards,

Ferdi Smit (M.Sc.)
Email: [email protected]
Room: C0.07  Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands
 
F

Ferdi Smit

Exactly; that's what went wrong in my first effort.

Also true. However the user is not constrained not to use some form of
small-object or pool allocator. As shown the size did go from 8 to 4 bytes
minimum. Why pay a potential cost for something you never use? Worst case
it's the same thing, best case you save half the storage space.

Or on the stack after all.
In other words, the only way to enjoy the savings of a zero-sized
object is to first create a non-zero sized object to hold it. I'm
thinking that I could profitably apply a similar technique and offer
every reader of comp.lang.c++ a free car, which I would deliver as soon
as I had received $50,000 to cover the cost of the key. In both cases,
the deal is not a great as it may first seem, and the savings (if any,
in the case of the "free" car) is only incremental and not absolute in
its nature.

By itself a zero sized object is nonsensical. It implies the object has no
state, and an object without state is not really an object at all. It might
as well have been a collection of functions then. Either way it doesn't make
sense to instantiate it, since every instantion would be equivalent. An
array of zero sized objects would have zero size, requiring special compiler
constructs to index this array and always return _the_ object.

However when included into another object, then it suddenly does matter
whether it contributes to the size of that object or not. Since you're
paying for the encompassing object anyway, it's better to get the included
object potentially for free, no? Even with a free store allocator that
allocates multiples of 16 bytes, the encompassing object might grow to 16
bytes exactly and thus fit in one block. Now when the included zero sized
object has an actual size of one, it suddenly costs you two blocks.

I think you should offer a free car stereo to whoever buys a new car anyway
;)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top