On Fri, 24 Aug 2001 21:33:21 GMT, Phil Edwards
<pedwards@dmapub.dma.org> wrote:

>Why?  I would have thought that [17.3.1.2]/6 and its
>footnote are clear enough:
>
>#  In some cases the semantic requirements are presented
>#  as C++ code. Such code is intended as a specification
>#  of equivalence of a construct to another construct,
>#  not necessarily as the way the construct must be
>#  implemented. 145)

All the daemons are hidden under the word "equivalence".

If I've a counter of all instances created of a given
class then the number of temporary copies isn't something
irrilevant. The standard is pretty clear about when
copies can be elided (for example return optimization
or passing temporaries as by value parameters).

>#  145) Although in some cases the code given is unambiguously the optimum
>#  implementation.

Hmmm. What about adding
  "whatever 'optimum' may mean."
?

>And if that isn't enough, the "as-if" rule trumps all.  :-)

That doesn't win anything in my opinion.

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

John Potter wrote:
>
> On Fri, 24 Aug 2001 21:33:21 GMT, Phil Edwards <pedwards@dmapub.dma.org>
> wrote:
...
> > Why?  I would have thought that [17.3.1.2]/6 and its footnote are clear
> > enough:
> >
> > #  In some cases the semantic requirements are presented as C++ code.
> > #  Such code is intended as a specification of equivalence of a construct
> > #  to another construct, not necessarily as the way the construct must be
> > #  implemented. 145)
> > #
> > #  145) Although in some cases the code given is unambiguously the optimum
> > #  implementation.
>
> Nice.  Now can you find a normative clause which makes that statement?

That IS normative text, except for the footnote, which is both clearly
true (note the word "some") and not very relevant.

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

On Sun, 26 Aug 2001 17:28:31 GMT, "James Russell Kuyper Jr."
<kuyper@wizard.net> wrote:

> John Potter wrote:

> > Nice.  Now can you find a normative clause which makes that statement?
>
> That IS normative text, except for the footnote, which is both clearly
> true (note the word "some") and not very relevant.

I don't think so.

17.3 Method of Description (Informative) [lib.description]

John

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

John Potter wrote:
>
> On Sun, 26 Aug 2001 17:28:31 GMT, "James Russell Kuyper Jr."
> <kuyper@wizard.net> wrote:
>
> > John Potter wrote:
>
> > > Nice.  Now can you find a normative clause which makes that statement?
> >
> > That IS normative text, except for the footnote, which is both clearly
> > true (note the word "some") and not very relevant.
>
> I don't think so.
>
> 17.3 Method of Description (Informative) [lib.description]

Sorry - you're correct. That's bizarre! How can sections 18-25 have
meaningful normative content, if the method used to describe them is
itself described in a non-normative clause?

I think we're better off pretending that word wasn't there, or at least
that the word doesn't actually affect the normative content of the
clauses which use the method of description described in 17.3.

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

On Sat, 25 Aug 2001 02:36:22 GMT, "James Russell Kuyper Jr."
<kuyper@wizard.net> wrote:

...

>No. "same result" was a bad choice of words. What the standard says is
>that the actual implementation must be equivalent to the example code.
>The observable effects of the code include the number, order, and
>arguments of calls to user-defined functions, which might be
>instrumented to detect the difference. In particular, operator[]'s
>effects are described in terms of insert(), which as you say, has a
>complexity specification. Therefore, any alternative implementation of
>operator[] must meet that same complexity specification.

So you're saying that I was right with my consideration
that the actual form of the description of map::operator[]
in the standard *requires* the creation of a minimum of
three T temporaries and two copies of the key value passed
(one temporary T and one copy of the key just because of
a bad use of make_pair in the example).

Any conforming implementation must create all those
useless objects.

...

>Those all seem to be valid deductions to me. Those all fall under the
>category of observable effects; an implementation that violates any of
>those is inconsistent with 17.3.1.2p6.

This is at the same time conforting and depressing.

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

On Sat, 25 Aug 2001 00:34:30 GMT, jpotter@falcon.lhup.edu (John
Potter) wrote:

>Would you also include complexity requirements which
>state exactly how many times which members are called?
>That effectively specifies the code.

