STL sets and iterators, with a custom comparison function that calls back into Perl, satisfy your requirements if you can use C++. They're probably red-black trees under the hood (they are in libg++).