[Mono-list] SortedList<> inconsistencies and deficiencies

[Nicholas Frechette]

In looking at the code in SortedList<>, I noticed the following things:

- Clear() causes a new allocation, this is inconsistent with other
generic containers such as List<> and Stack<> that simply perform an
Array.Clear() on their internal array.

- PutImpl(), if Find(key) throws an exception, it is swallowed and an
InvalidOperationException is thrown, this is something that happened
to me when my key was a System.Type and I have no way of figuring out
what happened (forcing me to use a Dictionary<> instead).

- Find(key), if I am not mistaken, when the list gets very large, the
line calculating the guess can overflow: int guess = (left + right) >>
1;
For example, if the size is 2^31 - 1, and we provide a key that is in
the top half, the loop will go as follow: left = 0, right = 2^31 - 2,
guess = ~2^30. if cmp < 0, left becomes ~2^30 and on the next
iteration, left + right will be (2^31 - 2 + ~2^30) which is larger
than int.MaxValue (2^31-1) thus causing overflow before the right
shift to divide by 2.

Cheers,
Nicholas