Custom Set in Crystal: Complete Solution & Deep Dive Guide

---

Mastering Crystal Data Structures: Build a Custom Set from Scratch

Creating a custom set in Crystal involves defining a class that encapsulates a collection, typically a Hash(T, Bool), to enforce element uniqueness. This guide covers implementing core set operations like add, contains?, subset?, disjoint?, intersection, and union from the ground up for maximum control and understanding.

Have you ever found yourself wrestling with a collection, wishing you had more control? You need a list of items, but duplicates are causing chaos in your logic. An Array lets them in, and while you can call .uniq, it feels reactive, not preventative. You need a data structure that inherently understands and enforces uniqueness from the very beginning. This is the classic use case for a Set.

While Crystal's standard library provides a powerful built-in Set(T), what happens when you need more? Perhaps you need to log every addition, implement a custom equality check, or simply want to demystify the "magic" behind how sets work. This is where the real learning begins. In this deep dive, we'll move beyond just using data structures and start building them. You will construct your own CustomSet in Crystal, gaining a fundamental understanding that separates proficient coders from true architects.

---

What Exactly Is a Set Data Structure?

Before we write a single line of Crystal code, it's crucial to understand the theoretical foundation. A set is an abstract data type inspired by the mathematical concept of a finite set. Its definition is elegantly simple, yet profoundly powerful, and is defined by two core principles:

• Uniqueness: A set contains no duplicate elements. If you try to add an element that already exists in the set, the set simply remains unchanged. This is its most defining characteristic.
• Unordered: The elements in a set have no specific order. Unlike an Array, you cannot ask for the "first" or "third" element. The only question you can reliably ask is whether an element is present or not.

Think of a set like a collection of unique trading cards. You can add a new card to your collection, check if you already own a specific card, or combine your collection with a friend's. However, having two identical cards in the collection is redundant; you either have the card or you don't. The order in which you acquired them doesn't matter to the collection itself.

In programming, sets are indispensable for tasks involving membership testing (checking for presence), removing duplicates from a list, and performing mathematical set operations like union, intersection, and difference.

---

Why Bother Building a Custom Set in Crystal?

Crystal already includes a robust Set(T) in its standard library, so why would we reinvent the wheel? The answer lies in control, understanding, and specialization. Building a data structure from scratch is one of the most effective ways to solidify your programming fundamentals.

The Core Motivations

• Deep Learning: By implementing your own set, you're forced to confront the design decisions that library authors make. Why is a Hash-based implementation often faster than an Array-based one for lookups? You'll not only learn the answer but feel it by writing the code. This knowledge is transferable to any programming language.
• Full Control & Customization: The standard Set(T) is a general-purpose tool. What if you need specialized behavior? With a custom set, you can add logging hooks, custom serialization logic, or performance metrics directly into the data structure's operations.
• Performance Tuning: For very specific use cases, you might be able to make different trade-offs than the standard library. Perhaps your data has unique characteristics that allow for a more memory-efficient or faster implementation under certain conditions.
• API Design Practice: Defining the public interface for your CustomSet is an excellent exercise in API design. You'll think about method names, argument types, and return values, all with the goal of creating something that is intuitive and easy to use.

This exercise, drawn from the exclusive kodikra.com learning curriculum, isn't just about creating a class; it's about understanding the "why" behind the "what" of data structures.

---

How to Design Our CustomSet: The Architectural Blueprint

A successful implementation starts with a solid plan. Our primary decision is choosing the right internal data structure to store the set's elements. This choice will directly impact the performance and complexity of our code.

Choosing the Internal Storage: Hash vs. Array

We have two primary candidates from Crystal's standard library to use as our backing store: Array(T) or Hash(T, V).

• Using an Array(T): We could store elements in an array. To add a new element, we would first have to scan the entire array to ensure it doesn't already exist. This check has a time complexity of O(n), meaning the time it takes grows linearly with the number of elements in the set. For large sets, this becomes very slow.
• Using a Hash(T, V): A hash provides a much more efficient solution. We can store the set's elements as the keys of a hash. The value associated with each key is irrelevant; we can simply use true. The magic of a hash is that checking for the existence of a key is, on average, an O(1) or constant time operation. It doesn't matter if the set has 10 elements or 10 million; the lookup time remains roughly the same.

