Sorted Containers in Ruby inspired by Python

submited by

Style Pass

2024-04-28 20:00:02

I converted Grant Jenks’s Python library Sorted Containers to Ruby. If you are interested in the details of this data structure, I recommend reading his website. His documentation is much more detailed, and I used it as a reference for this implementation.

SortedArray, SortedSet, and SortedHash are meant to be drop-in replacements for Array, Set, and Hash but with the extra property that the elements can be accessed in sorted order.

I compare the performance of SortedContainers to SortedSet a C extension red-black tree implementation. You can see the benchmarks below. The performance is comparable for add and delete, and much better for iteration, initialization, and lookup.

Some methods from Array, Set, and Hash have not been implemented in SortedContainers. I want to complete these before version 1.0.0. Feel free to open an issue if you would like a method added or add a pull request if you would like to contribute.

Modern computers are good at shifting arrays. For that reason, it’s often faster to keep an array sorted than to use the usual tree-based data structures.