On Sun, 19 Dec 2004 17:09:45 +0000 (UTC), Hans Bos <hans.bos@xelion.nl>
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.

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.

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

"John Potter" <jpotter@lhup.edu> wrote in message
news:6k1yd.7063$Z47.4121@newsread2.news.atl.earthlink.net...
> On Sun, 19 Dec 2004 17:09:45 +0000 (UTC), Hans Bos <hans.bos@xelion.nl>
> 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.

> 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

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