By Altair357


2014-09-09 07:21:58 8 Comments

Nowadays in Swift you simply type Set( yourArray ) to make an array unique. (Or an ordered set if needed.)

Before that was possible, how was it done?


I might have an array that looks like the following:

[1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]

Or, really, any sequence of like-typed portions of data. What I want to do is ensure that there is only one of each identical element. For example, the above array would become:

[1, 4, 2, 6, 24, 15, 60]

Notice that the duplicates of 2, 6, and 15 were removed to ensure that there was only one of each identical element. Does Swift provide a way to do this easily, or will I have to do it myself?

30 comments

@deanWombourne 2016-03-16 23:23:32

Here's a category on SequenceType which preserves the original order of the array, but uses a Set to do the contains lookups to avoid the O(n) cost on Array's contains(_:) method.

public extension Sequence where Element: Hashable {

    /// Return the sequence with all duplicates removed.
    ///
    /// i.e. `[ 1, 2, 3, 1, 2 ].uniqued() == [ 1, 2, 3 ]`
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234, as 
    ///         per @Alexander's comment.
    func uniqued() -> [Element] {
        var seen = Set<Element>()
        return self.filter { seen.insert($0).inserted }
    }
}

If you aren't Hashable or Equatable, you can pass in a predicate to do the equality check:

extension Sequence {

    /// Return the sequence with all duplicates removed.
    ///
    /// Duplicate, in this case, is defined as returning `true` from `comparator`.
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234
    func uniqued(comparator: @escaping (Element, Element) throws -> Bool) rethrows -> [Element] {
        var buffer: [Element] = []

        for element in self {
            // If element is already in buffer, skip to the next element
            if try buffer.contains(where: { try comparator(element, $0) }) {
                continue
            }

            buffer.append(element)
        }

        return buffer
    }
}

Now, if you don't have Hashable, but are Equatable, you can use this method:

extension Sequence where Element: Equatable {

    /// Return the sequence with all duplicates removed.
    ///
    /// i.e. `[ 1, 2, 3, 1, 2 ].uniqued() == [ 1, 2, 3 ]`
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234
    func uniqued() -> [Element] {
        return self.uniqued(comparator: ==)
    }
}

Finally, you can add a key path version of uniqued like this:

extension Sequence {

    /// Returns the sequence with duplicate elements removed, performing the comparison usinig the property at
    /// the supplied keypath.
    ///
    /// i.e.
    ///
    /// ```
    /// [
    ///   MyStruct(value: "Hello"),
    ///   MyStruct(value: "Hello"),
    ///   MyStruct(value: "World")
    ///  ].uniqued(\.value)
    /// ```
    /// would result in
    ///
    /// ```
    /// [
    ///   MyStruct(value: "Hello"),
    ///   MyStruct(value: "World")
    /// ]
    /// ```
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234
    ///
    func uniqued<T: Equatable>(_ keyPath: KeyPath<Element, T>) -> [Element] {
        self.uniqued { $0[keyPath: keyPath] == $1[keyPath: keyPath] }
    }
}

You can stick both of these into your app, Swift will choose the right one depending on your sequence's Iterator.Element type.

@Alexander - Reinstate Monica 2018-12-16 20:35:21

Heyyy finally someone with an O(n) solution. You can combine the "check" and "insert" set operations into one, by the way. See stackoverflow.com/a/46354989/3141234

@deanWombourne 2018-12-18 09:59:52

Oh, that's clever :)

@Erik Aigner 2020-04-02 15:22:08

Here is a solution that

  • Uses no legacy NS types
  • Is reasonably fast with O(n)
  • Is concise
  • Preserves element order
extension Array where Element: Hashable {

    var uniqueValues: [Element] {
        var allowed = Set(self)
        return compactMap { allowed.remove($0) }
    }
}

@vilas deshmukh 2020-03-14 10:30:48

Swift 3/ Swift 4/ Swift 5

Just one line code to omit Array duplicates without effecting order:

let filteredArr = Array(NSOrderedSet(array: yourArray))

@vilas deshmukh 2020-03-14 10:42:50

Here we are typecasting an array into Orderedset. Definition of "Sets" - sets allow only distinct values (It does not allow duplicates). Hence duplicates will be omitted As we are typecasting with NSOrderedSet hence array order will not be disturbed.

@Tim MB 2019-05-16 19:33:58

Think like a functional programmer :)

To filter the list based on whether the element has already occurred, you need the index. You can use enumerated to get the index and map to return to the list of values.

let unique = myArray
    .enumerated()
    .filter{ myArray.firstIndex(of: $0.1) == $0.0 }
    .map{ $0.1 }

This guarantees the order. If you don't mind about the order then the existing answer of Array(Set(myArray)) is simpler and probably more efficient.


UPDATE: Some notes on efficiency and correctness

A few people have commented on the efficiency. I'm definitely in the school of writing correct and simple code first and then figuring out bottlenecks later, though I appreciate it's debatable whether this is clearer than Array(Set(array)).

This method is a lot slower than Array(Set(array)). As noted in comments, it does preserve order and works on elements that aren't Hashable.

However, @Alain T's method also preserves order and is also a lot faster. So unless your element type is not hashable, or you just need a quick one liner, then I'd suggest going with their solution.

Here are a few tests on a MacBook Pro (2014) on Xcode 11.3.1 (Swift 5.1) in Release mode.

The profiler function and two methods to compare:

func printTimeElapsed(title:String, operation:()->()) {
    var totalTime = 0.0
    for _ in (0..<1000) {
        let startTime = CFAbsoluteTimeGetCurrent()
        operation()
        let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        totalTime += timeElapsed
    }
    let meanTime = totalTime / 1000
    print("Mean time for \(title): \(meanTime) s")
}

