plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1020226521 28911 127.0.0.1 (1 May 2002 04:15:21 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 1 May 2002 04:15:21 GMT
Content-Length: 996
ReSent-Date: Wed, 1 May 2002 08:23:35 -0700 (PDT)
ReSent-From: Steve Clamage <clamage@eng.sun.com>
ReSent-To:  <c++-submit@netlab.cs.rpi.edu>
ReSent-Subject: Re: Containers of incomplete types
ReSent-Message-ID: <Pine.SOL.4.33.0205010823350.10775@taumet>

"Arnold the Aardvark" <aardvark@NOTTHIStubulidentata.demon.co.uk> wrote in message news:<1020097449.7127.0.nnrp-12.c246aeef@news.demon.co.uk>...
> You might want to look at this:
>
> http://www.cuj.com/experts/2002/austern.htm?topic=experts
>

I believe this article has an error.  Here is a snippet.  Consider
"my_class" a forward declared class:

<quote>

You could write:

my_class& clone(const my_class&);

but you couldn't write:

int illegal_function(my_class);

or:

my_class illegal_function();

</quote>

I believe this is incorrect.  In fact, you can DECLARE a function
taking an argument of incomplete type, or returning an object of
incomplete type.  You can not INVOKE such a method until the type is
fully qualified, but you can DECLARE it.

So, this code is legal:

//forward declare
class my_class;

//declare function
my_class legal_function(my_class);

//complete class
class my_class { };

//call function
legal_function(my_class());

joshua lehrer
factset research systems



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

You might want to look at this:

http://www.cuj.com/experts/2002/austern.htm?topic=experts


Arnold the Aardvark
=======================================
7th Birmingham Circus Convention - May 4th 2002
http://www.bhamcircus.co.uk
"I'll do anything for an organiser's T-shirt"
  - A certain aardvark, in a moment of madness



      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On 29 Apr 2002 09:39:18 -0400, dylan@moldflow.com (Dylan Nicholson)
wrote:

> I'm designing a recursive data structure whereby a "widget" can hold a
> collection of widgets (child widgets).
> Widgets however are extremely light weight and can be copied easily,
> so it made sense not to use pointers.
> Dinkumware's STL implementation lets me use std::deque for this, but
> not std::list.

I can't say whether it is the library or compiler.  Here is a simple
example which may show that you have a compiler problem.  Since this
is not a standard container, there is nothing to prohibit the compiler
from accepting it.  I don't know if there is anything requiring the
compiler to accept it either.

template <class T>
class list {
    public :
        list ();
        ~list ();
    private :
        struct Node {
            T data;
            Node* next;
            };
        Node* head;
    };
struct S {
    list<S> l;
    };
S s;

It may still be possible that that library will not allow this with
std::list on compilers which accept the above.

John

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Forgive me for bringing this up again, but I hit this very problem
today.
I'm designing a recursive data structure whereby a "widget" can hold a
collection of widgets (child widgets).
Widgets however are extremely light weight and can be copied easily,
so it made sense not to use pointers.
Dinkumware's STL implementation lets me use std::deque for this, but
not std::list.  Rewriting the code to use pointers would be tedious
and dangerous, and even if I used some sort of smart pointer, it would
need to work with incomplete types.  If various implementations have
proven that certain STL containers can work with incomplete types, why
should it explicitly forbid it?

Dylan
---
[ 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                ]

On Fri,  1 Mar 2002 21:25:14 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:

> I got successful compilation on all six of my compiler/library combos.
> Five of them let me replace vector with list without complaining.  Four of
> them let me use set.

> FWIW, my primary interest here is in whether it is practical to suggest
> that for C++0x, the restriction against instantiating containers with
> incomplete be lifted.

Yes, this topic has also been discussed on clc++m.  There is
considerable interest in the container of self idiom.  There is also
interest in the list<container<self>::iterator> idiom.

I don't have your set of compiler/library combos available, but here is
a test case.

#include <deque>
#include <list>
#include <map>
#include <set>
#include <vector>
struct S {
    friend bool operator< (S const& lhs, S const& rhs) {
        return lhs.i < rhs.i;
        }
    S (int i) : i(i) { }
    void insert (S const& x) {
        v.push_back(x);
        d.push_back(x);
        l.push_back(x);
        s.insert(x);
        m.insert(std::make_pair(i, x));
        }
    int i;
    std::vector<S> v;
    std::deque<S> d;
    std::list<S> l;
    std::set<S> s;
    std::map<int,S> m;
    };
int main () {
    S s1(1);
    s1.insert(S(2));
    }

This compiles with gcc-2.95.2 + libstdc++v2, gcc-3.0.2 + libstdc++v3,
and Comeau online latest 4.2 and 4.3 beta.  The only other
implementation that I have available is an old BC4.5 which may be
excused for not accepting anything but vector.  The errors that I
checked were compiler not library.

Can you tell with your systems whether the problems are reasonable
library code which should not be accepted or compiler problems in
not accepting the library?  Is STLport in there?  Does it fail for
something other than a concept check?

I have found that I sometimes do not understand things like this
because of a lack of information.  It is obviously possible to
write a library which supports the above.  It is not obvious that
a reasonable library might not be supported by a conformant compiler.
It is even possible that all three of those compilers should reject
the code for reasons other than the undefined behavior.

Another simple test which I think should compile.

template <class T>
class List {
   public :
      List ();
      void push_front (T const&);
   private :
      struct Node {
         Node* next;
         T data;
         };
      Node* head;
   };
struct S {
   int i;
   List<S> l;
   };

How does that play with your compilers?  This is important for Matt's
parting shot that we can write containers which may be instantiated
on incomplete types.  What are the real standard constraints on us?
Is it reasonable to force library writers into those constraints?

John

---
[ 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                ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.16e77531e7b08b2d9896c2@news.hevanet.com...
> 17.4.3.6 says that I can't instantiate a standard library template with an
> incomplete type.  In his February column
> (http://www.cuj.com/experts/2002/austern.htm?topic=experts), Matt Austern
> explains the rationale behind this restriction, at one point writing:

>   It's easy to see that defining an std::map<K, V>, where K or V is an
>   incomplete type, is quite hopeless. The value type of an std::map<K, V>,
>   ... is std::pair<const K, V>. In turn, pair<T1, T2> has a member
variable
>   of type T1 and another one of type T2. You can't have member variables
of
>   an incomplete type, and that's what this would mean: instantiating
map<K,
>   V> necessarily requires instantiating pair<const K, V>.

> I don't get it, and I have to confess to being a little suspicious of his
> (usually excellent) reasoning, because in the same column he claims that
> you can't declare a function taking or returning an incomplete type, and I
> know that that is incorrect.  (Declaring them is fine, you just can't call
> them until the type is complete.)

> Unlike Matt, I've never had to implement the STL, but it seems to me that
a
> reasonable approach to implementing map is to have each object hold a
> pointer (initially null) to the root of the tree, something like this:

>   #include <utility>
>
>   template<typename K, typename V>
>   class myMap {
>     typedef typename std::pair<const K, V> value_type;
>
>     struct Node {
>       value_type val;
>       Node *left, *right;
>     };
>
>     Node *root;
>   };
>
> Given the above code and the following extensive test suite,

>   class Widget;
>   myMap<Widget, Widget> m1;

> I get successful compilation by g++ 2.95.2/mingw32, MWCW 6.1, and Comeau
> 4.2.45.2.  (MSVC 6 and Borland 5.5.1 reject it.)  When I replace myMap
with
> std::map, however, all my compilers reject the code.

> Can somebody offer a further clarification of why it makes sense to
> prohibit the instantiation of standard containers with incomplete types?
> I'm happy to believe that Matt's view is fundamentally correct, I just
> don't see how the argument in his column leads to that conclusion, and the
> fact that I have three compilers here that accept my primitive test case
> suggest that I have to dig deeper to find the problem.

Your simple test case has no constructors and no destructors, a real map has
both, which are required by a variable declaration. Since the map manages
memory, the destructor must delete the nodes, directly or indirectly. Unless
it has been written to explicitly separate the delete function from the
destructor, such as for Alan Griffiths' GrinPtr (which adds overhead in
terms of size and performance), the semantics of the destructor therefore
depend on the completeness of the pointed-to objects, and thus implicitly
instantiates the Node class, which fails as the value_type has an incomplete
class as a member. Try the following:

template<typename K, typename V>
class myMap {
    typedef typename std::pair<const K, V> value_type;

    struct Node {
        value_type val;
        Node *left, *right;
    };

    Node *root;

    void deleteNode(Node* p)
   {
        if(p->left) deleteNode(p->left);
        if(p->right) deleteNode(p->right);
        delete p;
    }
public:
    myMap():root(0){}
    ~myMap()
    {
        if(root) deleteNode(root);
    }
};

class Widget;
myMap<Widget,Widget> m2;

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optical Components Ltd
The opinions expressed in this message are not necessarily those of my
employer



---
[ 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                ]

On Fri,  1 Mar 2002 15:45:45 GMT, Martin von Loewis wrote:
> Now, instantiating std::map<K,V>, according to 14.7.1, means that the
> declarations (but not the definitions) of all member functions are
> instantiated.

If I copy the declaration for map out of the standard and provide types for
iterator, const_iterator, size_type, and difference_type, I can
successfully instantiate map on an incomplete type with my compilers from
Borland, Gnu, Metrowerks, and Comeau.  I take this as evidence that member
function declarations are not the motivation for the standard's prohibition
on instantiating containers with incomplete types.

Scott

---
[ 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                ]

On Fri,  1 Mar 2002 17:04:52 GMT, Anthony Williams wrote:
> Your simple test case has no constructors and no destructors, a real map has
> both, which are required by a variable declaration. Since the map manages
> memory, the destructor must delete the nodes, directly or indirectly.

I can see the destructor problem, but it seems to me that vector should
have this problem, too, because it has to delete the dynamically allocated
array holding the T objects.  Yet Matt writes this about vector:

  The C++ Standard doesn't say how vector<T> is supposed to be implemented,
  but in this case the obvious implementation is one that allows T to be an
  incomplete type. The straightforward way to write std::vector is
  something like this:

  template <class T, class Allocator>
  class vector {
   ...
  private:
   Allocator a;
   T* buffer;
   typename Allocator::size_type buffer_size;
   typename Allocator::size_type buffer_capacity;
  };

  Nothing in this requires T to be a complete type; a forward declaration
  is quite good enough. And none of the obvious variations (inheriting from
  Allocator, using three pointers instead of a pointer and two integers,
  and so on) affect this. Indeed, when I reran my tree_node test for this
  column, it passed on the first three compilers I tried.

Attempting to follow in Matt's footsteps, I tried this program:

  #include <vector>

  template<typename T>
  struct tree_node {
   T value;
   std::vector<tree_node> children;
  };

  int main()
  {
    tree_node<int> n;
    return 0;
  }

I got successful compilation on all six of my compiler/library combos.
Five of them let me replace vector with list without complaining.  Four of
them let me use set.

FWIW, my primary interest here is in whether it is practical to suggest
that for C++0x, the restriction against instantiating containers with
incomplete be lifted.  On that topic, Matt writes:

  In a future revision of C++, it might make sense to relax the restriction
  on instantiating standard library templates with incomplete
  types. Clearly, the general prohibition should stay in place ...  But
  perhaps it should be relaxed on a case-by-case basis, and vector looks
  like a good candidate for such special-case treatment: it's the one
  standard container class where there are good reasons to instantiate it
  with an incomplete type and where Standard Library implementors want to
  make it work. As of today, in fact, implementors would have to go out of
  their way to prohibit it!

My problem is that I still don't understand why vector is easy and map is
hard.

Scott
--
Check out the *new* "THE C++ Seminar,"
http://www.gotw.ca/cpp_seminar/

---
[ 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                ]

On Fri,  1 Mar 2002 21:25:14 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:

> Attempting to follow in Matt's footsteps, I tried this program:
>
>   #include <vector>
>
>   template<typename T>
>   struct tree_node {
>    T value;
>    std::vector<tree_node> children;
>   };
>
>   int main()
>   {
>     tree_node<int> n;
>     return 0;
>   }
>
> I got successful compilation on all six of my compiler/library combos.
> Five of them let me replace vector with list without complaining.  Four of
> them let me use set.

With gcc-2.95.2, you can even remove the template confusion and place
one each of vector, deque, list, set, map instantiated on tree_node in
tree_node and it will compile.  The smart compiler notes that it is
within tree_node and can determine the size of each of the containers
and complete tree_node and then instantiate the containers.  This is
an almost complete type which seems to be different from an incomplete
type.

It also rejects all containers of Widget with allocator problems
caused by the destructor and in most cases the constructor.

John

---
[ 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                ]

Scott Meyers <smeyers@aristeia.com> wrote in message news:<MPG.16e9735332a056839896c3@news.hevanet.com>...
> On Fri,  1 Mar 2002 15:45:45 GMT, Martin von Loewis wrote:
> > Now, instantiating std::map<K,V>, according to 14.7.1, means that the
> > declarations (but not the definitions) of all member functions are
> > instantiated.
>
> If I copy the declaration for map out of the standard and provide types for
> iterator, const_iterator, size_type, and difference_type, I can
> successfully instantiate map on an incomplete type with my compilers from
> Borland, Gnu, Metrowerks, and Comeau.  I take this as evidence that member
> function declarations are not the motivation for the standard's prohibition
> on instantiating containers with incomplete types.

A big part of the motivation was that the question of incomplete types
did not come up until very late in the standards process, in
processing public comments on CD-2.  The last meeting before the
meeting where the final vote would be taken, IIRC.  There was no time
to analyse a potentially tricky question, so we just prohibited
incomplete types to be on the safe side.  It is always much easier to
lift a prohibition later (because that does not break user code) than
to impose a new prohibition which will certainly break user code.

--Beman Dawes

---
[ 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                ]

17.4.3.6 says that I can't instantiate a standard library template with an
incomplete type.  In his February column
(http://www.cuj.com/experts/2002/austern.htm?topic=experts), Matt Austern
explains the rationale behind this restriction, at one point writing:

  It's easy to see that defining an std::map<K, V>, where K or V is an
  incomplete type, is quite hopeless. The value type of an std::map<K, V>,
  ... is std::pair<const K, V>. In turn, pair<T1, T2> has a member variable
  of type T1 and another one of type T2. You can't have member variables of
  an incomplete type, and that's what this would mean: instantiating map<K,
  V> necessarily requires instantiating pair<const K, V>.

I don't get it, and I have to confess to being a little suspicious of his
(usually excellent) reasoning, because in the same column he claims that
you can't declare a function taking or returning an incomplete type, and I
know that that is incorrect.  (Declaring them is fine, you just can't call
them until the type is complete.)

Unlike Matt, I've never had to implement the STL, but it seems to me that a
reasonable approach to implementing map is to have each object hold a
pointer (initially null) to the root of the tree, something like this:

  #include <utility>

  template<typename K, typename V>
  class myMap {
    typedef typename std::pair<const K, V> value_type;

    struct Node {
      value_type val;
      Node *left, *right;
    };

    Node *root;
  };

Given the above code and the following extensive test suite,

  class Widget;
  myMap<Widget, Widget> m1;

I get successful compilation by g++ 2.95.2/mingw32, MWCW 6.1, and Comeau
4.2.45.2.  (MSVC 6 and Borland 5.5.1 reject it.)  When I replace myMap with
std::map, however, all my compilers reject the code.

Can somebody offer a further clarification of why it makes sense to
prohibit the instantiation of standard containers with incomplete types?
I'm happy to believe that Matt's view is fundamentally correct, I just
don't see how the argument in his column leads to that conclusion, and the
fact that I have three compilers here that accept my primitive test case
suggest that I have to dig deeper to find the problem.

Thanks,

Scott

--
Check out the *new* "THE C++ Seminar,"
http://www.gotw.ca/cpp_seminar/

---
[ 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                ]

Scott Meyers <smeyers@aristeia.com> writes:

>   It's easy to see that defining an std::map<K, V>, where K or V is an
>   incomplete type, is quite hopeless. The value type of an std::map<K, V>,
>   ... is std::pair<const K, V>. In turn, pair<T1, T2> has a member variable
>   of type T1 and another one of type T2. You can't have member variables of
>   an incomplete type, and that's what this would mean: instantiating map<K,
>   V> necessarily requires instantiating pair<const K, V>.
>
> I don't get it, and I have to confess to being a little suspicious of his
> (usually excellent) reasoning

It's not quite clear what part of that reasoning you are questioning.

First, do you agree that you cannot instantiate the class std::pair<K,V>,
where either K or V is an incomplete type? According to 20.2.2, a pair
has both a K and a V member. Instantiating a class template is an
error if one of the members is of incomplete type.

Now, instantiating std::map<K,V>, according to 14.7.1, means that the
declarations (but not the definitions) of all member functions are
instantiated.

std::map<K,V> has a number of member functions that expect arguments
of type. 14.7.1/4 is a bit vague as to whether the instantiation of
the map member function declarations implicitly results in
instantiation of the function arguments - it does so if instantiation
"affects the semantics of the program". 14.7.1/5 leaves it unspecified
whether instantiation occurs if overload resolution can be performed
without instantiation.

It seems to me that an attempt to instantiate std::pair does affect
the semantics of the program - it will be ill-formed. There is a
number of cases explicitly excluded (if no template definition has
been seen, the type will be incomplete, and default arguments are not
instantiated); I cannot find any wording that prohibits the
instantiation of std::pair for use in the signatures, though.

Regards,
Martin

---
[ 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                ]