John E. Potter wrote:
>
> Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
> : John E. Potter wrote:
>
> : > Let r be a thing of the type
> : > returned by front() or *iterator and t of type T.  Given the requirements
> : > for use of T (tables 30 and 65) in a container and ignoring const, there
> : > are six valid uses for r.
> : >   1.  T(r)
> : >   2.  t = r
> : >   3.  r = t
> : >   4.  r1 = r2
> : >   5.  T* p = &r
> : >   6.  r.~T()  ( should this be (&r)->~T() ? )
> : > I would think that a convertable to T would satisfy only the first two.
> : > A T& clearly satisfies all six.
>
> : I'm not so sure about 5 and 6 since I couldn't find any requirement that
> : the value type of an iterator be copy-constructible.
>
> It is an assumption for iter_swap.

Which only means that an iterator can't be used with iter_swap if its
value type isn't copy-constructible. ( BTW, where are the requirements
for iter_swap? ) In fact, with the current requirements it is IMO
possible to create an iterator for which you can't do anything of the
above even if operator* returns T&. I'm not sure if this is a good
idea, though.

>
> : BTW, paragraph 3 of
> : secion 23.1 says:
> : "The type of objects stored in these components must meet the
> : requirements of CopyConstructible types, and the additional requirements
> : of Assignable types."
> : What does the word "components" refer to? Containers in general or just
> : the standard library containers? It seems to mean the latter in Table
> : 64.
>
> I agree with your reading.  "Components" is used as elements of the
> standard library.  But, I do not understand why it is important to you.

Just curious :-) It is IMO interesting that the standard seems to allow
Containers of objects with copy constructor, destructor, assignment
operator and operator& all declared private.
Really, my point is that a generic algorithm can't rely on e.g.
&(*iterator) being availble even if iterators are required to return
true references. With this in mind, it is unclear to me what
iterator_traits<T>::pointer is good for.

> I have found the workarounds for my compiler and have the Virtual Array
> working with sort and many other algorithms.
> [...]
> I found nothing that would give a performance hit for
> containers of objects at runtime.  There could be some compile time
> cost, I think.

There is obviously a significant performance hit if the compiler isn't
able to optimize away the temporary references. OTOH, would something
like this solve the problem?

class iterator {
  mutable reference ref;
  reference& operator*() const { return ref; }
};

IMO, this doesn't create temporaries unless necessary and is equivalent
to returning the reference by value. Does this cause any problems if
the iterator itself is a temporary? ( I don't think so but I'm not sure
).


Bye

Roman
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
: John E. Potter wrote:

: > Let r be a thing of the type
: > returned by front() or *iterator and t of type T.  Given the requirements
: > for use of T (tables 30 and 65) in a container and ignoring const, there
: > are six valid uses for r.
: >   1.  T(r)
: >   2.  t = r
: >   3.  r = t
: >   4.  r1 = r2
: >   5.  T* p = &r
: >   6.  r.~T()  ( should this be (&r)->~T() ? )
: > I would think that a convertable to T would satisfy only the first two.
: > A T& clearly satisfies all six.

: I'm not so sure about 5 and 6 since I couldn't find any requirement that
: the value type of an iterator be copy-constructible.

It is an assumption for iter_swap.

: BTW, paragraph 3 of
: secion 23.1 says:
: "The type of objects stored in these components must meet the
: requirements of CopyConstructible types, and the additional requirements
: of Assignable types."
: What does the word "components" refer to? Containers in general or just
: the standard library containers? It seems to mean the latter in Table
: 64.

I agree with your reading.  "Components" is used as elements of the
standard library.  But, I do not understand why it is important to you.
I see the library as a framework of algorithms.  To use the algorithms,
I must provide iterators over containers like those in the library.  If
I follow those guidelines, things should work.

: > There may be another overriding problem.  The reference class acts
: > like a reference; however, unlike a true reference, there can be a
: > reference to a reference class.  Consider the swap template when
: > used with two reference class objects.  They are passed by reference,
: > and the temp is a copy of one of the reference objects.  The two
: > assignments modify referents, but the first destroys the referent
: > of the temp.  Anyone have a solution for this one?

: Well, there is the iter_swap template. swap is for "real" objects only,
: I believe. OTOH, if something like iterator_traits was availble for
: references :-)
: BTW, shouldn't it be iter_swap instead of swap in the "Effects" sections
: of swap_ranges and reverse?

Yes, it should be and is in the code.

I have found the workarounds for my compiler and have the Virtual Array
working with sort and many other algorithms.  In the process, I have
gained a much greater appreciation for the elegance of the STL.  It was
carefully crafted to allow the use of reference classes throughout.  It
may be a much more difficult task for the committee to give the
requirements in a way that requires a compliant implementation to
support them.  I found nothing that would give a performance hit for
containers of objects at runtime.  There could be some compile time
cost, I think.

John
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

jpotter@falcon.lhup.edu (John E. Potter) writes:

|>   /2 reference is a class that simulates the behavior of references
|>   of a single bit in vector<bool>.
|>
|>  The assignment is now what you knew it must be.  The default constructor
|>  is private.  There must obviously be another private constructor for the
|>  vector to use.  Private parts are generally omitted.  The copy ctor is
|>  the default public one.  I expected it to be private also.

Why.  If you have a private copy constructor, you cannot return
instances of the class from a function.  That seems like giving up too
much to me.  (Note that you *can* copy construct references.  And that
the semantics of reference copy construction are *not* the same as
assignment.)

|>  I guess that
|>  there should also be operator& private to prevent address of.  Thoughts?

Alternatively, it might return a vector< bool >::iterator.  If the class
is supposed to simulate a reference, and the iterators are more or less
pointers, this would be roughly the equivalent of real references and
pointers.  (I'm not sure that the analogy should be taken that far, but
I do think the idea worthy of consideration.)

|>  : Another question is: should reference classes provide additional member
|>  : functions like vector<bool>::reference::flip? This depends on
|>  : expectations of the clients which will be influenced by the standard.
|>  : The point is, reference classes have non-trivial semantics. It would be
|>  : nice if these semantics were specified in the standard, at least by
|>  : example.
|>
|>  And should it be flip?  Since the vector has a flip member to flip all
|>  bits, it is consistent.  It could also have been operator^=.
|>
|>   bool b;
|>   vector<bool> vb;
|>   b ^= true;
|>   vb[5].flip();  // vb[5] ^= true ???
|>
|>  Specific references like this one can provide specific actions, but in
|>  general, it is difficult to support operations other than assignment.
|>  I see your point in flip setting a precedent.  Would the user above be
|>  happy with
|>
|>   b = ! b;
|>   vb[5] = ! vb[5];

What would you normally write if vb were "bool[ n ]"?  Off hand,
anything but the above seems too artificial.

There is the question of optimization.  For "bool[ n ]", it will depend
on the machine as to which form is faster, but once the helper class is
involved...  Still, I would prefer leaving the optimization to the
compiler; if the case is frequent enough, compiler writers should be
able to recognize it and generate the same code in both cases.
(Personally, I have my doubts as to whether it is that frequent.  I
cannot remember off hand ever having to flip boolean values.  Most of
the time, I am setting them to a constant, either true or false.  And I
hope that the compiler writers do recognize and optimize that case.)

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

"Nicolas Chapados" <chapados@nortel.ca> wrote:

>What's wrong with vector<char> or vector<int> for the unpacked version?
>Simply
>typedef it to give it a more explicit name.

A char is not a bool, nor is an int:

void func(char c) { cout << "ASCII value " << int(c) << endl; }
void func(bool b) { cout << "bool value " << (b ? "T" : "F") << endl;}

