On 8/10/07, Gottlob Frege <gottlobfrege@gmail.com> wrote:
I worked on a project where we found that copying of maps was one of the major bottle-necks, so we converted most of them to sorted vectors, and that fixed it.
We didn't need the sorted vectors to have all the same behaviour as maps, but I've had a plan for vector-based maps sitting on the back-burner for a while now. Might be something to consider.
It is true the vector copies are more efficient, but they are still linear time to copy. The bigger problem though is that each copy typically needs a few inserts done, so it's A.insert, A.insert, A.insert, B = A, B.insert, B.insert, B.insert, C = B, C.insert, C.insert, C.insert, so sorted vectors wouldn't work since they are bad at dealing with insertions. Also, I think I've figured out a better way to do iterators. I'll post again once I've gotten it all worked out. -Jeremy