How to create array of unique object list in Swift

Question

How can we create unique object list in Swift language like NSSet & NSMutableSet in Objective-C.

Desiccator

Why would this be downvoted? Swift has NSArray equivalents and NSDictionary equivalents, maybe it has sets too but they're simply not documented? – Banting

People downvote swift questions without considering that they might not be documented yet. – Heronry

Swift 1.2 adds a Set type. – Horologium

…and I guess I should also say that Swift 1.2 is available in the Xcode 6.3 beta. – Horologium

Answer 1

As of Swift 1.2 (Xcode 6.3 beta), Swift has a native set type. From the release notes:

A new Set data structure is included which provides a generic collection of unique elements, with full value semantics. It bridges with NSSet, providing functionality analogous to Array and Dictionary.

Here are some simple usage examples:

// Create set from array literal:
var set = Set([1, 2, 3, 2, 1])

// Add single elements:
set.insert(4)
set.insert(3)

// Add multiple elements:
set.unionInPlace([ 4, 5, 6 ])
// Swift 3: set.formUnion([ 4, 5, 6 ])

// Remove single element:
set.remove(2)

// Remove multiple elements:
set.subtractInPlace([ 6, 7 ])
// Swift 3: set.subtract([ 6, 7 ])

print(set) // [5, 3, 1, 4]

// Test membership:
if set.contains(5) {
    print("yes")
}

but there are far more methods available.

Update: Sets are now also documented in the "Collection Types" chapter of the Swift documentation.

Polecat

Yea for now just use NSMutableSet with addObject, removeObject, and allObject that pretty much does it. The native Set would be a nice thing to have later. – Spirometer

Answer 2

You can use any Objective-C class in Swift:

var set = NSMutableSet()
set.addObject(foo)

Maxma

You can, but if you try to put a Swift object in it it'll complain that it doesn't extend AnyObject. – Notum

Answer 3

Swift has no concept of sets. Using NSMutableSet in Swift might be slower than using a Dictionary that holds dummy values. You could do this :

var mySet: Dictionary<String, Boolean> = [:]
mySet["something"]= 1

Then just iterate over the keys.

Banting

Booleans in Swift are different than numbers. You probably meant true instead of 1. – Shandishandie

@Shandishandie You're thinking of the Bool struct; Boolean is a typealias for UInt8 in Swift. – Nairobi

IMO use Bool instead of Boolean. Bool is a swift data type and takes values true / false which can be stored in dictionaries – Leathers

Answer 4

I've built an extensive Set type similar to the built-in Array and Dictionary - here are blog posts one and two and a GitHub repository:

• Creating a Set Type in Swift
• Set Type Follow-up
• SwiftSets on GitHub

Lyckman

Answer 5

extension Array where Element: Hashable {
    var setValue: Set<Element> {
        return Set<Element>(self)
    }
}

let numbers = [1,2,3,4,5,6,7,8,9,0,0,9,8,7]
let uniqueNumbers = numbers.setValue    // {0, 2, 4, 9, 5, 6, 7, 3, 1, 8}

let names = ["John","Mary","Steve","Mary"]
let uniqueNames = names.setValue    // {"John", "Mary", "Steve"}

Allaallah

Answer 6

I thought a struct with an internal Dictionary would be the way to go. I have only just started using it, so it’s not complete and I have no idea on performance yet.

struct Set<T : Hashable>
{
    var _items : Dictionary<T, Bool> = [:]

    mutating func add(newItem : T) {
        _items[newItem] = true
    }

    mutating func remove(newItem : T) {
        _items[newItem] = nil
    }

    func contains(item: T) -> Bool {
        if _items.indexForKey(item) != nil { return true } else { return false }
    }

    var items : [T] { get { return [T](_items.keys) } }
    var count : Int { get { return _items.count } }
}

Horologium

Answer 7

You actually can create a Set object pretty easy (in contradiction to GoZoner, there is a built in contains method):

class Set<T : Equatable> {
    var items : T[] = []

    func add(item : T) {
        if !contains(items, {$0 == item}) {
            items += item
        }
    }
}

and you maybe even want to declare a custom operator:

@assignment @infix func += <T : Equatable> (inout set : Set<T>, items : T[]) -> Set<T> {
    for item in items {
        set.add(item)
    }
    return set
}

Constraint

I'm not sure why this was downvoted, it's not very efficient but it's definitely a viable solution for small sets. – Tacnaarica

Answer 8

Always in such a case the critical factor is how to compare objects and what types of objects go into the Set. Using a Swift Dictionary, where the Set objects are the dictionary keys, could be a problem based on the restrictions on the key type (String, Int, Double, Bool, valueless Enumerations or hashable).

If you can define a hash function on your object type then you can use a Dictionary. If the objects are orderable, then you could define a Tree. If the objects are only comparable with == then you'll need to iterate over the set elements to detect a preexisting object.

// When T is only Equatable
class Set<T: Equatable> {
  var items = Array<T>()

  func hasItem (that: T) {
   // No builtin Array method of hasItem... 
   //   because comparison is undefined in builtin Array   
   for this: T in items {
     if (this == that) {
       return true
     }
   }
   return false
  }

  func insert (that: T) {
    if (!hasItem (that))
      items.append (that)
  }
}

The above is an example of building a Swift Set; the example used objects that are only Equatable - which, while a common case, doesn't necessarily lead to an efficient Set implementations (O(N) search complexity - the above is an example).

Boycie

I think Equatable would be more correct than Comparable. Equatable is defined as protocol Equatable { func ==(lhs: Self, rhs: Self) -> Bool } while Comparable is protocol Comparable : Equatable { func <=(lhs: Self, rhs: Self) -> Bool func >=(lhs: Self, rhs: Self) -> Bool func >(lhs: Self, rhs: Self) -> Bool } – Tramline

Answer 9

So I think creating a Set with an array is a terrible idea - O(n) is the time complexity of that set.

I have put together a nice Set that uses a dictionary: https://github.com/evilpenguin/Swift-Stuff/blob/master/Set.swift

Gooey

Although for few elements an array is likely much faster. Cocoa collection classes often chose to return different subclasses of NSArray, NSSet etc depending on number of elements you used. – Laurilaurianne

The set implementation doesn't take into account hash collisions, where two objects create the same hash even though they are not identical. I believe a fully fledged implementation has to take into account equality as well as hash. – Loader

Answer 10

I wrote a function to solve this problem.

public func removeDuplicates<C: ExtensibleCollectionType where C.Generator.Element : Equatable>(aCollection: C) -> C {
    var container = C()

    for element in aCollection {
        if !contains(container, element) {
            container.append(element)
        }
    }

    return container
}

To use it, just pass an array which contains duplicate elements to this function. And then it will return a uniqueness-guaranteed array.

You also can pass a Dictionary, String or anything conforms to ExtensibleCollectionType protocol if you like.

Delorisdelorme

Note that this implementation is keeping the first occurence of each duplicate. – Tierratiersten

Answer 11

Special case for classes derived from NSObject

given that default Equitable (& Hashable) conformance in NSObject is basically trash you'd better make sure you provide a proper

static func == (lhs: YourClassDerivedFromNSObject, rhs: YourClassDerivedFromNSObject) -> Bool {

implementation lest you want plucking the duplicates inserted into Set

Boogiewoogie