The choice is clear: a Hash will give us the performance characteristics we expect from a set. We'll use Hash(T, Bool) as the engine for our CustomSet(T), where T is the generic type of the elements we want to store.

ASCII Diagram: The Logic of Adding an Element

Here is a visual representation of how our add method will work using the internal hash store. This flow ensures uniqueness with O(1) average time complexity.

    ● Start (Receive element `T`)
    │
    ▼
  ┌───────────────────────────┐
  │ Access `internal_store`   │
  │ (a Hash(T, Bool))         │
  └────────────┬──────────────┘
               │
               ▼
  ◆ Has key `T` already?
    (internal_store.has_key?(T))
   ╱                           ╲
  Yes (Element exists)          No (New element)
  │                              │
  ▼                              ▼
┌───────────┐               ┌───────────────────────────┐
│ Do nothing │              │ Add to hash:              │
│ (Set is   │              │ `internal_store[T] = true`│
│ unchanged)│              └───────────────────────────┘
└───────────┘                              │
  │                                        │
  └─────────────────┬──────────────────────┘
                    ▼
               ● End (Set now contains `T`)

Defining the Public API

A good class has a clean and intuitive public interface. Here are the methods we will implement for our CustomSet:

• new: Constructors to create an empty set or a set from an existing collection.
• empty?: Returns true if the set has no elements.
• size: Returns the number of elements in the set.
• contains?(element): Checks if an element is a member of the set.
• add(element): Adds an element to the set.
• subset?(other_set): Checks if this set is a subset of another set.
• disjoint?(other_set): Checks if this set has no elements in common with another set.
• union(other_set): Returns a new set containing all elements from both sets.
• intersection(other_set): Returns a new set containing only the elements common to both sets.
• difference(other_set): Returns a new set with elements from this set that are not in the other set.
• ==: Checks for equality between two sets.

We will also make our set Enumerable, allowing us to use methods like .each, .map, and .select, making it feel like a native Crystal collection.

---

Where the Magic Happens: The Complete Crystal Implementation

Now, let's translate our design into working Crystal code. We will create a generic class CustomSet(T) to allow it to hold elements of any type. This code is a complete, well-commented solution based on the principles discussed in the kodikra Crystal learning path.

# Implements a custom Set data structure.
# A set is a collection of unique, unordered elements.
# This implementation uses a Hash(T, Bool) for efficient storage and lookup.
class CustomSet(T)
  # Include Enumerable to get methods like .map, .select, .to_a, etc.
  include Enumerable(T)

  # The internal storage. Using a Hash where keys are the set elements
  # provides O(1) average time complexity for additions and lookups.
  private property internal_store : Hash(T, Bool)

  # Creates a new, empty CustomSet.
  def initialize
    @internal_store = {} of T => Bool
  end

  # Creates a new CustomSet from an enumerable (like an Array).
  # Duplicates in the initial array will be automatically removed.
  def initialize(elements : Enumerable(T))
    @internal_store = {} of T => Bool
    elements.each { |element| add(element) }
  end

  # Iterates over each element in the set. Required by the Enumerable module.
  def each(&block)
    @internal_store.each_key do |key|
      yield key
    end
  end

  # Checks if the set is empty.
  # Returns true if the set contains no elements, false otherwise.
  def empty? : Bool
    @internal_store.empty?
  end

  # Returns the number of elements in the set.
  def size : Int32
    @internal_store.size
  end

  # Checks if the given element is a member of the set.
  # Returns true if the element is present, false otherwise.
  def contains?(element : T) : Bool
    @internal_store.has_key?(element)
  end

  # Adds an element to the set.
  # If the element is already present, the set remains unchanged.
  # Returns self to allow for method chaining.
  def add(element : T)
    @internal_store[element] = true
    self
  end

  # Determines if this set is a subset of another CustomSet.
  # A set A is a subset of B if all elements of A are also in B.
  def subset?(other : CustomSet(T)) : Bool
    # If this set is larger than the other, it can't be a subset.
    return false if self.size > other.size
    # Check if every element in this set is also in the other set.
    all? { |element| other.contains?(element) }
  end

  # Determines if this set is disjoint from another CustomSet.
  # Two sets are disjoint if they have no elements in common.
  def disjoint?(other : CustomSet(T)) : Bool
    # Efficient check: iterate over the smaller set.
    smaller, larger = self.size < other.size ? {self, other} : {other, self}
    smaller.none? { |element| larger.contains?(element) }
  end



  # Checks for equality with another CustomSet.
  # Two sets are equal if they contain the exact same elements, regardless of order.
  def ==(other : self) : Bool
    # A quick optimization: if sizes are different, they can't be equal.
    return false if self.size != other.size
    # Since sizes are equal, we just need to check if one is a subset of the other.
    self.subset?(other)
  end

  # Returns a new CustomSet containing elements present in both this set and another.
  def intersection(other : CustomSet(T)) : CustomSet(T)
    new_set = CustomSet(T).new
    # Iterate over the smaller set for better performance.
    smaller, larger = self.size < other.size ? {self, other} : {other, self}
    smaller.each do |element|
      new_set.add(element) if larger.contains?(element)
    end
    new_set
  end

  # Returns a new CustomSet containing elements from this set that are not in the other.
  def difference(other : CustomSet(T)) : CustomSet(T)
    new_set = CustomSet(T).new
    self.each do |element|
      new_set.add(element) unless other.contains?(element)
    end
    new_set
  end

  # Returns a new CustomSet containing all unique elements from both sets.
  def union(other : CustomSet(T)) : CustomSet(T)
    # Initialize the new set with all elements from the first set.
    new_set = CustomSet(T).new(self)
    # Add all elements from the second set. Duplicates are handled by `add`.
    other.each { |element| new_set.add(element) }
    new_set
  end
