Abstract Data Types: Sets
I’ve written a few articles on abstract data types, and there was a sort of natural flow from one topic to the next: start with nodes, then linked lists, then queues and stacks, and then trees and graphs. Each of these structures have some sort order to their elements, and you can expect them to stay in that order. But there are data structures that don’t care about the order of their elements, and the most basic of these is the set.
What are Sets?
If queues are like a line at a movie theater, and stacks are like a pile of pancakes, then sets are like a bag. If you throw something in the bag, it shifts and jumbles around with the rest of the things in the bag. There’s no first or top item in the bag, it’s just sort of a mash of whatever is in there. You can also count the number of the items in the bag and you can see the individual items. But past that, this analogy starts to break down a bit. If you want to take something out of this bag, you’re not allowed to look at what you’re grabbing at; you have to grab blindly into the bag and take the first thing you run into. And totally outside of the bag analogy, this bag won’t allow you to place duplicate items into it. Every item in the bag must be distinct and unique.
And that might be the shortest definition of a set: an unordered, distinct collection of items. Compared to the other data structures, this probably sounds like a really terrible way to hold your data. If your data needs to be kept in a particular order, or you need to be able to access particular elements on request, then you’d be right, a set would be a terrible choice. But if ordered elements are not necessary for your task, a set’s unordered and distinct items can probably help you.
Set’s can be used as a quick way to select a random item out of a collection. If you wanted to pick a random number out of an array, you’d have to write a function to do it, but with a set, attempting to take an item out of the set will give you a random item. In fact, the function you write for taking an random item out of an array could simply be done by turning the array into a set so you can take advantage of the randomness of sets.
However, sets are more commonly used for the uniqueness of the elements they contain. With a set, you can quickly check to see if it already contains an item. Or better yet, comparing a set to another set to see what items they have in common, what items they don’t, or just combining them into a new set.
In the end, the big difference between sets and other ordered structures is that the ordered structures are focused on their individual items and elements, whereas sets are focused on their whole collection. So, if you don’t need your items to be in any particular order, you need them to be unique, or if you need to compare a collection to another collection, sets are your best choice.
