Topic: Comments on STL


Author: doug@deimos.ads.com (Doug Morgan)
Date: 15 Aug 94 12:40:47
Raw View
In article <CuEKHH.LpH@undergrad.math.uwaterloo.ca> r-ridge@calum.csclub.uwaterloo.ca (Ross Ridge) writes:
>Doug Morgan <doug@deimos.ads.com> wrote:
>>I should have been more explicit about what I meant by "changes in
>>semantics."  I prefer specs that guarantee that if you have any
>>reference (or pointer) to an object and perform a given operation, the
>>same action happens.  This should be independent of the declared type
>>of the reference.  This is not the case for classes inheriting from
>>empty.  Say I have two references to a forward_iterator, one through
>>forward_iterator& and one through empty&.  Executing separate =='s on
>>these references results in completely different actions (answers).
>
>First, don't confuse "forward_iterator" and "Forward Iterators".
>forward_iterator<T> isn't an iterator, as it doesn't have ++ and *
>defined for it.

I used "forward_iterator" the sense of an object of some class derived
from forward_iterator<T> and actually a member of the Forward Iterator
category --- I know that instances of the exact class
forward_iterator<T> are not iterators.

>Unless you try, the only way you're going to get a value of type empty
>& is if you compare two objects that inherit from empty, and the
>comparison done will be correct with respect to their emptiness.  I
>don't know exacly why Alex has classes inherit from empty, but I don't
>see it as problem.
>

It is more a matter of preference than a problem.  The use of empty
breaks my notion of what inheritance should mean for ==.  Not everyone
accepts the same notion of inheritance.

>>Forwarding nothing creates a class with a data member.  Such classes
>>do have uses.
>
>There are only two operations you do with such an encapsulated
>object, construct it using it's copy contructor when you
>create the restrictor and destroy it when you destroy the
>restrictor.  You can't assign to it, you can get it's value,
>you can't even compare it to anything.  It seems completely
>useless to me.

You can get it's value: a.value.  In fact, that is the way that
classes inheriting from the current restrictor get to the value.
Using a.value, comparisons can be written.  Such comparisons could
(and generally would) differ from the forwarding comparisons
automatically obtained with the current restrictor.

Also, to make restrictors work in some of the cases I was thinking of,
a default constructor would have to be defined.

>
>>As for forwarding only ==, it doesn't matter that the
>>class you are restricting supports <, what matters is that the class
>>you are deriving is supposed to support < and is supposed to support
>>it in a way that is compatible with the forwarded version.  For
>>instance, reverse_bidirectional_iterator supports <, but in a
>>completely different way than a forwarded version.  It is good to see
>>that reverse_bidirectional_iterator properly does not inherit from
>>restrictor.
>
>I have no idea what you're talking about here.  I think you're
>confused about what the template restrictor does.

That is one pretty confusing paragraph I pasted together.  I just
meant that a class like reverse_bidirectional_iterator could inherit
from an equal_restrictor and automatically get the proper value data
member and forwarding implementation of the == operation.  It would
not get the forwarding implementation of the < operation (as that
implementation is not the right one for
reverse_bidirectional_iterator).

I don't think I am confused about what the template restrictor does.
I just think that it would be nice to have a few more versions of
restrictor.  The current use of restrictor is logically OK (once empty
is removed), but I think the library would be ever so slightly better
with more restrictors.

>
>>>>    stack : equal_restrictor
>>>>    queue : equal_restrictor
>>>>    priority queue : holder_restrictor
>...
>>Correct on both points.  However, the given restrictor inheritance
>>would put exactly the needed data member and == on the derived
>>classes.
>
>Again I don't know what you're talking about.  Exactly
>what changes would you make to definition of the template stack?

I would derive stack from equal_restrictor, remove the declaration of
c, rename c in other uses to value, and remove the friend declaration
and the definition of operator==.  Thus, stack would be:

template <class Container>
class stack: public equal_restrictor<Container> <
public:
      typedef Container::value_type value_type;
      typedef Container::size_type size_type;
public:
      bool empty() const { return value.empty(); }
      size_type size() const { return value.size(); }
      ... etc.  with `c.' replaced by `value.' ...
};

No template for operator==.

This has the same functionality, is 7 to 8 lines shorter, has one less
template definition, and use of a single base class to help structure
code fragments/idioms that are repeated in multiple places --- like
queue.

For stack, the equal_restrictor would need a default constructor.

>
>>Sorry, I didn't mean to imply that reverse_bidirectional_iterator
>>would no longer also inherit from bidirectional_iterator, etc.  I just
>>meant that the restrictors would be added to the list of bases.
>
>I don't see the point of doing that.

Hopefully the above helps.  (After seeing the point, you might still
well decide it is not a good idea.)

>>Exactly, however by inheriting from empty, output_iterators do have ==
>>and < defined.  This is not correct and is what I am pointing out.
>
>Not correct?

