loading...

BONUS: A Quick Intro to Ruby's SortedSet

isalevine profile image Isa Levine ・4 min read

A Quick Intro to Ruby's Set (3 Part Series)

1) A Quick Intro to Ruby's Set Collection, Part 1: Creating Sets, and Adding/Removing Objects 2) A Quick Intro to Ruby's Set, Part 2: Object Lookups and Efficiency 3) BONUS: A Quick Intro to Ruby's SortedSet

To build on our coverage of Ruby's Set, let's look at another Ruby data structure that implements set: a SortedSet!

The key difference between a Set and SortedSet is that, well, SortedSets are sorted, meaning their contents must respond to being sorted by the <=> operator (or a custom-defined sort method).

To review, some key details about sets:

  • All objects in a Set are guaranteed unique
  • Objects in a Set are not ordered
  • Sets are built on top of Hashes for super-fast object lookup

And SortedSets add to this:

  • Objects in a SortedSet are ordered by index, and can be accessed with the at or [] methods, and negative indices count backwards from the end (same as Arrays)
  • All objects in a SortedSet must be mutually comparable, meaning that <=> or its custom sort must not return nil for all objects in the SortedSet (otherwise, an ArgumentError will be thrown)
  • SortedSets are built on top of Sets, and have access to most Set methods, including subset? and superset?

Let's see them in action!

Overview

In this article, we'll introduce this basic functionality for SortedSets:

  • Creating new SortedSets, and seeing their default sorting behavior

New SortedSets and default sorts

require 'set'

Because SortedSets are built on top of sets, we must start by requiring the set module:

require 'set'

Now we're ready to build some SortedSets!

SortedSets with Strings and Integers

We instantiate a new SortedSet with SortedSet.new(), and pass it a collection object. For our examples, we'll create some SortedSets out of arrays and sets.

Let's start by building some arrays to test:

str_array = ["i", "am", "watching", "the", "office", "right", "now", "now", "now"]
int_array = [2, 6, 1, 4, 7, 2, 3, 3, 3, 1, 0, 5]

Now, let's use SortedSet.new() to create SortedSets:

str_sorted_set = SortedSet.new(str_array)
int_sorted_set = SortedSet.new(int_array)

#<SortedSet: {"am", "i", "now", "office", "right", "the", "watching"}>
#<SortedSet: {0, 1, 2, 3, 4, 5, 6, 7}>

As expected, creating a SortedSet both 1) filters out duplicates and 2) sorts contents using default <=> behavior, here meaning alphabetically and lowest-to-highest value. (Also, we get some refrigerator-magnet-style poetry out of the string sorting!)

Now, let's create regular ol' Sets out of the Arrays, and pass the Sets to SortedSet.new():

str_set = Set.new(str_array)
int_set = Set.new(int_array)

str_sorted_set = SortedSet.new(str_set)
int_sorted_set = SortedSet.new(int_set)

#<SortedSet: {"am", "i", "now", "office", "right", "the", "watching"}>
#<SortedSet: {0, 1, 2, 3, 4, 5, 6, 7}>

Same behavior!

And for good measure, let's use the Vector collection too:

require 'matrix'

str_vector = Vector["i", "am", "watching", "the", "office", "right", "now", "now", "now"]
int_vector = Vector[2, 6, 1, 4, 7, 2, 3, 3, 3, 1, 0, 5]

str_sorted_set = SortedSet.new(str_vector)
int_sorted_set = SortedSet.new(int_vector)

#<SortedSet: {"am", "i", "now", "office", "right", "the", "watching"}>
#<SortedSet: {0, 1, 2, 3, 4, 5, 6, 7}>

And same behavior again! So, we can expect the same result from SortedSet.new() regardless of the type of collection!

ArgumentError with Mixed Types

If we try to create a SortedSet containing objects that cannot be compared with <=>, we will get an ArgumentError. If we try to print the following mixed_sorted_set:

mixed_array = [2, "i", 6, "am", 1, "watching", 4, "the", 7, "office", 2]

mixed_sorted_set = SortedSet.new(mixed_array)

# /Users/isalevine/.rvm/rubies/ruby-2.6.1/lib/ruby/2.6.0/set.rb:782:
# in `sort!': comparison of Integer with String failed (ArgumentError)

We see that SortedSet is trying to call a sort!, but throws an Argument error when trying to compare an Integer with a String.

Check out this RubyDoc.info guide for more information in implementing custom sort behavior on SortedSets.

And here's the RubyDoc.info regarding Set methods available (and not available) for SortedSets:

SortedSet supports the same basic set-theoretic operations as Set, including #union, #intersection, #difference, and #exclusion, as well as #subset?, #superset?, and so on. Unlike Set, it does not define comparison operators like #> or #< as aliases for the superset/subset predicates. Instead, these comparison operators do a item-by-item comparison between the SortedSet and another sequential collection. (See Array#<=> for details.)

Conclusion

Now you're equipped with two versions of sets in Ruby: Sets and SortedSets! Between them, you have the ability to guarantee unique collections of objects, in both an unordered and ordered/indexed form as needed. Think about using them the next time you have arrays of unique objects!

Links and Sources

Ruby-Doc - SortedSet

RubyDoc.info - SortedSet

StackOverflow - options for implementing custom sorts (not specific to SortedSet)

GitHub with code snippets used

Got any tips, tricks, or instances where you like to use sets? Please feel free to share in the comments below!

A Quick Intro to Ruby's Set (3 Part Series)

1) A Quick Intro to Ruby's Set Collection, Part 1: Creating Sets, and Adding/Removing Objects 2) A Quick Intro to Ruby's Set, Part 2: Object Lookups and Efficiency 3) BONUS: A Quick Intro to Ruby's SortedSet

Posted on by:

isalevine profile

Isa Levine

@isalevine

Isa (ee-suh). She/her pronouns. Full stack developer working with Rails and Vue. Drinks too much bubbly water.

Discussion

markdown guide