Inconsistent definition of erase() ?
Philip Brabbin
A while ago, I noticed that erase() is defined differently for
sequences and associative containers, in that there's a version which
returns an iterator to the next element for sequences but not for
associative containers.
I recently found out that originally both versions had void return
type, and the behaviour for sequences was extended to return the next
iterator. Does anybody know the reason for this ? I can't immediately
think why the behaviour can't be extended for associative containers as
well.
- Phil Brabbin
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]
Valentin Bonnard
> A while ago, I noticed that erase() is defined differently for
> sequences and associative containers, in that there's a version which
> returns an iterator to the next element for sequences but not for
> associative containers.
Correct
> I recently found out that originally both versions had void return
> type, and the behaviour for sequences was extended to return the next
> iterator. Does anybody know the reason for this ? I can't immediately
> think why the behaviour can't be extended for associative containers as
> well.
I think it's a shame not to have extended AssocCont::erase the
same way. I have heard some nonsensical arguments against
AssocCont::erase returning an iterator but nothing serious.
Note that for associative containers you cannot write:
it = m.erase (it);
but you can write
m.erase (it++);
with the same effects.
BTW, erase in the Dinkumware returns an iterator for
associative containers.
--
Valentin Bonnard
---
Ed Brey
news:375710...@wanadoo.fr...
>
> I think it's a shame not to have extended AssocCont::erase the
> same way. I have heard some nonsensical arguments against
> AssocCont::erase returning an iterator but nothing serious.
What do you think of the reasoning that ++it is often a more expensive
operation for an associative container than for a sequence container, and so
for an associative erase where the return value is not used, there would be
a performance penalty if it were provided?
I'm thinking of the situation in a binary tree when ++it requires walking
all the way up or down a tree, which would make ++it a log2(n) operation.
Of course, this is worst case, and for most values of it, the walking would
be much less. Still, overall there may be enough overhead in incrementing
that erase shouldn't take the time to do an increment just to have it be
thrown away.
Assuming the increment overhead is significant, the next question is whether
an optimizer would see that the return value is not used and avoid
performing the increment anyway.
Valentin Bonnard
Ed Brey wrote:
>
> Valentin Bonnard <Bonn...@wanadoo.fr> wrote in message
> news:375710...@wanadoo.fr...
> >
> > I think it's a shame not to have extended AssocCont::erase the
> > same way. I have heard some nonsensical arguments against
> > AssocCont::erase returning an iterator but nothing serious.
>
> What do you think of the reasoning that ++it is often a more expensive
> operation for an associative container than for a sequence container, and so
> for an associative erase where the return value is not used, there would be
> a performance penalty if it were provided?
Actually this is the nonsensical argument I was talking about.
> I'm thinking of the situation in a binary tree when ++it requires walking
> all the way up or down a tree, which would make ++it a log2(n) operation.
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.
> Assuming the increment overhead is significant, the next question is whether
> an optimizer would see that the return value is not used and avoid
> performing the increment anyway.
It wouldn't be a trivial optimisation, but since the loop would
be something like:
while (test)
assign auto variables
and if it's inline than I think it's doable.
--
Valentin Bonnard
James Kuyper
>
> Ed Brey wrote:
> >
> > Valentin Bonnard <Bonn...@wanadoo.fr> wrote in message
> > news:375710...@wanadoo.fr...
> > >
> > > I think it's a shame not to have extended AssocCont::erase the
> > > same way. I have heard some nonsensical arguments against
> > > AssocCont::erase returning an iterator but nothing serious.
> >
> > What do you think of the reasoning that ++it is often a more expensive
> > operation for an associative container than for a sequence container, and so
> > for an associative erase where the return value is not used, there would be
> > a performance penalty if it were provided?
>
> Actually this is the nonsensical argument I was talking about.
>
> > I'm thinking of the situation in a binary tree when ++it requires walking
> > all the way up or down a tree, which would make ++it a log2(n) operation.
>
> 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:
Associative containers are required to have bidirectional iterators.
Bidirectional iterators are required to provide constant-time ++ and
--. Therefore, determining the next node cannot be a log2(n)
operation. Whether or not there's a per-node pointer to the next and
previous node is implementation detail, though that's the most obvious
way to meet this requirement.
---
John Potter
: 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:
Which is incorrect.
: Associative containers are required to have bidirectional iterators.
: Bidirectional iterators are required to provide constant-time ++ and
: --.
Missing a key word, "amortized" constant time.
: Therefore, determining the next node cannot be a log2(n)
: operation.
It can as long as a complete traversal looks like constant time.
The same as vector::push_back which may be linear sometimes but
in the long run must be averaged to constant. This requirement
forces grow to be multiplicative not additive.
: Whether or not there's a per-node pointer to the next and
: previous node is implementation detail, though that's the most obvious
: way to meet this requirement.
Never seen one. The nodes already have left, right and parent
pointers. Consider a perfectly balanced tree with seven nodes.
Begin must be constant time, so there must be a way to get to
the left most node without starting at the root and working
down the left side. Now lets do the seven ++ operations to get
to end. 1 up to parent(1). 2 down to right(1). 3 up to parent
and up to root(2 lgN). 4 down right and down left(2 lgN).
5 up to parent(1). 6 down right(1). 7 up to parent and up to
root and up to end(3 lgN). Total 11 / 7 is amortized constant
time of 2 pointer chases per ++.
In a complete traversal of a tree, each arc will be followed
in each direction once for a total of 2N. Linear time traversal
gives amortized constant time increment.
Check your favorite rb-tree implementation sitting under the
associative containers. You will not likely find any pred/succ
pointers. Nor threads which would remove the up chases leaving
only the down chases. These things add space and only transfer
the time to other places for maintaining them. It is always a
space loss and usually an overall time loss.
John
John Potter
: Ed Brey wrote:
: > Valentin Bonnard <Bonn...@wanadoo.fr> wrote in message
: > news:375710...@wanadoo.fr...
: > >
: > > I think it's a shame not to have extended AssocCont::erase the
: > > same way. I have heard some nonsensical arguments against
: > > AssocCont::erase returning an iterator but nothing serious.
: > What do you think of the reasoning that ++it is often a more expensive
: > operation for an associative container than for a sequence container, and so
: > for an associative erase where the return value is not used, there would be
: > a performance penalty if it were provided?
: Actually this is the nonsensical argument I was talking about.
: > I'm thinking of the situation in a binary tree when ++it requires walking
: > all the way up or down a tree, which would make ++it a log2(n) operation.
: 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.
Not in the implementations that I have seen. Every node has a left,
right, and parent pointer. Moving from the rightmost node of the
left subtree to the root requires chasing parent pointers up the
tree. That is why ++ is amortized constant time and not constant
time like the sequences.
: > Assuming the increment overhead is significant, the next question is whether
: > an optimizer would see that the return value is not used and avoid
: > performing the increment anyway.
: It wouldn't be a trivial optimisation, but since the loop would
: be something like:
: while (test)
: assign auto variables
: and if it's inline than I think it's doable.
Let's see. We just deleted a node. If an internal node, it has
been replaced by its successor and we have the correct iterator.
If a leaf node, we must have its parent. If left of parent we
have the iterator. If right of parent we need to move up the
tree.
do {
c = p;
p = c->parent;
} while (p->right == c && p->parent != c);
return iterator(p);
To optimize that away, it is required to know that the constructor
has no side effects. Considering that this is just the end of the
nasty stuff needed to remove the node and rebalance the tree, it is
likely not inline. Yes, it would be non-trivial.
Howard Hinnant
<br...@afd.mke.etn.com> wrote:
> What do you think of the reasoning that ++it is often a more expensive
> operation for an associative container than for a sequence container, and so
> for an associative erase where the return value is not used, there would be
> a performance penalty if it were provided?
>
> I'm thinking of the situation in a binary tree when ++it requires walking
> all the way up or down a tree, which would make ++it a log2(n) operation.
> Of course, this is worst case, and for most values of it, the walking would
> be much less. Still, overall there may be enough overhead in incrementing
> that erase shouldn't take the time to do an increment just to have it be
> thrown away.
For a perfectly balanced, large binary tree the average cost of ++it is
twice that of going to an immediate neighbor (that is, amortized
constant). This statement assumes that incrementing from the last node to
end() walks all the way up the tree to the root, and then up one more
level to a psuedo node.
Here is a short program that computes the average for several sizes of
tree, and the resulting output:
#include <cmath>
#include <iostream>
double
avg(int level)
{
double a = 0;
for (int i = 1; i <= level; ++i)
a += i*2*std::pow(2.0, level-(1+i));
a /= std::pow(2.0, level) - 1;
return a;
}
int main()
{
for (int i = 1; i <= 10; ++i)
std::cout << "size = " << std::pow(2.0, i) - 1 << "\t\tavg = " <<
avg(i) << '\n';
}
size = 1 avg = 1
size = 3 avg = 1.33333
size = 7 avg = 1.57143
size = 15 avg = 1.73333
size = 31 avg = 1.83871
size = 63 avg = 1.90476
size = 127 avg = 1.94488
size = 255 avg = 1.96863
size = 511 avg = 1.98239
size = 1023 avg = 1.99022
Jerry Coffin
says...
[ ... ]
> What do you think of the reasoning that ++it is often a more expensive
> operation for an associative container than for a sequence container, and so
> for an associative erase where the return value is not used, there would be
> a performance penalty if it were provided?
[ example using binary tree elided ]
If this were really a major concern, they could require that it
happen, AND that it happen in O(1) time. One obvious implementation
that would satisfy the requirement would be a threaded tree.
James Kuyper
> : > next and previous pointers. You may like it or not, but this is one
> : > of teh roots of the STL.
>
>
> Which is incorrect.
>
> : Associative containers are required to have bidirectional iterators.
> : Bidirectional iterators are required to provide constant-time ++ and
> : --.
>
> Missing a key word, "amortized" constant time.
I deliberately left it out to avoid an unnecessary discussion of what
"amortized" means. In this context the important issue was whether the
increment was expensive.
> : Therefore, determining the next node cannot be a log2(n)
> : operation.
>
> It can as long as a complete traversal looks like constant time.
> The same as vector::push_back which may be linear sometimes but
> in the long run must be averaged to constant. This requirement
> forces grow to be multiplicative not additive.
In this context, it's the amortized time that matters, and the amortized
time cannot be log2(n).
> : Whether or not there's a per-node pointer to the next and
> : previous node is implementation detail, though that's the most obvious
> : way to meet this requirement.
>
> Never seen one. The nodes already have left, right and parent
> pointers. Consider a perfectly balanced tree with seven nodes.
> Begin must be constant time, so there must be a way to get to
> the left most node without starting at the root and working
> down the left side. Now lets do the seven ++ operations to get
> to end. 1 up to parent(1). 2 down to right(1). 3 up to parent
> and up to root(2 lgN). 4 down right and down left(2 lgN).
> 5 up to parent(1). 6 down right(1). 7 up to parent and up to
> root and up to end(3 lgN). Total 11 / 7 is amortized constant
> time of 2 pointer chases per ++.
>
> In a complete traversal of a tree, each arc will be followed
> in each direction once for a total of 2N. Linear time traversal
> gives amortized constant time increment.
I said it was "the most obvious way"; I emphasized that it was an
implementation detail. The important point is that erase() would have a
cheap way of returning an iterator to the next node, removing that as
reason for erase() not returning it.
Valentin Bonnard
> James Kuyper <kuy...@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
James Kuyper
Valentin Bonnard wrote:
>
> John Potter wrote:
>
> > James Kuyper <kuy...@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.
Howard Hinnant
In article <375A09...@wanadoo.fr>, Valentin Bonnard
<Bonn...@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
John Potter
: John Potter wrote:
: > James Kuyper <kuy...@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
---
John Potter
: John Potter wrote:
: >
: > James Kuyper <kuy...@wizard.net> wrote:
: >
: > : Associative containers are required to have bidirectional iterators.
: > : Bidirectional iterators are required to provide constant-time ++ and
: > : --.
: >
: > Missing a key word, "amortized" constant time.
: I deliberately left it out to avoid an unnecessary discussion of what
: "amortized" means.
OK. I will leave that to the other new thread.
: In this context the important issue was whether the
: increment was expensive.
: > : Therefore, determining the next node cannot be a log2(n)
: > : operation.
: >
: > It can as long as a complete traversal looks like constant time.
: > The same as vector::push_back which may be linear sometimes but
: > in the long run must be averaged to constant. This requirement
: > forces grow to be multiplicative not additive.
: In this context, it's the amortized time that matters, and the amortized
: time cannot be log2(n).
Accepted. Erase is only amortized constant time to start with and
could be log2(n) for a particular case. Adding another log2(n) is
not expensive anyway. It does not change either the worst case or
average case complexity.
The original objection to having erase return an iterator was based
on worst case behavior. Your argument states that worst case is
not important and the decision should be made on average behavior.
I agree with your analysis which invalidates the original objection.
Valentin Bonnard
James Kuyper wrote:
>
> Valentin Bonnard wrote:
> >
> > John Potter wrote:
> >
> > > James Kuyper <kuy...@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
Stanley Friesen [Contractor]
>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.
Stanley Friesen [Contractor]
Valentin Bonnard <Bonn...@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).
>
[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.
---
John Potter
: In article <375A09...@wanadoo.fr>,
: Valentin Bonnard <Bonn...@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
Geert-Jan Giezeman
>> > 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.
John Potter
a...@research.att.com (Andrew Koenig) wrote:
: In article <375D3A...@wanadoo.fr>,
: Valentin Bonnard <Bonn...@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
Stanley Friesen [Contractor]
John Potter <jpo...@falcon.lhup.edu> wrote:
>sta...@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.
---
Valentin Bonnard
>
> In article <SFg73.48590$OL.8...@newscene.newscene.com>,
> John Potter <jpo...@falcon.lhup.edu> wrote:
> >sta...@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
John Potter
: In <FD0vH...@research.att.com> a...@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
Stanley Friesen [Contractor]
Valentin Bonnard <Bonn...@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.
Geert-Jan Giezeman
>ge...@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.
John Potter
: 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
Fergus Henderson
>ge...@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 <f...@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 f...@128.250.37.3 | -- the last words of T. S. Garp.