int main()
{
  typedef char unpacked_bool;
  vector<unpacked_bool> v(10, false);
  func(v[0]);
  // ...

The above program prints out "ASCII value 0", not "bool value F".
It gets worse:

  void g(bool& b);
  g(v[1]);   // Illegal v[1] is not a bool&. No conversions allowed.
  bool *p = &v[2];  // Nope, no conversion from char* to bool*

The "proper" work-around is to create an unpacked_bool class with
conversions to/from all integral types as well as a conversion to bool&
and from bool. It is a pain in the neck and somewhat error prone. I
doubt every situation would be covered, even so. The approach is almost
identical to attempts to simulate bool using a class on compilers that
don't support a bool type yet. We know that such efforts can never quite
achieve the semantics of the built-in type.


-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kanze wrote:
>
> [about reference classes]
>
> Well, they are obviously useful for disk based containers.  By allowing
> them, you automatically make all of the STL algorithms work for data on
> disk.
>
> Whether this is a good idea or not, I don't know.  The time factors of
> disk access are significantly different than those of main memory, and
> it is probably that the specified time constraints of the algorithms
> would not hold.  Typically, the best algorithms for disk based data are
> NOT the same as those for memory based data.

Most of the algorithms for disk based data can be made to work with
iterators, however. In fact, to me the interfaces and requirements
defined by the STL are even more important than its algorithms and
containers. While I probably wouldn't use most of the standard
algorithms with disk based data I'd like to integrate the ones I do use
as neatly as possible with the standard library.

> I think that the authors of STL are to be congratulated on just how
> general they have managed to make the library without sacrificing
> performance.  It is necessary, however, to take into consideration the
> underlying unstated assumptions they made.  In particular, the STL
> time constraints are based on the premice that a simple access is
> constant time (O(k)), always the same constant time, and in fact, always
> so small as to be negligible, at least when compared to the operations
> effected on the accessed data.  This is not true for data on disk and it
> is not true for packed objects in memory.

This is probably true for the original STL ( even though it did include
stream iterators for which no guarantees can be made about the access
time ) but I can't find any time constraints on the algorithms in the
FCD. Only the number of the performed operations is specified. In fact,
IMO this change has been necessary precisely because of the unknown
access time.

Bye

Roman
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

herbs@cntc.com (Herb Sutter) writes:

|>  >I think that the authors of STL are to be congratulated on just how
|>  >general they have managed to make the library without sacrificing
|>  >performance.  It is necessary, however, to take into consideration the
|>  >underlying unstated assumptions they made.  In particular, the STL
|>  >time constraints are based on the premice that a simple access is
|>  >constant time (O(k)), always the same constant time, and in fact, always
|>  >so small as to be negligible, at least when compared to the operations
|>  >effected on the accessed data.  This is not true for data on disk and it
|>  >is not true for packed objects in memory.
|>
|>  This is a very good summary.  I'd only add that in both cases it doesn't
|>  usually make sense to have a true reference to (practically equivalent of
|>  taking the address of) a contained object either, since it may either not
|>  be in memory at all (if on disk) or not be addressable (if it's a single
|>  bit, unless you're on a machine that has bit-resolution pointers).

Correct.  Addesses/references to such objects are either impossible
(individual bits) or incredibly dangerous (objects which will be swapped
in and out from a disk).

My point was slightly different.  In both cases, it would not be to
difficult to specify the STL in such a way that it could be used with
iterators whose operator* returned a helper class instead of a pointer.
My point, however, was that this really doesn't gain much, because with
such objects, you also want to use a different algorithm or a different
data structure.  The function find, on a bit vector, for example, will
probably want to start by looking for the first BYTE in the vector that
is not ~0 or 0 (depending on the search value); this can easily result
in a magnitude of spead difference.  And a `set' or `map' of data on
disk should definitely use some variant of a B-tree, rather than a
balanced tree -- here we could easily be talking about several
magnitudes of speed improvement.

So my real point is that there is no point in trying to add this extra
flexibility to STL.

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze wrote:
>
> jpotter@falcon.lhup.edu (John E. Potter) writes:
>
> |>   /2 reference is a class that simulates the behavior of references
> |>   of a single bit in vector<bool>.
> |>
>
> |>  I guess that
> |>  there should also be operator& private to prevent address of.  Thoughts?
>
> Alternatively, it might return a vector< bool >::iterator.  If the class
> is supposed to simulate a reference, and the iterators are more or less
> pointers, this would be roughly the equivalent of real references and
> pointers.  (I'm not sure that the analogy should be taken that far, but
> I do think the idea worthy of consideration.)
>

But then I'd expect operator& of vector<bool>::const_reference to return
a const_iterator. Since const_reference is typedef'ed as bool this is
impossible. This is an interesting idea for containers in which both
reference and const_reference are classes, however.
A related question: should operator-> be provided for iterators that use
reference classes and what should it return? A pointer to reference,
perhaps? It could be implemented like this:

class iterator
{
  mutable reference ref;
  ...
  reference* operator->() const { return &ref; }
};

Any comments?

Bye

Roman
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Joe Buck (jbuck@Synopsys.COM) wrote:

  [ how to allow stack<bool, vector<bool> > ]

: jpotter@falcon.lhup.edu (John E. Potter) writes:
: >question.  The requirements in the FCD and in the original HP
: >documentation are not the same.  Do you know when they changed?  Was
: >it a conscious effort to eliminate reference classes?  Or was it just
: >a change of form (T& is shorter than convertable to T) which
: >accidentally changed the semantics?
:
: It has to be "convertable to T", as any other version disallows
: containers that use helper objects for references.  But it also
: has to be "assignable by T" for some uses.

Yes, I see the point, convertable to T may be too weak, and T& may be
too strong.  I could not find a definition of convertable to T or lvalue
of T as used in container::reference.  Let r be a thing of the type
returned by front() or *iterator and t of type T.  Given the requirements
for use of T (tables 30 and 65) in a container and ignoring const, there
are six valid uses for r.
  1.  T(r)
  2.  t = r
  3.  r = t
  4.  r1 = r2
  5.  T* p = &r
  6.  r.~T()  ( should this be (&r)->~T() ? )
I would think that a convertable to T would satisfy only the first two.
A T& clearly satisfies all six.  vector<bool>::reference satisfies the
first four.  Requirements 5 and 6 on T are needed to implement the
container; however, I am not so sure of them on r.  Use of 6 would
likely lead to undefined behavior when the destructed object was
destroyed again by the container which owns it.  There is not much
value in 5 since the only valid use of p would be (*p) in the place
of r in these six.

There may be another overriding problem.  The reference class acts
like a reference; however, unlike a true reference, there can be a
reference to a reference class.  Consider the swap template when
used with two reference class objects.  They are passed by reference,
and the temp is a copy of one of the reference objects.  The two
assignments modify referents, but the first destroys the referent
of the temp.  Anyone have a solution for this one?

No answers here, but maybe a clearer statement of the question.  Will
there be a vector<bool> or a bit_vector?  Will it be the model for a
container using reference classes fitting into the model of the standard
containers, iterators, and algorithms?

John
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

John E. Potter wrote:
>
> Joe Buck (jbuck@Synopsys.COM) wrote:
>
>   [ how to allow stack<bool, vector<bool> > ]
>
> : jpotter@falcon.lhup.edu (John E. Potter) writes:
> : >question.  The requirements in the FCD and in the original HP
> : >documentation are not the same.  Do you know when they changed?  Was
> : >it a conscious effort to eliminate reference classes?  Or was it just
> : >a change of form (T& is shorter than convertable to T) which
> : >accidentally changed the semantics?
> :
> : It has to be "convertable to T", as any other version disallows
> : containers that use helper objects for references.  But it also
> : has to be "assignable by T" for some uses.
>
> Yes, I see the point, convertable to T may be too weak, and T& may be
> too strong.  I could not find a definition of convertable to T or lvalue
> of T as used in container::reference.  Let r be a thing of the type
> returned by front() or *iterator and t of type T.  Given the requirements
> for use of T (tables 30 and 65) in a container and ignoring const, there
> are six valid uses for r.
>   1.  T(r)
>   2.  t = r
>   3.  r = t
>   4.  r1 = r2
>   5.  T* p = &r
>   6.  r.~T()  ( should this be (&r)->~T() ? )
> I would think that a convertable to T would satisfy only the first two.
> A T& clearly satisfies all six.

I'm not so sure about 5 and 6 since I couldn't find any requirement that
the value type of an iterator be copy-constructible. BTW, paragraph 3 of
secion 23.1 says:
"The type of objects stored in these components must meet the
requirements of CopyConstructible types, and the additional requirements
of Assignable types."
What does the word "components" refer to? Containers in general or just
the standard library containers? It seems to mean the latter in Table
64.

> There may be another overriding problem.  The reference class acts
> like a reference; however, unlike a true reference, there can be a
> reference to a reference class.  Consider the swap template when
> used with two reference class objects.  They are passed by reference,
> and the temp is a copy of one of the reference objects.  The two
> assignments modify referents, but the first destroys the referent
> of the temp.  Anyone have a solution for this one?

Well, there is the iter_swap template. swap is for "real" objects only,
I believe. OTOH, if something like iterator_traits was availble for
references :-)
BTW, shouldn't it be iter_swap instead of swap in the "Effects" sections
of swap_ranges and reverse?

Bye

Roman
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
: James Kanze wrote:

: > jpotter@falcon.lhup.edu (John E. Potter) writes:
: > |>   /2 reference is a class that simulates the behavior of references
: > |>   of a single bit in vector<bool>.

: > |>  I guess that
: > |>  there should also be operator& private to prevent address of.

: > Alternatively, it might return a vector< bool >::iterator.

: A related question: should operator-> be provided for iterators that use
: reference classes and what should it return? A pointer to reference,
: perhaps? It could be implemented like this:

: class iterator
: {
:   mutable reference ref;
:   ...
:   reference* operator->() const { return &ref; }
: };

: Any comments?

Sounds perfect.

   (*it).flip()
   it->flip()

Oops.  We made reference::operator& () return an iterator.  g++ is in an
infinite loop trying to compile this one.  Is there a portable way to
write this?

John
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

jpotter@falcon.lhup.edu (John E. Potter) writes:

>Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
>: A related question: should operator-> be provided for iterators that use
>: reference classes and what should it return? A pointer to reference,
>: perhaps? It could be implemented like this:
>
>: class iterator
>: {
>:   mutable reference ref;
>:   ...
>:   reference* operator->() const { return &ref; }
>: };
>
>: Any comments?
>
>Sounds perfect.
>
>   (*it).flip()
>   it->flip()
>
>Oops.  We made reference::operator& () return an iterator.  g++ is in an
>infinite loop trying to compile this one.  Is there a portable way to
>write this?

Sure.  Just return `ref.address()' rather than `&ref', where
reference::address() is defined by

 reference * reference::address() { return this; }

If `iterator' is a friend of `reference', then you can make
reference::address() a private member function.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

ncm@best.com (Nathan Myers) writes:

>jpotter@falcon.lhup.edu (John E. Potter) writes:
>>Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
>>: Herb Sutter wrote:
>>: >
>>: > [ Discussion of vector<bool>::reference ]
>>: >
>>: > A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
>>: > standard library. :-)  However, there may be fixes I can't think of.
>
>>: IMHO, this would be a bad solution. A much better one would be to
>>: rewrite the requirements in a way that allows the usage of reference
>>: classes.
>
>This is in general impossible, because operator.() is not overloadable.