Not correct in the model I like for inheritance (it is fine in some
other models).  Assume that i is an Output Iterator, is an object of a
class inheriting from output_iterator, and has no meaningful ==
operation.  Then, i will have an associated == operation defined
through inheritance from empty.  I see this as a flaw.  Others might
not.

>
>>Correct.  However, for instance, by inheriting from empty, there is no
>>way that an output_iterator cannot have an associated == (and it's
>>defined actions are likely to have nothing to do with the "contents"
>>of the iterator).
>
>There are any number of ways an Output iterator derived from
>output_iterator<T> could not have == defined for it.

I don't immediately see any way of stopping operator==(const empty&,
const empty&) from applying to a class derived from output_iterator
(no <T>, since output_iterator isn't a template).  Maybe something
could be done to create an ambiguity that would stop compilation?

>
>>>>Similarly for multiset, map, and multimap.  The non-``ordered_'' names
>>>>should be reserved for the appropriate containers based on equivalence
>>>>relations (not order relations).  (Otherwise, we will have amazing
>>>>names like unordered_set.)
>>>
>>>Actually, they're called sequences in STL.  Wrap them in with an
>>>adaptor to make them look the way you want.
>>
>>I don't follow.
>
> ... template definition of unordered_set

No, my problem was that the name "unordered_set" is almost too
painfully to contemplate (to me at least).  The point is then that by
preempting the name "set" by something that is logically an *ordered*
set (also a painful name, but made less so by tradition), STL leaves
little choice.  No amount of wrapping frees up the name "set" for its
proper use.

>
>>>I don't see the point, for speed you really, really want to have an
>>>ordering between objects in an associated container, even if you're
>>>otherwise uninterested in the ordering of the objects.  Otherwise
>>>just use one of the sequences.
>>
>>No, sometimes for speedy insert and find I want a hashing
>>implementation.
>
>How do you propose to hash objects of unknown type?

Use a hash function object and/or a hash template argument (just like
the current set orders objects of unknown type).  In addition, an
equality test is required (actually, the hash function is not required
for the implementation of every unordered set, but equality probably
is).

>>>If you can hash an object then you can order the object.
>>
>>Sure you can put some order on it, but, in general, that order will
>>not be compatible with any equivalence relation that is compatible
>>with the hash.  In other words, you can't simply convert a hash to an
>>ordering and expect the ordering to properly distinguish distinct
>>elements that hash to the same value.
>
>No, but if you can generate hash value then you have an unhashed value
>that does provide a total ordering.

Not necessarily, all objects *could* hash to zero.  More interesting
counterexamples might be dreamed up (but they might likely all have
some sort of kernel-like portion that affects equality comparisons,
but has no effect on the hash value).

>>>No, map is provides a one way mapping.  A two way mapping is different
>>>container with a significantly different implentation (and more
>>>importantly cost).
>>
>>I never mentioned one way or two way mapping.  I'm saying that I'd
>>like to see map with both operations like:
>>
>>iterator find(const key_type& x);
>>and
>>iterator find(const value_type& x);
>
>So then is:
>
>iterator find(value_type const &x) { find(x.first); }
>
>all you want here?

Right.  Or when thinking about map as a set of pairs with an n:1
constraint, the semantic (not literal) definition might more properly
be:

iterator find(key_type const &x)
  { find(pair(x,value_type::second_type())); }

>>The Compare template argument for associative containers can only be
>>used (consistently) as the default thing to store in an associative
>>container.
>
>No, less<T> not the default thing, it's the default type.

My sloppy English.  Yes, it is the default type of the thing to store.

>
>The rest of your article arrived mangled at this site.

I'll email it to you.

>
>Ross Ridge
>

Doug
--------------------------------------------------------------------
Doug Morgan, doug@ads.com, (415) 960-7444
Advanced Decision Systems (a division of Booz-Allen & Hamilton Inc.)
1500 Plymouth St., Mountain View, CA 94043-1230
--------------------------------------------------------------------




Author: r-ridge@calum.csclub.uwaterloo.ca (Ross Ridge)
Date: Thu, 11 Aug 1994 07:54:16 GMT
Raw View
Doug Morgan <doug@monet.ads.com> wrote:
>I only recently subscribed to this group, so I'm just hoping this
>posting is appropriate.  Here are some comments on the document:
>
>The Standard Template Library
>Alexander Stepanov & Meng Lee
>Doc No: X3J16/94-0095
>        WG21/N0482
>May 31, 1994

I'm hardly an expert on STL, but I throw in my response in anyways.

>1. Many uses of empty and restrictor seem like either strange uses or
>   misuses of public inheritance.
>
>I don't like to see changes in semantics of an operation between a
>base class and a derived class.  I also don't like seeing inheritance
>place an operation on a derived class that doesn't belong there.

There is no change in semantics between the operations of empty and
restrictor<T> and their base or derived classes.  Empty provides
default comparision operations between classes without members and
restrictor<T> removes all but the comparision operations from
a class without changing any operations.

>1.1 It seems arbitrary that there is just one restrictor class for
>    holding an object and forwarding both == and <.  Why isn't there
>    one for forwarding just == and one for forwarding nothing?

Because == and < are the minimal set of operations needed for doing equality
and inequality comparison operations on a object.  Forwarding nothing
only creates a useless class and there isn't any point to forwarding
== and not < if the class your restricting supports <.

>    With these restrictors, inheritance for adaptors would look like:
>
>    stack : equal_restrictor
>    queue : equal_restrictor
>    priority queue : holder_restrictor

None of these container adapters inherit from anything, and much more
than just the comparision operations need to be performed on the
containers these adapters use.

>    reverse_bidirectional_iterator : equal_restrictor (Note: operator<
>    is defined differently than defined by less_restrictor)
>    random_access_iterator : equal_restrictor
>    insert_iterator: holder_restrictor

Restricting the iterator bases used by these iterator adaptors would
prevent value_type() and difference_type() from working with
the classes produced by these adapters.

>1.2 raw_storage_iterator derives from output_iterator and
>    restrictor<OutputIterator>.  Both have global template functions
>    for == and <.  This creates an ambiguity that need never exist if
>    restrictor were replaced by holder_restrictor.  See also 1.3 for a
>    general problem with output_iterators having == and < derived from
>    empty.

Output iterators aren't required to have == and < defined.

>1.3 operators == and < for the base class empty will be redefined in
>    completely different ways for derived iterator classes.

So?  Remeber that iterator bases only exist to make defining
value_type(T *) and distance_type(T *) easier.  They aren't ment to
provide operations.

>Not only will they be redefined for the various iterators, but for
>some iterators one or both need not be defined at all according to the
>Tables (but will be defined according to derivation from empty.)

Need not doesn't mean shall not.

>2. set containers should be renamed to something like ordered_set.
>
>Similarly for multiset, map, and multimap.  The non-``ordered_'' names
>should be reserved for the appropriate containers based on equivalence
>relations (not order relations).  (Otherwise, we will have amazing
>names like unordered_set.)

Actually, they're called sequences in STL.  Wrap them in with an
adaptor to make them look the way you want.

>3. It would be nice if the spec explicitly defined unordered set
>   multiset, map and multimap.

I don't see the point, for speed you really, really want to have an
ordering between objects in an associated container, even if you're
otherwise uninterested in the ordering of the objects.  Otherwise
just use one of the sequences.

>These could allow for possible implementation by hashing.

If you can hash an object then you can order the object.

>4. I don't think set (or multiset) should bother with a key_type.

No, all associative containters are required to have both and
there is no need to split associative into two different classes
of containers.

>With this scheme, map would also have map operations (find, count,
>lower_bound, upper_bound, equal_range) that take value_type& as an
>argument.

No, map is provides a one way mapping.  A two way mapping is different
container with a significantly different implentation (and more
importantly cost).

>5. (Ordered) set should not have the type set::iterator.  The
>   functions set::find, lower_bound, and upper_bound should return a
>   set::constant_iterator.

I don't how requiring the user to type const_iterator instead
of iterator would be useful.

>There is clearly a contradiction between the X::iterator row of Table
>8 and the use of set::iterator in Section 9.2.1.  set::iterator is a
>constant_iterator and will therefore point to a const T instead of to
>a T as required by the table.

Yah, but this is minor.

>7. Putting compare arguments in associative container constructors
>   eliminates opportunities for inlining comparisons.  All members
>   will have to use the run-time stored comparison objects rather than
>   the compile-time-known template argument functions.

This isn't true.  Read section 7, Function objects, and examine
the definition of template less<T>, the default comparision
object type.

>8. I know the term for the action of Binders as Curry.  This could
>   just be my problem, but if not, Curry might at least mentioned in
>   the documentation, if not used in the class name.

Maybe in the paper, but I don't think this is necessary in the standard.

>11. ... However Table 10 explicitly specifies a sequence's a.front(),
>a.back(), a[n] to return references.  This somewhat restricts options
>for implementing sequences.

This is so you can assign to the return values.

>Demanding that references be returned weighs against sequence-like
>things that would more naturally return objects on the stack.  It is
>much harder to efficiently use a different internal representation for
>the stored object (maybe the sequence stores raw data (not object
>copies) in an array or communicates with an external data store, or
>whatever).

I think these are outside the scope of STL, but see the
specialization of vector<bool> which returns object of type
vector<bool>::reference instead of bool & for these operations.

>12. From the text alone, I couldn't deduce anything in particular
>    about what *a=t is required to do.  Did I miss something and, if
>    not, is it OK (I tend to think it is OK - but also see comment
>    13)?

It means exactly what it says, if "a" is a non-input iterator and "t"
is it's value_type then "*a = t" must work, that is the value of T must
be copied into the location pointed to by a.
 See the definition of back_insert_iterator for one implementation, the
definition of vector<T>::iterator, "typedef T *iterator;", is another.

>Also, Section 12.2.2 states that
>       while (first != last) *result++ = *first++
>``copies into a range.''  I think this is the only time that the word
>``copy'' is used with the *a=t construct.  This is just to note that
>the word ``copy'' might not be entirely appropriate.

Copy is the operation being performed here.  The values pointed to by first
are copied to the lvalues pointed to by result.

>13. Should there be some connnection between *a=t, ``insert a copy of
>    t'' (Table 9), ``inserts t'' (Table 11).  Something like:
>    inserting a t1 followed by assigning from a t2 is equivalent to
>    inserting a t2 directly?

The fact that:

 seq.insert(a, t1);
 *a = t2

is equivilent to:

 seq.insert(a, t2);

seems obvious to me.

>14. In Table 11 there are several mentions of ``inserts t.''  Should
>    this read ``inserts a copy of t'' (like Table 9)?

STL doesn't support putting anything but copies of objects in
containers.

>Table 7: Last line of next to last row -- replace ``then'' with
>``than.''

No.

>pg 21: This statement seems a bit strong: ``vector is the type of
>sequence that should be used by default.''

If any container will do then vector is by far the most efficient.

       Ross Ridge





Author: r-ridge@calum.csclub.uwaterloo.ca (Ross Ridge)
Date: Fri, 12 Aug 1994 03:32:04 GMT
Raw View
r-ridge@calum.csclub.uwaterloo.ca (Ross Ridge) writes:
>There is no change in semantics between the operations of empty and
>restrictor<T> and their base or derived classes.  Empty provides
>default comparision operations between classes without members and
>restrictor<T> removes all but the comparision operations from
>a class without changing any operations.

Doug Morgan <doug@deimos.ads.com> wrote:
>I should have been more explicit about what I meant by "changes in
>semantics."  I prefer specs that guarantee that if you have any
>reference (or pointer) to an object and perform a given operation, the
>same action happens.  This should be independent of the declared type
>of the reference.  This is not the case for classes inheriting from
>empty.  Say I have two references to a forward_iterator, one through
>forward_iterator& and one through empty&.  Executing separate =='s on
>these references results in completely different actions (answers).

First, don't confuse "forward_iterator" and "Forward Iterators".
forward_iterator<T> isn't an iterator, as it doesn't have ++ and *
defined for it.

Unless you try, the only way you're going to get a value of type empty
& is if you compare two objects that inherit from empty, and the
comparison done will be correct with respect to their emptiness.  I
don't know exacly why Alex has classes inherit from empty, but I don't
see it as problem.

>Forwarding nothing creates a class with a data member.  Such classes
>do have uses.

There are only two operations you do with such an encapsulated
object, construct it using it's copy contructor when you
create the restrictor and destroy it when you destroy the
restrictor.  You can't assign to it, you can get it's value,
you can't even compare it to anything.  It seems completely
useless to me.

>As for forwarding only ==, it doesn't matter that the
>class you are restricting supports <, what matters is that the class
>you are deriving is supposed to support < and is supposed to support
>it in a way that is compatible with the forwarded version.  For
>instance, reverse_bidirectional_iterator supports <, but in a
>completely different way than a forwarded version.  It is good to see
>that reverse_bidirectional_iterator properly does not inherit from
>restrictor.

I have no idea what you're talking about here.  I think you're
confused about what the template restrictor does.

>>>    stack : equal_restrictor
>>>    queue : equal_restrictor
>>>    priority queue : holder_restrictor
...
>Correct on both points.  However, the given restrictor inheritance
>would put exactly the needed data member and == on the derived
>classes.

Again I don't know what you're talking about.  Exactly
what changes would you make to definition of the template stack?

>Sorry, I didn't mean to imply that reverse_bidirectional_iterator
>would no longer also inherit from bidirectional_iterator, etc.  I just
>meant that the restrictors would be added to the list of bases.

I don't see the point of doing that.

>Exactly, however by inheriting from empty, output_iterators do have ==
>and < defined.  This is not correct and is what I am pointing out.

Not correct?

>Correct.  However, for instance, by inheriting from empty, there is no
>way that an output_iterator cannot have an associated == (and it's
>defined actions are likely to have nothing to do with the "contents"
>of the iterator).

There are any number of ways an Output iterator derived from
output_iterator<T> could not have == defined for it.

>>>Similarly for multiset, map, and multimap.  The non-``ordered_'' names
>>>should be reserved for the appropriate containers based on equivalence
>>>relations (not order relations).  (Otherwise, we will have amazing
>>>names like unordered_set.)
>>
>>Actually, they're called sequences in STL.  Wrap them in with an
>>adaptor to make them look the way you want.
>
>I don't follow.

template <class T, template <class U, class V> class sequence = vector
   template <class U> class A = allocator>
class unordered_set: public sequence<T, A> {
public:
 iterator find(T n) { return ::find(begin(), end(), n);
 size_type count(T n) {
  size_type cnt = 0;
  ::count(begin(), end(), n, cnt);
  return cnt;
 }
 iterator lower_bound(T n) {
  return ::find(begin(), end(), bind1st(less<T>(), n);
 }
};

>>I don't see the point, for speed you really, really want to have an
>>ordering between objects in an associated container, even if you're
>>otherwise uninterested in the ordering of the objects.  Otherwise
>>just use one of the sequences.
>
>No, sometimes for speedy insert and find I want a hashing
>implementation.

How do you propose to hash objects of unknown type?

>>If you can hash an object then you can order the object.
>
>Sure you can put some order on it, but, in general, that order will
>not be compatible with any equivalence relation that is compatible
>with the hash.  In other words, you can't simply convert a hash to an
>ordering and expect the ordering to properly distinguish distinct
>elements that hash to the same value.

No, but if you can generate hash value then you have an unhashed value
that does provide a total ordering.

>>No, map is provides a one way mapping.  A two way mapping is different
>>container with a significantly different implentation (and more
>>importantly cost).
>
>I never mentioned one way or two way mapping.  I'm saying that I'd
>like to see map with both operations like:
>
>iterator find(const key_type& x);
>and
>iterator find(const value_type& x);

So then is:

 iterator find(value_type const &x) { find(x.first); }

all you want here?

>>>7. Putting compare arguments in associative container constructors
>>>   eliminates opportunities for inlining comparisons.  All members
>>>   will have to use the run-time stored comparison objects rather than
>>>   the compile-time-known template argument functions.
>>
>>This isn't true.  Read section 7, Function objects, and examine
>>the definition of template less<T>, the default comparision
>>object type.

>No, this is true. Read the rows on constructors in Table 11.  If a user
>can place a comparison object at run-time into a container, it must be
>the case that that object will be stored and used for associative
>containers.

The fact that an object can be a member of a class doesn't
prevent inline member functions of the object's class from being
inlined.

>The Compare template argument for associative containers can only be
>used (consistently) as the default thing to store in an associative
>container.

No, less<T> not the default thing, it's the default type.

The rest of your article arrived mangled at this site.

       Ross Ridge





Author: doug@deimos.ads.com (Doug Morgan)
Date: 11 Aug 94 11:55:34
Raw View
In article <CuD1yG.72v@undergrad.math.uwaterloo.ca> r-ridge@calum.csclub.uwaterloo.ca (Ross Ridge) writes:
>Doug Morgan <doug@monet.ads.com> wrote:
>>I only recently subscribed to this group, so I'm just hoping this
>>posting is appropriate.  Here are some comments on the document:
>>
>>The Standard Template Library
>>Alexander Stepanov & Meng Lee
>>Doc No: X3J16/94-0095
>>        WG21/N0482
>>May 31, 1994
>
>I'm hardly an expert on STL, but I throw in my response in anyways.

I'm glad somebody responded.  From your comments, I see that I could
have been more clear with my comments.

>
>>1. Many uses of empty and restrictor seem like either strange uses or
>>   misuses of public inheritance.
>>
>>I don't like to see changes in semantics of an operation between a
>>base class and a derived class.  I also don't like seeing inheritance
>>place an operation on a derived class that doesn't belong there.
>
>There is no change in semantics between the operations of empty and
>restrictor<T> and their base or derived classes.  Empty provides
>default comparision operations between classes without members and
>restrictor<T> removes all but the comparision operations from
>a class without changing any operations.

I should have been more explicit about what I meant by "changes in
semantics."  I prefer specs that guarantee that if you have any
reference (or pointer) to an object and perform a given operation, the
same action happens.  This should be independent of the declared type
of the reference.  This is not the case for classes inheriting from
empty.  Say I have two references to a forward_iterator, one through
forward_iterator& and one through empty&.  Executing separate =='s on
these references results in completely different actions (answers).

To me, just providing a operation is not enough.  The provided
operation should either "do the right thing" or not be provided (by
inheritance) at all.

>>1.1 It seems arbitrary that there is just one restrictor class for
>>    holding an object and forwarding both == and <.  Why isn't there
>>    one for forwarding just == and one for forwarding nothing?
>
>Because == and < are the minimal set of operations needed for doing equality
>and inequality comparison operations on a object.  Forwarding nothing
>only creates a useless class and there isn't any point to forwarding
>== and not < if the class your restricting supports <.

Forwarding nothing creates a class with a data member.  Such classes
do have uses.  As for forwarding only ==, it doesn't matter that the
class you are restricting supports <, what matters is that the class
you are deriving is supposed to support < and is supposed to support
it in a way that is compatible with the forwarded version.  For
instance, reverse_bidirectional_iterator supports <, but in a
completely different way than a forwarded version.  It is good to see
that reverse_bidirectional_iterator properly does not inherit from
restrictor.

>>    With these restrictors, inheritance for adaptors would look like:
>>
>>    stack : equal_restrictor
>>    queue : equal_restrictor
>>    priority queue : holder_restrictor
>
>None of these container adapters inherit from anything, and much more
>than just the comparision operations need to be performed on the
>containers these adapters use.

Correct on both points.  However, the given restrictor inheritance
would put exactly the needed data member and == on the derived
classes.  If this is a poor use of inheritance, then I don't see why
using the currently defined restrictor for other classes is any better
(well, forwarding two operations could exceed a significance
threshold).

>>    reverse_bidirectional_iterator : equal_restrictor (Note: operator<
>>    is defined differently than defined by less_restrictor)
>>    random_access_iterator : equal_restrictor
>>    insert_iterator: holder_restrictor
>
>Restricting the iterator bases used by these iterator adaptors would
>prevent value_type() and difference_type() from working with
>the classes produced by these adapters.

Sorry, I didn't mean to imply that reverse_bidirectional_iterator
would no longer also inherit from bidirectional_iterator, etc.  I just
meant that the restrictors would be added to the list of bases.

>>1.2 raw_storage_iterator derives from output_iterator and
>>    restrictor<OutputIterator>.  Both have global template functions
>>    for == and <.  This creates an ambiguity that need never exist if
>>    restrictor were replaced by holder_restrictor.  See also 1.3 for a
>>    general problem with output_iterators having == and < derived from
>>    empty.
>
>Output iterators aren't required to have == and < defined.

Exactly, however by inheriting from empty, output_iterators do have ==
and < defined.  This is not correct and is what I am pointing out.

>
>>1.3 operators == and < for the base class empty will be redefined in
>>    completely different ways for derived iterator classes.
>
>So?  Remeber that iterator bases only exist to make defining
>value_type(T *) and distance_type(T *) easier.  They aren't ment to
>provide operations.

Then they shouldn't provide operations.  However, they do.  Again,
that is the thrust of my comments.  Sometimes the spec provides things
when they are not needed and some other times provides things that are
in fact incorrect.

>
>>Not only will they be redefined for the various iterators, but for
>>some iterators one or both need not be defined at all according to the
>>Tables (but will be defined according to derivation from empty.)
>
>Need not doesn't mean shall not.

Correct.  However, for instance, by inheriting from empty, there is no
way that an output_iterator cannot have an associated == (and it's
defined actions are likely to have nothing to do with the "contents"
of the iterator).

>>2. set containers should be renamed to something like ordered_set.
>>
>>Similarly for multiset, map, and multimap.  The non-``ordered_'' names
>>should be reserved for the appropriate containers based on equivalence
>>relations (not order relations).  (Otherwise, we will have amazing
>>names like unordered_set.)
>
>Actually, they're called sequences in STL.  Wrap them in with an
>adaptor to make them look the way you want.

I don't follow.

>>3. It would be nice if the spec explicitly defined unordered set
>>   multiset, map and multimap.
>
>I don't see the point, for speed you really, really want to have an
>ordering between objects in an associated container, even if you're
>otherwise uninterested in the ordering of the objects.  Otherwise
>just use one of the sequences.

No, sometimes for speedy insert and find I want a hashing
implementation.  For small sets and simple comparison operations, I
might also just want an comparison with all all (unordered) stored
elements.

>>These could allow for possible implementation by hashing.
>
>If you can hash an object then you can order the object.

Sure you can put some order on it, but, in general, that order will
not be compatible with any equivalence relation that is compatible
with the hash.  In other words, you can't simply convert a hash to an
ordering and expect the ordering to properly distinguish distinct
elements that hash to the same value.

>>4. I don't think set (or multiset) should bother with a key_type.
>
>No, all associative containters are required to have both and
>there is no need to split associative into two different classes
>of containers.



Author: doug@deimos.ads.com (Doug Morgan)
Date: 12 Aug 94 10:23:13
Raw View
In article <DOUG.94Aug11115534@deimos.ads.com> doug@deimos.ads.com (Doug Morgan) writes:
:In article <CuD1yG.72v@undergrad.math.uwaterloo.ca> r-ridge@calum.csclub.uwaterloo.ca (Ross Ridge) writes:
:>Doug Morgan <doug@monet.ads.com> wrote:
:>>7. Putting compare arguments in associative container constructors
:>>   eliminates opportunities for inlining comparisons.  All members
:>>   will have to use the run-time stored comparison objects rather than
:>>   the compile-time-known template argument functions.
:>
:>This isn't true.  Read section 7, Function objects, and examine
:>the definition of template less<T>, the default comparision
:>object type.
:
:No, this is true.  Read the rows on constructors in Table 11.  If a
:user can place a comparison object at run-time into a container, it
:must be the case that that object will be stored and used for
:associative containers.  The Compare template argument for associative
:containers can only be used (consistently) as the default thing to
:store in an associative container.  It cannot be used (consistently)
:for expanding efficient inline code for an associative container.
:(Section 7's example with transform is irrelevant to this aspect of
:associative container.)

My conclusion about loss of efficiency is wrong.  Nearly maximal
efficiency could be obtained by an implementation that stored a flag
denoting whether a non-default Compare was used to construct the
associative container.  Operations could then use the flag to branch
either to code using (potentially) inlined default Compares or to code
using explicit calls to compare objects.

Doug




Author: doug@monet.ads.com (Doug Morgan)
Date: 9 Aug 94 17:08:19
Raw View
I only recently subscribed to this group, so I'm just hoping this
posting is appropriate.  Here are some comments on the document:

The Standard Template Library
Alexander Stepanov & Meng Lee
Doc No: X3J16/94-0095
        WG21/N0482
May 31, 1994

(from ftp.cygnus.com:pub/stl.ps.gz)

I am a big fan of STL's definition of iterators and of its general
layout.  However, I see a few rough edges and minor inconsistencies.
As this document (or something like it) seems to have been accepted by
some standards group, perhaps comments are too late.  But, perhaps
not.

1. Many uses of empty and restrictor seem like either strange uses or
   misuses of public inheritance.

I don't like to see changes in semantics of an operation between a
base class and a derived class.  I also don't like seeing inheritance
place an operation on a derived class that doesn't belong there.

1.1 It seems arbitrary that there is just one restrictor class for
    holding an object and forwarding both == and <.  Why isn't there
    one for forwarding just == and one for forwarding nothing?  If
    these aren't reasonable, then why should the given restrictor be
    reasonable?  If these other restrictors existed, most adaptors
    could have a restrictor base class.  Maybe the name restrictor
    could even be changed to some kind of adaptor.  There could be:

    template <class T> holder_restrictor {...};
    that just provides a value member.

    template <class T> equal_restrictor : public holder_restrictor {...};
    this would add operator==

    template <class T> less_restrictor : public equal_restrictor {...};
    this would add operator< (this is the current unadorned
    ``restrictor'')

    With these restrictors, inheritance for adaptors would look like:

    stack : equal_restrictor
    queue : equal_restrictor
    priority queue : holder_restrictor
    reverse_bidirectional_iterator : equal_restrictor (Note: operator<
    is defined differently than defined by less_restrictor)
    random_access_iterator : equal_restrictor
    insert_iterator: holder_restrictor

    I doubt that restrictors would be good bases for
    back_insert_iterator or front_insert_iterator.

1.2 raw_storage_iterator derives from output_iterator and
    restrictor<OutputIterator>.  Both have global template functions
    for == and <.  This creates an ambiguity that need never exist if
    restrictor were replaced by holder_restrictor.  See also 1.3 for a
    general problem with output_iterators having == and < derived from
    empty.

1.3 operators == and < for the base class empty will be redefined in
    completely different ways for derived iterator classes.  Not only
    will they be redefined for the various iterators, but for some
    iterators one or both need not be defined at all according to the
    Tables (but will be defined according to derivation from empty.)

Also, do the given == and < operators make sense for unary_function
and binary_function?  I imagine that might, but am not sure.

2. set containers should be renamed to something like ordered_set.

Similarly for multiset, map, and multimap.  The non-``ordered_'' names
should be reserved for the appropriate containers based on equivalence
relations (not order relations).  (Otherwise, we will have amazing
names like unordered_set.)

3. It would be nice if the spec explicitly defined unordered set
   multiset, map and multimap.  These could allow for possible
   implementation by hashing.

Template arguments for Equal_to (and possibly Hash) would replace
Compare.

4. I don't think set (or multiset) should bother with a key_type.

(Ordered) set can be (and I think should be) defined with just an
ordered value_type.  Then, map can be defined (as though it inherited
from set) to add a key_type.  With this scheme, map would also have
map operations (find, count, lower_bound, upper_bound, equal_range)
that take value_type& as an argument.  Such operations are currently
missing from map (to the detriment, I think, of map).  For maps,
value_compare could be still be developed from key_compare.

5. (Ordered) set should not have the type set::iterator.  The
   functions set::find, lower_bound, and upper_bound should return a
   set::constant_iterator.

There is clearly a contradiction between the X::iterator row of Table
8 and the use of set::iterator in Section 9.2.1.  set::iterator is a
constant_iterator and will therefore point to a const T instead of to
a T as required by the table.  (A similar comment holds for multiset.)

6. It seems like there should be adaptors for turning a map into a
   unary function (or an operator() might be directly defined on map.)
   If so, there is a question of what to do with keys that don't
   currently exist in the map.  The action of operator [] is not OK,
   since it mutates the map.  Perhaps operator() could be an alias for
   find?  Perhaps several kinds of function adaptors could be defined:

   O return an iterator (just like find)
   O return the address of a dereferenced iterator or null pointer
   O return a dereferenced iterator or a default value.

7. Putting compare arguments in associative container constructors
   eliminates opportunities for inlining comparisons.  All members
   will have to use the run-time stored comparison objects rather than
   the compile-time-known template argument functions.  This may have
   been an intentional tradeoff, but I'm not convinced that the gain
   in flexibility is worth the loss in efficiency.

8. I know the term for the action of Binders as Curry.  This could
   just be my problem, but if not, Curry might at least mentioned in
   the documentation, if not used in the class name.

9. In the class pair, I would like to have typedefs for first_value
   and second_value.

These could sometimes be used to simplify template argument lists (the
list would mention just the pair and the element types would later be
extracted from the pair itself).

10. Inheritance could be used to structure the iterator tags and
    iterator bases.  This is certainly not necessary (the way given in
    the spec is workable), but I recommend it to make iterator
    relationships clear from the code and to automatically generate a
    larger number of efficient templates.

Below, I show what I meam by using inheritance to structure iterator
tags and bases.  (Also, as noted elsewhere, using empty as a base for
iterators is, to me, an abuse of inheritance.)  Besides being clearer
(to me at least) using inheritance could reduce the number of template
functions that a user (or library developer) would have to write to
make a full set of highest efficiency algorithms.  With inheritance,
an algorithm expansion can be written for one iterator tag and the
expansion will be automatically used for every derived tag (until
overridden).  Without inheritance, the same expansion has to be
manually arranged for each more specialized tag.  For instance, on
page 14, the definitions of value_type for four iterator classes could
be generated with just one template defined for input_iterator.

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag, output_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

template <class T, class Distance = prtdiff_t>
struct input_iterator : input_iterator_tag {};
struct output_iterator : output_iterator_tag {};
template <class T, class Distance = prtdiff_t>
struct forward_iterator : forward_iterator_tag,
       input_iterator<T, Distance>, output_iterator<T, Distance> {};
template <class T, class Distance = prtdiff_t>
struct bidirectional_iterator :  bidirectional_iterator_tag,
       forward_iterator<T, Distance> {};
template <class T, class Distance = prtdiff_t>
struct random_access_iterator : random_access_iterator_tag,
       bidirectional_iterator<T, Distance> {};

11. The spec is says that *copies* of objects are to be inserted into
    sequences.  It is more flexible on what comes out (usually
    something convertible to a T).  However Table 10 explicitly
    specifies a sequence's a.front(), a.back(), a[n] to return
    references.  This somewhat restricts options for implementing
    sequences.

Demanding that references be returned weighs against sequence-like
things that would more naturally return objects on the stack.  It is
much harder to efficiently use a different internal representation for
the stored object (maybe the sequence stores raw data (not object
copies) in an array or communicates with an external data store, or
whatever).

12. From the text alone, I couldn't deduce anything in particular
    about what *a=t is required to do.  Did I miss something and, if
    not, is it OK (I tend to think it is OK - but also see comment
    13)?

Also, Section 12.2.2 states that
       while (first != last) *result++ = *first++
``copies into a range.''  I think this is the only time that the word
``copy'' is used with the *a=t construct.  This is just to note that
the word ``copy'' might not be entirely appropriate.

13. Should there be some connnection between *a=t, ``insert a copy of
    t'' (Table 9), ``inserts t'' (Table 11).  Something like:
    inserting a t1 followed by assigning from a t2 is equivalent to
    inserting a t2 directly?

14. In Table 11 there are several mentions of ``inserts t.''  Should
    this read ``inserts a copy of t'' (like Table 9)?

15. Errata/quibbles:

Table 3: Shouldn't a = t and X(a) = t be *a = t and *X(a) = t?

pg 12: inline_random_access_iterator_tag iterator_category(T*)) {
is missing a const:                                       ^^
       inline_random_access_iterator_tag iterator_category(const T*)) {

Table 7: Last line of next to last row -- replace ``then'' with
``than.''

pg 20: Next to last paragraph --- semicolons would be nice in this
list of lists.

pg 21: This statement seems a bit strong: ``vector is the type of
sequence that should be used by default.''

pg 21: A ``that'' is missing in: ``vector is a kind of sequence *that*
supports....''

Doug
--------------------------------------------------------------------
Doug Morgan, doug@ads.com, (415) 960-7444
Advanced Decision Systems (a division of Booz-Allen & Hamilton Inc.)
1500 Plymouth St., Mountain View, CA 94043-1230
--------------------------------------------------------------------