Re: [boost] [Boost Review] Property Tree Library

From: Marcin Kalicinski (kalita_at_[hidden])
Date: 2006-04-21 18:10:04

>> I cannot agree. Can you imagine an XML or JSON library that would do O(n)
>> lookup on keys?
>
> Shouldn't a tree already be approx log N in most cases.

This is the case if your config is well balanced among nodes. If you have a 
long linear sequence of subkeys that becomes O(N).

> Optimizing it into log log N by adding a multimap to each node seems like 
> an
> overkill to me. (at least as default)

I don't think it costs that much. It's just an implementation detail hidden 
deep inside, several more bytes per node, that's all to it. It is not 
exposed in the interface. In return we get nice time constraints, which, I 
believe, adhere to the principle of least surprise. Usually if you have a 
lookup by name in some library you don't expect it does linear search 
through the whole lot. Especially if that lot can be arbitrarily large.

Best regards,
Marcin