Topic: Complexity of map::erase(map::iterator)
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Sun, 4 Mar 2001 20:21:37 GMT Raw View
On Fri, 2 Mar 2001 18:39:22 GMT, "Hans Bos" <hans.bos@xelion.nl> wrote:
> Hello,
>
> According to table 69 of the C++ standard, erase(iterator) of an
> associative container can be done in amortized constant time.
Amortized means averaged over something.
> Is this possible if the associative container is implemented as a binary
> tree?
Yes, if you use the right average.
> As far as I now removing a node takes Log(size) time (even if you have
> a reference to that node, e.g. to remove the head node you have to
> traverse down the tree).
Consider that removal of a node first requires finding a leaf node to
replace it. Half of the nodes are leaves. Half of what is left take
one step to find the leaf, ... If you average this, you will find
that the total is less than 4N and the average is thus less than 4
which is a constant. The same logic applies to the rebalancing after
removal of the leaf. So, averaged over all possible trees and all
possible nodes within them, the average time to remove an element is
less than 4 operations, amortized constant. Log(N) is an upper bound
on any one removal.
> Also according to table 69 erase(iterator start, iterator end) takes
> log(size) + (end - start) time. If this function is implemented with
> erase(iterator) it should be possible to do this in (end - start)
> operations.
Yes, because half of the nodes in that range will be leaf nodes. It
all comes out in the wash^H^H^H^Hmath. This one amortizes itself.
The log(size) is there to cover the case where end - start == 1.
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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "Hans Bos" <hans.bos@xelion.nl>
Date: Mon, 5 Mar 2001 16:28:29 GMT Raw View
John Potter <jpotter@falcon.lhup.edu> wrote in message news:3aa02906.14032316@news.csrlink.net...
> On Fri, 2 Mar 2001 18:39:22 GMT, "Hans Bos" <hans.bos@xelion.nl> wrote:
>
> > Hello,
> >
> > According to table 69 of the C++ standard, erase(iterator) of an
> > associative container can be done in amortized constant time.
>
> Amortized means averaged over something.
>
> > Is this possible if the associative container is implemented as a binary
> > tree?
>
> Yes, if you use the right average.
>
What is the precise definition of amortized. Is it the same as avarage?
If I remove N objects by calling map::erase(iterator), it is possible that on each deletion the head node will be removed. So on avarage each removal still takes Log(size) time. Only if remove objects in the correct order I will get a constant average.
Hans.
---
[ 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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Mon, 5 Mar 2001 19:31:59 GMT Raw View
On Fri, 2 Mar 2001 18:39:22 GMT, "Hans Bos" <hans.bos@xelion.nl> wrote:
> Hello,
>
> According to table 69 of the C++ standard, erase(iterator) of an
> associative container can be done in amortized constant time.
Amortized means averaged over something.
> Is this possible if the associative container is implemented as a binary
> tree?
Yes, if you use the right average.
> As far as I now removing a node takes Log(size) time (even if you have
> a reference to that node, e.g. to remove the head node you have to
> traverse down the tree).
Consider that removal of a node first requires finding a leaf node to
replace it. Half of the nodes are leaves. Half of what is left take
one step to find the leaf, ... If you average this, you will find
that the total is less than 4N and the average is thus less than 4
which is a constant. The same logic applies to the rebalancing after
removal of the leaf. So, averaged over all possible trees and all
possible nodes within them, the average time to remove an element is
less than 4 operations, amortized constant. Log(N) is an upper bound
on any one removal.
> Also according to table 69 erase(iterator start, iterator end) takes
> log(size) + (end - start) time. If this function is implemented with
> erase(iterator) it should be possible to do this in (end - start)
> operations.
Yes, because half of the nodes in that range will be leaf nodes. It
all comes out in the wash^H^H^H^Hmath. This one amortizes itself.
The log(size) is there to cover the case where end - start == 1.
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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Mon, 5 Mar 2001 20:12:04 GMT Raw View
On Mon, 5 Mar 2001 16:28:29 GMT, "Hans Bos" <hans.bos@xelion.nl> wrote:
> John Potter <jpotter@falcon.lhup.edu> wrote in message news:3aa02906.14032316@news.csrlink.net...
> > On Fri, 2 Mar 2001 18:39:22 GMT, "Hans Bos" <hans.bos@xelion.nl> wrote:
> >
> > > Hello,
> > >
> > > According to table 69 of the C++ standard, erase(iterator) of an
> > > associative container can be done in amortized constant time.
> >
> > Amortized means averaged over something.
> >
> > > Is this possible if the associative container is implemented as a binary
> > > tree?
> >
> > Yes, if you use the right average.
> >
>
> What is the precise definition of amortized. Is it the same as avarage?
It's not defined in the standard, of course. It is the same as average
only if you take a large enough sample.
> If I remove N objects by calling map::erase(iterator), it is possible
> that on each deletion the head node will be removed.
Yes, you can rig the experiment.
> So on avarage
> each removal still takes Log(size) time. Only if remove objects in
> the correct order I will get a constant average.
You could look at it the other way. Only if you remove objects in a
special way will you get anything other than a constant average.
I agree with you that many of the complexity requirements in the
standard are questionable. They can usually be justified, but it
might be a better service to users to state that any operation on
an associative container could be log(size()). The requirements
for sort are NlogN with a disclaimer that it could degenerate to
N*N. The associative containers use expected performance without
the disclaimer.
If you feel strongly about it, a DR would be the approach to take.
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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: "Hans Bos" <hans.bos@xelion.nl>
Date: Fri, 2 Mar 2001 18:39:22 GMT Raw View
Hello,
According to table 69 of the C++ standard, erase(iterator) of an associative container can be done in amortized constant time.
Is this possible if the associative container is implemented as a binary tree?
As far as I now removing a node takes Log(size) time (even if you have a reference to that node, e.g. to remove the head node you have to traverse down the tree).
Also according to table 69 erase(iterator start, iterator end) takes log(size) + (end - start) time. If this function is implemented with erase(iterator) it should be possible to do this in (end - start) operations.
Greetings,
Hans.
---
[ 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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: Wil Evers <bouncer@dev.null>
Date: Sun, 4 Mar 2001 18:22:34 GMT Raw View
In article <97oh4f$cqo$1@porthos.nl.uu.net>, Hans Bos wrote:
> According to table 69 of the C++ standard, erase(iterator) of an
> associative container can be done in amortized constant time.
>
> Is this possible if the associative container is implemented as a binary
> tree? As far as I now removing a node takes Log(size) time (even if you
> have a reference to that node, e.g. to remove the head node you have to
> traverse down the tree).
The map implementations I've seen don't use a pure binary tree; they use a
red-black tree where each node not only keep pointers to its two children,
but also one pointing to its parent. The main reason for this is that it
simplifies the implementation of iterators; an additional benefit is that
there is no need to find the parent node by traversing the tree. Of
course, some additional node-hopping is needed when the tree needs to be
rebalanced, which is why the standard says erase takes amortized constant
time.
- Wil
--
Wil Evers, DOOSYS IT Consultants, Maarssen, Holland
[Wil underscore Evers at doosys dot 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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Sun, 4 Mar 2001 18:24:47 GMT Raw View
On Fri, 2 Mar 2001 18:39:22 GMT, "Hans Bos" <hans.bos@xelion.nl> wrote:
> Hello,
>
> According to table 69 of the C++ standard, erase(iterator) of an
> associative container can be done in amortized constant time.
Amortized means averaged over something.
> Is this possible if the associative container is implemented as a binary
> tree?
Yes, if you use the right average.
> As far as I now removing a node takes Log(size) time (even if you have
> a reference to that node, e.g. to remove the head node you have to
> traverse down the tree).
Consider that removal of a node first requires finding a leaf node to
replace it. Half of the nodes are leaves. Half of what is left take
one step to find the leaf, ... If you average this, you will find
that the total is less than 4N and the average is thus less than 4
which is a constant. The same logic applies to the rebalancing after
removal of the leaf. So, averaged over all possible trees and all
possible nodes within them, the average time to remove an element is
less than 4 operations, amortized constant. Log(N) is an upper bound
on any one removal.
> Also according to table 69 erase(iterator start, iterator end) takes
> log(size) + (end - start) time. If this function is implemented with
> erase(iterator) it should be possible to do this in (end - start)
> operations.
Yes, because half of the nodes in that range will be leaf nodes. It
all comes out in the wash^H^H^H^Hmath. The log(size) is there to
cover the case where end - start == 1. This one amortizes itself.
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 ]
[ Note that the FAQ URL has changed! Please update your bookmarks. ]