 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Hans Bos
Guest
|
 Posted: Sun Dec 19, 2004 5:09 pm Post subject: Defect report: Wrong runtime complexity for associative cont |
 |
|
According to [lib.associative.reqmts] table 69, the runtime comlexity
of insert(p, t) and erase(q) can be done in amortized constant time.
It was my understanding that an associative container could be
implemented as a balanced binary tree.
For inser(p, t), you 'll have to iterate to p's next node to see if t
can be placed next to p.
Furthermore, the insertion usually takes place at leaf nodes. An
insert next to the root node will be done at the left of the root next
node
So when p is the root node you 'll have to iterate from the root to
its next node, which takes O(log(size)) time in a balanced tree.
If you insert all values with insert(root, t) (where root is the root
of the tree before insertion) then each insert takes O(log(size))
time.
The amortized complexity per insertion will be O(log(size)) also.
For erase(q), the normal algorithm for deleting a node that has no
empty left or right subtree, is to iterate to the next (or previous),
which is a leaf node. Then exchange the node with the next and delete
the leaf node.
Furthermore according to DR 130, erase should return the next node of
the node erased.
Thus erasing the root node, requires iterating to the next node.
Now if you empty a map by deleting the root node until the map is
empty, each operation will take O(log(size)), and the amortized
complexity is still O(log(size)).
The operations can be done in amortized constant time if iterating to
the next node can be done in (non amortized) constant time.
This can be done by putting all nodes in a double linked list.
This requires two extra links per node.
To me this is a bit overkill since you can already efficiently insert
or erase ranges with erase(first, last) and insert(first, last).
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.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
 |
John Potter
Guest
|
| Posted: Tue Dec 21, 2004 11:49 pm Post subject: Re: Defect report: Wrong runtime complexity for associative |
|
|
On Sun, 19 Dec 2004 17:09:45 +0000 (UTC), Hans Bos <hans.bos (AT) xelion (DOT) nl>
wrote:
| Quote: | According to [lib.associative.reqmts] table 69, the runtime comlexity
of insert(p, t) and erase(q) can be done in amortized constant time.
It was my understanding that an associative container could be
implemented as a balanced binary tree.
|
This is just a special case of a general problem. To be amortized,
there must be a "with respect to" present. The standard is void of
any such clauses.
In this example, if you amortize the insert or erase time with respect
to a given tree and a single insert or erase at each possible position,
you will see that each has a constant average.
Another example is iterator ++/--. Each is amortized constant time
with respect to a complete traversal; however, a sequence of alternating
++ and -- at the root will have lgN average.
It has been stated that there is only "amortized bologna" in the
standard.
| Quote: | To me this is a bit overkill since you can already efficiently insert
or erase ranges with erase(first, last) and insert(first, last).
|
If you check the balancing algorithms, you will find that insert/erase
range is implemented using the single item insert and erase functions.
There is no nice insert/erase group and rebalance algorithm available.
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.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Hans Bos
Guest
|
| Posted: Wed Dec 22, 2004 11:40 pm Post subject: Re: Defect report: Wrong runtime complexity for associative |
|
|
"John Potter" <jpotter (AT) lhup (DOT) edu> wrote
| Quote: | On Sun, 19 Dec 2004 17:09:45 +0000 (UTC), Hans Bos
wrote:
According to [lib.associative.reqmts] table 69, the runtime comlexity
of insert(p, t) and erase(q) can be done in amortized constant time.
It was my understanding that an associative container could be
implemented as a balanced binary tree.
This is just a special case of a general problem. To be amortized,
there must be a "with respect to" present. The standard is void of
any such clauses.
Since nothing special was mentioned, I assumed it was amortized over all |
elements in the container.
In general this cannot be done in constant avarage time.
| Quote: | In this example, if you amortize the insert or erase time with respect
to a given tree and a single insert or erase at each possible position,
you will see that each has a constant average.
|
But each operation will modify the tree.
It is only constant avarage if you start each operation on the initial tree.
This doesn't sound very usefull to me
....
| Quote: | To me this is a bit overkill since you can already efficiently insert
or erase ranges with erase(first, last) and insert(first, last).
If you check the balancing algorithms, you will find that insert/erase
range is implemented using the single item insert and erase functions.
There is no nice insert/erase group and rebalance algorithm available.
|
If you ignore rebalancing you can implement those algorithms in O(log(size)) +
O(distance(first, last)).
You can choose your own order so you always erase or insert values at leaf
nodes).
I always assumed that total the time to rebalance was less then O(number of
erased elements).
Note that insert(first, last) has some other problems, see defect report 264.
Also, it is possible to split a balanced avl tree at a node in two balanced avl
trees in log(size) time.
You can join two balanced avl trees into one balanced tree in log(size)
(assuming that the values in the tree don't overlap)..
You can implement erase(first, last) by splitting the tree in 3 parts [begin,
first), [first, last) and [last, end).
Then you can join the first and last part: [begin, first) and [last, end).
All those operations take log(size) time, so the total operation can be done in
O(log size).
You will need an extra O(distance(first, last)) to delete the nodes [first,
last).
I don't know if this is a nice algorithm :-)
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.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
