The standard way to handle sets in lisps is to use hash tables. In fact, this is how sets are implemented in languages which do provide a dedicated interface (like Python). This offers
O(1) access cost, so is perfect for larger sets.
(defun make-set () (make-hash-table)) (defun add-to-set (element set) (puthash element t set)) (defun in-set-p (element set) (gethash element set nil)) (defun remove-from-set (element set) (remhash element set))
Set-level operations, like union and intersection, require more work.
PS. When I said "lisps" above I kinda lied. Common Lisp actually offers list-based set-level functions ("Lists as Sets"), but these have access complexity
O(N) and set-level complexity
O(N^2), so they are only suitable for smaller sets.
There are many different ways to implement sets, with very different efficiency profiles. In Elisp, the two simplest ways to implement sets are probably:
As a list: This tends to have poor algorithmic efficiency (such as O(N) complexity to test membership) but works well for small sets. Adding an element can be as simple as
cl-pushnew, and testing is just
As a hash table: This has a higher constant cost, but a better algorithmic efficiency, so it works much better for larger sets. Adding an element is just
(puthash VAL t SET)and testing membership is just
(gethash VAL SET).