func method1<T: Hashable>(_ array: Array<T>) -> Array<T> {
    return Array(Set(array))
}

func method2<T: Equatable>(_ array: Array<T>) -> Array<T>{
    return array
    .enumerated()
    .filter{ array.firstIndex(of: $0.1) == $0.0 }
    .map{ $0.1 }
}

// Alain T.'s answer (adapted)
func method3<T: Hashable>(_ array: Array<T>) -> Array<T> {
    var uniqueKeys = Set<T>()
    return array.filter{uniqueKeys.insert($0).inserted}
}

And a small variety of test inputs:

func randomString(_ length: Int) -> String {
  let letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
  return String((0..<length).map{ _ in letters.randomElement()! })
}

let shortIntList = (0..<100).map{_ in Int.random(in: 0..<100) }
let longIntList = (0..<10000).map{_ in Int.random(in: 0..<10000) }
let longIntListManyRepetitions = (0..<10000).map{_ in Int.random(in: 0..<100) }
let longStringList = (0..<10000).map{_ in randomString(1000)}
let longMegaStringList = (0..<10000).map{_ in randomString(10000)}

Gives as output:

Mean time for method1 on shortIntList: 2.7358531951904296e-06 s
Mean time for method2 on shortIntList: 4.910230636596679e-06 s
Mean time for method3 on shortIntList: 6.417632102966309e-06 s
Mean time for method1 on longIntList: 0.0002518167495727539 s
Mean time for method2 on longIntList: 0.021718120217323302 s
Mean time for method3 on longIntList: 0.0005312927961349487 s
Mean time for method1 on longIntListManyRepetitions: 0.00014377200603485108 s
Mean time for method2 on longIntListManyRepetitions: 0.0007293639183044434 s
Mean time for method3 on longIntListManyRepetitions: 0.0001843773126602173 s
Mean time for method1 on longStringList: 0.007168249964714051 s
Mean time for method2 on longStringList: 0.9114790915250778 s
Mean time for method3 on longStringList: 0.015888616919517515 s
Mean time for method1 on longMegaStringList: 0.0525397013425827 s
Mean time for method2 on longMegaStringList: 1.111266262292862 s
Mean time for method3 on longMegaStringList: 0.11214958941936493 s

@Porter Child 2019-10-21 20:11:16

unlike Array(Set(myArray)), this works for things that aren't Hashable

@Sander Saelmans 2020-02-10 06:50:29

... and unlike Array(Set(myArray)) the order of your array is maintained.

@oradyvan 2020-02-13 10:22:01

It looks like the best answer to me, at least at the present when Swift 5 is already the current version.

@Colin Stark 2020-02-14 08:18:59

This is a very elegant solution; unfortunately, it's also rather slow.

@Alexander - Reinstate Monica 2020-02-15 03:44:53

This is really slow. If you wanted to keep the last of each element, you would be better users a better implementation, and doing array.reversed().unique().reversed().

@Tim MB 2020-02-16 13:59:30

@Alexander-ReinstateMonica I don't understand your suggestion of array.reversed().unique().reversed(). The above solution keeps the first rather than the last of each element, and as far as I know there is no unique() method - that is the whole point of the question. Anyway, I don't doubt it's probably not the fastest method but unless it's in a performance sensitive place I'd go with readability and clarity of correctness over optimisation.

@Alexander - Reinstate Monica 2020-02-16 16:21:44

@TimMB Oh I misread your post. I saw someone's adaptation that usedthe lastIndex(of:). I totally disagree over the clarity vs optimization point in this case. I don't think this implementation is particularly clear, especially compared to a simple set-based solution. In any case, such code should be extracted out to an extension function. This algorithm becomes basically unusable at even a low input size, like in the thousands to tens of thousands. It's not hard to find such data sets, people can have thousands of songs, files, contacts, etc.

@Alexander - Reinstate Monica 2020-02-17 14:54:06

