On 18.10.2010, at 14:38, Thorsten Ottosen wrote:
I've never done a performance analysis of PTree (I hardly have time to get the docs up to date with the actual library), so I don't know what is fast and what is slow. PTree is definitely not a fast library. I have some ideas about how to make it faster, but that would take essentially a reimplementation of the ptree class.
ptree uses std::list internally, right? I think it would be worth to use e.g. boost::ptr_deque or boost::ptr_vector (or a similar scheme) to reduce the number of heap allocations somewhat.
No. It used to do that, but when I took the library over, I realized that the documentation made complexity guarantees for find() that it couldn't keep (and also that it created a std::list of an undefined type, which is technically undefined), so I reimplemented it using a multi-index container and some seriously ugly data hiding to delay the container definition to where the ptree type is complete. I've played with the idea of creating the index-by-name lazily, and indeed use a ptr_vector to hold the sequence of elements. I think it would improve performance, but as I said, that would be essentially another reimplementation. Also, last time I looked, intrusive containers (for the index) didn't like incomplete member types, which is a real pity. Also, the library currently makes iterator validity guarantees that would be rather tricky, if not impossible, to keep for containers other than list and multi_index. I still might do it, if I ever find the time. But don't count on it. Sebastian