I think I would like the standard to read something
in the spirit of ...

  map element access               [lib.map.access]

  T& operator[](const key_type& x);

  Effects:
    Finds the existing element in the map with the
    specified key value or adds a new one with
    the specified key and a default constructed
    mapped_type part if such an element is not
    present in the container.

  Complexity:
    Logarithmic in the number of elements present
    in the container.

  Returns:
    A reference to the mapped_type part of the
    element.

(sorry if that reads funny... but english isn't
my native language and I'm not used to write this
kind of documents even in italian; you anyway
got the picture).

In other words I would like the standard to
say *less* about temporaries than it's saying
in its current form.

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

On Fri, 24 Aug 2001 21:22:39 GMT, Howard Hinnant
<hinnant@antispam.metrowerks.com> wrote:

>This is sort of an extreme view, but on some days I feel like every
>single place where the standard uses code in place of a description of
>the desired results is worthy of a defect report.

It doesn't seem to me that *all* code provided is
that bad. Sometimes the room for "improvement" seems
to me kind of little.

The situation is different for map::operator[]; that
implementation is indeed quite bad (partly for what
I think being just an oversight about the type of
pair deduced by make_pair and partly for how the
interface of insert is designed).
I think map::operator[] is used a lot and often
with possilbly already existing elements (that
interface seems to me natural and clean; I suppose
many other C++ programmers feel the same about it),
and the standard *requires* three T and two key
duplications when *none* of them is needed.

I'm not saying that the standard should provide an
optimal implementation (that requires using something
alternative to insert(...) to fill the container);
but at least shouldn't be forcing conforming
implementations to (mis)behave that way on this
specific point.

I've to say that having a standard forcing the
implementation details to the level of actual
code (or any visible effect thereof, that's
exactly the same) gives me some strange feelings.

Probably would have been better using words to
express only the guarantees a user of the library
could count on. An implementation actually
forces much more and not always everything is
good for the user.

For example I don't think that anyone sitting in
the comitee reunion would have used the words
"And map::operator[] will make two copies of the
passed key and will create three temporary T
objects"; and probably wouldn't have said even
"It calls insert(...) to add a default
constructed element to the map".

Those are implementation details that shouldn't
in my opinion be covered, either intentionally
or unintentionally.

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

On Thu, 23 Aug 2001 21:53:42 GMT, agriff@tin.it (Andrea Griffini) wrote:

> None of these solution is standard-conforming as
> also isn't the one from MetroWerks (optimal and not
> based on insert), if I understood correctly.

I think that may be a misunderstanding.  The standard uses that line
of code to state what is returned, not how it is calculated.  One line
of code is worth many lines of prose sometimes.  Anything which gives
the same result is standard conforming.

John

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

On Fri, 24 Aug 2001 16:32:23 GMT, jpotter@falcon.lhup.edu (John
Potter) wrote:

>I think that may be a misunderstanding.  The standard uses that line
>of code to state what is returned, not how it is calculated.  One line
>of code is worth many lines of prose sometimes.  Anything which gives
>the same result is standard conforming.

That is a strong proposition. Sure allows for great
implementation (and for terrible ones) but weakens a
lot of what I was thinking the standard was saying.

For example complexity is stated for insert,
lower_bound & similar and operator[] isn't in the
table. If that algorithm isn't meant as a directive
then are you saying that an implementation is free
to require (just to exaggerate a bit) O(n^3) to
implement operator[] ?

Does the same "just the result counts" hold for all
other cases in which an implementation is presented
instead of a description ?

On [lib.vector] I read:

  void assign(size_type n, const T& t);

  Effects:
        erase(begin(), end());
        insert(begin(), n, t);

and I was supposing this implementation being quite a
requirement. Looking at that code I can deduce that:

  - Elements currently in the vector will be
    destroyed, and won't just become assigned
    with copies of t, not even the first n.

  - I'm expecting linear complexity on size()+n

  - I'm expecting and a certain behaviour in respect
    to reallocations. For example if capacity()>=n
    then no reallocation will occur during the fill.

  - I can assume that elements will be first destroyed
    and then created (this can be important if my
    element are huge or if both size() and n are big
    numbers, or if I've a max limit on the number of
    elements of a certain class).

  - I know that the operation won't give me
    the succeed-or-nop guarantee.

