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

>geert@cs.uu.nl (Geert-Jan Giezeman) wrote:
>
>: The point is that when the standard states something
>: about amortized time, it should also state over which sequences the times
>: are amortized. It should not make us guess.
>
>Good point.  How about:
>
>The reference implementation of associative containers uses a
>red-black tree.  The complexity requirements of all operations
>are that they be as good as that data structure.  This standard
>imposes no requirement that a balanced binary search tree be
>used in the implementation of associative containers and
>encourages implementers to use a data structure which is better
>for some operations with no degradation of other operations.
>
>Would that remove the guessing? :)

No.  Saying that "the reference implementation of associative containers uses
a red-black tree." does not nail it down well enough.  There might well be
two implementations that both use a red-black tree but that nevertheless
have different complexities for a given operation.

--
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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

geert@cs.uu.nl (Geert-Jan Giezeman) wrote:

: I don't think it makes sense to state anything about the (amortized) time
: complexity of a single iteration step, if the only sequence allowed is the
: complete traversal. Then it would make more sense to state only that a
: complete traversal takes O(N) time. Perhaps it is possible to allow more
: sequences: starting with the iterator returned by begin() you could be
: allowed to have any number of ++ operations (as long as the iterator is
: valid). Then amortized time makes sense. I'm not sure if this can be
: guaranteed by associative container implementations without forward and
: backward pointers, though.

Good points.

It can recursively.  The worst point is the descent from the root to
the left most node of the right subtree which is lgN.  Prior to that, we
had N {2 * N/2}.  (N + lgN) / (N/2 + 1) < 3.  Because of the constant
jump to begin we get enough saving to amortize the traversal to any
point.  Advance(s.begin(), n) is linear in n.

: Anyway, it is not clear what is natural. For me it would also be natural to
: be allowed to mix -- and ++ (or it would be, if I had no knowledge of
: balanced trees). The point is that when the standard states something
: about amortized time, it should also state over which sequences the times
: are amortized. It should not make us guess.

Good point.  How about:

The reference implementation of associative containers uses a
red-black tree.  The complexity requirements of all operations
are that they be as good as that data structure.  This standard
imposes no requirement that a balanced binary search tree be
used in the implementation of associative containers and
encourages implementers to use a data structure which is better
for some operations with no degradation of other operations.

Would that remove the guessing? :)

: I guess coming up with a good specification of those sequences would be
: hard and probably not very interesting to most users of containers.  But I
: would be happy if the requirement for bidirectional iterator operations was
: relaxed to O(log N) time (N being the size of the underlying sequence) and
: a requirement that iterating over a complete container takes O(N) time.
: Probably, this has no consequence for the time complexity of the algorithms
: in the STL. Of course, list can state that its iterators have constant
: complexity operations.

But it doesn't state that.  Not even random access iterators have
constant time operations.  Even they are amortized over "quess what."

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Stanley Friesen [Contractor] wrote:
>
> In article <SFg73.48590$OL.882676@newscene.newscene.com>,
> John Potter <jpotter@falcon.lhup.edu> wrote:
> >stanley@west.sun.com (Stanley Friesen [Contractor]) wrote:
> >: If it is meaningless, then why did the writers of the standard put so
> >: much effort into distinguishing the two cases? (amortized and
> >: non-amortized).
> >
> >Well yes, I read:  const == worst case O(1) and amortized const ==
> >average case O(1).  But, Valentin has a point that if it is so
> >important, why is it not specified?  Is it intuitively obvious to
> >the most casual observer?
>
> I think it is rather that the terminology is considered standard in the
> CS industry, and so need not be defined further.  [The treatment certainly
> follows fairly typical complexity analysis procedures from theoretical
> CS]

Then I am sure that you can give me a reference to such classical
literature.

Standards should rely resonnably on literature: ie, don't try
to redefine the world, but don't rely on local idioms or habits.

--

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

geert@cs.uu.nl (Geert-Jan Giezeman) wrote:

: In <FD0vHC.C8K@research.att.com> ark@research.att.com (Andrew Koenig) writes:

: >If we define the complexity of this loop as the number of vector elements
: >copied, then saying that the amortized complexity of the call to push_back
: >is O(1) is equivalent to saying that there exists a constant K such that
: >the total number of elements copied in the entire loop is always less
: >than K * n.  This is a more precise, and probably stronger, statement
: >than one would typically make about averages.


: In the book Introduction to Algorithms by Cormen, Leiserson and Rivest, we
: read:

