David Hossack wrote:
...
> I think value_type would have to be T& for a tfn_list<T&>.
...
> My main interest in this is that I'd like to store these things in
> lists - I don't think there is a fundamental problem with this - but
> the standard libary doesn't help me, so I'm going to have to write my
> own non-standard list class.  I'm less interested in the using the std
> agorithms.

What would a container of reference give you, that a container of
pointers wouldn't give you, just with a slightly different syntax?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <ba9e6ee6.0111290748.1f08bf53@posting.google.com>, David Hossack
says...
>
>The standard library containers cannot be used with element types
>which are references or are non-copyable (private copy constructor).
>The "standard" way around this is to use some sort of smart pointer.
>
>I can understand this for vector and deque, but not for list and the
>other node based containers.
>

I've forgotten who said it, but I still want to quote him:" The
containers in the std:: libarary are just examples so the algorithms
can be explained". I think that's a bit strong, but Ok, there is a
point there.

However, the algorithm aspect is important. What is the value_type of
your iterators? Can std:: algorithms handle that? If your container
doesn't work with std:: algorithms, you'll have to write all those,
too.

Regards,

--
Michiel Salters
Consultant Technical Software Engineering
CMG Trade, Transport & Industry
Michiel.Salters@cmg.nl

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Michiel Salters wrote:
...
> I've forgotten who said it, but I still want to quote him:" The
> containers in the std:: libarary are just examples so the algorithms
> can be explained". I think that's a bit strong, but Ok, there is a
> point there.

That IS too strong. The containers are there so users don't have to
create their own, and can count on the presence of standard-defined
containers. However, the standard also defines generic container
requirements, and requires that various templates provided by the
standard must work with any container that meets those requirements,
whether or not it's a standard-defined container.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Michiel Salters<Michiel.Salters@cmg.nl> wrote in message news:<GuKO7.46691$xS6.76063@www.newsranger.com>...
> In article <ba9e6ee6.0111290748.1f08bf53@posting.google.com>, David Hossack
> says...
> >
> >The standard library containers cannot be used with element types
> >which are references or are non-copyable (private copy constructor).
> >The "standard" way around this is to use some sort of smart pointer.
> >
> >I can understand this for vector and deque, but not for list and the
> >other node based containers.
> >
>
> I've forgotten who said it, but I still want to quote him:" The
> containers in the std:: libarary are just examples so the algorithms
> can be explained". I think that's a bit strong, but Ok, there is a
> point there.
>
> However, the algorithm aspect is important. What is the value_type of
> your iterators? Can std:: algorithms handle that? If your container
> doesn't work with std:: algorithms, you'll have to write all those,
> too.

I think value_type would have to be T& for a tfn_list<T&>.

This poses some problems since a T& cannot be default constructed
etc.  I guess that would mean that some algorithms would not work
without modification since the std library assumes that you can
default construct elements and then assign to them.  I'm not sure
which algorithms are likely to need to do this, and whether they could
be rewritten to avoid this.

It should be possible to create copies of link nodes for case of
holding references (not for the case of holding non-copyable elements
directly).

I think that most of the algorithms ought to work, but there could be
no guarantees because some of the STL rules are being broken.  I think
it would be possible to write an implementation of the std library
which would allow references and non-copyable types for a good subset
of the algorithms.

My main interest in this is that I'd like to store these things in
lists - I don't think there is a fundamental problem with this - but
the standard libary doesn't help me, so I'm going to have to write my
own non-standard list class.  I'm less interested in the using the std
agorithms.

David.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

The standard library containers cannot be used with element types
which are references or are non-copyable (private copy constructor).
The "standard" way around this is to use some sort of smart pointer.

I can understand this for vector and deque, but not for list and the
other node based containers.

Below is a skeleton implementation of a list type which does not need
to copy its elements and can be used for references.  I believe that
it should be possible to extend this to retain almost all the functionality
of the std::list - without the drawbacks.  It may even work for T =
auto_ptr<T>.

I believe that it is too easy to copy large objects inadvertly in C++
- so I like to prevent this by using private copy constructors - but
this memory management technique is incompatible with the std library.
 My approach allows a container to own objects (which might not be
copyable) or to refer to objects by reference (ie not owned by the
container) without any mucking about with smart pointers, reference
counts etc.  The code below compiles cleanly with g++ 2.95 (-Wall) and
with Comeau C++ (strict mode).

Any comments?  The code below is experimental - I'm not even sure
whether the list links are properly maintained - I just want to
demonstrate the idea.

David.

// PLEASE SNIP THE CODE WHEN REPLYING

#include <iostream>
// #include <list>

// some declarations
template< class T > class tfn_list_node;
template< class T > class tfn_list_iterator;
template< class T > class tfn_list;

// set of specialised traits classes for passing by reference -
avoiding reference to reference problems
template< class T >
struct pass_trait { typedef const T & type;     };
template< class T >
struct pass_trait< T & > { typedef T & type; };
template< class T >
struct pass_trait< const T & > { typedef const T & type; };