Are all those deduction just "wild guesses" as even a
conforming version may have used instead of that code
something like...

  template<class T>
  vector<T> assign(size_type n, const T& t)
  {
    vector<T>(n,t).swap(this);
  }

or

  template<class T>
  vector<T> assign(size_type n, const T& t)
  {
    resize(n);
    fill(begin(),end(),t);
  }

?

If like you said the implementation is worth several
lines of explanation is just the final result that
should be considered in all the code examples ?

I know I may be a bit annoying; but the standard
document is meant to be precise. Annoyingly precise.

I've got the impression that on operator[] of map the
standard is annoyingly precise and requires a bad
implementation.

And also got the impression that implementers ignored
that bad implementation (I'm a bit undecided on the
point if this is a good or a bad thing).

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

In article <3b868511.11642088@news.interbusiness.it>, Andrea Griffini
<agriff@tin.it> wrote:

| And also got the impression that implementers ignored
| that bad implementation (I'm a bit undecided on the
| point if this is a good or a bad thing).

This is sort of an extreme view, but on some days I feel like every
single place where the standard uses code in place of a description of
the desired results is worthy of a defect report.

--
Howard Hinnant
Metrowerks

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

Howard Hinnant  <hinnant@antispam.metrowerks.com> wrote:
> In article <3b868511.11642088@news.interbusiness.it>, Andrea Griffini
> <agriff@tin.it> wrote:
>
> | And also got the impression that implementers ignored
> | that bad implementation (I'm a bit undecided on the
> | point if this is a good or a bad thing).
>
> This is sort of an extreme view, but on some days I feel like every
> single place where the standard uses code in place of a description of
> the desired results is worthy of a defect report.

Why?  I would have thought that [17.3.1.2]/6 and its footnote are clear
enough:

#  In some cases the semantic requirements are presented as C++ code.
#  Such code is intended as a specification of equivalence of a construct
#  to another construct, not necessarily as the way the construct must be
#  implemented. 145)
#
#  145) Although in some cases the code given is unambiguously the optimum
#  implementation.

And if that isn't enough, the "as-if" rule trumps all.  :-)

Phil

--
Would I had phrases that are not known, utterances that are strange, in
new language that has not been used, free from repetition, not an utterance
which has grown stale, which men of old have spoken.
                                     - anonymous Egyptian scribe, c.1700 BC

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

John Potter <jpotter@falcon.lhup.edu> wrote:

> On Thu, 23 Aug 2001 21:53:42 GMT, agriff@tin.it (Andrea Griffini) wrote=
:
>=20
> > None of these solution is standard-conforming as
> > also isn't the one from MetroWerks (optimal and not
> > based on insert), if I understood correctly.
>=20
> I think that may be a misunderstanding.  The standard uses that line
> of code to state what is returned, not how it is calculated.  One line
> of code is worth many lines of prose sometimes.  Anything which gives
> the same result is standard conforming.

This depends on the definition of 'the same result'.=20

It seems that A. Griffini counts possible side effects of default,
converting and copy constructors (and maybe even destructors) to the
effects of a piece of code, unless you are dealing with a copy that
explicitly can be elided by the compiler.
=20
By that definition most effects-by-example-implementation sections in
the standard cannot be implemented much differently from the sample
implementation. This holds at least for the implementation that applies
non-POD class types.

I don't think that this is what was intended, but it might be legally
correct.

Regards, J=F6rg
=20
--=20
J=F6rg Barfurth                         joerg.barfurth@attglobal.net
<<<<<<<<<<<<< using std::disclaimer;  <<<<<<<<<<<<<<<<<<<<<<<<<<<<
Software Developer                    http://www.OpenOffice.org
StarOffice Configuration              http://www.sun.com/staroffice

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

On Fri, 24 Aug 2001 21:33:21 GMT, Phil Edwards <pedwards@dmapub.dma.org>
wrote:

>
> Howard Hinnant  <hinnant@antispam.metrowerks.com> wrote:
> > In article <3b868511.11642088@news.interbusiness.it>, Andrea Griffini
> > <agriff@tin.it> wrote:
> >
> > | And also got the impression that implementers ignored
> > | that bad implementation (I'm a bit undecided on the
> > | point if this is a good or a bad thing).
> >
> > This is sort of an extreme view, but on some days I feel like every
> > single place where the standard uses code in place of a description of
> > the desired results is worthy of a defect report.