@TimMB You can achieve the same goal of uniquing non-Hashable elements, keeping the first ones, by using Array for contains checks, similar to how the set is being used. That removes the need for enumerated (which doesn't really cost much) and the final map call (which does one full sweep of the full array). Furthermore, you can use .reserveCapacity on the set/array, to tradeoff some extra memory use for removing the need for reallocations mid-way through the algorithm.

@Alexander - Reinstate Monica 2020-02-17 15:14:02

@TimMB Other things to consider: method3 allows for an implementation that removes elements inline from the existing buffer using removeAll, which isn't possible with methods 1 or 2. Method 2 and 3 are also generalizable to sequences that aren't Collection (which might not be re-iterable)

@Alexander - Reinstate Monica 2020-02-18 15:16:16

@Jas_meet 2020-04-28 19:54:50

This is absolute gold

@blackjacx 2018-08-02 22:12:04

Swift 5

extension Sequence where Element: Hashable {
    func unique() -> [Element] {
        NSOrderedSet(array: self as! [Any]).array as! [Element]
    }
}

@Marcelo de Aguiar 2018-08-07 14:10:17

I did some variation so I could select a key to compare. extension Sequence { // Returns distinct elements based on a key value. func distinct<key: Hashable>(by: ((_ el: Iterator.Element) -> key)) -> [Iterator.Element] { var existing = Set<key>() return self.filter { existing.insert(by($0)).inserted } } }

@Alexander - Reinstate Monica 2020-02-15 03:46:59

There no need to use a Bool, when the only value you use is true. You're reaching for a "unit type" (a type with only one possible value). Swift's unit type is Void, whose only value is () (a.k.a. the empty tuple). So you can just use [T: Void]. Though you shouldn't do that, because you've basically just invented Set. Use Set instead. See stackoverflow.com/a/55684308/3141234 Please delete this answer.

@Deepak Yadeedya 2019-11-24 06:13:30

I think this the better way with knowing the logic itself

var arrayOfInts = [2, 2, 4, 4]
var mainArray = [Int]()

for value in arrayOfInts {

if mainArray.contains(value) == false  {

    mainArray.append(value)
    print("mainArray:\(mainArray)")
}}

@Alexander - Reinstate Monica 2020-02-15 03:40:04

This is quadratic behavior. Each iteration of your loop call contains, which itself uses a loop over all elements. Really slow.

@Sander Saelmans 2019-11-20 14:24:51

A slighly shorted version based on @Jean-Philippe Pellet's array extension answer:

extension Array where Element: Hashable {

    var uniques: Array {
        var added = Set<Element>()
        return filter { element in
            defer { added.insert(element) }
            return !added.contains(element)
        }
    }
}

@Alexander - Reinstate Monica 2020-02-15 03:41:35

This does two hashing operations per element, which is unnecessary. insert returns a tuple that tells you whether the element was already there, or was added for the first time. stackoverflow.com/a/55684308/3141234 Please delete this answer.

@Jessy 2015-11-05 19:41:03

If you put both extensions in your code, the faster Hashable version will be used when possible, and the Equatable version will be used as a fallback.

public extension Sequence where Element: Hashable {
  var firstUniqueElements: [Element] {
    var set: Set<Element> = []
    return filter { set.insert($0).inserted }
  }
}

public extension Sequence where Element: Equatable {
  var firstUniqueElements: [Element] {
    reduce(into: []) { uniqueElements, element in
      if !uniqueElements.contains(element) {
        uniqueElements.append(element)
      }
    }
  }
}

If order isn't important, then you can always just use this Set initializer.

@David Seek 2016-12-21 17:35:45

okay, got it. i wasnt able to call it because my array is an array of structs... how would i handle it in my case? struct of 20 different variables, string and [string]

@Jessy 2016-12-21 20:49:57

@David Seek It sounds like you haven't made your strict hashable or equatable. Is that correct?

@Mert Celik 2018-08-16 21:29:03

@DavidSeek like this, uniqueArray = nonUniqueArray.uniqueElements

@David Seek 2018-08-16 22:11:23

yeah dont worry. got it working right after. been almost 2 years now :P

@Duncan C 2018-09-03 15:59:09

This will have O(n²) time performance, which is really bad for large arrays.

@Duncan C 2018-09-03 16:03:04

The hahsable version will have better performance, but won't preserve the order of elements in the original array. Leo's answer will give both O(n) performance AND preserve object ordering.

@Jessy 2018-09-03 19:44:29

@DuncanC The answer you’re referring to only “preserves ordering” for arrays in which the first instances of elements are ordered.

@Duncan C 2018-09-03 20:56:17

More precisely, it preserves the original order of the array (whatever that is) and removes all but the first occurrence of duplicate items.

@Alexander - Reinstate Monica 2018-12-17 00:41:12

@Jessy There are already multiple O(1) answers, but they have way less votes than most of the naive O(n^2) solutions. This one is particularly good for its simplicity: stackoverflow.com/a/46354989/3141234

@Jessy 2018-12-17 04:08:52

@Alexander That requires Hashable. As I state in my answer, my Hashable implementation from Swift 3 translates directly to Swift 4. You need to include solutions for both Hashable and Equatable for the beginning of my answer to be accurate.

@Cœur 2019-04-15 07:26:07

Inspired by https://www.swiftbysundell.com/posts/the-power-of-key-paths-in-swift, we can declare a more powerful tool that is able to filter for unicity on any keyPath. Thanks to Alexander comments on various answers regarding complexity, the below solutions should be near optimal.

Non-mutating solution

We extend with a function that is able to filter for unicity on any keyPath:

extension RangeReplaceableCollection {
    /// Returns a collection containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> Self {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}

Note: in the case where your object doesn't conform to RangeReplaceableCollection, but does conform to Sequence, you can have this additional extension, but the return type will always be an Array:

extension Sequence {
    /// Returns an array containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> [Element] {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}

Usage

If we want unicity for elements themselves, as in the question, we use the keyPath \.self:

let a = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
let b = a.unique(for: \.self)
/* b is [1, 4, 2, 6, 24, 15, 60] */

If we want unicity for something else (like for the id of a collection of objects) then we use the keyPath of our choice:

let a = [CGPoint(x: 1, y: 1), CGPoint(x: 2, y: 1), CGPoint(x: 1, y: 2)]
let b = a.unique(for: \.y)
/* b is [{x 1 y 1}, {x 1 y 2}] */

Mutating solution

We extend with a mutating function that is able to filter for unicity on any keyPath:

extension RangeReplaceableCollection {
    /// Keeps only, in order, the first instances of
    /// elements of the collection that compare equally for the keyPath.
    mutating func uniqueInPlace<T: Hashable>(for keyPath: KeyPath<Element, T>) {
        var unique = Set<T>()
        removeAll { !unique.insert($0[keyPath: keyPath]).inserted }
    }
}

Usage

If we want unicity for elements themselves, as in the question, we use the keyPath \.self:

var a = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
a.uniqueInPlace(for: \.self)
/* a is [1, 4, 2, 6, 24, 15, 60] */

If we want unicity for something else (like for the id of a collection of objects) then we use the keyPath of our choice:

var a = [CGPoint(x: 1, y: 1), CGPoint(x: 2, y: 1), CGPoint(x: 1, y: 2)]
a.uniqueInPlace(for: \.y)
/* a is [{x 1 y 1}, {x 1 y 2}] */

@Alexander - Reinstate Monica 2019-04-15 15:42:36

Now that's a good implementation! I only with that key paths were convertible to closures, so that you can use a closure arg to support both arbitrary code (in closures) and mere property look ups (via key paths). Only change I would make is to make keyPath default to \.self, because that's probably the majority of use cases.

@Cœur 2019-04-15 18:33:38

@Alexander I tried to default to Self, but then I would need to make Element always Hashable. An alternative to a default value is adding a simple overload without parameters: extension Sequence where Element: Hashable { func unique() { ... } }

@Alexander - Reinstate Monica 2019-04-15 20:49:10

Ah yes, makes sense!

@BonanzaDriver 2019-10-01 22:08:07

Brilliant ... simple, and best of all 'flexible'. Thx.

@FizzBuzz 2020-07-02 22:51:18

@Alexander-ReinstateMonica: This looks very similar to your own solution from March 2018: gist.github.com/amomchilov/fbba1e58c91fbd4b5b767bcf8586112b 👏👏👏

@Cœur 2020-07-03 09:12:45

Ah, @FizzBuzz, that's a good find. Congrats to Martin R and Alexander for being, like John Sundell, avant-gardists of those techniques.

@Alexander - Reinstate Monica 2020-07-03 13:35:49

@FizzBuzz I have no idea how you found that, but that's been kind of interesting to see. I forget that all this random crap I put out on the internet sticks around and get eventually seened by people. I can only hope it helped :p

@Sanjay Mishra 2019-10-07 12:21:32

In Swift 5

 var array: [String] =  ["Aman", "Sumit", "Aman", "Sumit", "Mohan", "Mohan", "Amit"]

 let uniq = Array(Set(array))
 print(uniq)

Output Will be

 ["Sumit", "Mohan", "Amit", "Aman"]

@Alexander - Reinstate Monica 2020-02-15 03:37:51

This is a repeat of many of the answers already here, and it doesn't preserve ordering.

@Jean-Philippe Pellet 2014-09-09 08:02:50

You can roll your own, e.g. like this (updated for Swift 1.2 with Set):

func uniq<S : SequenceType, T : Hashable where S.Generator.Element == T>(source: S) -> [T] {
    var buffer = [T]()
    var added = Set<T>()
    for elem in source {
        if !added.contains(elem) {
            buffer.append(elem)
            added.insert(elem)
        }
    }
    return buffer
}

let vals = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
let uniqueVals = uniq(vals) // [1, 4, 2, 6, 24, 15, 60]

Swift 3 version:

func uniq<S : Sequence, T : Hashable>(source: S) -> [T] where S.Iterator.Element == T {
    var buffer = [T]()
    var added = Set<T>()
    for elem in source {
        if !added.contains(elem) {
            buffer.append(elem)
            added.insert(elem)
        }
    }
    return buffer
}

And as an extension for Array:

extension Array where Element: Hashable {
    var uniques: Array {
        var buffer = Array()
        var added = Set<Element>()
        for elem in self {
            if !added.contains(elem) {
                buffer.append(elem)
                added.insert(elem)
            }
        }
        return buffer
    }
}

@Airspeed Velocity 2014-12-23 17:10:40

You could also implement the body of that function as var addedDict = [T:Bool](); return filter(source) { addedDict(true, forKey: $0) == nil }

@Jean-Philippe Pellet 2014-12-24 20:01:53

Very nice. Your solution will be my preferred approach for this kind of situations from now on.

@Jawwad 2015-01-25 01:38:41

@AirspeedVelocity: Did you mean updateValue(true, forKey: $0)... instead of addedDict(true, forKey: $0)...

@Airspeed Velocity 2015-01-25 01:48:39

Oops yes sorry I accidentally the method! Should be return filter(source) { addedDict.updateValue(true, forKey: $0) == nil } as you say.

@whoKnows 2016-01-16 22:39:00

Is this answer, or converting it to a set faster?

@Jean-Philippe Pellet 2016-01-17 20:10:20

Converting to a set, I suppose. I don't see how this one could possibly be faster, as it indeed adds each element to the set, with additional logic on top. But this approach preserves the initial order, which may be a necessity.

@Blixt 2016-02-04 14:52:50

Just a word of caution: Avoid discussing performance for simple functions like this until you provably depend on their performance, at which point the only thing you should do is benchmark. Too often have I seen unmaintainable code or even less performant code due to making assumptions. :) Also, this is probably easier to grasp: let uniques = Array(Set(vals))

@Jean-Philippe Pellet 2016-02-04 19:28:59

@Blixt Agreed. Once again, here the advantage lies in respecting the order of elements of the original array.

@lvp 2016-09-08 07:51:50

What would be safest way to define this method as extension of SequenceType? Does it need to be mutating? I tried myself, but failed :/

@Honey 2018-05-10 12:37:32

Why do you limit T to be Hashable? I'm assuming it's because if it's not Hashable you're not allowed to use on Sets. I'm trying to remove duplicates from an multi-demensional array, but since arrays aren't hashable...I'm thinking I should simply just append them to an array, rather than inserting. Obviously using sets are faster because it benefits from hashing...

@Nirav Hathi 2018-06-07 05:07:30

i have [[1,2,4],[1,2,3],[2,3,1],[2,3,4]] this kind of array so what i have to change in your code

@wardw 2018-06-22 11:09:56

@Jean-PhilippePellet @Blixt Some cursory benchmarking: For a large number of elements, observed all Set based variants to benchmark roughly the same - just minor differences over the implementations here (5-10%). Only the use of a Dictionary over Set benchmarks consistently slower (~0.5x). Release -O, swift 4.1

@Honey 2019-04-15 14:59:13

@Cœur I wrote that comment a while ago. Wouldn't it be better to limit it Equatable. That way it be more inclusive?

@Cœur 2019-04-15 18:26:48

@Honey if you use Equatable, then you can't use a Set (you'd need an Array) and you lose in performances. So you should only add an Equatable overload if you really need it. I would be curious to know your use case.

@Honey 2019-04-15 18:50:51

@Cœur I don't remember my case. Merely pointing out that this implementation is restricting, but possibly more optimized.

@Mahendra Thotakura 2019-07-22 09:45:01

  1. First add all the elements of an array to NSOrderedSet.
  2. This will remove all the duplicates in your array.
  3. Again convert this orderedset to an array.

Done....

Example

let array = [1,1,1,1,2,2,2,2,4,6,8]

let orderedSet : NSOrderedSet = NSOrderedSet(array: array)

let arrayWithoutDuplicates : NSArray = orderedSet.array as NSArray

output of arrayWithoutDuplicates - [1,2,4,6,8]

@Abhijit 2019-07-18 04:03:24

I have created a higher-order function that has time complexity is o(n). Also, capability like the map to return any type you want.

extension Sequence {
    func distinct<T,U>(_ provider: (Element) -> (U, T)) -> [T] where U: Hashable {
        var uniqueKeys = Set<U>()
        var distintValues = [T]()
        for object in self {
            let transformed = provider(object)
            if !uniqueKeys.contains(transformed.0) {
                distintValues.append(transformed.1)
                uniqueKeys.insert(transformed.0)
            }
        }
        return distintValues
    }
}

@Alexander - Reinstate Monica 2020-02-15 03:42:28

This does two hashing operations per element, which is unnecessary. insert returns a tuple that tells you whether the element was already there, or was added for the first time. stackoverflow.com/a/55684308/3141234 Please delete this answer.

@Michał Ziobro 2019-07-15 13:40:43

My solution, it seems it can be in O(n) time as Hash map access is O(1), and filter is O(n). It also uses by closure to select property by which to make the distinction of elements in sequence.

extension Sequence {

    func distinct<T: Hashable>(by: (Element) -> T) -> [Element] {
        var seen: [T: Bool] = [:]
        return self.filter { seen.updateValue(true, forKey: by($0)) == nil }
    }
}

@Alexander - Reinstate Monica 2020-02-15 03:44:09

There no need to use a Bool, when the only value you use is true. You're reaching for a "unit type" (a type with only one possible value). Swift's unit type is Void, whose only value is () (a.k.a. the empty tuple). So you can just use [T: Void]. Though you shouldn't do that, because you've basically just invented Set. Use Set instead. See stackoverflow.com/a/55684308/3141234 Please delete this answer.

@Leo Dabus 2016-01-11 00:09:44

edit/update Swift 4 or later

We can also extend RangeReplaceableCollection protocol to allow it to be used with StringProtocol types as well:

extension RangeReplaceableCollection where Element: Hashable {
    var orderedSet: Self {
        var set = Set<Element>()
        return filter { set.insert($0).inserted }
    }
    mutating func removeDuplicates() {
        var set = Set<Element>()
        removeAll { !set.insert($0).inserted }
    }
}

let integers = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
let integersOrderedSet = integers.orderedSet // [1, 4, 2, 6, 24, 15, 60]

"abcdefabcghi".orderedSet  // "abcdefghi"
"abcdefabcghi".dropFirst(3).orderedSet // "defabcghi"

Mutating method:

var string = "abcdefabcghi"
string.removeDuplicates() 
string  //  "abcdefghi"

var substring = "abcdefabcdefghi".dropFirst(3)  // "defabcdefghi"
substring.removeDuplicates()
substring   // "defabcghi"

For Swift 3 click here

@DeyaEldeen 2016-09-28 12:01:14

I like this, it works with an array of dictionarys too!

@Alexander - Reinstate Monica 2016-11-13 23:16:53

O(N^2) is bad :(

@Cœur 2017-06-16 03:08:31

@Alexander Leo Dabus has replaced the reduce implementation, so now the complexity is different.

@Duncan C 2017-09-11 19:50:56

What is the expression .inserted above? I can't find it anywhere.

@Leo Dabus 2017-09-11 19:54:06

@DuncanC it is the return value from the insert method.developer.apple.com/documentation/swift/set/1541375-i‌​nsert it returns a tuple. (inserted: Bool, memberAfterInsert: Element) if newMember was not contained in the set. If an element equal to newMember was already contained in the set, the method returns (false, oldMember), where oldMember is the element that was equal to newMember. In some cases, oldMember may be distinguishable from newMember by identity comparison or some other means.

@Duncan C 2017-09-11 20:09:27

Yup, I found it finally. That's very cool. What's the time complexity of your solution? At a glance I think it would be n • log(n), since sets use hashes to determine membership. The naive solution of using array.contains yields n^2 performance, which is really bad.

@Leo Dabus 2017-09-11 20:28:34

@DuncanC I don't know the complexity but I think it can't get any faster than that

@Duncan C 2017-09-11 20:36:01

I just did a quick test on 1m and 8m items, and it seems to run in O(n) time!

@Leo Dabus 2017-09-11 20:40:17

Which one is faster flatmap or filter ? Or is it the same?

@Duncan C 2017-09-12 16:00:18

The results are interesting. For both 1 million unique items and 8 million, the filter version is faster. However, the filter-based version takes 8.38x longer for 8 million unique items (a hair over O(n) time), where the flatmap-based version takes 7.47x longer for 8 million unique entries than 1 million, suggesting that the flatmap based version scales better. Somehow the flatmap based version does slightly better than O(n) time!

@Duncan C 2017-09-12 16:09:46

In fact, when I run the test with 64x more items in the array, the flatmap based version is faster.

@Leo Dabus 2018-09-03 23:26:48

@Jessy yes it keeps the original order. It is not called sortedSet. Btw it uses the same name Apple uses in NSOrderedSet just dropping the NS

@Jessy 2018-09-03 23:37:08

"Original order" is an undefined concept, but wow, you are correct about Apple naming it wrong too. NSOrderedSet(array: [1, 3, 2, 3]) does not enforce order; it's [1, 3, 2].

@Leo Dabus 2018-09-03 23:40:20

kkkk Why do you think your way is correct? How would you name it? Note that this method it is not restricted to numbers. Its is constrained to Hashable not Comparable

@user28434 2019-04-10 12:35:50

@Jessy, ordered collection means that no matter how many times you gonna access it, it will have same order of elements. Like Array, each element will stay on it's place. For Set and Dictionary it's not true, if you will try to iterate over or print content you may have elements in different order each time. And that type of collections is called unordered.

@Cœur 2019-04-12 07:59:46

@DuncanC a filter { expression } is a flatmap { expression ? $0 : nil }, so there shouldn't be any difference and I recommend filter for readability.

@Alain T. 2017-03-16 11:41:08

For arrays where the elements are neither Hashable nor Comparable (e.g. complex objects, dictionaries or structs), this extension provides a generalized way to remove duplicates:

extension Array
{
   func filterDuplicate<T:Hashable>(_ keyValue:(Element)->T) -> [Element]
   {
      var uniqueKeys = Set<T>()
      return filter{uniqueKeys.insert(keyValue($0)).inserted}
   }

   func filterDuplicate<T>(_ keyValue:(Element)->T) -> [Element]
   { 
      return filterDuplicate{"\(keyValue($0))"}
   }
}

// example usage: (for a unique combination of attributes):

peopleArray = peopleArray.filterDuplicate{ ($0.name, $0.age, $0.sex) }

or...

peopleArray = peopleArray.filterDuplicate{ "\(($0.name, $0.age, $0.sex))" }

You don't have to bother with making values Hashable and it allows you to use different combinations of fields for uniqueness.

Note: for a more robust approach, please see the solution proposed by Coeur in the comments below.

stackoverflow.com/a/55684308/1033581

[EDIT] Swift 4 alternative

With Swift 4.2 you can use the Hasher class to build a hash much easier. The above extension could be changed to leverage this :

extension Array
{
    func filterDuplicate(_ keyValue:((AnyHashable...)->AnyHashable,Element)->AnyHashable) -> [Element]
    {
        func makeHash(_ params:AnyHashable ...) -> AnyHashable
        { 
           var hash = Hasher()
           params.forEach{ hash.combine($0) }
           return hash.finalize()
        }  
        var uniqueKeys = Set<AnyHashable>()
        return filter{uniqueKeys.insert(keyValue(makeHash,$0)).inserted}     
    }
}

The calling syntax is a little different because the closure receives an additional parameter containing a function to hash a variable number of values (which must be Hashable individually)

peopleArray = peopleArray.filterDuplicate{ $0($1.name, $1.age, $1.sex) } 

It will also work with a single uniqueness value (using $1 and ignoring $0).

peopleArray = peopleArray.filterDuplicate{ $1.name } 

@Cœur 2017-06-16 01:41:13

This could give random results depending on the behavior of "\()", as it may not gives you unique values like conforming to Hashable should. Example, if your elements conform to Printable by all returning the same description, then your filtering fails.

@Alain T. 2017-06-16 12:27:46

Agreed. Selection of the fields (or formula) that will produce the desired uniqueness pattern will have to take this into account. For many use cases, this provides a simple ad-hoc solution that requires no alteration of the element's class or struct.

@Alexander - Reinstate Monica 2018-12-16 20:37:47

@AlainT. Don't do this, really. String's purpose is not to be some ghetto ad-hoc key generation mechanism. Just constrain T to being Hashable.

@Cœur 2019-04-15 07:26:55

@Alexander I've applied this idea in a new answer: stackoverflow.com/a/55684308/1033581

@Hardik Thakkar 2019-06-07 07:24:18

Perfect answer as i want. Thank you so much.

@Saranjith 2019-01-17 09:58:20

Xcode 10.1 - Swift 4.2 Simple and Powerful Solution

func removeDuplicates(_ nums: inout [Int]) -> Int {
    nums = Set(nums).sorted()
    return nums.count
}

Example

var arr = [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9]
removeDuplicates(&arr)

print(arr) // [1,2,3,4,5,6,7,8,9]

@Cœur 2019-04-15 07:03:59

This does not keep the original order: it applies a new order, which may or may not be the same. Even if it's the same order, it's not as performant as a solution that would simply keep the existing order without adding an extra sorted.

@Alexander - Reinstate Monica 2020-02-15 03:46:05

Yeah, the sorted() call is a totally misplaced responsibility. The caller asked for deduplication. If they also wanted sorting they can already do that themselves. I would suggest deleting this answer.

@Pliskin 2014-11-20 15:31:00

An alternate (if not optimal) solution from here using immutable types rather than variables:

func deleteDuplicates<S: ExtensibleCollectionType where S.Generator.Element: Equatable>(seq:S)-> S {
    let s = reduce(seq, S()){
        ac, x in contains(ac,x) ? ac : ac + [x]
    }
    return s
}

Included to contrast Jean-Pillippe's imperative approach with a functional approach.

As a bonus this function works with strings as well as arrays!

Edit: This answer was written in 2014 for Swift 1.0 (before Set was available in Swift). It doesn't require Hashable conformance & runs in quadratic time.

@Airspeed Velocity 2014-12-23 17:03:30

Beware, there are not one, but two ways this runs in quadratic time – both contains and array append run in O(n). Though it does have the benefit of only requiring equatable, not hashable.

@Alexander - Reinstate Monica 2018-12-16 21:13:22

this is a really complicated way of writing filter. It's O(n^2) (which is required if you don't want to require Hashable conformance), but you should at least call that out explicitly

@Mauricio Chirino 2018-04-06 16:56:23

In case you need values sorted, this works (Swift 4)

let sortedValues = Array(Set(array)).sorted()

@Shmidt 2018-11-16 18:13:36

You loosing elements order in this case.

@Mauricio Chirino 2018-11-19 18:44:16

Not at all, that's what the .sorted() at the end is for. Regards.

@Alexander - Reinstate Monica 2018-12-16 20:27:18

@MauricioChirino And if your original array was [2, 1, 1]? It would come out [1, 2], that's not ordered :p

@Alexander - Reinstate Monica 2018-12-20 20:48:06

@MauricioChirino No, it wouldn't. The correct answer would be [2, 1], but this would return [1, 2], which is wrong.

@Mauricio Chirino 2018-12-26 13:09:12

I think you're confusing sorted with reversed @Alexander.

@Alexander - Reinstate Monica 2018-12-27 18:30:43

@MauricioChirino No, I'm not. If the goal is to remove duplicate values from a sequence, while retaining the order in which elements uniquely appeared, this doesn't do that. The very clear counter example is [2, 1, 1]. The first appearance of unique elements, in order is [2, 1]. That's the correct answer. But using your (incorrect) algorithm, you get [1, 2], which is sorted, but is not in the correct, original, order.

@Mauricio Chirino 2018-12-28 12:39:37

You're right, I've edited the answer. Regards @Alexander

@Mecki 2019-07-09 15:19:24

Fails if the elements in array are not Hashable; only Hashable data types can be added to a Set, yet any data type can be added to an array.

@Deepak Yadeedya 2018-09-06 12:14:15

this is the simplest way in swift 4.2 onwards the code like below

let keyarray:NSMutableArray = NSMutableArray()

for  object in dataArr
{
    if !keysArray.contains(object){
        keysArray.add(object)
    }
}

print(keysArray)

@Alexander - Reinstate Monica 2018-12-16 20:22:31

Ooof. Don't do this. That's an O(n^2) algorithm (because contains is O(n), which itself runs n times). And don't use NSMutableArray in Swift

@Rok Gregorič 2018-06-12 12:31:10

Swift 4.x:

extension Sequence where Iterator.Element: Hashable {
  func unique() -> [Iterator.Element] {
    return Array(Set<Iterator.Element>(self))
  }

  func uniqueOrdered() -> [Iterator.Element] {
    return reduce([Iterator.Element]()) { $0.contains($1) ? $0 : $0 + [$1] }
  }
}

usage:

["Ljubljana", "London", "Los Angeles", "Ljubljana"].unique()

or

["Ljubljana", "London", "Los Angeles", "Ljubljana"].uniqueOrdered()

@Alexander - Reinstate Monica 2018-12-16 20:23:27

This is O(n^2). Don't do this.

@mxcl 2017-09-22 00:10:47

Swift 4

public extension Array where Element: Hashable {
    func uniqued() -> [Element] {
        var seen = Set<Element>()
        return filter{ seen.insert($0).inserted }
    }
}

every attempt to insert will also return a tuple: (inserted: Bool, memberAfterInsert: Set.Element). See documentation.

Using the returned value helps us to avoid looping or doing any other operation.

@Kelvin 2018-04-04 19:36:47

After simple profiling, this method is really fast. Its hundreds times faster then using reduce( _: _:), or even reduce(into: _:)

@Alexander - Reinstate Monica 2018-12-16 20:24:21

@Kelvin Because all those other algorithm were O(n^2), and nobody noticed.

@Cœur 2018-12-16 23:59:39

@Kelvin this answer is identical to Eneko Alonso answer + my comment (Jun 16 '17).

@Johannes 2018-05-08 08:43:13

This works in Swift 4, if you do not want/need to convert the result to an Array, but can do with a Set. The result is not sorted by default, but you can do that with sorted(), which returns an array, as shown in the print statement.

let array = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]

var result = Set<Int>()
_ = array.map{ result.insert($0) }

print(result.sorted())  // [1, 2, 4, 6, 15, 24, 60]

@Alexander - Reinstate Monica 2018-12-16 20:26:05

This irreversibly loses ordering. Sorting only makes sense if your original ordering was sorted order, which isn't the case your example. Also, don't abuse map where forEach would make more sense. Even still, it could be just let result = Set(array)

@sgl0v 2018-04-25 11:54:45

The easiest way would be to use NSOrderedSet, that stores unique elements and preserves the elements order. Like:

func removeDuplicates(from items: [Int]) -> [Int] {
    let uniqueItems = NSOrderedSet(array: items)
    return (uniqueItems.array as? [Int]) ?? []
}

let arr = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
removeDuplicates(from: arr)

@Alexander - Reinstate Monica 2018-12-16 20:26:45

I wonder how this performance compares to the better answers on here. Have you compared?

@MarkHim 2018-02-19 15:13:37

Here's a more flexible way to make a sequence unique with a custom matching function.

extension Sequence where Iterator.Element: Hashable {

    func unique(matching: (Iterator.Element, Iterator.Element) -> Bool) -> [Iterator.Element] {

        var uniqueArray: [Iterator.Element] = []
        forEach { element in
            let isUnique = uniqueArray.reduce(true, { (result, item) -> Bool in
                return result && matching(element, item)
            })
            if isUnique {
                uniqueArray.append(element)
            }
        }
        return uniqueArray
    }
}

@Alexander - Reinstate Monica 2018-12-16 20:30:21

That is an interesting demonstration of how contains(where:) can be implemented with only reduce, but in production code like this, it's better to just use contains(where:) directly. For one, it can short circuit the search if an element is found early on (no need to keep searching after that, but this reduce method does that anyway)

@Alessandro Martin 2018-01-11 15:38:25

Swift 4

Guaranteed to keep ordering.

extension Array where Element: Equatable {
    func removingDuplicates() -> Array {
        return reduce(into: []) { result, element in
            if !result.contains(element) {
                result.append(element)
            }
        }
    }
}

@J. Doe 2018-03-28 19:22:53

I use this now, only changed the method name to removeDuplicates :)

@Cœur 2018-08-21 11:25:48

I guess this solution is compact, but I believe that deanWombourne solution posted a year earlier may be slightly more efficient than a reduce: overall, it's just one more line in your whole project to write your function as: var unique: [Iterator.Element] = []; for element in self where !unique.contains(element) { unique.append(element) }; return unique. I admit I haven't tested the relative performances yet.

@Duncan C 2018-09-03 15:58:05

This will have O(n²) time performance, which is really bad for large arrays.

@Alexander - Reinstate Monica 2018-12-16 20:32:59

@NickGaens No it's not, it's O(n²). There's nothing swift about this.

@Alexander - Reinstate Monica 2018-12-16 20:33:52

@Cœur reduce or reduce(into:) wouldn't make a critical difference. Rewriting this to not repeatedly call contains would make a MUCH bigger difference.

@Alexander - Reinstate Monica 2018-12-16 23:58:04

@Cœur Of course you can. It's actually quite simple. You just filter array elements according to whether or not you have seen them already (which you maintain using a set for O(1) insert and contains). See stackoverflow.com/a/46354989/3141234

@Cœur 2018-12-17 00:04:28

@Alexander sorry, yes, I was distracted. I even found that solution BEFORE mxcl.

@Alessandro Martin 2020-03-02 18:54:21

Yes, as many comments pointed out, this is not very time efficient and, if the Elements is also Hashable, other solutions are more efficient.

@Igor Silva 2018-01-05 19:25:13

I've made a simple-as-possible extension for that purpose.

extension Array where Element: Equatable {

    func containsHowMany(_ elem: Element) -> Int {
        return reduce(0) { $1 == elem ? $0 + 1 : $0 }
    }

    func duplicatesRemoved() -> Array {
        return self.filter { self.containsHowMany($0) == 1 }
    }

    mutating func removeDuplicates() {
        self = self.duplicatesRemoved(()
    }
}

You can use duplicatesRemoved() to get a new array, whose duplicate elements are removed, or removeDuplicates() to mutate itself. See:

let arr = [1, 1, 1, 2, 2, 3, 4, 5, 6, 6, 6, 6, 6, 7, 8]

let noDuplicates = arr.duplicatesRemoved()
print(arr) // [1, 1, 1, 2, 2, 3, 4, 5, 6, 6, 6, 6, 6, 7, 8]
print(noDuplicates) // [1, 2, 3, 4, 5, 6, 7, 8]

arr.removeDuplicates()
print(arr) // [1, 2, 3, 4, 5, 6, 7, 8]

@Alexander - Reinstate Monica 2018-12-16 20:34:09

This is also O(n²).

@Jack Rus 2017-01-02 00:37:59

func removeDublicate (ab: [Int]) -> [Int] {
var answer1:[Int] = []
for i in ab {
    if !answer1.contains(i) {
        answer1.append(i)
    }}
return answer1
}

Usage:

let f = removeDublicate(ab: [1,2,2])
print(f)

@Jack Rus 2017-01-02 00:39:35

I think this is the simplest

@Jack Rus 2017-01-02 00:40:49

it keeps the order and gives you an array you want

@Alexander - Reinstate Monica 2018-12-16 20:34:20

This is also O(n²).

@Jovan Stankovic 2017-05-28 14:36:18

Swift 3.0

let uniqueUnordered = Array(Set(array))
let uniqueOrdered = Array(NSOrderedSet(array: array))

@Zaporozhchenko Oleksandr 2018-06-18 13:07:54

let uniqueOrderedNames = Array(NSOrderedSet(array: userNames)) as! [String] if u have array of String, not of Any

@Mecki 2019-07-09 15:18:45

Fails if the elements in array are not Hashable; only Hashable data types can be added to a Set, yet any data type can be added to an array.

@dlemex 2019-08-01 22:41:29

Tested in Swift 5.1b5, given that the elements are Hashable and a desire to retain ordering, the NSOrderedSet(array: array).array is marginally faster than the pure swift func uniqued() using a set with filter. I tested with 5100 strings that resulted in 13 unique values.

@DaveAMoore 2016-06-09 21:48:12

This is just a very simple and convenient implementation. A computed property in an extension of an Array that has equatable elements.

extension Array where Element: Equatable {
    /// Array containing only _unique_ elements.
    var unique: [Element] {
        var result: [Element] = []
        for element in self {
            if !result.contains(element) {
                result.append(element)
            }
        }

        return result
    }
}

@Alexander - Reinstate Monica 2018-12-16 20:38:11

This is also O(n^2).

Related Questions

Sponsored Content

38 Answered Questions

[SOLVED] Deleting an element from an array in PHP

  • 2008-12-15 20:28:55
  • Ben
  • 2663780 View
  • 2541 Score
  • 38 Answer
  • Tags:   php arrays unset

96 Answered Questions

[SOLVED] How can I remove a specific item from an array?

  • 2011-04-23 22:17:18
  • Walker
  • 6830167 View
  • 8410 Score
  • 96 Answer
  • Tags:   javascript arrays

95 Answered Questions

[SOLVED] Get all unique values in a JavaScript array (remove duplicates)

36 Answered Questions

[SOLVED] Create ArrayList from array

53 Answered Questions

49 Answered Questions

[SOLVED] How to check if an object is an array?

39 Answered Questions

[SOLVED] Loop through an array in JavaScript

40 Answered Questions

[SOLVED] For-each over an array in JavaScript

30 Answered Questions

[SOLVED] How to append something to an array?

Sponsored Content