Prev: templates, namespaces, and questions
Next: C++0x two Unicode proposals. A correction one and a different one
From: Kaba on 18 Jan 2008 06:05
Hi,

What are the requirements the standard places on the asymptotic
behaviour of the std::map container?

>From Wikipedia:

http://en.wikipedia.org/wiki/Map_%28C%2B%2B_container%29

The article claims O(n log n) for copying and O(log n) for iterator
increment/decrement. It also claims O(n) for visiting all elements, but
this contradicts the iterator increment/decrement behaviour.

However, a common implementation using a red-black tree achieves
amortized constant time for increment/decrementing an iterator.
Similarly, copying takes O(n).

--
http://kaba.hilvi.org

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Jerry Coffin on 18 Jan 2008 14:24
In article <MPG.21fb3ee18c2fc0ed989986(a)news.cc.tut.fi>, none(a)here.com
says...
> Hi,
>
> What are the requirements the standard places on the asymptotic
> behaviour of the std::map container?

Copying is N log(N) in general, but linear if the elements are sorted
(in the order expected by that map's comparison function).

Inserting an item is logarithmic in general, but amortized constant if
you use an accurate hint.

std::set uses BiDirectional iterators, which support incrementing and
decrementing functions.

"All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized)."

--
Later,
Jerry.

The universe is a figment of its own imagination.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Jiri Palecek on 19 Jan 2008 05:15
Kaba wrote:

> However, a common implementation using a red-black tree achieves
> amortized constant time for increment/decrementing an iterator.

Not really, unless you maintain something like a linked list of node in the
tree in the order of their elements.

For example, imagine that you get an iterator to the root of the tree.
Clearly, incrementing the iterator takes log(N), and subsequent
decrementing too. So if you increment-decrement-increment-decrement... the
iterator, the time it'll take O(log N)*(number of rounds) which cannot be
paid by 2*(number of rounds) O(1) operations.

The O(1) amortised complexity for tree iterator increment only applies to
iterators that only move one direction.

Regards
Jiri Palecek


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Juha Nieminen on 19 Jan 2008 05:12
Kaba wrote:
> The article claims O(n log n) for copying and O(log n) for iterator
> increment/decrement. It also claims O(n) for visiting all elements, but
> this contradicts the iterator increment/decrement behaviour.

Actually it doesn't. O() denotes the *worst-case* scenario. In other
words, what is the worst possible amount of steps required to perform
the operation. It doesn't denote the average case. O(log n) does not
mean that if the operation is performed n times, the total amount of
operations will be O(n*log n) because it depends on how often the log n
behavior happens.

In this case, while the worst-case of an iterator increment is
O(log n), a traversal is O(n).

To understand why this is, think about two situations:

1) The iterator points to the largest element of the left sub-tree of
the root node. Incrementing this iterator will make it point to the
smallest element of the right sub-tree of the root node, thus requiring
approximately 2*log n steps. Thus the increment in this case required an
amount of operations proportional to log n.

2) However, traversing the tree from the smallest element to the largest
can be thought differently: Think about the amount of steps required at
each individual node. These steps are, roughly:

- Arrive at the node from the parent.
- Go to the left sub-tree.
- Arrive at the node from the left sub-tree.
- Go to the right sub-tree.
- Arrive at the node from the right sub-tree.
- Go to the parent.

Notice that this is a *fixed* amount of steps. It doesn't depend on
the amount of elements in the tree in any way. These steps are executed
for each node, ergo they are executed n times. Thus the total number of
steps needed to traverse the entire tree is, roughly, something like
6*n, which is O(n).
And this still even though one individual iterator increment may
require 2*log n steps.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Stuart Golodetz on 19 Jan 2008 11:21
"Juha Nieminen" <nospam(a)thanks.invalid> wrote in message
news:4791ec38$0$15003$4f793bc4(a)news.tdc.fi...
> Kaba wrote:
>> The article claims O(n log n) for copying and O(log n) for iterator
>> increment/decrement. It also claims O(n) for visiting all elements, but
>> this contradicts the iterator increment/decrement behaviour.
>
> Actually it doesn't. O() denotes the *worst-case* scenario. In other
> words, what is the worst possible amount of steps required to perform
> the operation. It doesn't denote the average case. O(log n) does not
> mean that if the operation is performed n times, the total amount of
> operations will be O(n*log n) because it depends on how often the log n
> behavior happens.

Just a minor nitpick (sorry): I know what you mean, but actually if
something is O(log n) and is performed n times, the total cost will be O(n
log n). The fact that it may also be O(n) doesn't matter since Big-O
notation is an upper bound.

Cheers,
Stu

<snip>



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: templates, namespaces, and questions
Next: C++0x two Unicode proposals. A correction one and a different one