Would you also include complexity requirements which state exactly how
many times which members are called?  That effectively specifies the
code.

> Why?  I would have thought that [17.3.1.2]/6 and its footnote are clear
> enough:
>
> #  In some cases the semantic requirements are presented as C++ code.
> #  Such code is intended as a specification of equivalence of a construct
> #  to another construct, not necessarily as the way the construct must be
> #  implemented. 145)
> #
> #  145) Although in some cases the code given is unambiguously the optimum
> #  implementation.

Nice.  Now can you find a normative clause which makes that statement?

> And if that isn't enough, the "as-if" rule trumps all.  :-)

Nope, it changes the observable behavior of a program with
instrumentation.

John

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

Andrea Griffini wrote:
>
> On Fri, 24 Aug 2001 16:32:23 GMT, jpotter@falcon.lhup.edu (John
> Potter) wrote:
>
> >I think that may be a misunderstanding.  The standard uses that line
> >of code to state what is returned, not how it is calculated.  One line
> >of code is worth many lines of prose sometimes.  Anything which gives
> >the same result is standard conforming.
>
> That is a strong proposition. Sure allows for great
> implementation (and for terrible ones) but weakens a
> lot of what I was thinking the standard was saying.
>
> For example complexity is stated for insert,
> lower_bound & similar and operator[] isn't in the
> table. If that algorithm isn't meant as a directive
> then are you saying that an implementation is free
> to require (just to exaggerate a bit) O(n^3) to
> implement operator[] ?

No. "same result" was a bad choice of words. What the standard says is
that the actual implementation must be equivalent to the example code.
The observable effects of the code include the number, order, and
arguments of calls to user-defined functions, which might be
instrumented to detect the difference. In particular, operator[]'s
effects are described in terms of insert(), which as you say, has a
complexity specification. Therefore, any alternative implementation of
operator[] must meet that same complexity specification.

> Does the same "just the result counts" hold for all
> other cases in which an implementation is presented
> instead of a description ?

17.3.1.2p6 applies to all such examples in the descriptions of the
standard library.

> On [lib.vector] I read:
>
>   void assign(size_type n, const T& t);
>
>   Effects:
>         erase(begin(), end());
>         insert(begin(), n, t);
>
> and I was supposing this implementation being quite a
> requirement. Looking at that code I can deduce that:
>
>   - Elements currently in the vector will be
>     destroyed, and won't just become assigned
>     with copies of t, not even the first n.
>
>   - I'm expecting linear complexity on size()+n
>
>   - I'm expecting and a certain behaviour in respect
>     to reallocations. For example if capacity()>=n
>     then no reallocation will occur during the fill.
>
>   - I can assume that elements will be first destroyed
>     and then created (this can be important if my
>     element are huge or if both size() and n are big
>     numbers, or if I've a max limit on the number of
>     elements of a certain class).
>
>   - I know that the operation won't give me
>     the succeed-or-nop guarantee.
>
> Are all those deduction just "wild guesses" as even a
> conforming version may have used instead of that code
> something like...

Those all seem to be valid deductions to me. Those all fall under the
category of observable effects; an implementation that violates any of
those is inconsistent with 17.3.1.2p6.

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

Reading "Effective STL" i found a mention to the fact that to
insert a new element in a std::map it's better to use the
insert method instead of operator[].

I don't agree with that vision, at least froma philosophical
point of view.

Assuming...

  struct V
  {
    V(Y);
    V& operator=(const Y&);
  };

  std::map<K,V> m;

When I write

  m[k1] = y1;

I only see that a "const K&" value is passed to operator[] to
look for the associated node, and such a node should be
created with the default constructor if not present.
Once found (created) the node the mapped_type part of it is
returned by reference so the assignment operator can do its
job. In other words I see no *need* for temporary V objects
but just an in-place creation inside the container of a
default V object.

Using map::insert, on the other side...

  m.insert(std::map<K,V>::value_type(k1,y1));

