To tree or not to tree (alternatives to std::map)
I noticed that when working with maps containing a great number of entries (1,000,000+) and requiring a large volume of insertions/deletions, a severe degradation of performance developed ( presumably because of frequent tree-rebalancing). So I switched to (sorted) arrays of pointers - just hoping to eke out a little faster processing time - and as it turns out, the bottleneck completely disappeared! Apparently, even though every single insert/delete required a memcpy/memmove of several magabytes, it was still several orders of magnitude faster than the (relatively) occasional task of rebalancing a large binary tree. So I wonder: why use binary trees at all? Or am I missing something here?