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?

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.