On Sat, Dec 11, 2004 at 09:58:17PM +0100, JOAQUIN LOPEZ MU?Z wrote:

De: David Abrahams <dave@boost-consulting.com> [...]

...

Is that the right way to understand the complexity guarantee? I'm really asking. Consider std::set. As the size of the set grows, the average cost of incrementing an iterator grows without bound.

This is not correct, IMHO. Consider a set::iterator doing a full traversal from begin to end. From the rb-tree point of view, this is equivalent to visiting the whole tree in an inorder fashion. And it is easy to see that every node will get hopped from at most three times: - when visiting its left subtree. - when visiting its right subtree. - when leaving to an upper level.

So the total number of hops is bounded by 3*N, and the average cost of incrementing is constant, which is the same as to say that increment complexity is amortized constant, as required by the std.

I can't find anything in the standard that says that the cost should be amortized over the full traversal of the std::set. And it's possible to find sub-ranges which take non-bounded average time to traverse, when the size of the std::set increases : - take the range [ (begin+end)/2 - n ; (begin+end)/2 + n ] in an std::set of size() = 2^(2^n). This is a sequence of ranges of size 2n, and which take at least O(2^n) to traverse, and so definitely not constant time amortized [over the length of the range]... When considering an amortized cost/complexity, it refers to sequences, whose lengths grow to infinity, but here nothing specifies which sequences we are considering. And if you allow any kind of infinite sequences, then set::iterator does not have the required complexity, from the example above :( What am I missing ? -- Sylvain