:   In an amortized analysis, the time required to perform a sequence of data
:   structure operations is averaged over all the operations performed. ...
:   Amortized analysis differs from the average case analysis in that
:   probability is not involved; an amortized analysis guarantees the average
:   performance of each operation in worst case.

Thank you for that which also makes Andy's point clear.

: A weak point in the standard is that is does not make very clear what kind
: of sequences may be involved. For instance, the associative containers have
: bidirectional iterators. So, operator++ and operator-- take amortized
: constant time. However, if arbitrary sequences are allowed, this would
: imply that each individual increment and decrement must be constant time.
: Otherwise we could have an arbitrary long sequence of
: ++it; --it; ++it; --it; ++it; --it;
: If ++it can take time proportional to say log(size()), then there is no way
: to amortize this sequence to constant time per operation.

Would it not be fair to assume that the sequence involved could only
contain the operation?  In the above, there was no doubt that push_back
is amortized constant time over a sequence of push_back operations.  It
seems natural when saying that operator++ is amortized constant time
that the sequence is a complete traversal of the data structure.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <37627B4C.534A@wanadoo.fr>,
Valentin Bonnard  <Bonnard.V@wanadoo.fr> wrote:
>> I think it is rather that the terminology is considered standard in the
>> CS industry, and so need not be defined further.  [The treatment certainly
>> follows fairly typical complexity analysis procedures from theoretical
>> CS]
>
>Then I am sure that you can give me a reference to such classical
>literature.

If you will give me three or four weeks to find time to go to the library
and look for it.  (As I do not use it routinely, I do not have such
material immediately to hand).
>
>Standards should rely resonnably on literature: ie, don't try
>to redefine the world, but don't rely on local idioms or habits.
>
Agreed.

