Linked list of references

[er]

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]

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.

 

[er]

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]

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]

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.