end

Detailed Code Walkthrough

Let's dissect some of the key methods to understand their inner workings.

initialize(elements : Enumerable(T))

This constructor is what allows us to create a set from an existing array, like CustomSet.new([1, 2, 2, 3]). It first initializes an empty internal hash. Then, it iterates through every element of the provided enumerable and calls our own add method for each one. Because add inherently handles uniqueness, any duplicates in the input array are automatically discarded, resulting in a clean set.

subset?(other : CustomSet(T))

This method checks if every element of the current set (self) is also present in the other set. It starts with a quick optimization: if our set has more elements than the other, it's impossible for it to be a subset, so we can return false immediately. Otherwise, it uses the all? method provided by the Enumerable module. The block { |element| other.contains?(element) } is executed for every element in our set. If even one of those checks returns false, all? stops and returns false. Only if all elements are found in the other set will it return true.

disjoint?(other : CustomSet(T))

Two sets are disjoint if they share zero common elements. A naive approach would be to build the intersection and see if it's empty. A more performant approach, which we've used here, is to iterate over one set and check for the presence of its elements in the other. We add a small optimization by first identifying which set is smaller and iterating over that one, minimizing the number of lookups we need to perform. The none? enumerable method is perfect here; it returns true only if the given block returns false for every single element.

intersection(other : CustomSet(T))

The intersection is the set of elements that exist in *both* sets. Our implementation again finds the smaller of the two sets to iterate over. It creates a new, empty CustomSet. Then, for each element in the smaller set, it checks if that element is also contained in the larger set. If it is, the element is added to our new set. Finally, this new set, containing only the common elements, is returned.

ASCII Diagram: The Logic of Set Intersection

This diagram illustrates the process of finding the common elements between two sets, `Set A` and `Set B`, to create a new `Intersection Set`.

    ● Start (Inputs: Set A, Set B)
    │
    ▼
  ┌───────────────────────────┐
  │ Create `Intersection Set` │
  │ (Initially empty)         │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ For each `element` in Set A │
  └────────────┬──────────────┘
               │
               ▼
      ◆ Does Set B contain `element`?
     ╱            ╲
    Yes            No
    │              │
    ▼              ▼
  ┌───────────┐   (Continue to
  │ Add       │    next element)
  │ `element` │
  │ to        │
  │ `Result`  │
  └───────────┘
    │
    └──────────────┐
                   │
                   ▼
  (Loop until all elements in Set A are checked)
                   │
                   ▼
  ┌───────────────────────────┐
  │ Return `Intersection Set` │
  └────────────┬──────────────┘
               │
               ▼
               ● End

---

When to Use CustomSet vs. The Standard `Set(T)`