requires at least the creation of *two* temporary V objects:
the first is used to create a V from y1 and then this object
is used to create a *temporary* value_type object required
by the insert. No final assignment is done but there are two
extra instances of V and even copies of K (this because
insert accepts a "const value_type&" but a value_type is
a pair of *values* and not of *references*).

This from a philosophical point of view...

However, making some test I found that even the operator[]
version creates two temporaries with all the C++ compilers
I checked out. So the use of insert was indeed more efficient
(at least the assignment call isn't performed).

Looking at the draft I have I found this rather disappointing
description for map::operator[]

  T& operator[](const key_type& x);

  Returns:
    (*((insert(make_pair(x, T()))).first)).second.

looking at which I've the clear impression that the two
temporaries for T and a copy for x are *required*.
Actually that expression looks even worse... I made
an experiment and using the expression described in the
draft there are *three* temporaries involved and things
are back to the two I've measured with operator[] only if
instead of using make_pair automatic deduction of types
the template parameters are explicit.
I suspect the problem being that make_pair if passed
two expressions of type (const key_type&,const mapped_type&)
creates a pair<key_type,mapped_type> that is missing
the const qualifier on the first member... so another
pair-to-pair conversion is needed (hence another copy).

Is there any reason for which the standard has been so
clear about *how* operator[] must be implemented (i.e.
inefficent) instead of just saying *what* should have
been the behaviour (returning a reference to an existing
or newly default-created T object) ?

Of course an efficient version of operator[] that
just creates the new default V object in the container
and that doesn't require copying around the key cannot
be based on insert as it's the prototype of that method
requiring a const T& and the fact that pairs have been
used that force all those duplications and useless
default creations.

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

agriff@tin.it (Andrea Griffini) writes:

> to insert a new element in a std::map it's better to use the insert
> method instead of operator[].

You might want to check out a similar discussion=B9 from May 2000, along
with the follow-ups from John Potter.


Footnotes:=20
=B9 http://groups.google.com/groups?hl=3Den&safe=3Doff&th=3D2b9bca2c4fb99=
79c,84&seekm=3Dsv7ld1yshf.fsf%40hodge.primus.com#p

--=20
Steven E. Harris        :: seharris@raytheon.com
Raytheon                :: http://www.raytheon.com

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

On Mon, 20 Aug 2001 20:47:12 GMT, "Steven E. Harris"
<seharris@raytheon.com> wrote:

>agriff@tin.it (Andrea Griffini) writes:
>
>> to insert a new element in a std::map it's better to use the insert
>> method instead of operator[].
>
>You might want to check out a similar discussion=B9 from May 2000, along
>with the follow-ups from John Potter.

Thank you for the pointer. I've read the thread and it's
interesting but my question was different.

The standard explain map::operator[] using a C++
expression that I think is inherently quite inefficient:

  T& operator[](const key_type& x);

  Returns:
    (*((insert(make_pair(x, T()))).first)).second.

In my opinion this expression requires at *least* three
temporary T objects (excluding the eventual fourth one
that will be the one in the container if it's not
already present). Also requires at least two copies of
the key (excluding the construction of the final key in
the container if not present).

I think that all these copies are needed because:

 - A default T object is constructed explictly

 - A pair has to be built and is a pair of values, not
   of references (you can't create a std::pair of
   references) so this requires at least copying that
   default constructed T object and the key

 - The pair built by make_pair is of the wrong type
   due to the rules of implicit template parameter
   deduction. So another pair must be created using
   a template conversion from pair<key_type,T> to
   pair<const key_type,T>

I don't think that a compiler is allowed to optimize
any of those objects. For example make_pair is a
function and the returned pair is created after
entering the function but the parameters must exist
*before* of that moment so the parameter can't be
constructed "in-place" in the pair (I've read that
temporaries can be constructed in-place in by-value
parameters or in the return value but this seems to
me quite different because of the explicit timeline).

Does the presence of this description in the standard
actually require an implementer to make all those
copies ? Must actually operator[] call insert ?

(the way the *interface* of insert is defined implies
in my opinion an inefficient operation in this context).

Why this explicit description of an implementation
instead of just telling that operator[] must return
a reference to the T object identified by the key
(eventually adding it to the container if not present) ?

Given enough freedom operator[] could be made as
efficient as theoretically possible, requiring no
copying or object creation/destruction at all if
the element is already in the map...

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

In article <3b843437.7560189@news.interbusiness.it>, Andrea Griffini
<agriff@tin.it> wrote:

| Given enough freedom operator[] could be made as
| efficient as theoretically possible, requiring no
| copying or object creation/destruction at all if
| the element is already in the map...

I think some implementations have taken this freedom.... at least
Metrowerks has, and maybe others.  The Metrowerks implementation of
operator[] forwards to a private call named find_or_insert.  This
method only default constructs the value_type if it can not find one.

That being said, I believe the advice given in ESTL is not quite
correct.  I would advise using operator[] only when readability and/or
convenience is the formost importance.  When (portable) efficiency is
paramount, use insert or find, depending on whether you expect to
insert or update respectively.

Metrowerks strives to make operator[] the same expense as find if the
key already exists, but the standard obviously does not guarantee that
performance (actually discourages it).  So YMMV.

--
Howard Hinnant
Metrowerks

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

"Andrea Griffini" <agriff@tin.it> wrote in message
news:3b843437.7560189@news.interbusiness.it...
> The standard explain map::operator[] using a C++
> expression that I think is inherently quite inefficient:
>
>   T& operator[](const key_type& x);
>
>   Returns:
>     (*((insert(make_pair(x, T()))).first)).second.
[snip]
>  - A pair has to be built and is a pair of values, not
>    of references (you can't create a std::pair of
>    references) so this requires at least copying that
>    default constructed T object and the key
>
>  - The pair built by make_pair is of the wrong type
>    due to the rules of implicit template parameter
>    deduction. So another pair must be created using
>    a template conversion from pair<key_type,T> to
>    pair<const key_type,T>
>

make_pair() is bogus when dealing with a map. I'm sure
that that using map<..>::value_type would allay some
of your concerns.

marco


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

On Thu, 23 Aug 2001 17:46:58 GMT, Howard Hinnant
<hinnant@antispam.metrowerks.com> wrote:

>I think some implementations have taken this freedom....
>at least Metrowerks has, and maybe others. The Metrowerks
>implementation of operator[] forwards to a private call
>named find_or_insert. This method only default constructs
>the value_type if it can not find one.

Indeed you can't get optimal if you want to use insert.
The need of copies is tied to the *interface* of that
standard method.

g++ implementation uses lower_bound and then calls
insert only if no match is found so their implementation
is optimal if the element is already present.

BCC55 and VC++ just saved one temporary and one copy of
the key by not using make_pair wrong implicit template
parameter deduction (is that acceptable as standard
conforming ?).

Anyway if many are ignoring the bad implementation in
the standard then there's a hope that next standard
won't require that ... right ?

Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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

On Thu, 23 Aug 2001 18:11:43 GMT, "Marco Dalla Gasperina"
<marcodg@home.com> wrote:

>make_pair() is bogus when dealing with a map. I'm sure
>that that using map<..>::value_type would allay some
>of your concerns.

In that case there will be just two(*) temporary T
objects and the copy construction of a temporary
key_type object (supposing the element is already in
the map). And you can't get better if you want to
use the insert method call as the reasons for this
inefficiency is in its *interface*. Unless you happen
to have handy a pair<const key_type,mapped_type> then
these temporaries are unavoidable (and it's quite
unlikely that you happen having such a useless object
already available).

This solution (basically just removing the wrong
make_pair) is what I found implemented in BCC55 and
VC++. It's still not optimal, but better.

g++ 2.95 is even better and uses lower_bound to
search the element, if that is present the no
temporaries are needed at all (optimal). However
if that's not the case then insert is called
(suboptimal and requires the same two T temporaries
and copying the key -- in addition to the creation
of the final pair held in the container).

None of these solution is standard-conforming as
also isn't the one from MetroWerks (optimal and not
based on insert), if I understood correctly.

Andrea

(*)
  Even using directly map<...>::value_type(key,T())
  I think that the T object must exist in order to
  be passed to the constructor of pair as a const
  reference. Does the standard allow in this case
  to just create the T object in place inside the
  pair ? That would surprise me as in the pair
  constructor there is a quite explicit call to
  the copy constructor of T.

--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

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