D library projects

[Steven Schveighoffer]

On Sun, 15 Nov 2009 12:48:34 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> Ok, thanks for clarifying. I thought the overhead of traversal is  
> considerable, which would make it advantageous to specialize add on  
> select pairs of containers.

In all cases, traversing all elements of a container is an O(n)  
operation.  For a binary tree, traversing a *single* element can be up to  
O(lgn), but it amortizes out to O(n) over the whole container, because you  
traverse every edge exactly twice, and there are at most 2 edges per  
node.  So it works out to be about O(4n).

-Steve