The literature on algorithmic theory covers the issues involved in
complexity analysis is considerable detail.
---
[ 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 <FoA83.38443$wk2.553149@newscene.newscene.com> jpotter@falcon.lhup.edu (John Potter) writes:

>geert@cs.uu.nl (Geert-Jan Giezeman) wrote:

>: In the book Introduction to Algorithms by Cormen, Leiserson and Rivest, we
>: read:
>
>:   In an amortized analysis, the time required to perform a sequence of data
>:   structure operations is averaged over all the operations performed. ...
>:   Amortized analysis differs from the average case analysis in that
>:   probability is not involved; an amortized analysis guarantees the average
>:   performance of each operation in worst case.
>
>Thank you for that which also makes Andy's point clear.
>
>: A weak point in the standard is that is does not make very clear what kind
>: of sequences may be involved. For instance, the associative containers have
>: bidirectional iterators. So, operator++ and operator-- take amortized
>: constant time. However, if arbitrary sequences are allowed, this would
>: imply that each individual increment and decrement must be constant time.
>: Otherwise we could have an arbitrary long sequence of
>: ++it; --it; ++it; --it; ++it; --it;
>: If ++it can take time proportional to say log(size()), then there is no way
>: to amortize this sequence to constant time per operation.
>
>Would it not be fair to assume that the sequence involved could only
>contain the operation?  In the above, there was no doubt that push_back
>is amortized constant time over a sequence of push_back operations.  It
>seems natural when saying that operator++ is amortized constant time
>that the sequence is a complete traversal of the data structure.

I don't think it makes sense to state anything about the (amortized) time
complexity of a single iteration step, if the only sequence allowed is the
complete traversal. Then it would make more sense to state only that a
complete traversal takes O(N) time. Perhaps it is possible to allow more
sequences: starting with the iterator returned by begin() you could be
allowed to have any number of ++ operations (as long as the iterator is
valid). Then amortized time makes sense. I'm not sure if this can be
guaranteed by associative container implementations without forward and
backward pointers, though.

Anyway, it is not clear what is natural. For me it would also be natural to
be allowed to mix -- and ++ (or it would be, if I had no knowledge of
balanced trees). The point is that when the standard states something
about amortized time, it should also state over which sequences the times
are amortized. It should not make us guess.

I guess coming up with a good specification of those sequences would be
hard and probably not very interesting to most users of containers.  But I
would be happy if the requirement for bidirectional iterator operations was
relaxed to O(log N) time (N being the size of the underlying sequence) and
a requirement that iterating over a complete container takes O(N) time.
Probably, this has no consequence for the time complexity of the algorithms
in the STL. Of course, list can state that its iterators have constant
complexity operations.
---
[ 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 <SFg73.48590$OL.882676@newscene.newscene.com>,
John Potter <jpotter@falcon.lhup.edu> wrote:
>stanley@west.sun.com (Stanley Friesen [Contractor]) wrote:
>: If it is meaningless, then why did the writers of the standard put so
>: much effort into distinguishing the two cases? (amortized and
>: non-amortized).
>
>Well yes, I read:  const == worst case O(1) and amortized const ==
>average case O(1).  But, Valentin has a point that if it is so
>important, why is it not specified?  Is it intuitively obvious to
>the most casual observer?

I think it is rather that the terminology is considered standard in the
CS industry, and so need not be defined further.  [The treatment certainly
follows fairly typical complexity analysis procedures from theoretical
CS]
>
>: It is fairly clear, just from the care with which the word is used or not,
>: that, to the authors, it meant something.
>
>Not enough care IMHO.  Iterators are the counter example.  All
>operations must be doable in amortized const time.  For ++, I
>expect deque, vector, list to be const but can't find that care
>in the standard.

I don't have the standard handy to cross-check this, but I do seem to remember
some subtle distinction in this area in the standard, I am just not sure
where it is.
---
[ 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 <FD0vHC.C8K@research.att.com> ark@research.att.com (Andrew Koenig) writes:

>> > Amortized cost has a fairly
>> > well-understood meaning;
>
>> Unknown to me, but I am want to learn.

>Perhaps this example will make the difference clearer.  Suppose I
>execute the following code:
>
> vector<int> v;  // initially empty
> for (int i = 0; i < n; ++i)
>  v.push_back(i);
>
>If we define the complexity of this loop as the number of vector elements
>copied, then saying that the amortized complexity of the call to push_back
>is O(1) is equivalent to saying that there exists a constant K such that
>the total number of elements copied in the entire loop is always less
>than K * n.  This is a more precise, and probably stronger, statement
>than one would typically make about averages.


In the book Introduction to Algorithms by Cormen, Leiserson and Rivest, we
read:

  In an amortized analysis, the time required to perform a sequence of data
  structure operations is averaged over all the operations performed. ...
  Amortized analysis differs from the average case analysis in that
  probability is not involved; an amortized analysis guarantees the average
  performance of each operation in worst case.

A weak point in the standard is that is does not make very clear what kind
of sequences may be involved. For instance, the associative containers have
bidirectional iterators. So, operator++ and operator-- take amortized
constant time. However, if arbitrary sequences are allowed, this would
imply that each individual increment and decrement must be constant time.
Otherwise we could have an arbitrary long sequence of
++it; --it; ++it; --it; ++it; --it;
If ++it can take time proportional to say log(size()), then there is no way
to amortize this sequence to constant time per operation.



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

ark@research.att.com (Andrew Koenig) wrote:

: In article <375D3ABB.1FF1@wanadoo.fr>,
: Valentin Bonnard  <Bonnard.V@wanadoo.fr> wrote:

: > > Amortized cost has a fairly
: > > well-understood meaning;

: > Unknown to me, but I am want to learn.

: > > my understanding is that it is the average cost
: > > over a typical statistical universe of calling contexts. Many of the
: > > standard library's requirements are impossible to achieve, or at least
: > > excessively expensive to achieve, unless they refer to amortized costs
: > > rather than applying exactly to every call.

: > That's average complexity to me (as opposed to maximum = worst case
: > complexity).

: Indeed.

: Perhaps this example will make the difference clearer.  Suppose I
: execute the following code:

:  vector<int> v;  // initially empty
:  for (int i = 0; i < n; ++i)
:   v.push_back(i);

: If we define the complexity of this loop as the number of vector elements
: copied, then saying that the amortized complexity of the call to push_back
: is O(1) is equivalent to saying that there exists a constant K such that
: the total number of elements copied in the entire loop is always less
: than K * n.  This is a more precise, and probably stronger, statement
: than one would typically make about averages.

total copies for n push_back < K * n

average copies for n push_back = total copies for n push_back / n
   < K * n / n = K

Sounds the same to me.  Anyway, we know that a push_back may make
size copies but for large n the average will be constant.  The
result is that the growth function must be of the form m * cap + b
with m > 1.  The usual implementation is 2 * cap with a base case
to cover growth from 0.  2 * cap + 1 is about the same and has no
special cases.  This gives K = 3.

The restriction in the standard prohibits 1 * cap + 10 because there
is no K.  With this function, at n = 8192, K has reached 410 and
grows without bound.  The standard allows 1.001 * cap + 1 because it
has a K of 1002.  At 8192 K has reached 833 but there is a limit to
its growth.  The standard also allows 1.000000001 * cap + 10 because
it has a K of 100000002 and is for all practical purposes the same
as the disallowed one above.

The standard essentially places no limits on the implementation
and offers no assurances to the user.  In Valentin's words, amortized
constant is meaningless; however, without amortized the constant would
be impossible and with nothing cap + 1 would be allowed and we would
have total copies < K * n * n.  From a practical view, any reasonable
implementation will use 2 * cap or some closely related function which
might save space at a slight increase in K.

The statement that started this was that ++ for an associative
container iterator needed to be constant.  Without amortized, that
is possible but adds space to each node and time in the insert/delete
operations to maintain the extra pointers.  With amortized, it allows
some operations to be lgN but the average is still constant at 2.  It
is then an implementer's choice on the space/time tradeoff.  OTOH, the
requirement on begin is constant which forces an implementation to
maintain a path to the leftmost node else it would be lgN.  This is a
much smaller space and time requirement.  Of course, there is nothing
to amortize begin over.

There are many places where amortized const for generalities is not
improved to const for specifics.  One could conclude that amortized
was overused but I don't see it as meaningless.  The work to nail down
all of the complexities may not be worth the effort.  I'm sure that
there are cases which seem obviously constant to me yet have reasonable
implementations which could only provide amortized constant.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter wrote:

> James Kuyper <kuyper@wizard.net> wrote:
>
> : Valentin Bonnard wrote:
> : >
> : > The next node in the tree is just one pointer away; every node has
> : > next and previous pointers. You may like it or not, but this is one
> : > of teh roots of the STL.
>
> : Expanding on that statement:

(James: I didn't expanded my claim precisely not to get
into such arguments --

> Which is incorrect.

-- too late, let the war begin)

> : Associative containers are required to have bidirectional iterators.
> : Bidirectional iterators are required to provide constant-time ++ and
> : --.
>
> Missing a key word, "amortized" constant time.

My eyes to educated not to see it anymore.

> : Therefore, determining the next node cannot be a log2(n)
> : operation.
>
> It can as long as a complete traversal looks like constant time.

Unless you can find support for your claims in the standard,
I will consider to be pure nonsense (sorry for the repetition).

If you can back-up these claims, then I'll just say that
the standard itself is broken.   ;-)

(In any case, I won't {admit that I am wrong}.)
({} used to force the parsing the above sentence)

Nowhere in the standard the meaning of complexity requirements
is defined, so all usual when the standard doesn't say everything,
I have looked at the SGI documentation, which says:

: All container or iterator complexity specifications refer to
: amortized complexity.

I personnaly take the opposite view that `` amortized '' is
a nice looking but absolutly meaningless word that I always
ignore.

In any case I would immediatly send a bug report for any
implementation for which I would discover that it doesn't
has next/previous pointers for nodes in the tree used for
sorted associative container.

> Check your favorite rb-tree implementation sitting under the
> associative containers.

I did, I cannot find the next/prev links.  :-(

I hope it's just me.

[ This is a newsgroup post and potential (maybe I missed
something) bugreport at the same time. ]

--

Valentin Bonnard
---
[ 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:
>
> John Potter wrote:
>
> > James Kuyper <kuyper@wizard.net> wrote:
> >
> > : Valentin Bonnard wrote:
> > : >
> > : > The next node in the tree is just one pointer away; every node has
> > : > next and previous pointers. You may like it or not, but this is one
> > : > of teh roots of the STL.
> >
> > : Expanding on that statement:
>
> (James: I didn't expanded my claim precisely not to get
> into such arguments --

Well, I did expand upon it, because your version could give the false
impression that the standard actually goes into that level of detail in
specifying how the standard library is implemented.

....
> > Missing a key word, "amortized" constant time.
>
> My eyes to educated not to see it anymore.

It's there, it's meaningful, and it's important; I'd recommend
uneducating your eyes. It's not defined within the standard, which but
then the meaning of complexity isn't either - for example, there's
nothing in the standard to indicate that complexity measures are
conventionally described in terms of the highest order term of a
power/log series, without it's coefficient. Amortized cost has a fairly
well-understood meaning; my understanding is that it is the average cost
over a typical statistical universe of calling contexts. Many of the
standard library's requirements are impossible to achieve, or at least
excessively expensive to achieve, unless they refer to amortized costs
rather than applying exactly to every call.

....
> > It can as long as a complete traversal looks like constant time.
>
> Unless you can find support for your claims in the standard,
> I will consider to be pure nonsense (sorry for the repetition).

Section 24.1, p8: "All of the categories of iterators require only those
functions that are realizable for a given category in constant time
(amortized). Therefore, requirement tables for the iterators do not hav
a complexity column."

That doesn't even say that the required functions are required to be
realized using constant time (amortized) algorithms; it merely mentions
that they can be. That's probably defective wording. The intent seems
clearly to have been to require constant time (amortized) algorithms.
There's no requirement for constant-time iterator implementation that
doesn't include the word "amortized".

....
> In any case I would immediatly send a bug report for any
> implementation for which I would discover that it doesn't
> has next/previous pointers for nodes in the tree used for
> sorted associative container.

"sorted associative"? Associative containers must support access in sort
order, but they aren't required to actually be sorted.


[ 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 <375A0986.1E6F@wanadoo.fr>, Valentin Bonnard
<Bonnard.V@wanadoo.fr> wrote:

> > It can as long as a complete traversal looks like constant time.
>
> Unless you can find support for your claims in the standard,
> I will consider to be pure nonsense (sorry for the repetition).
>
> If you can back-up these claims, then I'll just say that
> the standard itself is broken.   ;-)
>
> (In any case, I won't {admit that I am wrong}.)
> ({} used to force the parsing the above sentence)

24.1 - Iterator requirements [lib.iterator.requirements]
....
-8- All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized). Therefore,
requirement tables for the iterators do not have a complexity column.

-Howard


[ 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 <Bonnard.V@wanadoo.fr> wrote:

: John Potter wrote:

: > James Kuyper <kuyper@wizard.net> wrote:
: >
: > : Valentin Bonnard wrote:
: > : >
: > : > The next node in the tree is just one pointer away; every node has
: > : > next and previous pointers. You may like it or not, but this is one
: > : > of teh roots of the STL.
: >
: > : Expanding on that statement:

: (James: I didn't expanded my claim precisely not to get
: into such arguments --

: > Which is incorrect.

: -- too late, let the war begin)

I must have stumbled into an old war which makes no sense to me.

: > : Associative containers are required to have bidirectional iterators.
: > : Bidirectional iterators are required to provide constant-time ++ and
: > : --.
: >
: > Missing a key word, "amortized" constant time.

: My eyes to educated not to see it anymore.

It means alot to me.

: > : Therefore, determining the next node cannot be a log2(n)
: > : operation.
: >
: > It can as long as a complete traversal looks like constant time.

: Unless you can find support for your claims in the standard,
: I will consider to be pure nonsense (sorry for the repetition).

: If you can back-up these claims, then I'll just say that
: the standard itself is broken.   ;-)

: (In any case, I won't {admit that I am wrong}.)
: ({} used to force the parsing the above sentence)

OK.

: Nowhere in the standard the meaning of complexity requirements
: is defined, so all usual when the standard doesn't say everything,
: I have looked at the SGI documentation, which says:

Hum.  I think that I know what it means without definition like
many of the words used in the standard.  Checking my dictionary
for amortized, it does not really contain my understanding.  You
may have a point or maybe I should be looking in a technical
standard which describes its meaning in complexity rather than
banking.  If amortized means averaged, is it obvious what it is
averaged over?  Should it always state amortized constant time
over X?

: : All container or iterator complexity specifications refer to
: : amortized complexity.

That is a cop-out.  Constant is amortized constant which allows them
to say nothing much better than the standard.  I expect pop_back to
be constant for all sequences and push_back to be constant for
list but amortized constant for vector.  I think the standard says
that since it says amortized constant for sequences and modifies
that to constant for list.

: I personnaly take the opposite view that `` amortized '' is
: a nice looking but absolutly meaningless word that I always
: ignore.

: In any case I would immediatly send a bug report for any
: implementation for which I would discover that it doesn't
: has next/previous pointers for nodes in the tree used for
: sorted associative container.

: > Check your favorite rb-tree implementation sitting under the
: > associative containers.

: I did, I cannot find the next/prev links.  :-(

: I hope it's just me.

: [ This is a newsgroup post and potential (maybe I missed
: something) bugreport at the same time. ]

I don't see any smily and the omission does not seem to be an
accident.

I read "constant" as a worst case complexity and "amortized constant"
as average case complexity.  It is of practical importance to know
that the average time for vector<>::push_back is likely to be better
than the average time for list<>::push_back.  It is also important
to know that the time will be relatively consistent for list but not
for vector.  If there are worst case requirements and there is no
known upper bound on size, vector is not usable.

I don't think that a bugreport would be taken seriously.  Maybe a
defect report on the standard which allows you to think that each
increment of a map::iterator must be relatively constant with no
regard for the container size while I read it to only expect the
time for a total traversal to be linear in container size.

Iterators are the worst part.  All operations are amortized constant
time or not provided.  But there are no details for specific
iterators such as map::iterator or vector::iterator.

In the absense of standard sense, I will use common sense and not
bother implementers with bugreports about common practice versions
of well known data structures.

I really do not understand this "war".  I understand style wars and
usually avoid them, but this is not the same.  I can understand why
people differ on style and usually accept almost any consistent use.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> Valentin Bonnard wrote:
> >
> > John Potter wrote:
> >
> > > James Kuyper <kuyper@wizard.net> wrote:
> > >
> > > : Valentin Bonnard wrote:

> > > Missing a key word, "amortized" constant time.
> >
> > My eyes to educated not to see it anymore.
>
> It's there, it's meaningful, and it's important; I'd recommend
> uneducating your eyes.

Only when I'll have the meaning...

> Amortized cost has a fairly
> well-understood meaning;

Unknown to me, but I am want to learn.

> my understanding is that it is the average cost
> over a typical statistical universe of calling contexts. Many of the
> standard library's requirements are impossible to achieve, or at least
> excessively expensive to achieve, unless they refer to amortized costs
> rather than applying exactly to every call.

That's average complexity to me (as opposed to maximum = worst case
complexity).

...which shows again the need for a definition of the notion
of complexity

> "sorted associative"? Associative containers must support access in sort
> order, but they aren't required to actually be sorted.

???

(SortedAssociativeCOntainer is from the SGI terminology)

--

Valentin Bonnard


[ 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 <375A0986.1E6F@wanadoo.fr>,
Valentin Bonnard  <Bonnard.V@wanadoo.fr> wrote:
>
>I personnaly take the opposite view that `` amortized '' is
>a nice looking but absolutly meaningless word that I always
>ignore.

If it is meaningless, then why did the writers of the standard put so
much effort into distinguishing the two cases? (amortized and non-amortized).

It is fairly clear, just from the care with which the word is used or not,
that, to the authors, it meant something.


[ 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 <375D3ABB.1FF1@wanadoo.fr>,
Valentin Bonnard  <Bonnard.V@wanadoo.fr> wrote:
>
>James Kuyper wrote:
>> my understanding is that it is the average cost
>> over a typical statistical universe of calling contexts. Many of the
>> standard library's requirements are impossible to achieve, or at least
>> excessively expensive to achieve, unless they refer to amortized costs
>> rather than applying exactly to every call.
>
>That's average complexity to me (as opposed to maximum = worst case
>complexity).
>
Nontheless, what you call "average complexity", the standard calls "amortized".

[I suspect there may be a subtle distinction in how the computation
of the "average" is done that is implied by the use of "amortized"]

>...which shows again the need for a definition of the notion
>of complexity
>
In algorithm theory there is a standard definition of complexity.  It
is clear to me that the standard intends to invoke this theoretical
definition.
---
[ 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              ]

stanley@west.sun.com (Stanley Friesen [Contractor]) wrote:

: In article <375A0986.1E6F@wanadoo.fr>,
: Valentin Bonnard  <Bonnard.V@wanadoo.fr> wrote:
: >
: >I personnaly take the opposite view that `` amortized '' is
: >a nice looking but absolutly meaningless word that I always
: >ignore.

: If it is meaningless, then why did the writers of the standard put so
: much effort into distinguishing the two cases? (amortized and
: non-amortized).

Well yes, I read:  const == worst case O(1) and amortized const ==
average case O(1).  But, Valentin has a point that if it is so
important, why is it not specified?  Is it intuitively obvious to
the most casual observer?

: It is fairly clear, just from the care with which the word is used or not,
: that, to the authors, it meant something.

Not enough care IMHO.  Iterators are the counter example.  All
operations must be doable in amortized const time.  For ++, I
expect deque, vector, list to be const but can't find that care
in the standard.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]