RB Tree performance aspects in a map

RB Tree performance aspects in a map

[Anitha Boyapati]

Hi,

This is more of analytical question. Perhaps someone can discern me when 
an _Rb_Tree::find becomes expensive.

Going into details, I have a map<long, TestVec>. TestVec is a vector of 
trees(once can think of a forest). So, I kind of insert this TestVec 
rather heavily. This can be thought similar to inserting a single TestVec 
for each instruction execution in a simulator of a cross compiler tool chain. 

A profiling version shows that _Rb_Tree::find() is taking about 15% of the 
time. As such this is a not a serious concern but it would be nice to know 
more on factors that would affect balancing these Red Black trees.

One thought particularly influencing is operator<. When the key is a user 
defined class object, obviously operator< impacts. My question is to what 
extent can we expect inlining of operator< (if it gets inlined at all).
Probably, I have not asked right point about operator<. Various views on 
this will be truly helpful.

-- 
Regards,
Anitha B
@S A N K H Y A