Improving equal_range and erase(key) in tree containers

[Ion Gaztañaga]

Hi,

 While implementing my own tree containers, I've found that nearly
every standard library version implements multiset/multimap
equal_range with something like this:

std::pair<iterator,iterator> equal_range(const key_type& val)
{
   return std::pair<iterator,iterator> (lower_bound (val),
                                        upper_bound (val));
}

However, it's clear that lower_bound and upper_bound have common
operations that could be executed just once:

iterator lower_bound (const key_type& key)
{
   node_ptr y = &root_;
   node_ptr x = parent(node_ptr(&root_));
   while (x) {
      if (comp(to_key(x), key)) {
         x = right(x);
      }
      else {
         y = x;
         x = left(x);
      }
   }
   return iterator (y);
}

iterator upper_bound (const key_type& key)
{
   node_ptr y = &root_;
   node_ptr x = parent(node_ptr(&root_));
   while (x) {
      if (comp(key, to_key(x))) {
         y = x;
         x = left(x);
      }
      else {
         x = right(x);
      }
   }
   return iterator (y);
}

Since the upper bound must be the same as the lower bound or bigger,
we could merge operations while the lower and upper bound search leads
to the same subtree:

std::pair<iterator,iterator> equal_range(const key_type& key)
{
   node_ptr y = root_;
   node_ptr x = parent(root_);

   while (x) {
      if (comp(*to_key(x), key)) {
         x = right(x);
      }
      else if (comp(key, *to_key(x))) {
         y = x;
         x = left(x);
      }
      else{
         //Now the subtrees are different, lower bound
         //and upper bound are two different searches
         node_ptr xu(x), yu(y);
         y = x, x = left(x);
         xu = right(xu);

         //lower bound
         while (x) {
            if (comp(to_key(x), key)) {
               x = right(x);
            }
            else {
               y = x;
               x = left(x);
            }
         }

         //upper bound
         while (xu) {
            if (comp(key, to_key(xu))) {
               yu = xu;
               xu = left(xu);
            }
            else {
               xu = right(xu);
            }
         }
         return std::pair<iterator,iterator> (iterator(y), iterator(yu));
      }
   }
   return std::pair<iterator,iterator> (iterator(y), iterator(y));
}

My measurements show that for multisets with few copies of the same
value (for example 1), expensive comparisons (strings with long common
prefixes), and large different values (10000) the algorithm can be 25%
faster if we try to search every key. The algorithm can't be slower in
any case. Of course, there are corner cases where the search is much
faster (basically because the key leads to a lot of true returns in
the first comparison). This would help other functions calling
equal_range, like count(), and erase(const key &x).

Regarding erase(const key &x) in tree containers, at least in the v7
branch, also uses std::distance() after equal_range to know the number
of erased elements:

size erase(const _Key& __x)
{
   pair<iterator,iterator> __p = equal_range(__x);
   size_type __n = std::distance(__p.first, __p.second);
   erase(__p.first, __p.second);
   return __n;
}

Both distance and erase(iterator, iterator) traverse the sequence so
we are traversing the sequence to be erased more than necessary. we
can implement erase(iterator, iterator) if a private function that
returns the number of erased elements, so we can save some cycles if
we want to erase many nodes with the same key. Another way is to get
the size of the tree before calling erase and to substract the size
after calling erase.

Regards,

Ion