insert_unique with hint bug

[John Potter]

In case anyone is interested, I stumbled across this.  It survived
quite a while and may still be in the library.  The insert with hint
function works fine except when hint == begin().  Given a sequence
of multiX entries at the beginning of the tree, an attempt to insert
at begin() will insert at the end of the sequence.  This code is
from the library distributed with egcs 1.1 at release time.  I do
not read this list; so, please direct any out of date flames to me
rather than the list.

John

template <class Key, class Val, class KeyOfValue, class Compare,
      class Alloc>
typename rb_tree<Key, Val, KeyOfValue, Compare, Alloc>::iterator
      rb_tree<Key, Val, KeyOfValue, Compare,
      Alloc>::insert_unique(iterator position, const Val& v) {
  if (position.node == header->left) // begin()
    if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
      return __insert(position.node, position.node, v);

The test is for less and should be for less-equal

  if (size() > 0 && ! key_compare(key(position.node), KeyOfValue()(v)))

A simple test program follows.  5 should be first not last in output.

#include <iostream>
#include <multiset>
#include <algorithm>
ostream& operator<< (ostream& os, pair<int, int> const& p) {
   return os << p.first << ' ' << p.second;
   }
bool operator< (pair<int, int> const& lhs, pair<int, int> const& rhs) {
   return lhs.first < rhs.first;
   }
int main () {
   pair<int, int> p(69, 0);
   multiset<pair<int, int> > s;
   for (p.second = 0; p.second < 5; ++ p.second)
   	  s.insert(p);
   for (multiset<pair<int, int> >::iterator it = s.begin();
         it != s.end(); ++ it)
      if (it->second < 5) {
         s.insert(it, p);
         ++ p.second;
         }
   copy(s.begin(), s.end(),
         ostream_iterator<pair<int, int> >(cout, "\n"));
   }