No, that doesn't follow.

The fact that operator.() is not overloadable makes it impossible
to write a generic template reference class that will work for any
type.  However, it's quite possible to write a reference (or "proxy")
class that will work for a particular type, e.g. `bool', and in fact
this has been done, often -- vector<bool>::reference is one such
example.

It would certainly be possible to rewrite the requirements for
containers and iterators in a way that allowed the usage of reference
or proxy classes such as these.  (Though I'm not saying it would
necessarily be easy.  Choosing the right generalization of the
properties of builtin references may be a hard task.)

>Precisely: vector<bool> is an example *in the Standard* of a container
>that is not a Container, for very good (if unfortunate) reasons.  This
>only means that vector<bool> is not suitable as an argument for templates
>(e.g. stack<>) that require a Container.

"only"?  I think the fact that vector<bool> is not a Container
may prove quite inconvenient.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

jpotter@falcon.lhup.edu (John E. Potter) wrote:
>I should also note that the vector<bool> is not in bvector.h
>in either HP, GNU, or SGI.  It is bit_vector, a non-template class
>which implements the vector<bool> of the draft.  The reason is that
>the compilers do not support partial template specialization.  It seems
>that this temporary solution would make everybody here happy if it
>became permenant.  In the Moscow SPARC STL, bvector.h contains either
>bit_vector or vector<bool> depending on the compiler support.

Yes, that would be fine with me, as long as it was documented that such a
bit_vector is not a container.

>If the standard eventually contains vector<bool> as in the FCD, would it
>be acceptable to use vector<bool> for space optimization and vector<int>
>for time optimization?  Not as nice as it could be, but I think we could
>get by with it.

(Or vector<char>.)  If it were possible to have a packed vector<bool>
container, I could live with this.  My main question is whether it is
possible to have a packed container at all without doing violence to the
container requirements in order to shoehorn it in.

---
Herb Sutter (herbs@cntc.com)

Current Network Technologies Corp.
3100 Ridgeway, Suite 42, Mississauga ON Canada L5L 5M5
Tel 416-805-9088  Fax 905-608-2611
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <32FA74B2.5FC@cs.tu-berlin.de>,
Roman Lechtchinsky  <wolfro@cs.tu-berlin.de> wrote:
>Herb Sutter wrote:
[snipping the paragraphs on references]
>
>> Aside: It seems anachronistic to hear some argue that you 'almost always'
>> want to save 7 bits of space per bool at the expense of addressing overhead
>> and temporary reference objects, at a time when memory is less than $5 per
>> MB. ;-)  If you were creating vectors of tens of thousands of bools, okay,
>> you could save 10K or 20K... but does anyone really want to do that? and
>
>Oh-oh, then I must be really anachronistic :-) The embedded system I'm
>currently working on has 256K for the OS, program (>100K) and data. I
>can't afford to waiste even 1K and I have to do some complicated
>statistical computations. But that's a bad example. However, a
>mathematical application can easily use more than tens of thousands of
>bools, I think.
>
>> wouldn't any space benefit get swamped by the performance hit, since it'd
>> cost tens of thousands of temporaries every time you did a find<>()?
>> (Assuming the compiler couldn't optimise away the existence of the
>> temporary.)
>

Forgive a late joiner jumping in like this, but isn't this what
bitstring.h and, erm, the other bit vector class (forgot its name)
were made for?  Or are you using vector<bool> for its iterators?

I agree that the "memory is cheap" argument is specious though.
Many programs are light users of memory, but i can tell you that
even multi-megabyte machines can run short if your application is
memory intensive.  And "virtual memory" is merely a synonym for
"slow memory".

 -john
jgamble@ripco.com
February 28 1997: Last day libraries can order catalogue cards
from the Library of Congress.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

ncm@best.com (Nathan Myers)
: jpotter@falcon.lhup.edu (John E. Potter) writes:
: >Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
: >: Herb Sutter wrote:
: >: > [ Discussion of vector<bool>::reference ]
: >: > A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
: >: > standard library. :-)  However, there may be fixes I can't think of.
: >: IMHO, this would be a bad solution. A much better one would be to
: >: rewrite the requirements in a way that allows the usage of reference
: >: classes.

: This is in general impossible, because operator.() is not overloadable.
: (The idea has been discussed to death, in many guises.)

Understood.  But, I doubt that STL algorithms have use for operator..  And
no one is trying to reopen that debate ;-)

: >But, is it a standard container?  The requirements on a sequence
: >container require that C<T>::front() return a T&; however,
: >vector<bool>::front() returns a reference.  The requirements on a
: >container are that C<T>::reference be an lvalue of type T; however,
: >vector<bool>::reference is a class.  etc.  So, is this standard
: >container that fails to meet container requirements a standard
: >container?

: Precisely: vector<bool> is an example *in the Standard* of a container
: that is not a Container, for very good (if unfortunate) reasons.  This
: only means that vector<bool> is not suitable as an argument for templates
: (e.g. stack<>) that require a Container.

This is a very nice explanation.  I think everyone would be happy with it
if it concerned bit_vector and that was described as not a "Contianer".
But it concerns vector<bool> which is a specialization of vector.  It is
in the section on sequences, and is not accompanied by anything to say
that it is not one.  23.2.3.3[lib.stack] says, "Any sequence supporting
operations back(), push_back() and pop_back() can be used to instantiate
stack."  Those operations are supported by vector<bool>.  What am I
missing?

You have been there in the trenches, perhaps you can answer Roman's
question.  The requirements in the FCD and in the original HP
documentation are not the same.  Do you know when they changed?  Was
it a conscious effort to eliminate reference classes?  Or was it just
a change of form (T& is shorter than convertable to T) which
accidentally changed the semantics?  Given what I see as inconsistencies
in the iterator tables, I lean toward the latter, but am in no
position to make a conclusion.

Any enlightenment appreciated,
John
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Roman Lechtchinsky <wolfro@cs.tu-berlin.de> wrote:

>Herb Sutter wrote:
>>
>> On 29 Jan 1997 16:05:55 GMT, Roman Lechtchinsky <wolfro@cs.tu-berlin.de>
>> wrote:
>> >Herb Sutter wrote:
>> >> [ Discussion of vector<bool>::reference ]
>> >> A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
>> >> standard library. :-)  However, there may be fixes I can't think of.
>> >
>> >IMHO, this would be a bad solution. A much better one would be to
>> >rewrite the requirements in a way that allows the usage of reference
>> >classes.

[ deletia ]

>My point is more about iterators, however. Container requirements merely
>describe what the standard containers do; you don't have to meet them
>when implementing your own containers. But if you want to use any of the
>standard algorithms with them you have to meet the iterator
>requirements. Note that in the Jan 96 WP, for a forward iterator with
>the value type T operator*() has to return T& ( I'm still waiting for my
>copy of the Dec 96 WP; please correct me if this has changed ).

This has not changed.

>vector<bool>::iterator doesn't meet this requirement; thus, it is not a
>random access iterator or its value type cannot bool.
>Now, I agree that vector<bool> shouldn't use a packed representation (
>see below ).  However, IMHO a container with the semantics of
>vector<bool> should be in the standard or at least it should be possible
>to integrate such a container with the STL.

After reading some of this discussion, I have come to understand the
desire for allowing iterators that do not provide a way to get to the
address of a container element (e.g., databases, virtual arrays, packed
vectors, etc.). It also seems like a lot of code depends or wants to be
able to depend on the ability to get a reference or pointer into a
container. I think I have an idea for reconciling these desires:

PROPOSAL: An additional way of describing iterator and container
requirements

Background:

Currently, iterators requirements are described on two axis: iterator
category (input, output, forward, bidirectional and random access) and
mutability. Using vector as an example, it is desirable that the
following expressions work in intuitive ways:

  class myclass { public: void member(); /* ... */ };
  template <class T> void func(T&);

  vector<myclass> myvector;
  // ... insert stuff into myvector
  myvector[n].member();   // Assumes myvector[n] return myclass&
  func(myvector[n]);   // Assumes myvector[n] is convertible to myclass&
  sizeof(myvector[n]); // Assumed == sizeof(myclass)

  vector<myclass>::iterator myiter = myvector.begin();
  myiter->member();   // Assumes myiter->() returns non-const myclass*
  func(*myiter);   // Assumes *myiter is convertible to myclass&
  sizeof(*myiter); // Assumes == sizeof(myclass)

  vector<bool> mybits;
  func(mybits[n]); // Currently bad: mybits[n] not convertible to bool&
  sizeof(mybits[n]); // Currently unexpected: != sizeof(bool)
  vector<bool>::iterator mybititer = mybits.begin();
  func(*mybititer); // Currently bad: mybits[n] not convertible to bool&
  sizeof(*mybititer); // Currently unexpected: != sizeof(bool)

However, there are containers where the above code could not be made to
work and would not be expected to work. Even if vector<bool> were not
specialized, a packed bit-vector is a desirable class to have. If we
named it bitvector, and substituted bitvector for vector<bool>, you
would not necessarily expect the above code to work.

Solution:

My proposal, then is to add a new axis for describing iterators:
element-addressability.  An element-addressible iterator is one where
*iter returns a T&. An element-addressable container is one that has an
element-addressible iterator and which returns T& for operator[],
front(), back() and related functions.

Each standard algorithm would indicate whether element-addressibility is
a requirement for its inputs. A user-defined non-element-addressible
container/iterator pair could only be used with those algorithms that
don't require element-addressiblity. To keep things clean and minimize
changes from  the current draft, I would add the following:

* vector, deque, list, set, multiset, map and multimap and their
associated iterators are all element-addresssible.

* A new non-template container, bitvector, is a non-element-addressible
packed-bit vector. vector<bool> would not be a packed implementation.

* All of the standard algorithms that only require input or output
interators (but not forward, bidirectional or random access iterators)
would not require element-addressibility. (This is currently the case,
since input and output iterators are not currently required to be
element-addressible).

>
>I'd rather say that reference classes should
>
>a) meet the container::reference requirements if used by a container;
>b) meet the iterator::reference requirements if used by an iterator;
>c) provide an intuitive interface.
>
>If a) and/or b) are to be allowed then the standard should say what
>exactly a reference class should do.

Exactly, this would be one more thing needed in my proposal.

Unfortunately, I think this proposal constitutes a substantive change in
the draft standard. If we left the specialization of vector<bool> alone,
it might escape the substantive-change label, but I doubt it.

Any thoughts?

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

jpotter@falcon.lhup.edu (John E. Potter) writes:
>: Precisely: vector<bool> is an example *in the Standard* of a container
>: that is not a Container, for very good (if unfortunate) reasons.  This
>: only means that vector<bool> is not suitable as an argument for templates
>: (e.g. stack<>) that require a Container.

Actually this is an error in the specification of stack<>.  There's
a perfectly sensible way to make vector<bool> work with stack<>.
The problem is inconsistent requirements; in some places we specify
that a call returns something that works like a reference (but may
not be a reference); in other places we require a reference.

Let's consider SGI's implementation of STL, and see why there is a
problem with stack<bit_vector> (bit_vector can be thought of as
the implementation for vector<bool>).

(Note: I'm not positive that I have the latest SGI code).

For example, in SGI's implementation of bit_vector (which is really
vector<bool>) we have

template <class T, class Sequence = vector<T> >
class stack {
...
protected:
 Sequence c;
 ...
public:
 value_type& top() { return c.back();}
};

Now, in the case of vector<bool>, back() does not return a bool&.
It returns a vector<bool>::reference, a helper object that works
like a reference.  But this is the same as what vector<T> does:
it also returns a vector<T>::reference.  The difference is that
in the unspecialized case, vector<T>::reference is a typedef
for T&.

How to fix stack then?  As follows:

...
 Sequence::reference top() { return c.back();}

Voila!  stack now works!  All we require is that every container
define its reference type.  Many Container<T> classes will just
define it as T&.

>question.  The requirements in the FCD and in the original HP
>documentation are not the same.  Do you know when they changed?  Was
>it a conscious effort to eliminate reference classes?  Or was it just
>a change of form (T& is shorter than convertable to T) which
>accidentally changed the semantics?

It has to be "convertable to T", as any other version disallows
containers that use helper objects for references.  But it also
has to be "assignable by T" for some uses.



--
-- Joe Buck http://www.synopsys.com/pubs/research/people/jbuck.html

Help stamp out Internet spam: see http://www.vix.com/spam/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
: Actually, I would expect most of the current implementations to allow
: reference classes - how could they provide vector<bool> otherwise? Mine
: does. I'm sure that the HP implementation does, too - it doesn't even
: mention T& in the iterator requirements.

One bad note.  I am using g++2.7.2.  Now that I have found bit_vector
in bvector.h which shipped with it, I find that it can not compile it.
It handled my reference class but not its own.  Have not had time to
investigate.  I wonder if bit_vector is in the STL test suits?

Later,
John
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Herb Sutter (herbs@cntc.com) wrote:
: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) wrote:
: >jpotter@falcon.lhup.edu (John E. Potter) writes:
: >>I finally found vector<bool> in my g++ system.  It is in bvector.h; so,
: >>there is no forced space optimisation here.  <vector> does not include
: >>it.  If I #include <vector> then vector<bool> is a vector of whatever
: >>bool is.  If I want the space optimization, I can #include <bvector.h>.
: >
: >This is a really bad way for the user to indicate whether the space
: >optimization should be applied, since (a) it applies only on a
: >per-translation-unit basis, whereas the decision ought be made on a
: >more fine-grained basis, and (b) it is very easy to unknowningly
: >#include a header file that #includes some other header file that
: >#includes <bvector.h>.

: Agreed, and (c) it's very bad for both versions to have the same name,
: "vector<bool>".  A packed specialisation of vector<bool> should be named
: differently if it were supplied at all

Yes, I am convinced that the above which seemed reasonable to me, is not
reasonable.  I should also note that the vector<bool> is not in bvector.h
in either HP, GNU, or SGI.  It is bit_vector, a non-template class
which implements the vector<bool> of the draft.  The reason is that
the compilers do not support partial template specialization.  It seems
that this temporary solution would make everybody here happy if it
became permenant.  In the Moscow SPARC STL, bvector.h contains either
bit_vector or vector<bool> depending on the compiler support.

If the standard eventually contains vector<bool> as in the FCD, would it
be acceptable to use vector<bool> for space optimization and vector<int>
for time optimization?  Not as nice as it could be, but I think we could
get by with it.

[ remaining unaddressed comments snipped]

Later,
John
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Herb Sutter wrote:
> Aside: It seems anachronistic to hear some argue that you 'almost always'
> want to save 7 bits of space per bool at the expense of addressing overhead
> and temporary reference objects, at a time when memory is less than $5 per
> MB. ;-)  If you were creating vectors of tens of thousands of bools, okay,
> you could save 10K or 20K... but does anyone really want to do that? and
> wouldn't any space benefit get swamped by the performance hit, since it'd
> cost tens of thousands of temporaries every time you did a find<>()?

Some applications require huge vectors of bools.

What's wrong with vector<char> or vector<int> for the unpacked version?
Simply
typedef it to give it a more explicit name.

---
Nicolas Chapados                    Nortel Technology Ltd. (formerly
BNR)
chapados@nortel.ca                  Montreal, Canada
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

herbs@cntc.com (Herb Sutter) writes:

|>  fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) wrote:
|>  >jpotter@falcon.lhup.edu (John E. Potter) writes:
|>  >>I finally found vector<bool> in my g++ system.  It is in bvector.h; so,
|>  >>there is no forced space optimisation here.  <vector> does not include
|>  >>it.  If I #include <vector> then vector<bool> is a vector of whatever
|>  >>bool is.  If I want the space optimization, I can #include <bvector.h>.
|>  >
|>  >This is a really bad way for the user to indicate whether the space
|>  >optimization should be applied, since (a) it applies only on a
|>  >per-translation-unit basis, whereas the decision ought be made on a
|>  >more fine-grained basis, and (b) it is very easy to unknowningly
|>  >#include a header file that #includes some other header file that
|>  >#includes <bvector.h>.
|>
|>  Agreed, and (c) it's very bad for both versions to have the same name,
|>  "vector<bool>".  A packed specialisation of vector<bool> should be named
|>  differently if it were supplied at all, but anyway it can't meet the
|>  current sequence requirements because a bool& isn't a reference to a bit
|>  (addressability).
|>
|>  I strongly disagree with the suggestion that the sequence and iterator
|>  requirements be relaxed from the current "T&".  Besides the possibility
|>  that some of the algorithms may rely on this behaviour (assumption, I
|>  haven't checked this), I can see no benefit except to allow reference
|>  classes in order to implement a bitvector.  Can anyone cite another useful
|>  vector specialisation that requires a proxy class?  The only reason it's
|>  needed at all here is because of the bit-packing, which seems unuseful for
|>  any other type (except bitfields, which IMO shouldn't be used anyway, and
|>  enums, which would require another similar specialisation for each enum).

Well, they are obviously useful for disk based containers.  By allowing
them, you automatically make all of the STL algorithms work for data on
disk.

Whether this is a good idea or not, I don't know.  The time factors of
disk access are significantly different than those of main memory, and
it is probably that the specified time constraints of the algorithms
would not hold.  Typically, the best algorithms for disk based data are
NOT the same as those for memory based data.

|>  Aside: It seems anachronistic to hear some argue that you 'almost always'
|>  want to save 7 bits of space per bool at the expense of addressing overhead
|>  and temporary reference objects, at a time when memory is less than $5 per
|>  MB. ;-)  If you were creating vectors of tens of thousands of bools, okay,
|>  you could save 10K or 20K... but does anyone really want to do that? and
|>  wouldn't any space benefit get swamped by the performance hit, since it'd
|>  cost tens of thousands of temporaries every time you did a find<>()?
|>  (Assuming the compiler couldn't optimise away the existence of the
|>  temporary.)

I rather agree, although...

One of the applications I've seen for bit vectors is an allocation map
of disk blocks.  If you have a 2 Gigabyte disk, with 1 Kilobyte
allocation block size, that's 2 Mega bools.  The difference between 2
Megabytes and 256 Kilobytes could be important.

Never the less: my comments concerning disk based structures hold
equally well here.  The standard find algorithm is NOT the best way to
search for an unallocated block.  It is, in fact, a disaster in terms of
speed.  And with an array this size, the speed will be a factor.  (Note
that done correctly, using 1 bit per bool will also result in a
significant speed increase, because of the reduced paging.)

When I first heard about STL, I experimented making my classes as
general as possible (in my case, using a mixture of inheritance and
templates).  I've since reversed my position, at least with regards to
my own containers.  My own containers were general enough for what I
normally do, and the extra generality did have a cost in performance
(usually unimportant, but every once in a while...).

I think that the authors of STL are to be congratulated on just how
general they have managed to make the library without sacrificing
performance.  It is necessary, however, to take into consideration the
underlying unstated assumptions they made.  In particular, the STL
time constraints are based on the premice that a simple access is
constant time (O(k)), always the same constant time, and in fact, always
so small as to be negligible, at least when compared to the operations
effected on the accessed data.  This is not true for data on disk and it
is not true for packed objects in memory.

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

James Kanze <james-albert.kanze@vx.cit.alcatel.fr> wrote:
>herbs@cntc.com (Herb Sutter) writes:
>|>  Aside: It seems anachronistic to hear some argue that you 'almost always'
>|>  want to save 7 bits of space per bool at the expense of addressing overhead
>|>  and temporary reference objects, at a time when memory is less than $5 per
>|>  MB. ;-)  If you were creating vectors of tens of thousands of bools, okay,
>|>  you could save 10K or 20K... but does anyone really want to do that? and
>|>  wouldn't any space benefit get swamped by the performance hit, since it'd
>|>  cost tens of thousands of temporaries every time you did a find<>()?
>|>  (Assuming the compiler couldn't optimise away the existence of the
>|>  temporary.)
>
>I rather agree, although...

[good examples snipped]  (I just knew that paragraph was going to draw
commentary.)

I definitely agree there are applications where the space is more
important.  I only disagree with the original poster's comment that you'd
'almost always' prefer space efficiency (justifying that the standard
forces it on us, unless we work around it using something like vector<char>
as a kludge).

>I think that the authors of STL are to be congratulated on just how
>general they have managed to make the library without sacrificing
>performance.  It is necessary, however, to take into consideration the
>underlying unstated assumptions they made.  In particular, the STL
>time constraints are based on the premice that a simple access is
>constant time (O(k)), always the same constant time, and in fact, always
>so small as to be negligible, at least when compared to the operations
>effected on the accessed data.  This is not true for data on disk and it
>is not true for packed objects in memory.

This is a very good summary.  I'd only add that in both cases it doesn't
usually make sense to have a true reference to (practically equivalent of
taking the address of) a contained object either, since it may either not
be in memory at all (if on disk) or not be addressable (if it's a single
bit, unless you're on a machine that has bit-resolution pointers).

---
Herb Sutter (herbs@cntc.com)

Current Network Technologies Corp.
3100 Ridgeway, Suite 42, Mississauga ON Canada L5L 5M5
Tel 416-805-9088  Fax 905-608-2611
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Roman Lechtchinsky <wolfro@cs.tu-berlin.de> wrote
: Herb Sutter wrote:
: >
: > On 29 Jan 1997 16:05:55 GMT, Roman Lechtchinsky <wolfro@cs.tu-berlin.de>
: > wrote:
: > >Herb Sutter wrote:
: > >> [ Discussion of vector<bool>::reference ]
: > >> A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
: > >> standard library. :-)  However, there may be fixes I can't think of.

: > >IMHO, this would be a bad solution. A much better one would be to
: > >rewrite the requirements in a way that allows the usage of reference
: > >classes.

: > How would you do this?  Is there a way to allow this without disallowing
: > getting a pointer or reference into the collection?

: I think not. The standard could guarantee that this is possible for the
: standard containers but nevertheless relax the sequence requirements,
: though.
: My point is more about iterators, however. Container requirements merely
: describe what the standard containers do; you don't have to meet them
: when implementing your own containers. But if you want to use any of the
: standard algorithms with them you have to meet the iterator
: requirements. Note that in the Jan 96 WP, for a forward iterator with
: the value type T operator*() has to return T& ( I'm still waiting for my
: copy of the Dec 96 WP; please correct me if this has changed ).

No change.

: vector<bool>::iterator doesn't meet this requirement; thus, it is not a
: random access iterator or its value type cannot bool.
: Now, I agree that vector<bool> shouldn't use a packed representation (
: see below ).  However, IMHO a container with the semantics of
: vector<bool> should be in the standard or at least it should be possible
: to integrate such a container with the STL. I wouldn't mind if this
: class didn't meet the sequence requirements. It should support
: iterators, however. Unfortunately, it seems to be nearly impossible to
: provide mutable random access iterators for this container if their
: value type is to be bool because in this case, operator*() would have to
: return bool&. In general, the problem is: how do we implement iterators
: for collections that do not manage the objects they hold ( e.g. wrappers
: for the OS or existing code ), do not store the objects in memory ( e.g.
: databases ) or use a non-standard representation ( e.g. a packed
: representation like vector<bool> ).

: > >vector<bool> is important
: > >in this respect because, being the only standard container to use
: > >reference classes, it can define a standard interface for them.

: > This is a good point.  Still, the only point of reference classes is to
: > meet the container requirements, and so any implementation that does so
: > whether it looked like vector<bool>::reference or not -- would be fine.

: I'd rather say that reference classes should

: a) meet the container::reference requirements if used by a container;
: b) meet the iterator::reference requirements if used by an iterator;
: c) provide an intuitive interface.

: If a) and/or b) are to be allowed then the standard should say what
: exactly a reference class should do. As to c), it is quite easy to get
: the interface of a reference class wrong. E.g., in the Jan 96 interface
: for vector<bool>::reference neither the copy constructor nor the
: assignment from reference are mentioned. I don't know if this means that
: they are not availble or that compiler-generated implementations are to
: be used.

I forced myself to read clause 17.  I found it both informative and
readable, my compliments to the authors.  17.2.2.2 states that the
copy ctor, copy assignment and dtor are omitted when the semantics
is default generated.

: In the former case the client can't store a reference in a
: variable or copy one vector<bool> into another with std::copy. In the
: latter a const_reference ( typedef'd as const reference ) can be
: converted to a reference and the assignment operator reassigns the
: reference itself instead of the referrent. Both alternatives are at
: least counter-intuitive.

The good news is that the class has changed.

 typedef bool                      const_reference;
 typedef *implementation defined*  iterator;
 typedef *implementation defined*  const_iterator;

 class reference {
  friend class vector;
  reference ();
   public :
  ~reference ();
  operator bool () const;
  reference& operator= (bool const x);
  reference& operator= (reference const& x);
  void flip ();
 };

Vector has *implementation defined* random access iterators.  Since
vector<bool> is a specialization, I assume its iterators are also
random access.

 /2 reference is a class that simulates the behavior of references
 of a single bit in vector<bool>.

The assignment is now what you knew it must be.  The default constructor
is private.  There must obviously be another private constructor for the
vector to use.  Private parts are generally omitted.  The copy ctor is
the default public one.  I expected it to be private also.  I guess that
there should also be operator& private to prevent address of.  Thoughts?

: Another question is: should reference classes provide additional member
: functions like vector<bool>::reference::flip? This depends on
: expectations of the clients which will be influenced by the standard.
: The point is, reference classes have non-trivial semantics. It would be
: nice if these semantics were specified in the standard, at least by
: example.

And should it be flip?  Since the vector has a flip member to flip all
bits, it is consistent.  It could also have been operator^=.

 bool b;
 vector<bool> vb;
 b ^= true;
 vb[5].flip();  // vb[5] ^= true ???

Specific references like this one can provide specific actions, but in
general, it is difficult to support operations other than assignment.
I see your point in flip setting a precedent.  Would the user above be
happy with

 b = ! b;
 vb[5] = ! vb[5];

Assuming that iterator::operator*() is allowed to return a reference
and that the referent is struct S with member int x, how do we handle it?

 ContainerUsingReferences::iterator it;
 (*it).x = 5;  // I don't see how to do this
 int i = (*it).x;  // or this however
 int i = S(*it).x; // OK user write it my way

Nobody likes that anyway and operator-> is now usable, thanks committee.

 it->x = 5;  // Could this be done?
 int i = it->x;  // This seems doable

There is also an example of a proxie class in 24.5.3.1 which could be
used with istreambuf_iterator.

One other thing, iterators have traits classes.  Could setting the
traits get the iterator conforming and still do what we want?

later,
John


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

James Kanze wrote:
>
> It's worth pointing out that in fact, it is impossible to write a
> general reference class in C++, since you cannot overload operator.().

Agreed. But does ( or should ) the algorithm library really require
this? Should this be required for iterators? I think not. As I've
pointed out a previous posting, there exists at least one STL
implementation ( the Rogue Wave's one ) which works with my reference
classes ( and yes, sort works fine, too ). Even though many language
constructs required by the standard are not implemented in the compiler
I've tested it on, this seems to indicate that it is in fact possible to
implement the library in a way that allows reference classes.

> (Of course, for basic types like bool, this is not a problem.)

It depends on what you consider to be a problem. Obviously, sizeof won't
work as expected. operator&() is another problem if the referrent
doesn't exist in memory.

Bye

Roman
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Herb Sutter (herbs@cntc.com) wrote:
: On 29 Jan 1997 16:05:55 GMT, Roman Lechtchinsky <wolfro@cs.tu-berlin.de>
: wrote:
: >Herb Sutter wrote:
: >> [ Discussion of vector<bool>::reference ]
: >> (Aside: A secondary argument for dropping it is that it forces a
: >> (possibly unwanted) space/time tradeoff on the developer, since on
: >> many architectures accessing a single bit is more expensive than
: >> accessing a byte.  What if I don't care about space, but I need a fast
: >> vector<bool>?  Why should this force a space optimisation on me at the
: >> expense of performance?)
: >
: >That's a good point. However, I think that most of the time you will
: >want a packed representation.

I finally found vector<bool> in my g++ system.  It is in bvector.h; so,
there is no forced space optimisation here.  <vector> does not include
it.  If I #include <vector> then vector<bool> is a vector of whatever
bool is.  If I want the space optimization, I can #include <bvector.h>.
Found the same thing elsewhere.

Why can't I find it in the FCD?  If it is there, it setles this.

John


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

jpotter@falcon.lhup.edu (John E. Potter) writes:

>I finally found vector<bool> in my g++ system.  It is in bvector.h; so,
>there is no forced space optimisation here.  <vector> does not include
>it.  If I #include <vector> then vector<bool> is a vector of whatever
>bool is.  If I want the space optimization, I can #include <bvector.h>.

This is a really bad way for the user to indicate whether the space
optimization should be applied, since (a) it applies only on a
per-translation-unit basis, whereas the decision ought be made on a
more fine-grained basis, and (b) it is very easy to unknowningly
#include a header file that #includes some other header file that
#includes <bvector.h>.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

jpotter@falcon.lhup.edu (John E. Potter) writes:
>Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
>: Herb Sutter wrote:
>: >
>: > [ Discussion of vector<bool>::reference ]
>: >
>: > A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
>: > standard library. :-)  However, there may be fixes I can't think of.

>: IMHO, this would be a bad solution. A much better one would be to
>: rewrite the requirements in a way that allows the usage of reference
>: classes.

This is in general impossible, because operator.() is not overloadable.
(The idea has been discussed to death, in many guises.)

>But, is it a standard container?  The requirements on a sequence
>container require that C<T>::front() return a T&; however,
>vector<bool>::front() returns a reference.  The requirements on a
>container are that C<T>::reference be an lvalue of type T; however,
>vector<bool>::reference is a class.  etc.  So, is this standard
>container that fails to meet container requirements a standard
>container?

Precisely: vector<bool> is an example *in the Standard* of a container
that is not a Container, for very good (if unfortunate) reasons.  This
only means that vector<bool> is not suitable as an argument for templates
(e.g. stack<>) that require a Container.

Nathan Myers
ncm@cantrip.org

---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) wrote:
>jpotter@falcon.lhup.edu (John E. Potter) writes:
>>I finally found vector<bool> in my g++ system.  It is in bvector.h; so,
>>there is no forced space optimisation here.  <vector> does not include
>>it.  If I #include <vector> then vector<bool> is a vector of whatever
>>bool is.  If I want the space optimization, I can #include <bvector.h>.
>
>This is a really bad way for the user to indicate whether the space
>optimization should be applied, since (a) it applies only on a
>per-translation-unit basis, whereas the decision ought be made on a
>more fine-grained basis, and (b) it is very easy to unknowningly
>#include a header file that #includes some other header file that
>#includes <bvector.h>.

Agreed, and (c) it's very bad for both versions to have the same name,
"vector<bool>".  A packed specialisation of vector<bool> should be named
differently if it were supplied at all, but anyway it can't meet the
current sequence requirements because a bool& isn't a reference to a bit
(addressability).

I strongly disagree with the suggestion that the sequence and iterator
requirements be relaxed from the current "T&".  Besides the possibility
that some of the algorithms may rely on this behaviour (assumption, I
haven't checked this), I can see no benefit except to allow reference
classes in order to implement a bitvector.  Can anyone cite another useful
vector specialisation that requires a proxy class?  The only reason it's
needed at all here is because of the bit-packing, which seems unuseful for
any other type (except bitfields, which IMO shouldn't be used anyway, and
enums, which would require another similar specialisation for each enum).

Aside: It seems anachronistic to hear some argue that you 'almost always'
want to save 7 bits of space per bool at the expense of addressing overhead
and temporary reference objects, at a time when memory is less than $5 per
MB. ;-)  If you were creating vectors of tens of thousands of bools, okay,
you could save 10K or 20K... but does anyone really want to do that? and
wouldn't any space benefit get swamped by the performance hit, since it'd
cost tens of thousands of temporaries every time you did a find<>()?
(Assuming the compiler couldn't optimise away the existence of the
temporary.)

---
Herb Sutter (herbs@cntc.com)

Current Network Technologies Corp.
3100 Ridgeway, Suite 42, Mississauga ON Canada L5L 5M5
Tel 416-805-9088  Fax 905-608-2611
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Herb Sutter wrote:
>
> I strongly disagree with the suggestion that the sequence and iterator
> requirements be relaxed from the current "T&".  Besides the possibility
> that some of the algorithms may rely on this behaviour (assumption, I

I haven't checked this, either, but I don't think they do. They don't
call member functions which means that the so-called operator.() is not
required ( some use operators but I don't see a problem here: if all
else fails there are still function adaptors ). They don't need to take
the address of an object - after all, they are supposed to work with
iterators and not with pointers. Pointers probably could be an
optimization for some of the algorithms but then again, nothing prevents
an implementation from providing specializations for standard
containers. IMO, this is a quality of implementation issue anyway.
Actually, I would expect most of the current implementations to allow
reference classes - how could they provide vector<bool> otherwise? Mine
does. I'm sure that the HP implementation does, too - it doesn't even
mention T& in the iterator requirements.

> haven't checked this), I can see no benefit except to allow reference
> classes in order to implement a bitvector.  Can anyone cite another useful
> vector specialisation that requires a proxy class?  The only reason it's

I don't think any vector specializations except vector<bool> are or will
be allowed by the standard. I can' think of any, anyway. However, there
are many libraries and OS which provide get(index,item*) and
set(index,item*) or similar interface. Wouldn't it be nice if those
could be wrapped in iterators?

> Aside: It seems anachronistic to hear some argue that you 'almost always'
> want to save 7 bits of space per bool at the expense of addressing overhead
> and temporary reference objects, at a time when memory is less than $5 per
> MB. ;-)  If you were creating vectors of tens of thousands of bools, okay,
> you could save 10K or 20K... but does anyone really want to do that? and

Oh-oh, then I must be really anachronistic :-) The embedded system I'm
currently working on has 256K for the OS, program (>100K) and data. I
can't afford to waiste even 1K and I have to do some complicated
statistical computations. But that's a bad example. However, a
mathematical application can easily use more than tens of thousands of
bools, I think.

> wouldn't any space benefit get swamped by the performance hit, since it'd
> cost tens of thousands of temporaries every time you did a find<>()?
> (Assuming the compiler couldn't optimise away the existence of the
> temporary.)

IMO, a decent compiler can and should do it.

Bye

Roman
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <32ecba8c.251251099@news.interlog.com>, Herb Sutter
(herbs@cntc.com) wrote:
[snip]
>For example, given the following code:
>
>    template< class T >
>    void f( vector<T>& v )
>    {
>        T* pt = &v.front();
>    }
>
>is the code legal for every type T other than bool, yet illegal for
>bool?

I haven't checked, but I assume this isn't legal for bitfield types.
It seems to me that the vector<bool> override is trying to accomplish the
same thing that vector<unsigned int:1> would accomplish if it was legal;
that is, to pack sizeof(unsigned int)*CHAR_BIT bits into each unsigned
int.  And you're right, that amounts to "forcing" us to accept space
efficiency in return for loss of both run-time efficiency and
flexibility!
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Herb Sutter wrote:
>
> [ Discussion of vector<bool>::reference ]
>
> A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
> standard library. :-)  However, there may be fixes I can't think of.

IMHO, this would be a bad solution. A much better one would be to
rewrite the requirements in a way that allows the usage of reference
classes. I believe that they can become a very powerful tool. This won't
happen, however, if containers and iterators that return reference
classes fail to meet the requirements and thus can't be used with the
algorithm library ( at least not portably ). vector<bool> is important
in this respect because, being the only standard container to use
reference classes, it can define a standard interface for them.

An example: I once wrote a ListBox class which provided a vector-like
interface to list boxes ( including random access iterators ). I've used
vector<bool>::reference as a reference ( sounds funny, doesn't it ) for
its implementation. It worked with all ( i.e. the ones I've tested )
algortihms from the Rogue Wave STL implementation. I believed ( and I
still do ) that it should be possible to design a portable library which
would integrate such GUI objects with the STL. I stopped the
development, however, when I realized that my iterators didn't meet the
iterator requirements.
Another example are databases: I can see no way of neatly integrating
them with the standard library if iterators are to return true
references.

BTW, I believe that the requirements in the original STL were different.
They are in "STL Tutorial and Reference Guide" by Musser&Saini. I don't
know about the original proposal. Does someone know when and why they
have changed?

>
> (Aside: A secondary argument for dropping it is that it forces a
> (possibly unwanted) space/time tradeoff on the developer, since on
> many architectures accessing a single bit is more expensive than
> accessing a byte.  What if I don't care about space, but I need a fast
> vector<bool>?  Why should this force a space optimisation on me at the
> expense of performance?)
>

That's a good point. However, I think that most of the time you will
want a packed representation.

Bye

Roman


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

On 29 Jan 1997 16:05:55 GMT, Roman Lechtchinsky <wolfro@cs.tu-berlin.de>
wrote:
>Herb Sutter wrote:
>> [ Discussion of vector<bool>::reference ]
>> A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
>> standard library. :-)  However, there may be fixes I can't think of.
>
>IMHO, this would be a bad solution. A much better one would be to
>rewrite the requirements in a way that allows the usage of reference
>classes.

How would you do this?  Is there a way to allow this without disallowing
getting a pointer or reference into the collection?

>vector<bool> is important
>in this respect because, being the only standard container to use
>reference classes, it can define a standard interface for them.

This is a good point.  Still, the only point of reference classes is to
meet the container requirements, and so any implementation that does so --
whether it looked like vector<bool>::reference or not -- would be fine.  Of
course, this is assuming that it is feasible to change the container
requirements so as to allow such reference classes.

>> (Aside: A secondary argument for dropping it is that it forces a
>> (possibly unwanted) space/time tradeoff on the developer, since on
>> many architectures accessing a single bit is more expensive than
>> accessing a byte.  What if I don't care about space, but I need a fast
>> vector<bool>?  Why should this force a space optimisation on me at the
>> expense of performance?)
>
>That's a good point. However, I think that most of the time you will
>want a packed representation.

Really?  Why?

---
Herb Sutter (herbs@cntc.com)

Current Network Technologies Corp.
3100 Ridgeway, Suite 42, Mississauga ON Canada L5L 5M5
Tel 416-805-9088  Fax 905-608-2611
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Roman Lechtchinsky wrote:
>
> Herb Sutter wrote:
> >
> > [ Discussion of vector<bool>::reference ]
> >
> > A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
> > standard library. :-)  However, there may be fixes I can't think of.
>
> IMHO, this would be a bad solution. A much better one would be to
> rewrite the requirements in a way that allows the usage of reference
> classes. I believe that they can become a very powerful tool. This won't
> happen, however, if containers and iterators that return reference
> classes fail to meet the requirements and thus can't be used with the
> algorithm library ( at least not portably ). vector<bool> is important
> in this respect because, being the only standard container to use
> reference classes, it can define a standard interface for them.

But code that bind a reference with vector<T>::reference is
expected to work; I think in practice the reference won't be
built explicitly but with a function call.

vec[4] += newItem;

> An example: I once wrote a ListBox class which provided a vector-like
> interface to list boxes ( including random access iterators ). I've used
> vector<bool>::reference as a reference ( sounds funny, doesn't it ) for
> its implementation. It worked with all ( i.e. the ones I've tested )
> algortihms from the Rogue Wave STL implementation. I believed ( and I
> still do ) that it should be possible to design a portable library which
> would integrate such GUI objects with the STL. I stopped the
> development, however, when I realized that my iterators didn't meet the
> iterator requirements.

Why couldn't you return references to the items ?

> Another example are databases: I can see no way of neatly integrating
> them with the standard library if iterators are to return true
> references.

You mean that the data cannot be in a file ?

STL is a very general framework, but we must stop somewhere

> > (Aside: A secondary argument for dropping it is that it forces a
> > (possibly unwanted) space/time tradeoff on the developer, since on
> > many architectures accessing a single bit is more expensive than
> > accessing a byte.  What if I don't care about space, but I need a fast
> > vector<bool>?  Why should this force a space optimisation on me at the
> > expense of performance?)
> >
>
> That's a good point. However, I think that most of the time you will
> want a packed representation.

I would really prefer to write bitvector in this case.

--

Valentin Bonnard
mailto:bonnardv@pratique.fr
http://www.pratique.fr/~bonnardv (Informations sur le C++ en Francais)


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Roman Lechtchinsky (wolfro@cs.tu-berlin.de) wrote:
: Herb Sutter wrote:
: >
: > [ Discussion of vector<bool>::reference ]
: >
: > A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
: > standard library. :-)  However, there may be fixes I can't think of.

: IMHO, this would be a bad solution. A much better one would be to
: rewrite the requirements in a way that allows the usage of reference
: classes. I believe that they can become a very powerful tool. This won't
: happen, however, if containers and iterators that return reference
: classes fail to meet the requirements and thus can't be used with the
: algorithm library ( at least not portably ). vector<bool> is important
: in this respect because, being the only standard container to use
: reference classes, it can define a standard interface for them.

But, is it a standard container?  The requirements on a sequence
container require that C<T>::front() return a T&; however,
vector<bool>::front() returns a reference.  The requirements on a
container are that C<T>::reference be an lvalue of type T; however,
vector<bool>::reference is a class.  etc.  So, is this standard
container that fails to meet container requirements a standard
container?

: An example: I once wrote a ListBox class which provided a vector-like
: interface to list boxes ( including random access iterators ). I've used
: vector<bool>::reference as a reference ( sounds funny, doesn't it ) for
: its implementation. It worked with all ( i.e. the ones I've tested )
: algortihms from the Rogue Wave STL implementation. I believed ( and I
: still do ) that it should be possible to design a portable library which
: would integrate such GUI objects with the STL. I stopped the
: development, however, when I realized that my iterators didn't meet the
: iterator requirements.
: Another example are databases: I can see no way of neatly integrating
: them with the standard library if iterators are to return true
: references.

Yes.  I recently wrote a VirtualArray (remember BASIC?) class.  Looks
like an array, but is a random access file.  It works fine and so do
the iterators; however, they do not meet the specs.  Simple algorithms
work fine with it.  Sort fails to compile.  Template unification
errors, all of which can be traced to use of a builtin pointer to T.
It still needs some work to complete it, but I have reached the same
conclusion as you.  Did you try sort with your GUI thingie?

: BTW, I believe that the requirements in the original STL were different.
: They are in "STL Tutorial and Reference Guide" by Musser&Saini. I don't
: know about the original proposal. Does someone know when and why they
: have changed?

I think you have hit the problem.  The documentation for the public
HP STL also has the much weaker requirements.  It looks like they
were intended to allow proxies (reference classes) to be used.  See
my post on iterator requirements for examples of things which have
partially changed.  Things like T& (FCD) are mixed with convertable
to T (HP-STL).

How about a solution?  I think what is missing is requirements on
algorithms.  Everything is value semantics; so, algorithms should
be required to use value semantics.  T* and T& forbidden.  There
are no builtin pointers to container internals.  Those things are
iterators.  That would also solve Herb's problem with front.  You
can have the front item by value or an iterator to it but not a
builtin pointer.  Builtin pointers violate the whole framework of
the library unless the container is a builtin array.  But we
wouldn't think of using that would we?

: >
: > (Aside: A secondary argument for dropping it is that it forces a
: > (possibly unwanted) space/time tradeoff on the developer, since on
: > many architectures accessing a single bit is more expensive than
: > accessing a byte.  What if I don't care about space, but I need a fast
: > vector<bool>?  Why should this force a space optimisation on me at the
: > expense of performance?)
: >

: That's a good point. However, I think that most of the time you will
: want a packed representation.

Would vector<int> serve the other cases?  Or should vector<bool> be
moved to another header so that it is only used when requested?  I
agree with you that it should be in the standard and serve as the
reference-class reference.

John


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Herb Sutter wrote:
>
> On 29 Jan 1997 16:05:55 GMT, Roman Lechtchinsky <wolfro@cs.tu-berlin.de>
> wrote:
> >Herb Sutter wrote:
> >> [ Discussion of vector<bool>::reference ]
> >> A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
> >> standard library. :-)  However, there may be fixes I can't think of.
> >
> >IMHO, this would be a bad solution. A much better one would be to
> >rewrite the requirements in a way that allows the usage of reference
> >classes.
>
> How would you do this?  Is there a way to allow this without disallowing
> getting a pointer or reference into the collection?

I think not. The standard could guarantee that this is possible for the
standard containers but nevertheless relax the sequence requirements,
though.
My point is more about iterators, however. Container requirements merely
describe what the standard containers do; you don't have to meet them
when implementing your own containers. But if you want to use any of the
standard algorithms with them you have to meet the iterator
requirements. Note that in the Jan 96 WP, for a forward iterator with
the value type T operator*() has to return T& ( I'm still waiting for my
copy of the Dec 96 WP; please correct me if this has changed ).
vector<bool>::iterator doesn't meet this requirement; thus, it is not a
random access iterator or its value type cannot bool.
Now, I agree that vector<bool> shouldn't use a packed representation (
see below ).  However, IMHO a container with the semantics of
vector<bool> should be in the standard or at least it should be possible
to integrate such a container with the STL. I wouldn't mind if this
class didn't meet the sequence requirements. It should support
iterators, however. Unfortunately, it seems to be nearly impossible to
provide mutable random access iterators for this container if their
value type is to be bool because in this case, operator*() would have to
return bool&. In general, the problem is: how do we implement iterators
for collections that do not manage the objects they hold ( e.g. wrappers
for the OS or existing code ), do not store the objects in memory ( e.g.
databases ) or use a non-standard representation ( e.g. a packed
representation like vector<bool> ).

> >vector<bool> is important
> >in this respect because, being the only standard container to use
> >reference classes, it can define a standard interface for them.
>
> This is a good point.  Still, the only point of reference classes is to
> meet the container requirements, and so any implementation that does so --
> whether it looked like vector<bool>::reference or not -- would be fine.  Of

I'd rather say that reference classes should

a) meet the container::reference requirements if used by a container;
b) meet the iterator::reference requirements if used by an iterator;
c) provide an intuitive interface.

If a) and/or b) are to be allowed then the standard should say what
exactly a reference class should do. As to c), it is quite easy to get
the interface of a reference class wrong. E.g., in the Jan 96 interface
for vector<bool>::reference neither the copy constructor nor the
assignment from reference are mentioned. I don't know if this means that
they are not availble or that compiler-generated implementations are to
be used. In the former case the client can't store a reference in a
variable or copy one vector<bool> into another with std::copy. In the
latter a const_reference ( typedef'd as const reference ) can be
converted to a reference and the assignment operator reassigns the
reference itself instead of the referrent. Both alternatives are at
least counter-intuitive.
Another question is: should reference classes provide additional member
functions like vector<bool>::reference::flip? This depends on
expectations of the clients which will be influenced by the standard.
The point is, reference classes have non-trivial semantics. It would be
nice if these semantics were specified in the standard, at least by
example.


> >> (Aside: A secondary argument for dropping it is that it forces a
> >> (possibly unwanted) space/time tradeoff on the developer, since on
> >> many architectures accessing a single bit is more expensive than
> >> accessing a byte.  What if I don't care about space, but I need a fast
> >> vector<bool>?  Why should this force a space optimisation on me at the
> >> expense of performance?)

After a second thought - you're right. vector<bool> should be just that
- a vector of bools. Probably, it shouldn't be dropped completely but
rather renamed so that both vector<bool> with an unpacked and another
container type ( e.g. bitvector as Valentin Bonnard suggested in another
posting ) with a packed representation are availble. bitset doesn't seem
sufficient to me since its maximum size has to be known at compile time
and it provides no iterators.

Bye

Roman
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

herbs@cntc.com (Herb Sutter) writes:

|>  On 29 Jan 1997 16:05:55 GMT, Roman Lechtchinsky <wolfro@cs.tu-berlin.de>
|>  wrote:

|>  >vector<bool> is important
|>  >in this respect because, being the only standard container to use
|>  >reference classes, it can define a standard interface for them.
|>
|>  This is a good point.  Still, the only point of reference classes is to
|>  meet the container requirements, and so any implementation that does so --
|>  whether it looked like vector<bool>::reference or not -- would be fine.  Of
|>  course, this is assuming that it is feasible to change the container
|>  requirements so as to allow such reference classes.

It's worth pointing out that in fact, it is impossible to write a
general reference class in C++, since you cannot overload operator.().
(Of course, for basic types like bool, this is not a problem.)

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

This question is based on a recent discussion with James Kanze on
clcm.

- In 23.1 [lib.container.requirements], Table 66 requires that
X::reference have return type "lvalue of T".

- In 23.1.1 [lib.sequence.requirements], Table 69 requires that (for
example) a.front() return a T& or const T&.

- In 23.2.4 [lib.vector], vector<T,A>::front returns
vector<T,A>::reference, which is typedef'd as A::reference, which
20.1.5 [lib.allocator.requirements] Table 32 requires to be a T&.
Fine, that's as it should be.

- However, in 23.2.5 [lib.vector.bool], the packed specialisation for
vector<bool>, vector<bool,A>::front returns vector<bool,A>::reference,
which is a nested class and cannot be converted to "lvalue of T" or a
T& or a const T&.  Hence vector<bool> is not a sequence...?  (Aside:
vector<bool,A>::reference does define an operator bool() const, but it
is not an lvalue into the sequence as provided by the general
vector<T,A>::reference.  Even if it were not illegal, it would be
inconsistent with the general vector<> template.)

For example, given the following code:

    template< class T >
    void f( vector<T>& v )
    {
        T* pt = &v.front();
    }

is the code legal for every type T other than bool, yet illegal for
bool?

A fundamental problem is addressability (as James pointed out): for a
packed implementation of vector<bool> to return a true pointer or
reference to one of its elements would require bit-addressability, and
therefore ALL bool* and bool& in the program must be larger than
"normal" pointers.  (Does the standard allow having data pointers of
different sizes?)

A simple solution would be to drop 23.2.5 [lib.vector.bool] from the
standard library. :-)  However, there may be fixes I can't think of.

(Aside: A secondary argument for dropping it is that it forces a
(possibly unwanted) space/time tradeoff on the developer, since on
many architectures accessing a single bit is more expensive than
accessing a byte.  What if I don't care about space, but I need a fast
vector<bool>?  Why should this force a space optimisation on me at the
expense of performance?)

---
Herb Sutter (herbs@cntc.com)

Current Network Technologies Corp.
3100 Ridgeway, Suite 42, Mississauga ON Canada L5L 5M5
Tel 416-805-9088  Fax 905-608-2611


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]