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

Discussion in 'C++' started by Ferdi Smit, Oct 21, 2005.

  1. Ferdi Smit

    Ferdi Smit Guest

    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:
    Room: C0.07 Phone: 4229
    INS3 Visualization and 3D Interfaces
    CWI Amsterdam, The Netherlands
     
    Ferdi Smit, Oct 21, 2005
    #1
    1. Advertisements

  2. 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
    V
     
    Victor Bazarov, Oct 21, 2005
    #2
    1. Advertisements

  3. Ferdi Smit

    Kai-Uwe Bux Guest

    [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
     
    Kai-Uwe Bux, Oct 21, 2005
    #3
  4. Ferdi Smit

    Ferdi Smit Guest

    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.
    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:
    Room: C0.07 Phone: 4229
    INS3 Visualization and 3D Interfaces
    CWI Amsterdam, The Netherlands
     
    Ferdi Smit, Oct 21, 2005
    #4
  5. Ferdi Smit

    Ferdi Smit Guest

    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 ?


    --
    Regards,

    Ferdi Smit (M.Sc.)
    Email:
    Room: C0.07 Phone: 4229
    INS3 Visualization and 3D Interfaces
    CWI Amsterdam, The Netherlands
     
    Ferdi Smit, Oct 21, 2005
    #5
  6. 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
     
    Victor Bazarov, Oct 21, 2005
    #6
  7. Ferdi Smit

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Oct 21, 2005
    #7
  8. 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.
    If they are created in an array, and by tens of thousands at a time, it
    might...

    V
     
    Victor Bazarov, Oct 21, 2005
    #8
  9. Ferdi Smit

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Oct 21, 2005
    #9
  10. Ferdi Smit

    Greg Guest

    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
     
    Greg, Oct 22, 2005
    #10
  11. Ferdi Smit

    Ferdi Smit Guest

    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:
    Room: C0.07 Phone: 4229
    INS3 Visualization and 3D Interfaces
    CWI Amsterdam, The Netherlands
     
    Ferdi Smit, Oct 22, 2005
    #11
  12. Ferdi Smit

    Ferdi Smit Guest

     
    Ferdi Smit, Oct 22, 2005
    #12
  13. Ferdi Smit

    Ferdi Smit Guest

    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.
    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
    ;)
     
    Ferdi Smit, Oct 22, 2005
    #13
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.