Knowing when to build your own solution versus using a standard library component is a key skill for any developer. While our CustomSet is a fantastic learning tool, Crystal's built-in Set(T) is highly optimized, battle-tested, and integrated into the ecosystem.

Here’s a breakdown to help you decide:

Aspect	Our CustomSet(T)	Crystal's Standard Set(T)
Primary Goal	Learning, full control, custom behavior (e.g., logging).	Performance, reliability, and general-purpose use in production.
Performance	Very good (O(1) lookups), but may lack the micro-optimizations of the standard library.	Highly optimized C-bindings and Crystal code for maximum speed. Likely faster.
Features	Contains the core set operations we implemented. Easily extensible.	A rich API with many convenience methods and full integration with the language.
Maintenance	You are responsible for fixing bugs and adding features.	Maintained by the Crystal core team. Benefits from language updates.
Use Case	Educational purposes, projects requiring special hooks, or when you need a data structure with a slightly different contract.	The default choice for almost all production applications that require a set.

In short, use the standard Set(T) for your day-to-day work. Use the knowledge gained from building CustomSet to understand *how* it works and to empower you to build other custom data structures when a real, specific need arises.

---

Frequently Asked Questions (FAQ)

1. Why did we use a Hash(T, Bool) instead of an Array(T) for the internal storage?

Performance. A Hash provides, on average, O(1) constant time complexity for checking if an element exists (has_key?). An Array would require an O(n) linear scan (includes?), which is significantly slower as the number of elements grows.

2. Is this CustomSet implementation thread-safe?

No, this implementation is not thread-safe by default. If multiple fibers or threads were to try and modify the set concurrently (e.g., one calls add while another iterates), it could lead to race conditions and unpredictable behavior. Making it thread-safe would require using synchronization primitives like a Mutex to protect access to the @internal_store.

3. How can I make the CustomSet work with my own custom objects?

For a custom object to work correctly as a key in a Hash (and therefore in our CustomSet), it must properly implement two methods: hash and eql?(other). The hash method should return a consistent integer hash code for the object's state, and eql? should define value-based equality. Crystal's record type handles this for you automatically.

4. What is the time complexity of the main operations in our CustomSet?

• add(element): O(1) on average.
• contains?(element): O(1) on average.
• size: O(1).
• intersection(other): O(min(n, m)), where n and m are the sizes of the two sets.
• union(other): O(n + m).
• subset?(other): O(n), where n is the size of the potential subset.

5. Can I extend this CustomSet with more features?

Absolutely! That's the primary benefit of a custom implementation. You could add methods like symmetric_difference, implement `Comparable` to sort sets, or add methods to convert the set to and from JSON/YAML. The foundation is there for you to build upon.

6. How does this differ from just using Array#uniq?

Array#uniq is an operation that creates a *new* array with duplicates removed from an *existing* one. A Set is a data structure that *enforces* uniqueness at all times. With a set, you can never have duplicates in the first place, and checking for membership is much faster than with an array.

7. Is this implementation considered production-ready?

While it is functionally correct and follows good design principles, it has not undergone the rigorous testing and optimization of Crystal's standard library Set(T). For production code, it is almost always better to rely on the standard library unless you have a very specific, benchmarked reason to roll your own.

---

Conclusion: From User to Architect

You've successfully journeyed from the abstract concept of a set to a concrete, working implementation in Crystal. By building CustomSet from the ground up, you've gained more than just a new class; you've acquired a deeper appreciation for the trade-offs and design decisions involved in creating fundamental data structures. You now understand *why* sets are efficient for membership testing and how to leverage the power of hashes to enforce uniqueness.

This hands-on experience is a cornerstone of the practical, in-depth approach we champion in our learning modules. The ability to not just use but also to build and reason about the tools you work with is a critical step in your evolution as a software developer. You are no longer just a user of the language; you are beginning to think like an architect of it.

Disclaimer: The code and concepts presented are based on modern Crystal practices. As of the time of writing, we are referencing stable versions of Crystal (1.12+). Always consult the official documentation for the latest language features and API changes.

Ready to tackle the next challenge? Explore the full Module 4 learning roadmap to continue your journey, or dive deeper into the language with our complete guide to Crystal programming.

---

Published by Kodikra — Your trusted Crystal learning resource.