// only ever used as base class for tfn_list_node<T>
// holds the linked list pointers, but not the data
template< class T >
class tfn_list_node_base
{
private:
        tfn_list_node_base<T> *         prev;
        tfn_list_node_base<T> *         next;
public:
        tfn_list_node_base() : prev( this), next(this ) {
                }
        tfn_list_node<T> * up() { // or "down" depending on terminology....
                return static_cast< tfn_list_node<T> *>( this );
                }
friend class tfn_list_iterator<T>;
friend class tfn_list<T>;
        };

// add the data to the base class
template< class T >
class tfn_list_node : public tfn_list_node_base< T >
{
        T                       x;
public:
        tfn_list_node( typename pass_trait<T>::type xx ) : x(xx) {
                }
        template< class RHS >
        tfn_list_node( const RHS & rhs ) : x(rhs) {
                }
        template< class RHS >
        tfn_list_node( RHS & rhs ) : x(rhs) {
                }
friend class tfn_list_iterator<T>;
friend class tfn_list<T>;
        };

template< class T >
class tfn_list_iterator
{
        tfn_list_node_base<T> *         it;
public:
        tfn_list_iterator( tfn_list_node_base<T> * xit ) :it( xit) {
                }
        tfn_list_iterator<T> & operator++(int) {
                it = it->next;
                return *this;
                }
        bool operator!=( const tfn_list_iterator<T> & rhs ) {
                return it != rhs.it;
                }
        typename pass_trait<T>::type operator*() {
                return it->up()->x;
                }
friend class tfn_list_node<T>;
friend class tfn_list<T>;

        };

// the list class
template< class T >
class tfn_list
{
        tfn_list_node_base<T>   dummy; // - just the links - no data - illegal
to call up()
public:
        typedef  tfn_list_iterator<T> iterator;

        tfn_list() {
                dummy.prev = &dummy;
                dummy.next = &dummy;
                }

        iterator begin() {
                return iterator( dummy.next );
                }
        iterator end() {
                return iterator( &dummy );
                }

        template< class RHS >
        void push_back( const RHS & rhs ) {
                tfn_list_node<T> * new_node = new tfn_list_node<T>( rhs );
                dummy.prev->next = new_node;
                new_node->next = &dummy;
                new_node->prev = dummy.prev;
                dummy.prev = new_node;
                }

        template< class RHS >
        void push_back(  RHS & rhs ) {
                tfn_list_node<T> * new_node = new tfn_list_node<T>( rhs );
                dummy.prev->next = new_node;
                new_node->next = &dummy;
                new_node->prev = dummy.prev;
                dummy.prev = new_node;
                }

        template< class RHS >
        void insert( iterator it, const RHS & rhs ) {
                tfn_list_node<T> * new_node = new tfn_list_node<T>( rhs );
                it.it->prev->next = new_node;
                new_node->next = it.it;
                new_node->prev =  it.it->prev;
                it.it->prev = new_node;
                }
friend class tfn_list_node<T>;
friend class tfn_list_iterator<T>;

        };

// end of library part
// start of client code


// define an "awkward" object which doesn't allow
// copy construction (or default construction
class awkward
{
        awkward( const awkward & );
        awkward();
public:
        double  v;
        awkward( double xv ) :v(xv) {
                }
        };
// and output operator so we can view the contents of the list
std::ostream & operator<<( std::ostream & out, const awkward & a )
{
        out << "Help: " << a.v << std::endl;
        return out;
        }

int main()
{
        tfn_list<awkward>       a1;

        a1.push_back( 1.0 );    // awkward objects constructed within the list
        a1.push_back( 2.0 );    // the list owns the objects
        a1.push_back( 3.0 );
        a1.push_back( 4.0 );
        a1.push_back( 5.0 );

        for( tfn_list<awkward>::iterator it = a1.begin(); it != a1.end();
it++ ) {
                std::cout << *it << std::endl;
                }

        tfn_list<awkward>::iterator it = a1.begin();
        it++;
        it++;
        a1.insert( it, 100.0 );
        for( tfn_list<awkward>::iterator it = a1.begin(); it != a1.end();
it++ ) {
                std::cout << *it << std::endl;
                }

//      typedef std::list<awkward & > list_type;        // doesn't work - can't
use references with std library
//      typedef std::list<awkward > list_type;          // only works if awkward
has public copy constructor

        typedef tfn_list<awkward & > list_type; // but this one works!
        list_type       a2;

        awkward d1( 1.0 );      // build up some awkward objects - owned here
        awkward d2( 2.0 );
        awkward d3( 3.0 );

        a2.push_back( d1 ); // push references on to list - list does not own
the objects
        a2.push_back( d2 );
        a2.push_back( d3 );

        for( list_type::iterator it = a2.begin(); it != a2.end(); it++ ) {
                std::cout << *it << std::endl;
                }

        d2 = 100.0;  // modify one our awkward objects and check that this is
reflected in list

        for( list_type::iterator it = a2.begin(); it != a2.end(); it++ ) {
                std::cout << *it << std::endl;
                }
        }

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]