Linked list of references

Discussion in 'C++' started by er, Mar 20, 2011.

  1. er

    er Guest

    Here's a toy linked list of references. I'd like to know if it's
    conforming with C++ rules or not.

    #include <iostream>

    template<typename T> struct head_holder
    {
    explicit head_holder(T& t) : head_( &t ){}

    T& head() const{ return (*this->head_); }

    private:

    T* head_;

    };

    template<typename T> struct tail_holder
    {

    tail_holder(T const& t) : tail_( t ){}
    typedef T const& result_type;

    T const& tail()const{ return this->tail_; }
    private:

    T const& tail_;

    };


    template<typename T> struct list1;
    template<typename T> struct list0 : head_holder<T>
    {

    list0(T& x) : head_holder<T>( x ){}
    list1<T> operator()(T& y)const{
    return list1<T>(*this, y);
    }

    };

    template<typename T> struct list2; template<typename T> struct list1 :
    head_holder<T>
    {
    typedef list0<T> list0_; typedef tail_holder<list0_ >
    tail_holder_;

    list1(const list0_& t, T& y) : head_holder<T>( y ),
    tail_holder( t ){}

    list2<T> operator()(T& z)const{ return list2<T>(*this, z); }

    typename tail_holder_::result_type tail()const{
    return this->tail_holder.tail();
    }
    private:
    tail_holder_ tail_holder;

    };

    template<typename T> struct list2 : head_holder<T>
    {
    typedef list1<T> list1_; typedef tail_holder<list1_ >
    tail_holder_;

    list2(const list1_& t, T& y) : head_holder<T>( y ),
    tail_holder( t ){}

    list2<T> operator()(T& z)const{ return list2<T>(*this, z); }

    typename tail_holder_::result_type tail()const{
    return this->tail_holder.tail();
    }
    private:
    tail_holder_ tail_holder;

    };

    template<typename T> list0<T> make( T& x ){ return list0<T>( x ); }
    template<typename T>list0<T const> make( T const& x ){ return list0<T
    const>( x ); }

    int main()
    {

    int x = -1, y = 2, z = -3;
    {

    std::cout << "lvalue" << std::endl; typedef int T;

    list2<T> l2 = list0<T>( x )( y )( z );
    if( &l2.head() != &z ){ std::cout << l2.head(); }
    if( &l2.tail().head() != &y ){ std::cout << l2.tail().head(); }
    if( &l2.tail().tail().head() != &z ){ std::cout <<
    l2.tail().tail().head(); }

    }
    {

    std::cout << "rvalue" << std::endl; typedef int const T;
    list2<T> l2 = list0<T>( -1 )( 2 )( -3 );
    if( l2.head() != -3 ){ std::cout << l2.head(); }
    if( l2.tail().head() != 2 ){ std::cout << l2.tail().head(); } //
    Access violation, some not all compilers
    if( l2.tail().tail().head() == -1 ){ std::cout <<
    l2.tail().tail().head(); }

    // I suspect it breaks the [bound temporary persists for the lifetime
    of the reference] rule.
    // Can anyone confirm or deny with certainty?

    }

    return 0;

    }

    Thanks.
     
    er, Mar 20, 2011
    #1
    1. Advertising

  2. er

    er Guest


    > The lifetime prolonging rule only holds for the lexical scope of the
    > const reference, the class data member won't work. If you think how the
    > compiler writer should implement it, then you will understand the reasons
    > (hint: temporaries live on stack).


    You have convinced me. We should still be able to prolong references
    to -1, 2, -3 below

    list2<T> l2 = list0<T>( -1 )( 2 )( -3 );

    since they are in the scope of l2. So then while replacing

    struct tail_holder
    {
    T const& tail_;
    };


    by

    struct tail_holder
    {
    T const tail_;
    };

    would be valid, there would be a dramatic increase in complexity.




    >
    > hth
    > Paavo
     
    er, Mar 25, 2011
    #2
    1. Advertising

  3. er

    er Guest

    This is still buggy in VC++-10.0/Release (not debug)


    #include
    <iostream>

    template<typename T> struct head_holder

    {

    explicit head_holder(T& t) : head_( &t ){}

    T& head()
    const{ return (*this->head_); }

    private:

    T* head_;

    };

    template<typename T>

    struct tail_holder

    {

    tail_holder(T const& t) : tail_( t ){}

    typedef T const& result_type;

    T const& tail()const{ return this->tail_; }

    private:

    T const tail_; // notice value

    };


    template<typename T, typename H>
    struct list1;

    template<typename H>
    struct list0

    : head_holder<H>

    {

    list0(H& x)

    :head_holder<H>( x )

    {}

    template<typename U>

    list1<list0, U>
    operator()(U& y)const

    {

    return list1<list0, U>(*this, y);

    }

    template<typename U>

    list1<list0, U
    const> operator()(U const& y)const

    {

    return list1<list0, U const>(*this, y);

    }

    };

    template<typename T, typename H>

    struct list2;

    template<typename T, typename H>

    struct list1

    :

    tail_holder<T>,

    head_holder<H>

    {

    list1(T t, H& y)

    :tail_holder<T>( t )

    , head_holder<H>( y )

    {}

    template<typename U>

    list2<list1, U>
    operator()(U& z)const{

    return list2<list1, U>(*this, z);

    }

    template<typename U>

    list2<list1, U
    const> operator()(U const& z)const{

    return list2<list1, U const>(*this, z);

    }

    };

    template<typename T, typename H>

    struct list2

    :

    tail_holder<T>,

    head_holder<H>

    {

    list2(T t, H& y)

    :tail_holder<T>( t )

    ,head_holder<H>( y )

    {}

    };

    template<typename T>

    list0<T> make( T& x ){
    return list0<T>( x ); }

    template<typename T>

    list0<T
    const> make( T const& x ){ return list0<T const>( x ); }

    int
    main()

    {

    int x = -1, y = 2, z = -3;

    {

    std::cout <<
    "lvalue" << std::endl;

    typedef int T;

    list2<list1<list0<T>, T>, T > l2 = list0<T>( x )( y )( z );

    if( &l2.head() != &z ){ std::cout << l2.head() << ' '; }

    if( &l2.tail().head() != &y ){ std::cout << l2.tail().head() << ' '; }

    if( &l2.tail().tail().head() != &x ){ std::cout <<
    l2.tail().tail().head(); }

    std::cout << std::endl;

    }

    {

    std::cout <<
    "rvalue" << std::endl;

    typedef int const T;

    list2<list1<list0<T>, T>, T> l2 = list0<T>( -1 )( 2 )( -3 );

    if( l2.head() != -3 ){ std::cout << l2.head() << ' '; }

    if( l2.tail().head() != 2 ){ std::cout << l2.tail().head() << ' '; }

    if( l2.tail().tail().head() != -1 ){ std::cout <<
    l2.tail().tail().head(); }

    std::cout << std::endl;

    }

    return 0;

    }

    // outputs lvalue rvalue -3 -3
    // should output lvalue rvalue
     
    er, Mar 25, 2011
    #3
  4. er

    er Guest

    Thanks again for following up.

    > list2<T> l2 = list0<T>( -1 )( 2 )( -3 );


    Temporaries are destroyed past the semicolon, so I guess this should
    be fine then?

    std::cout << list0<T>( -1 )( 2 )( -3 ).tail().tail().head() <<
    std::endl /*temporaries destroyed past->*/;

    Seen like this it doesn't offer much advantage, as you say, but there
    are other uses for it.
     
    er, Mar 25, 2011
    #4
  5. er

    er Guest

    On Mar 26, 9:17 am, Paavo Helde <> wrote:
    > er <> wrote in news:0ac5128e-ae51-4f56-9c10-
    > :
    >
    > > Thanks again for following up.

    >
    > >> list2<T> l2 = list0<T>( -1 )( 2 )( -3 );

    >
    > > Temporaries are destroyed past the semicolon, so I guess this should
    > > be fine then?

    >
    > > std::cout << list0<T>( -1 )( 2 )( -3 ).tail().tail().head() <<
    > > std::endl /*temporaries destroyed past->*/;

    >
    > Yes, this should be OK in regard of temporaries.
    >
    > Cheers
    > Paavo


    Thanks, and to answer your question "Depends on what you mean by
    complexity." I mean the running time bound, O( f(n) ), with n as the
    size of the list. Heap allocating the tail might do better job than
    copying in this regard, while also taking care of temporaries.
     
    er, Apr 5, 2011
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    488
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    477
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    518
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    679
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    770
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page