Christopher Eltschka <celtschk@physik.tu-muenchen.de> writes:

|>  J. Kanze wrote:
|>
|>  [...]
|>
|>  > I'm certain that forbidding lazy copy was not the intent.  Also, there
|>  > are no formal conformance procedures; anyone *can* claim whatever they
|>  > want as a conforming compiler, so the interpretation of the standard is
|>  > in the hands of the implementors, controlled by market presures.  In the
|>
|>  I don't think so. I think if an implementor claims its compiler to
|>  be standard conforming, and it has significant deviations from the
|>  standard (which cannot be explained as bugs or language extensions;
|>  say, they are not implementing templates at all), then you could sue
|>  them,

You sue them, and they answer: it's a bug, but we don't think it is an
important one, and we aren't fixing it.  Or they answer, our
interpretation of the standard is... so they are right.

Remember, it isn't people like ourselves you have to convince, it is
twelve technically naive jurors.  And the companies arguing their case
probably have better lawyers than you or I could afford to hire.

|>  on the same reason why you could sue someone who sells you
|>  kangoroo meat as beef - there's no "beef conformance procedure" as
|>  well.

In that particular case, there are government agencies which enforce the
"standard".

|>  While it is true that there is no formal conformance procedure, there
|>  *is* a clear definition of what means "conforming" - the standard.

Really.  What is it?  (I can think of one, but it is useless, since it
supposes bug-free software.)

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung


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

J. Kanze wrote:

[...]

> I'm certain that forbidding lazy copy was not the intent.  Also, there
> are no formal conformance procedures; anyone *can* claim whatever they
> want as a conforming compiler, so the interpretation of the standard is
> in the hands of the implementors, controlled by market presures.  In the

I don't think so. I think if an implementor claims its compiler to
be standard conforming, and it has significant deviations from the
standard (which cannot be explained as bugs or language extensions;
say, they are not implementing templates at all), then you could sue
them, on the same reason why you could sue someone who sells you
kangoroo meat as beef - there's no "beef conformance procedure" as
well.
While it is true that there is no formal conformance procedure, there
*is* a clear definition of what means "conforming" - the standard.


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

jkanze@otelo.ibmmail.com wrote in message
<6utpo8$t1v$1@nnrp1.dejanews.com>...
>In article <slrn712cp7.32o.sbnaran@fermi.ceg.uiuc.edu>,
>  sbnaran@KILL.uiuc.edu wrote:
>>
>> On 29 Sep 98 18:02:52 GMT, Zeisel Helmut  VAI/TAP 2
>>
>> >Instead of repeated writing reference-counting & copy-on-write
>> >for several classes I would prefer to use
>> >containers that are themselves implemented using reference counting and
>> >copy-on-write.
>>
>> The standard does not specify that reference counting be used or not.
>> It does not specify a complexity requirement for op= either (if the
>> complexity of op= was O(1), this suggests that reference counting is
>> in effect).  An implementation may chose to use reference counting
>> if it wants to.
>
>On the other hand, the standard does require a complexity of O(1) for
>operator[] on a vector, for example.  Which means that any implementation
>where v[i] = ... might require copying the vector is out.
>

I'm not so sure. I think one can garantee that the copying would otherwise
always be done beforehand. So maybe this is not to the letter of the
standard, but surely to the intent. I think this would not make any program
slower in any way, it would just defer the copying. Maybe this could be
added in an amendment. But then, maybe I'm plain wrong.

Greetz,
Martijn (see sig for real email address)

--
My email address is intentionally invalid against spam
reply to mlievaart at orion in nl
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Martijn Lievaart" <nobody@orion.nl> writes:

|>  jkanze@otelo.ibmmail.com wrote in message
|>  <6utpo8$t1v$1@nnrp1.dejanews.com>...
|>  >In article <slrn712cp7.32o.sbnaran@fermi.ceg.uiuc.edu>,
|>  >  sbnaran@KILL.uiuc.edu wrote:

|>  >> On 29 Sep 98 18:02:52 GMT, Zeisel Helmut  VAI/TAP 2

|>  >> >Instead of repeated writing reference-counting & copy-on-write
|>  >> >for several classes I would prefer to use
|>  >> >containers that are themselves implemented using reference counting and
|>  >> >copy-on-write.

|>  >> The standard does not specify that reference counting be used or not.
|>  >> It does not specify a complexity requirement for op= either (if the
|>  >> complexity of op= was O(1), this suggests that reference counting is
|>  >> in effect).  An implementation may chose to use reference counting
|>  >> if it wants to.

|>  >On the other hand, the standard does require a complexity of O(1) for
|>  >operator[] on a vector, for example.  Which means that any implementation
|>  >where v[i] = ... might require copying the vector is out.


|>  I'm not so sure. I think one can garantee that the copying would otherwise
|>  always be done beforehand. So maybe this is not to the letter of the
|>  standard, but surely to the intent. I think this would not make any program
|>  slower in any way, it would just defer the copying. Maybe this could be
|>  added in an amendment. But then, maybe I'm plain wrong.

I'm certain that forbidding lazy copy was not the intent.  Also, there
are no formal conformance procedures; anyone *can* claim whatever they
want as a conforming compiler, so the interpretation of the standard is
in the hands of the implementors, controlled by market presures.  In the
end, the question is: will any significant group of people not purchase
a compiler on the grounds that it fails to conform because of this
point?

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung


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

In article <slrn712cp7.32o.sbnaran@fermi.ceg.uiuc.edu>,
  sbnaran@KILL.uiuc.edu wrote:
>
> On 29 Sep 98 18:02:52 GMT, Zeisel Helmut  VAI/TAP 2
>
> >Instead of repeated writing reference-counting & copy-on-write
> >for several classes I would prefer to use
> >containers that are themselves implemented using reference counting and
> >copy-on-write.
>
> The standard does not specify that reference counting be used or not.
> It does not specify a complexity requirement for op= either (if the
> complexity of op= was O(1), this suggests that reference counting is
> in effect).  An implementation may chose to use reference counting
> if it wants to.

On the other hand, the standard does require a complexity of O(1) for
operator[] on a vector, for example.  Which means that any implementation
where v[i] = ... might require copying the vector is out.

> Strings are normally always reference counted.

It depends on the implementation.  There has been quite a bit of discussion
about whether they should be or not lately.

More to the point, of course, strings (or other containers, for that matter)
do not have to be contiguous, so you might find some parts reference counted,
and others not.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

jkanze@otelo.ibmmail.com wrote:

> On the other hand, the standard does require a complexity of O(1) for
> operator[] on a vector, for example.  Which means that any implementation
> where v[i] = ... might require copying the vector is out.

Not in my understanding, because COW only cause _whole_ programs
to have a lower complexity. The O(n) cost you are talking about
is a one time cost. It corresponds to the allowed O(n) cost which
was avoided before, during the copy (in other words, it's a delayed
cost).

The question is: are complexity requirements lazy or not ? Do you
think the question should officially be asked ?

I don't think so, because a string is a reversible containner
which supports [], so string::operator[] must also be O(1).

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/


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

Valentin Bonnard wrote:
>
> jkanze@otelo.ibmmail.com wrote:
>
> > On the other hand, the standard does require a complexity of O(1) for
> > operator[] on a vector, for example.  Which means that any implementation
> > where v[i] = ... might require copying the vector is out.
>
> Not in my understanding, because COW only cause _whole_ programs
> to have a lower complexity. The O(n) cost you are talking about
> is a one time cost. It corresponds to the allowed O(n) cost which
> was avoided before, during the copy (in other words, it's a delayed
> cost).

Isn't that what's meant by "amortized complexity"?

The allocator requirements in Table 31, and all iterator requirements
are explicitly stated to be amortized constant time.
The following member function are explicit stated to take amortized
constant time: a.insert(p,t) if t is inserted right after p in
associative containers, a.erase() in associative containers, and
insert() and erase() at the ends of vector<>s.

Since it is explicitly stated in those cases, I presume that none of the
other complexity requirements refer to amortized time. Am I presuming
too much?


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

I have several classes with STL containers as members;
for some of my classes reference-counting and a copy-on-write technique
(see e.g., Meyers II, Item 29, or Koenig & Moo, Ruminations on C++)
might be a suitable optimization.

Instead of repeated writing reference-counting & copy-on-write
for several classes I would prefer to use
containers that are themselves implemented using reference counting and
copy-on-write.

Does someone know whether such an implementation exists?
Can copy-on-write standard containers (std::vector, std::list, std::map)
be implemented in a way that  is conform to ISO C++
or are there some restrictions in the standard that make such an
implementaion
nonconform?

Helmut Zeisel
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 29 Sep 98 18:02:52 GMT, Zeisel Helmut  VAI/TAP 2

>Instead of repeated writing reference-counting & copy-on-write
>for several classes I would prefer to use
>containers that are themselves implemented using reference counting and
>copy-on-write.

The standard does not specify that reference counting be used or not.
It does not specify a complexity requirement for op= either (if the
complexity of op= was O(1), this suggests that reference counting is
in effect).  An implementation may chose to use reference counting
if it wants to.  Strings are normally always reference counted.
Vectors may be too, but don't count on it.  But all the other
containers are usually not reference counted.

You can write your own reference counting class, and use this as a
building block of your own class.  This approach may involve lots of
typing, but it's pretty cool once it is working.


--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


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

In article <5A02ED32FF38D211AA4F0008C72438BD26B14D@mail1.vai.co.at>,
  Zeisel Helmut  VAI/TAP 2 <Zeisel@linz.vai.co.at> wrote:
> I have several classes with STL containers as members;
> for some of my classes reference-counting and a copy-on-write technique
> (see e.g., Meyers II, Item 29, or Koenig & Moo, Ruminations on C++)
> might be a suitable optimization.
>
> Instead of repeated writing reference-counting & copy-on-write
> for several classes I would prefer to use
> containers that are themselves implemented using reference counting and
> copy-on-write.
>
> Does someone know whether such an implementation exists?

Not for free, AFAIK.  I have been told that the RogueWave Tools.h++
package does some of that, but that could be completely wrong; I don't
have a copy of Tools.h++.


> Can copy-on-write standard containers (std::vector, std::list, std::map)
> be implemented in a way that  is conform to ISO C++
> or are there some restrictions in the standard that make such an
> implementaion
> nonconform?

Um, well, you've read Meyers II, it seems, and the implementations shown
in Items 29 through 31 are conforming.  (There may have been some
funkiness with the member template functions; it's been a while since I
looked.)

The RCObject and RCPtr class developed in those Items are fairly compact;
you could probably save yourself some time /and/ find out about possible
nonconformance just by typing them in.  (Or downloading the source.)  The
point of those Items is that you can mix-in reference counting easily,
after all.


Did this answer your questions?

Luck++;
/dev/phil


-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


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