Ed Brey wrote in message <8bd9m1$fhi1@interserv.etn.com>...
>In the associative container requirements in 23.1.2/7, a.clear() has
>complexity "log(size()) + N". However, the meaning of N is not defined.
>
>Proposed Resolution:
>
>Change the complexity of a.clear() to "linear".
>
>Rationale:
>
>If N were to be defined, clearly it would be defined as size().  This would
>cause the complexity to be O(log(size()) + size()), which is equal to
>O(size()).

Hi Ed

Maybe I'm dumb, maybe I'm stupid and maybe I'm ignorant. However to me it
seems that N is "big-Oh"-notation is intended to be constant, and thus
independent of the size of the container.

Peter Koch Larsen



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

PETER KOCH LARSEN wrote:
>
> Ed Brey wrote in message <8bd9m1$fhi1@interserv.etn.com>...
> >In the associative container requirements in 23.1.2/7, a.clear() has
> >complexity "log(size()) + N". However, the meaning of N is not defined.
> >
> >Proposed Resolution:
> >
> >Change the complexity of a.clear() to "linear".
> >
> >Rationale:
> >
> >If N were to be defined, clearly it would be defined as size().  This would
> >cause the complexity to be O(log(size()) + size()), which is equal to
> >O(size()).
>
> Hi Ed
>
> Maybe I'm dumb, maybe I'm stupid and maybe I'm ignorant. However to me it
> seems that N is "big-Oh"-notation is intended to be constant, and thus
> independent of the size of the container.

That would imply that the leading term of the complexity requirement is
log(size()). That isn't feasible. It must, at a minimum, perform
per-element destruction, so the best it can be is linear. a.clear() is
defined as being equivalent to erase(a.begin(),a.end()), which  is
defined as having a complexity of log(size())+N, where N in this case is
the distance from a.begin() to a.end(). In other words,
log(size())+size().

I don't think that the definition of 'N' in the description of clear()
is missing; I think it's intended to be inherited from the definition of
'N' in the description of erase().

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

[ moderator's note: forwarded to C++ committee. -sdc ]

In the associative container requirements in 23.1.2/7, a.clear() has
complexity "log(size()) + N". However, the meaning of N is not defined.

Proposed Resolution:

Change the complexity of a.clear() to "linear".

Rationale:

If N were to be defined, clearly it would be defined as size().  This would
cause the complexity to be O(log(size()) + size()), which is equal to
O(size()).




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