In article <0ffbj0t8q2d3k1lvkg6v6bsd3e7aql02il@4ax.com>,
 tom_usenet@hotmail.com (tom_usenet) wrote:

> >That's true. Keeping the "end" node by value can be a little
> >faster. On the other hand, the perfomance hit for allocation
> >and deallocation should be minor if the user does not create
> >and destroy a lot of empty lists. And also begin() will be
> >just a single assembler instruction longer for the allocated
> >"end" node. (Did I forget any other performance hits?)
>
> Obviously this affects the other node based containers too. I can't
> think of any other performance problems, which isn't to say they don't
> exist; a Dinkumware or libstdc++ implementor would be more qualified
> to comment.

Consider:

vector<list<T> > v(100);

In one design you go to the heap 101 times to construct the vector.  In
another you go to the heap 1 time.  Metrowerks has been doing the "by
value" end node optimization for nearly 6 years now.  It is an
incredibly important part of a well optimized STL.  It is very
liberating in code design to be able to create a list even if it might
end up being empty.  Indeed I've seen way too much code that looks like:

class MyClass
{
public:
...
private:
    ...
    std::list<stuff>* data_;
};

I.e. the MyClass author didn't want to pay for the data_ until the
situation came up that he was sure he needed it.  But if list<T> is
essentially cost free to default construct, then you can do:

class MyClass
{
public:
...
private:
    ...
    std::list<stuff> data_;
};

Which simplifies MyClass's design in several places, including the copy
constructor, other constructors, assignment operator, and destructor.
It also simplifies the logic MyClass goes through to access data_ (e.g.
there is no need to check for the null list pointer and new a list if
necessary).

The downside of the "by value" end node optimization?  If done properly,
I can't really think of any.

-Howard

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

hinnant@metrowerks.com (Howard Hinnant) wrote (abridged):
> The downside of the "by value" end node optimization?  If done
> properly, I can't really think of any.

I think you're assuming the node is always allocated. It's possible to
have a design in which:

    vector<list<T> > v(100);

goes to the heap just once, and where sizeof(list<T>) == sizeof(T*). This
probably means more checks and indirections on just about every other list
operation, though. It is a time versus space tradeoff. The STL makes a lot
of fuss about time costs and generally ignores space. Back in the days
when I wrote C/BCPL I used to prefer lists partly because an empty one
only took a single word of memory.

I thought the other downside of the "by value" end node optimisation was
that T cannot be an incomplete type? The ability to use incomplete types
is important and often worth fighting for, even at some cost in run-time
efficiency.

-- Dave Harris, Nottingham, UK

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

In article <memo.20040905110355.3092A@brangdon.m>,
 brangdon@cix.co.uk (Dave Harris) wrote:

> hinnant@metrowerks.com (Howard Hinnant) wrote (abridged):
> > The downside of the "by value" end node optimization?  If done
> > properly, I can't really think of any.
>
> I think you're assuming the node is always allocated. It's possible to
> have a design in which:
>
>     vector<list<T> > v(100);
>
> goes to the heap just once, and where sizeof(list<T>) == sizeof(T*).

You're right, I did forget about this possibility.

> This
> probably means more checks and indirections on just about every other list
> operation, though. It is a time versus space tradeoff.

Yep.

> The STL makes a lot
> of fuss about time costs and generally ignores space. Back in the days
> when I wrote C/BCPL I used to prefer lists partly because an empty one
> only took a single word of memory.

Fwiw, an empty std::list<T> in the Metrowerks implementation takes 3
words of memory (no matter the sizeof(T)), and one of those words is the
cached size (another incredibly important optimization).  The other two
words are essentially begin() and end().

A good single word overhead list could be done with slist, though the
current Metrowerks implementation does not achieve this.  Such an slist
would lack a size() member function, lest unwary clients read the
standard:

> a.size() ... (Note A)
> ...
> Those entries marked ``(Note A)'' should have constant complexity.

and incorrectly interpreted it in the obvious way.

> I thought the other downside of the "by value" end node optimisation was
> that T cannot be an incomplete type? The ability to use incomplete types
> is important and often worth fighting for, even at some cost in run-time
> efficiency.

<shrug>  This compiles for me:

#include <list>

struct A
{
    std::list<A> list_;
};

int main()
{
    A a;
    a.list_.push_back(a);
}

Admittedly, not all of the Metrowerks containers do allow incomplete
types.  But that's more a function of other optimizations, and the lack
of intentional design for this scenario since the standard does define
it as undefined behavior.  But by no means does the "by value" end node
optimization prohibit incomplete types ... unless incorrectly
implemented.

-Howard

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

