I'm failing to understand why you have to do the search this way.  Naively I would have used std::map::upper_bound to find the first element in the map with a key greater than requested_oid and be done.  I suspect there is some subtlety with the subtree_contains method that stops you doing this, but I would like to discuss, so I'll grab you later so you can explain it to me.