"tom_usenet" <tom_usenet@hotmail.com> wrote in message
news:glt0i050v78sht3litjnlerj90edqn70h5@4ax.com...
On Mon,  9 Aug 2004 16:42:49 GMT, vm@nowhere.invalid ("Vladim   r
Marko") wrote:
> >The first evident use of containers of ITs is the
> >recursive design of a class that contains a container
> >of objects of the same class (see [CoIT]). This
> >seems to be a legal use for any container.
>
> Yes, but carefully writing the container and supporting classes, I
> think you can make this work for all the standard containers. However,
> this will impact ease of implementation, and possibly even performance
> (since, e.g., a std::list can't contain by value its "end" node if it
> is to work with incomplete types).

Well, on second thought, I believe the implementation is not
allowed to keep the "end" node by value at all. Or, more
precisely, the "end" node may not be a true node, because
the contained class need not be DefaultConstructible.
That said, we need to see how to make the containers
work at all.

The first option is to allocate a node for use as an "end"
node and never construct the value, just set up the links.

The second option (the one I just [re?]invented) is to make
the links form a base class of the node,
  struct Node: public Links { T Value; };
The Links class shall contain the links as pointers to Links
and the iterator shall also internaly contain
  Links* p_;
The iterator dereference shall return
  static_cast<Node*>(p_)->Value
and with the guarantee for static_cast in 5.2.9/5 of the
standard everything works fine. The "end" "node" can be
held by value even for ITs and we have also eliminated
the memory waste introduced by the first option. This is
the optimal solution, isn't it?

Regards,
Vladimir Marko



---
[ 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 Fri, 20 Aug 2004 20:45:21 GMT, vm@nowhere.invalid ("Vladim=EDr
Marko") wrote:

>That's true. Keeping the "end" node by value can be a little
>faster. On the other hand, the perfomance hit for allocation
>and deallocation should be minor if the user does not create
>and destroy a lot of empty lists. And also begin() will be
>just a single assembler instruction longer for the allocated
>"end" node. (Did I forget any other performance hits?)

Obviously this affects the other node based containers too. I can't
think of any other performance problems, which isn't to say they don't
exist; a Dinkumware or libstdc++ implementor would be more qualified
to comment.

>> What do you mean by "use" them. I think certain operations (such as
>> copying them around) might be ok, but others (such as incrementing
>> them) not. IOW, instantiation of the iterator types might be allowed,
>> but most uses not. Obviously it's impossible to increment a vector
>> iterator for a vector<IT>!
>
>Well, it is also impossible to increment a plain pointer to an
>IT, isn't it? By "using" the iterators I mean all uses that are
>allowed with pointers to ITs.

Ok.

[snip]

>Keeping a vector<CT>::iterator around while modifiing the
>vector is a dangerous thing to do.

But it is perfectly legal and safe if done according to the rules of
vector iterator invalidation.

> IMHO the only valid use
>of a vector iterator is the use as a local variable (or an
>unnamed temporary used to initialize an unnamed inserter
>to be passed to some algorithm). By allowing the "use"
>(see above) of vector<IT>::iterator we would only allow
>something that's both useless and dangerous.

The stability of vector (and deque) iterators is well defined, well
documented, and, dare I say it, reasonably well understood, just as it
is for the  node based containers. Again, this has nothing to do with
incomplete types, and I still don't see why you want to make your
feature inconsistent when it makes no difference to iterator stability
anyway. Remember, iterators to node based containers can be
invalidated too.

There are legitimate uses of vector and deque iterators beyond local
variables. For a start, const_iterators into const containers have no
issues of invalidation to worry about. Also, vector::reserve can be
used to prevent iterator invalidation and deque iterators aren't
invalidated by push/pop/ _front/_back. The advantage of a vector
iterator over an index is that you don't need the container in order
to get at the referenced element. The advantage over a pointer is that
you might gain access to debugging iterators during development.

>[snip]
>> However, again we have the same problem with user defined comparators
>> as with user defined allocators; they may not be instantiable with
>> incomplete types.
>
>If the user suplies the comparator class it must be
>a complete type. Who cares if it is an instantiatiation of
>a user template with an incomplete type? Corect me if
>I am wrong, but I think that the standard cares not.

You're right.

>> Yes, this is possible, but I don't see the harm in allowing
>> vector<IT>::iterator to be instantiated. e.g.
>>
>> class Foo;
>>
>> struct Bar
>> {
>>   vector<Foo> foovec;
>>   vector<Foo>::iterator specialpos;
>> };
>>
>> As long as the iterators are correctly kept valid, this is fine; ITs
>> have no extra bearing on the problem compared to the general problem
>> of iterator invalidation.
>
>And with every insertion to foovec the specialpos needs
>to be updated. This is reasonable only if specialpos marks
>the insertion position, so that we insert exclusively by
>  specialpos=3Dfoovec.insert(specialpos,foo);
>as the inserter does. Otherwise, use
>  vector<Foo>::size_type specialpos
>instead.

specialpos does *not* necessarily have to be updated after every
insertion; it depends on whether it will be invalidated by the
insertion or not, and that is something that is known a priori.

Tom

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

"tom_usenet" <tom_usenet@hotmail.com> wrote in message
news:glt0i050v78sht3litjnlerj90edqn70h5@4ax.com...
On Mon,  9 Aug 2004 16:42:49 GMT, vm@nowhere.invalid ("Vladim   r
Marko") wrote:
[snip]
> >The first evident use of containers of ITs is the
> >recursive design of a class that contains a container
> >of objects of the same class (see [CoIT]). This
> >seems to be a legal use for any container.
>
> Yes, but carefully writing the container and supporting classes, I
> think you can make this work for all the standard containers. However,
> this will impact ease of implementation, and possibly even performance
> (since, e.g., a std::list can't contain by value its "end" node if it
> is to work with incomplete types).

That's true. Keeping the "end" node by value can be a little
faster. On the other hand, the perfomance hit for allocation
and deallocation should be minor if the user does not create
and destroy a lot of empty lists. And also begin() will be
just a single assembler instruction longer for the allocated
"end" node. (Did I forget any other performance hits?)

[snip]
> >The iterators are a generalization of pointers
> >and as such we should be able to use them
> >to point to ITs.
>
> What do you mean by "use" them. I think certain operations (such as
> copying them around) might be ok, but others (such as incrementing
> them) not. IOW, instantiation of the iterator types might be allowed,
> but most uses not. Obviously it's impossible to increment a vector
> iterator for a vector<IT>!

Well, it is also impossible to increment a plain pointer to an
IT, isn't it? By "using" the iterators I mean all uses that are
allowed with pointers to ITs.

[snip]
> This is fine for std::allocator, but what about special allocators? If
> you are to support allocators with, e.g., special pointer types, it
> doesn't seem feasible to ask the implementors of such allocators (i.e.
> end users) to make sure that their allocators can be instantiated with
> ITs.
>
> So any allowance for instantiating containers with incomplete types
> can only really be extended to instantiations using std::allocator.
> The alternative allowance might be:
> You can instantiate a container with an incomplete type as long as the
> allocator argument can be instantiated with an incomplete type.
> std::allocator may be instantiated with an incomplete type.

Yes, that's it. The container can be instantiated with an IT
iff the supplied allocator class is complete and its member
rebind<T>::other is also complete even for incomplete Ts.
(This is the most strict version, maybe the second part
could be relaxed... further research required.)

[snip]
> > ... as we
> >want the
> >  iterator and const_iterator
> >(the last two nested types for a generic container)
> >to be complete types for an incomplete
> >value_type anyway.
>
> That isn't necessary for your first example - holding a container of
> self.

True. But I think the second example is more
important to me anyway.

[snip]
> >To impose even more tight relationship
> >between pointers and iterators we need to look
> >at the events that invalidate them. In C, plain
> >pointers are invalidated only when the
> >pointed-to object ceases to exist. In a generic
> >C++ container the iterators are invalidated on
> >many ocasions even when the element is still
> >present. There are some exceptions, namely
> >associative containers and std::list (see 23.1.2/8,
> >23.2.2.3 and 23.1/10 for swap), where the
> >iterators behave as pointers wrt the invalidation.
> >As such only these should be safe to use with IT.
>
> In what way does your argument above apply to vector<IT>::iterator and
> not to vector<CT>::iterator? I see no problem with including vector
> and deque along with the others.

Keeping a vector<CT>::iterator around while modifiing the
vector is a dangerous thing to do. IMHO the only valid use
of a vector iterator is the use as a local variable (or an
unnamed temporary used to initialize an unnamed inserter
to be passed to some algorithm). By allowing the "use"
(see above) of vector<IT>::iterator we would only allow
something that's both useless and dangerous.

[snip]
> However, again we have the same problem with user defined comparators
> as with user defined allocators; they may not be instantiable with
> incomplete types.

If the user suplies the comparator class it must be
a complete type. Who cares if it is an instantiatiation of
a user template with an incomplete type? Corect me if
I am wrong, but I think that the standard cares not.

[snip]
> I still don't understand this argument about iterator validity being
> related in any way to allowing the container to be instantiated with
> an incomplete type.

See above ("avoid what is both useless and dangerous").

> >Remark4:
> >  It is possible to implement std::vector in such
> >  a way that vector<T> is complete type and
> >  vector<T>::iterator is IT for IT T. This would
> >  allow the recursive design from [CoIT] while
> >  protecting from the "linked vector" example.
> >  This would require additional research.
>
> Yes, this is possible, but I don't see the harm in allowing
> vector<IT>::iterator to be instantiated. e.g.
>
> class Foo;
>
> struct Bar
> {
>   vector<Foo> foovec;
>   vector<Foo>::iterator specialpos;
> };
>
> As long as the iterators are correctly kept valid, this is fine; ITs
> have no extra bearing on the problem compared to the general problem
> of iterator invalidation.

And with every insertion to foovec the specialpos needs
to be updated. This is reasonable only if specialpos marks
the insertion position, so that we insert exclusively by
  specialpos=foovec.insert(specialpos,foo);
as the inserter does. Otherwise, use
  vector<Foo>::size_type specialpos
instead.

[snip]
> Again, why do incomplete types have any extra problems with iterator
> invalidation compared to complete types? There are just as many
> potential errors to be made either way.

See above.

[snip]
> > ... nested types
> >    std::list<T>::iterator ,
> >    std::list<T>::const_iterator
> >  must be complete.
>
> They need not be complete, but they should be instantiable.

The second example requires the iterators to be complete.
The same should be imposed for list's iterators to make
this proposal useful and consistent.

[snip]
> >  To allow the instantiation of standard
> >  associative containers (std::set, std::map,
> >  std::multiset, std::multimap) with incomplete
> >  types also std::less should be allowed to be
> >  instantiated with incomplete types in
> >  addition to the same requirements as for
> >  std::list. [snip]
>
> This requirement would also have to be passed onto user defined
> comparators in some way.

User supplied comparator is a class, not a template.
See above.

Sorry, for the late response, I was offline for a week.
And I will likely be offline for another one.

Regards,
Vladimir Marko



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

..
> Once again I looked into the standard and I liked what
> I saw. In 12.1/7 I read
>   An implicitly-declared default constructor for a class is
>   implicitly defined when it is used to create an object of
>   its class type (intro.object). [snip]

My mistake. I didn't read this before I posted my response.

>
> What do you need that for?

We use it for the empty string.

> Well, I could imagine some
> use of sizeof(T) for std::vector and std::basic_string,
> but I can't think of any use for std::list or associative
> containers.

The Dinkumware library that comes with MSVC seems to rely on it
even in those containers.

> do you know of any implementation that won't compile
>   #include <memory>
>   struct S;
>   std::alocator<S> aS;
>   int main() { return 0; }
> ? I do not. (I tested BCB5, gcc 3.2 and 3.4,
> Comeau Online and Visual C++ Toolkit.)

Not off the top of my head but I can easily imagine a user-defined
allocator that would not.

> AFAICT this proposal would be supported
> by the users of STL and more or less opposed
> by the implementors. With some of the
> implementations already providing some or all
> of the requested functionality the opposition
> should not be too strong.

Write it up and let's see how it does :)

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

(moderators, I posted this a few days ago, but I didn't get a
moderator bot response, even though I cc'ed it to the posting e-mail
address)

On Mon,  9 Aug 2004 16:42:49 GMT, vm@nowhere.invalid ("Vladim=EDr
Marko") wrote:

>I would like to discuss the restriction on instantiation
>of standard containers with incomplete types. IMHO
>the restriction could be removed for associative
>containers and std::list. This post is a little longer,
>so a summary can be found at the end.

I've been meaning to reply to this before now, but only just found
time.

>The article
>  http://www.cuj.com/documents/s=3D7986/cujcexp2002austern/
>(from now on just [CoIT])
>discusses the reasons why the instantiation of
>standard library templates with incomplete types
>is forbidden. It is a little flawed as I will show
>while explaining my "rationale", but these little
>details are unrelated to the restriction itself.
>
>>From now on IT will denote an incomplete type.
>
>The first evident use of containers of ITs is the
>recursive design of a class that contains a container
>of objects of the same class (see [CoIT]). This
>seems to be a legal use for any container.

Yes, but carefully writing the container and supporting classes, I
think you can make this work for all the standard containers. However,
this will impact ease of implementation, and possibly even performance
(since, e.g., a std::list can't contain by value its "end" node if it
is to work with incomplete types).

>The second very useful case is to keep a linked
>list within a container by using the nested type
>iterator or const_iterator.

I think that's also possible with a sufficiently careful standard
library implementation.

>Similar, we might need to keep references
>in two containers to each other or otherwise
>link two or more containers.

Again, I think that's possible.

>The iterators are a generalization of pointers
>and as such we should be able to use them
>to point to ITs.

What do you mean by "use" them. I think certain operations (such as
copying them around) might be ok, but others (such as incrementing
them) not. IOW, instantiation of the iterator types might be allowed,
but most uses not. Obviously it's impossible to increment a vector
iterator for a vector<IT>!

>Let's see in detail what do we need to do to
>allow to instantiate a container with an IT. We
>will suppose that the container has an allocator
>and nested types
>  pointer and const_pointer
>although the container requirements do not
>contain them (all the standard containers do).
>
>First, the allocator must be a complete type even
>if it is the default std::allocator instantiated with
>the IT. The allocator's nested types
>  pointer, reference and const versions
>are harmless and
>  value_type
>is IT and should be used accordingly. The
>remaining types
>  difference_type and size_type
>would need to be type independent which is the
>first necessary additional requirement. The
>member functions of the allocator are not
>instantiated until actualy used, thus no more
>changes for the allocator are needed.

This is fine for std::allocator, but what about special allocators? If
you are to support allocators with, e.g., special pointer types, it
doesn't seem feasible to ask the implementors of such allocators (i.e.
end users) to make sure that their allocators can be instantiated with
ITs.=20

So any allowance for instantiating containers with incomplete types
can only really be extended to instantiations using std::allocator.
The alternative allowance might be:
You can instantiate a container with an incomplete type as long as the
allocator argument can be instantiated with an incomplete type.
std::allocator may be instantiated with an incomplete type.

>Then, back to the container, the nested type
>  allocator
>has already been discussed, the nested types
>  pointer, reference and const versions
>are harmless again,
>  value_type
>is an IT again and
>  difference_type and size_type
>would need to be type independent once again
>which imposes the same requirement as for the
>allocator with the difference that these nested
>types are bound to iterator and const_iterator.
>This time it is completely unimportant as we
>want the
>  iterator and const_iterator
>(the last two nested types for a generic container)
>to be complete types for an incomplete
>value_type anyway.

That isn't necessary for your first example - holding a container of
self.

 And that simply implies that
>the difference_type and value_type will not
>depend on value_type. So, the last thing to do is
>to discuss the nested  iterator types in detail.
>
>To make the instantiaton of containers with ITs
>useful, the nested types
>  iterator and const_iterator
>should be complete even if the value_type is
>incomplete. This mimics the semantics of plain
>C pointers and implies  that the difference does
>not depend on value_type as required (see
>above). To impose even more tight relationship
>between pointers and iterators we need to look
>at the events that invalidate them. In C, plain
>pointers are invalidated only when the
>pointed-to object ceases to exist. In a generic
>C++ container the iterators are invalidated on
>many ocasions even when the element is still
>present. There are some exceptions, namely
>associative containers and std::list (see 23.1.2/8,
>23.2.2.3 and 23.1/10 for swap), where the
>iterators behave as pointers wrt the invalidation.
>As such only these should be safe to use with IT.

In what way does your argument above apply to vector<IT>::iterator and
not to vector<CT>::iterator? I see no problem with including vector
and deque along with the others.=20

>Concerning the std::list, we are finished.
>Concerning the associative containers we need
>to look at the additional nested types. These are
>  key_type, key_compare and value_compare.
>We want to allow the first to be an IT. The
>second is either user supplied comparison
>object type or default std::less<key_type>.
>This brings us to the next standard template
>that should be allowed to specialize for ITs,
>namely std::less.

If you take the definition of std::less literally (as I think one
can), then it can be instantiated with an incomplete type already.
However, this could be made explicit.

However, again we have the same problem with user defined comparators
as with user defined allocators; they may not be instantiable with
incomplete types.

 Then we have both
>key_compare and value_compare complete
>types. This is all that needs to be done for
>std::set and std::multiset. For std::map and
>std::multimap we also need to state that the
>nested type
>  mapped_type
>can be an IT and everything seems fine. Back
>to the std::less with IT, it seems logical to allow
>other function object templates such as
>std::greater, etc. to be instantiated with ITs.
>
>Remark1:
>  The library changes would not break any
>  existing valid code. It would only make more
>  code valid.
>
>Remark2:
>  gcc (3.2; 3.4) allows even the instantiation of
>    map<Key,Val>
>  with both Key and Val incomplete types. This
>  shows that it is not hopeless as stated in [CoIT].
>  It is in fact an existing practice, though I don't
>  know how many programmers actualy use this
>  feature.

Yes, Matt Austern seemed to think that if map<U,T> is instantated,
pair<const U, T> is necessarily instantiated as well, and this isn't
the case, as long as the implementation is sufficiently careful.

>Remark3:
>  Unordered associative containers (also known
>  as hash_... containers) in proposal
>    http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1456.html
>  have less restrictions on iterators, which can
>  be invalidated also by insertions. As such they
>  are not good candidates for instantiation with
>  incomplete types.

I still don't understand this argument about iterator validity being
related in any way to allowing the container to be instantiated with
an incomplete type.

>Remark4:
>  It is possible to implement std::vector in such
>  a way that vector<T> is complete type and
>  vector<T>::iterator is IT for IT T. This would
>  allow the recursive design from [CoIT] while
>  protecting from the "linked vector" example.
>  This would require additional research.

Yes, this is possible, but I don't see the harm in allowing
vector<IT>::iterator to be instantiated. e.g.

class Foo;

struct Bar
{
  vector<Foo> foovec;
  vector<Foo>::iterator specialpos;
};

As long as the iterators are correctly kept valid, this is fine; ITs
have no extra bearing on the problem compared to the general problem
of iterator invalidation.

>Summary:
>--------
>
>  The instantiation of standard containers with
>  incomplete types would be a useful feature.
>  However, taking into account the possible
>  iterator abuse, it is really safe only for those
>  containers where the iterator invalidation
>  happens only when the pointed-to object is
>  erased, i.e. std::list and associative containers.

Again, why do incomplete types have any extra problems with iterator
invalidation compared to complete types? There are just as many
potential errors to be made either way.

>  To allow the instantiation of std::list with
>  incomplete types, we need to allow also the
>  instantiation of std::allocator with incomplete
>  types and impose a few new requirements,
>  namely that the nested types
>    std::allocator<T>::difference_type ,
>    std::allocator<T>::size_type ,
>    std::list<T>::difference_type ,
>    std::list<T>::size_type
>  may not depend on T and the nested types
>    std::list<T>::iterator ,
>    std::list<T>::const_iterator
>  must be complete.

They need not be complete, but they should be instantiable.

 In fact, the latter implies
>  that the std::list<T>'s difference_type and
>  size_type do not depend on T anyway.
>
>  To allow the instantiation of standard
>  associative containers (std::set, std::map,
>  std::multiset, std::multimap) with incomplete
>  types also std::less should be allowed to be
>  instantiated with incomplete types in
>  addition to the same requirements as for
>  std::list. It would be logical to allow also
>  other function object templates such as
>  std::greater, std::plus, etc. to be instantiated
>  with incomplete types.

This requirement would also have to be passed onto user defined
comparators in some way.

Tom

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

If all you want to be able to do is declare a member of a class whose type
is some container specialized on an incomplete type (such as the class itself),
it seems that it shouldn't be that hard to do given a decent compiler (our
implementation that comes with HP aCC or SunPro already lets you do that with
all containers except map; gcc 3.4's libstdc++ and Intel C++ 8.0 let you do
all four). But if you're proposing a core change that would be whole other
story.

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

"Martin Sebor" <sebormartin@netscape.net> wrote in message
news:a220a90a.0408101750.2eecc74b@posting.google.com...
> If all you want to be able to do is declare a member of a class whose type
> is some container specialized on an incomplete type (such as the class
itself),
> it seems that it shouldn't be that hard to do given a decent compiler (our
> implementation that comes with HP aCC or SunPro already lets you do that
with
> all containers except map; gcc 3.4's libstdc++ and Intel C++ 8.0 let you
do
> all four). But if you're proposing a core change that would be whole other
> story.
>
> Martin

Well, it comes down to how do you define a "decent" compiler.
(Or, perhaps, "decent" std lib implementation.) I sometimes use
the Comeau Online to test code snippets and I also used it to
test the map with IT. It failed on the concept check: assignable.

What I realy want is to be able to use this features _portably_.
(Both, the class with a container of objects of the same class
and, more importantly, the iterator stuff discussed in the
original post.) So I would indeed like to propose a change
to the library part of the standard. To do that I firstly want to
know all the changes that would be needed and any possible
pitfalls that this would introduce. IMHO, the necessary
changes to the standard are small and there are no new
pitfalls. If you know of any problems I did not write about,
please, post it.

Regards,
Vladimir Marko



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

""Vladim   r Marko"" <vm@nowhere.invalid> wrote in message
news:cf7kq8$1rt$1@news.wplus.net...
> The article
>   http://www.cuj.com/documents/s=7986/cujcexp2002austern/
> (from now on just [CoIT])
> discusses the reasons why the instantiation of
> standard library templates with incomplete types
> is forbidden. It is a little flawed as I will show
> while explaining my "rationale", but these little
> details are unrelated to the restriction itself.

Also the article makes the mistake (that I also made until very recently) to
assume that functions taking or returning incomplete types by value cannot
be *declared*. Granted they can't be defined, but declaring is no problem.
Here's an excerpt from the article:

<<
You could write:

my_class& clone(const my_class&);

but you couldn't write:

int illegal_function(my_class);

or:

my_class illegal_function();

You can't pass or return incomplete types by value, for the same reason that
you can't define variables of an incomplete type. And, of course, the
restriction applies to member functions just as it applies to stand-alone
functions. Just as you can't write illegal_function above, so you can't
write:

struct illegal_class {
 my_class f();
};
>>

The above is wrong as a header could define all of the above if my_class is
an incomplete type.


Andrei


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

..
> Well, it comes down to how do you define a "decent" compiler.

I meant one that doesn't needlessly instantiate "too much" of the
template.

> (Or, perhaps, "decent" std lib implementation.) I sometimes use
> the Comeau Online to test code snippets and I also used it to
> test the map with IT. It failed on the concept check: assignable.

Sure, the concept check probably just enforces a requirement of the
standard at the earlies opportunity. Take it out, it will most likely
compile.

>
> What I really want is to be able to use this features _portably_.
> (Both, the class with a container of objects of the same class
> and, more importantly, the iterator stuff discussed in the
> original post.) So I would indeed like to propose a change
> to the library part of the standard. To do that I firstly want to
> know all the changes that would be needed and any possible
> pitfalls that this would introduce. IMHO, the necessary
> changes to the standard are small and there are no new
> pitfalls. If you know of any problems I did not write about,
> please, post it.

I can't think of any inherent technical problems with instantiating
only as much as is necessary to compile a declaration of a template
that depends on an incomplete type, as in the one below.

    struct S {
        S ();
        ~S ();
        std::vector<S> v;
    };

The ctor and dtor declarations are necessary to prevent the compiler
from generating the default versions and instantiating the vector<S>
default ctor in the process. But this in and of itself doesn't
guarantee that the definition of std::vector is well-formed if T
is an incomplete type. If the definition contains a reference to
sizeof(T) (as the MSVC/Dinkumware implementation does) or anything
that requires T to to be a complete type (such as a data member of
type T as in our basic_string). Requiring that it be possible to
instantiate the template on an IT has the potential of pretty
severely limiting implementors' choices. I suspect that a proposal
for such a restriction wouldn't fly with most of them. I certainly
would hesitate to support it.

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

"Martin Sebor" <sebormartin@netscape.net> wrote in message
news:a220a90a.0408121327.6a7cc0be@posting.google.com...
> > Well, it comes down to how do you define a "decent" compiler.

> I meant one that doesn't needlessly instantiate "too much" of the
> template.

That's a reasonable definition. Let's stick to it.

[snip]
> I can't think of any inherent technical problems with instantiating
> only as much as is necessary to compile a declaration of a template
> that depends on an incomplete type, as in the one below.
>
>     struct S {
>         S ();
>         ~S ();
>         std::vector<S> v;
>     };
>
> The ctor and dtor declarations are necessary to prevent the compiler
> from generating the default versions and instantiating the vector<S>
> default ctor in the process.

Once again I looked into the standard and I liked what
I saw. In 12.1/7 I read
  An implicitly-declared default constructor for a class is
  implicitly defined when it is used to create an object of
  its class type (intro.object). [snip]
and similar in 12.8/7 for the copy ctor and in 12.4/5 for
the dtor. Thus, the definition
  struct S{
    std::vector<S> v;
  };
only declares these special members and does not
enforce the instantiation of the std::vector<S>'s default
ctor (copy ctor, dtor). If you later define
  S s;
the struct S is already a complete type.

> But this in and of itself doesn't
> guarantee that the definition of std::vector is well-formed if T
> is an incomplete type. If the definition contains a reference to
> sizeof(T) (as the MSVC/Dinkumware implementation does) or anything
> that requires T to to be a complete type (such as a data member of
> type T as in our basic_string).

What do you need that for? Well, I could imagine some
use of sizeof(T) for std::vector and std::basic_string,
but I can't think of any use for std::list or associative
containers. Especialy when following the footnote
in 20.1.5/2:
  [Footnote: It is intended that a.allocate be an efficient
  means of allocating a single object of type T , even
  when sizeof(T) is small. That is, there is no need for
  a container to maintain its own ``free list''.
  --- end foonote]

> Requiring that it be possible to
> instantiate the template on an IT has the potential of pretty
> severely limiting implementors' choices.

I think it's not _too_ limiting. With a decent compiler
only members, bases and perhaps compile time
constants (enum, static const) are really relevant.
Considering only std::list and associative containers,
the members and bases should only be some
pointers (iterators) and an allocator and if need be
for compile time constants dependent on the type
these can be calculated within the member functions
or nested classes that actualy need them. The only
danger lies with the allocator member, but... do you
know of any implementation that won't compile
  #include <memory>
  struct S;
  std::alocator<S> aS;
  int main() { return 0; }
? I do not. (I tested BCB5, gcc 3.2 and 3.4,
Comeau Online and Visual C++ Toolkit.)

May be I am wrong. An insight from the actual
implementors would be welcome. The more
the better, of course -- a single implementors
opinion could be misleading.

> I suspect that a proposal
> for such a restriction wouldn't fly with most of them. I certainly
> would hesitate to support it.

AFAICT this proposal would be supported
by the users of STL and more or less opposed
by the implementors. With some of the
implementations already providing some or all
of the requested functionality the opposition
should not be too strong.

Vladimir Marko



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

Andrei Alexandrescu (See Website for Email) wrote:
> ""Vladim=EDr Marko"" <vm@nowhere.invalid> wrote in message
> news:cf7kq8$1rt$1@news.wplus.net...
>=20
>>The article
>>  http://www.cuj.com/documents/s=3D7986/cujcexp2002austern/
>>(from now on just [CoIT])
>>discusses the reasons why the instantiation of
>>standard library templates with incomplete types
>>is forbidden. It is a little flawed as I will show
>>while explaining my "rationale", but these little
>>details are unrelated to the restriction itself.
>=20
>=20
> Also the article makes the mistake (that I also made until very recentl=
y) to
> assume that functions taking or returning incomplete types by value can=
not
> be *declared*. Granted they can't be defined, but declaring is no probl=
em.

I already noticed this mistake a few days ago to the editor. Hopefully,=20
the article will be corrected.

--=20
Lo=EFc

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

X-No-Acknowledgement
X-No-Reject-Notice
I would like to discuss the restriction on instantiation
of standard containers with incomplete types. IMHO
the restriction could be removed for associative
containers and std::list. This post is a little longer,
so a summary can be found at the end.

The article
  http://www.cuj.com/documents/s=7986/cujcexp2002austern/
(from now on just [CoIT])
discusses the reasons why the instantiation of
standard library templates with incomplete types
is forbidden. It is a little flawed as I will show
while explaining my "rationale", but these little
details are unrelated to the restriction itself.

>From now on IT will denote an incomplete type.

The first evident use of containers of ITs is the
recursive design of a class that contains a container
of objects of the same class (see [CoIT]). This
seems to be a legal use for any container.

The second very useful case is to keep a linked
list within a container by using the nested type
iterator or const_iterator.
[Example:
We need a map<Key,Data> with an additional
time stamp of the insertion/update. The check for
a too old element should be O(1). To achieve
this we need these structures:
  struct Val{
    Data d;
    time_t iu_time; ///< insert/update time
    map<Key,Val>::iterator next,prev; ///< Val is IT here
  };
  map<Key,Val> m;
  map<Key,Val>::iterator first,last;
--- end example]
Similar, we might need to keep references
in two containers to each other or otherwise
link two or more containers.
[Example:
We need a O(log n) search for some data
using two different criteria. It could be
implemented with these structures:
  struct Val1{
    Data d;
    map<Key2,map<Key1,Val>::iterator>
        ::iterator map2_node; ///< Val is IT here
  }
  map<Key1,Val> m1;
  map<Key2,map<Key1,Val>::iterator> m2;
(A currently valid implementation with no worse
computational complexity features smart
pointers to ITs to work around the iterator
limitations. It comes with a certain performance
hit due to double indirection and additional
memory management.)
--- end example]

The iterators are a generalization of pointers
and as such we should be able to use them
to point to ITs. It may, however, be dangerous.
It comes from the possibility of iterator
invalidation.
[Example:
  struct Val{
    Data d;
    time_t iu_time; ///< insert/update time
    vector<Val>::iterator next,prev; ///< Val is IT here
  };
  vector<Val> m;
  vector<Val>::iterator first,last;
For example a push_back(.) can invalidate all
"next" and "prev" members. Insertion and
erasure with this structure would be very time
consuming and error prone.
(This is a counteraxample for the suggestion
in [CoIT] that the vector is a good candidate
for instantiating with an IT. IMO it is not.)
--- end example]

Let's see in detail what do we need to do to
allow to instantiate a container with an IT. We
will suppose that the container has an allocator
and nested types
  pointer and const_pointer
although the container requirements do not
contain them (all the standard containers do).

First, the allocator must be a complete type even
if it is the default std::allocator instantiated with
the IT. The allocator's nested types
  pointer, reference and const versions
are harmless and
  value_type
is IT and should be used accordingly. The
remaining types
  difference_type and size_type
would need to be type independent which is the
first necessary additional requirement. The
member functions of the allocator are not
instantiated until actualy used, thus no more
changes for the allocator are needed.

Then, back to the container, the nested type
  allocator
has already been discussed, the nested types
  pointer, reference and const versions
are harmless again,
  value_type
is an IT again and
  difference_type and size_type
would need to be type independent once again
which imposes the same requirement as for the
allocator with the difference that these nested
types are bound to iterator and const_iterator.
This time it is completely unimportant as we
want the
  iterator and const_iterator
(the last two nested types for a generic container)
to be complete types for an incomplete
value_type anyway. And that simply implies that
the difference_type and value_type will not
depend on value_type. So, the last thing to do is
to discuss the nested  iterator types in detail.

To make the instantiaton of containers with ITs
useful, the nested types
  iterator and const_iterator
should be complete even if the value_type is
incomplete. This mimics the semantics of plain
C pointers and implies  that the difference does
not depend on value_type as required (see
above). To impose even more tight relationship
between pointers and iterators we need to look
at the events that invalidate them. In C, plain
pointers are invalidated only when the
pointed-to object ceases to exist. In a generic
C++ container the iterators are invalidated on
many ocasions even when the element is still
present. There are some exceptions, namely
associative containers and std::list (see 23.1.2/8,
23.2.2.3 and 23.1/10 for swap), where the
iterators behave as pointers wrt the invalidation.
As such only these should be safe to use with IT.

To complete the iterator discussion we need to
add a note on the reverse iterators. The relation
  &*(reverse_iterator(i)) == &*(i - 1)
shows that a reverse iterator is allways
invalidated when the _next_ element is beeing
erased and the pointed-to element allways
changes with insertion after the pointed-to
object. So the use of reverse iterators has
allways been dangerous and the fact that the
value_type is an IT makes really no difference.

Concerning the std::list, we are finished.
Concerning the associative containers we need
to look at the additional nested types. These are
  key_type, key_compare and value_compare.
We want to allow the first to be an IT. The
second is either user supplied comparison
object type or default std::less<key_type>.
This brings us to the next standard template
that should be allowed to specialize for ITs,
namely std::less. Then we have both
key_compare and value_compare complete
types. This is all that needs to be done for
std::set and std::multiset. For std::map and
std::multimap we also need to state that the
nested type
  mapped_type
can be an IT and everything seems fine. Back
to the std::less with IT, it seems logical to allow
other function object templates such as
std::greater, etc. to be instantiated with ITs.

Remark1:
  The library changes would not break any
  existing valid code. It would only make more
  code valid.

Remark2:
  gcc (3.2; 3.4) allows even the instantiation of
    map<Key,Val>
  with both Key and Val incomplete types. This
  shows that it is not hopeless as stated in [CoIT].
  It is in fact an existing practice, though I don't
  know how many programmers actualy use this
  feature.

Remark3:
  Unordered associative containers (also known
  as hash_... containers) in proposal
    http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1456.html
  have less restrictions on iterators, which can
  be invalidated also by insertions. As such they
  are not good candidates for instantiation with
  incomplete types.

Remark4:
  It is possible to implement std::vector in such
  a way that vector<T> is complete type and
  vector<T>::iterator is IT for IT T. This would
  allow the recursive design from [CoIT] while
  protecting from the "linked vector" example.
  This would require additional research.

Summary:
--------

  The instantiation of standard containers with
  incomplete types would be a useful feature.
  However, taking into account the possible
  iterator abuse, it is really safe only for those
  containers where the iterator invalidation
  happens only when the pointed-to object is
  erased, i.e. std::list and associative containers.

  To allow the instantiation of std::list with
  incomplete types, we need to allow also the
  instantiation of std::allocator with incomplete
  types and impose a few new requirements,
  namely that the nested types
    std::allocator<T>::difference_type ,
    std::allocator<T>::size_type ,
    std::list<T>::difference_type ,
    std::list<T>::size_type
  may not depend on T and the nested types
    std::list<T>::iterator ,
    std::list<T>::const_iterator
  must be complete. In fact, the latter implies
  that the std::list<T>'s difference_type and
  size_type do not depend on T anyway.

  To allow the instantiation of standard
  associative containers (std::set, std::map,
  std::multiset, std::multimap) with incomplete
  types also std::less should be allowed to be
  instantiated with incomplete types in
  addition to the same requirements as for
  std::list. It would be logical to allow also
  other function object templates such as
  std::greater, std::plus, etc. to be instantiated
  with incomplete types.

Regards,
Vladimir Marko





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

..
> First, the allocator must be a complete type even
> if it is the default std::allocator instantiated with
> the IT.

Uhm, how do you suggest that std::allocator<T>::allocate()
deal with T being an IT when sizeof(IT) is ill-formed?

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

"Martin Sebor" <sebormartin@netscape.net> wrote in message
news:a220a90a.0408091715.6ffc1cbf@posting.google.com...
> ..
> > First, the allocator must be a complete type even
> > if it is the default std::allocator instantiated with
> > the IT.
>
> Uhm, how do you suggest that std::allocator<T>::allocate()
> deal with T being an IT when sizeof(IT) is ill-formed?
>
> Martin

I should have writen that we are dealing with implicit
instantiation, not an explicit one. While the explicit
instantiation
  template class std::allocator<T>;
would instantiate all members (14.7.2/7), the implicit
specialization is forbidden to do so (14.7.1/9):
  An implementation shall not implicitly instantiate
  a function template, a member template, a non-virtual
  member function, a member class or a static data
  member of a class template that does not require
  instantiation. It is unspecified whether or not an
  implementation implicitly instantiates a virtual member
  function of a class template if the virtual member
  function would not otherwise be instantiated. [snip]

Thus, we have
  template <class T,class Alloc=std::allocator<T> >
  class list{
    Alloc alloc_;
    ...
  };
  struct A;
  struct B{
    list<A> la; // implicit instantiation of list<A> forces
               // implicit instantiation of std::allocator<A>
  };
where the std::allocator<A>::allocate will not be
intantiated. (*) On the other hand, if you write
  list<A> ns_la;
at the namespace scope, the default ctor is used
and, depending on the implementation, the allocator
may be used to obtain some storage. I think that
the instantiation with ITs in class definitions should
be fine whereas the definition of an object such as
ns_la is a bad idea. The difference could be defined
in terms of ctor use, namely that the type must be
complete at the point of instantiation of any of the
container's ctors.

(*) is the place where a new previously unexplored
idea starts. All prior to (*) has been considered
and included in the original post in a highy
compressed form: "The member functions of the
allocator are not instantiated until actualy used..."

Vladimir Marko



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