By Altair357


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

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

@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 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

@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 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 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 2019-04-15 20:49:10

Ah yes, makes sense!

@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.

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

Constraining the collection elements to Equatable you can use contains:

extension Collection where Element: Equatable {
    var orderedSet: [Element]  {
        var array: [Element] = []
        return compactMap {
            if array.contains($0) {
                return nil
            } else {
                array.append($0)
                return $0
            }
        }
    }
}

Another option is to constrain the collection element to Hashable and use a set to control which elements you have to map into the result:

extension Collection where Element: Hashable {
    var orderedSet: [Element]  {
        var set = Set<Element>()
        return compactMap { set.insert($0).inserted ? $0 : nil }
    }
}

using filter:

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

or using NSOrderedSet:

extension Array where Element: Hashable {
    var orderedSet: Array {
        return NSOrderedSet(array: self).array as? Array ?? []
    }
}

Using Swift 4 reduce(into:)

extension Collection where Element: Hashable {
    var orderedSet: [Element] {
        var set: Set<Element> = []
        return reduce(into: []) { set.insert($1).inserted ? $0.append($1) : () }
    }
}

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

You can also extend RangeReplaceableCollection protocol to allow it to be used with StringProtocol types as well (Strings and SubStrings):

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 }
    }
}

"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"

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

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

@Alexander 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.

@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 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 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

@Mauricio Chirino 2018-12-20 19:19:50

It would also work @Alexander

@Alexander 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 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

@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 Array where Element: Hashable {

    /// Return the array 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.
    public func uniqued() -> [Element] {
        var seen = Set<Element>()
        return self.filter { seen.insert($0).inserted }
    }
}

or if you don't have Hashable, you can do this:

public extension Sequence where Iterator.Element: Equatable {

    public func uniqued() -> [Iterator.Element] {
        var buffer: [Iterator.Element] = []

        for element in self {
            guard !buffer.contains(element) else { continue }

            buffer.append(element)
        }

        return buffer
    }
}

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

@Alexander 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 :)

@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 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

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

Swift 4.2 Tested

extension Sequence where Iterator.Element: Hashable {
    func unique() -> [Iterator.Element] {
        var seen: [Iterator.Element: Bool] = [:]
        return self.filter { seen.updateValue(true, forKey: $0) == nil }
    }
}

@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 } } }

@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()

@Usman Nisar 2018-06-19 08:06:55

for latest swift. its rename to .uniq()

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

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

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

This takes some of the good information that's already on this page, and applies the Hashable/Set approach when possible, and falls back to the Equatable code otherwise.

Swift 4 change for the Equatable extension (Hashable stays the same)

public extension Sequence where Element: Equatable {
  var uniqueElements: [Element] {
    return self.reduce(into: []) {
      uniqueElements, element in

      if !uniqueElements.contains(element) {
        uniqueElements.append(element)
      }
    }
  }
}

Swift 3

public extension Sequence where Iterator.Element: Hashable {
    var uniqueElements: [Iterator.Element] {
        return Array( Set(self) )
    }
}
public extension Sequence where Iterator.Element: Equatable {
    var uniqueElements: [Iterator.Element] {
        return self.reduce([]){
            uniqueElements, element in

            uniqueElements.contains(element)
            ? uniqueElements
            : uniqueElements + [element]
        }
    }
}

Swift 2

public extension SequenceType where Generator.Element: Hashable {
  var uniqueElements: [Generator.Element] {
    return Array(
      Set(self)
    )
  }
}
public extension SequenceType where Generator.Element: Equatable {
  var uniqueElements: [Generator.Element] {
    return self.reduce([]){uniqueElements, element in
      uniqueElements.contains(element)
        ? uniqueElements
        : uniqueElements + [element]
    }
  }
}

@Alessandro Ornano 2016-05-27 17:11:26

This method work with Swift 2.2, great solution.

@Serluca 2016-08-08 13:54:18

It works but doesn't keep the order

@David Seek 2016-12-21 17:27:43

stupid question, but how is this called? :/

@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.

@Jessy 2018-09-03 23:31:04

"Whatever that is" is undefined. Example: [1, 3, 2, 3]. There is no concept of order for unique elements built into the standard Swift types.

@Alexander 2018-12-16 20:23:53

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

@Jessy 2018-12-17 00:08:10

@Alexander What should be done instead? Please contribute an answer! Stack Overflow’s a great place to contribute answers instead of offering no alternatives. An alternative for you is to write the alternative, then don’t type the thing that you typed, and instead type the hint that you typed along with an alternative!

@Alexander 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.

@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 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 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 2018-12-16 20:26:45

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

@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
}

@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.

@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 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)
            }
        }
    }
}

@Nick Gaens 2018-03-06 13:03:57

A very Swifty piece of code; excellent.

@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 2018-12-16 20:32:59

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

@Alexander 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 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.

@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 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 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 Aleksandr 2018-06-18 13:07:54

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

@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
    }
}

@GoodSp33d 2016-11-18 11:51:37

probably an if condition makes sense here than a guard.

@DaveAMoore 2017-04-01 15:02:12

I agree, it makes the solution clearer.

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

This is also O(n^2).

@oOEric 2017-03-25 13:39:34

Preserve unique values and preserve sorting in an array.

(using Swift 3)

    var top3score: [Int] = []


    outerLoop: for i in 0..<top10score.count {
        dlog(message: String(top10score[i]))

        if top3score.count == 3 {
            break
        }

        for aTop3score in top3score {
            if aTop3score == top10score[i] {
                continue outerLoop
            }
        }

        top3score.append(top10score[i])

    }

    print("top10score is \(top10score)")  //[14, 5, 5, 5, 3, 3, 2, 2, 2, 2]
    print("top3score is \(top3score)")   //[14, 5, 3]

@oOEric 2017-08-22 03:30:57

why -1 my answer....

@Alexander 2018-12-16 20:41:17

This is a good first approach, but it's quite complex and verbose. This code does too many things (deduplicating, truncating to 3 results), and there's no easy way to reuse it without mass copy/paste. You should take a look at this answer. You could then write something like scores.uniqued().prefix(3). Simple!

@oOEric 2018-12-17 08:52:58

Thanks for your comment. The main points of the code above are not only to preserve unique values but also to preserve the original ordering. Using "Set" seems can't preserve the ordering. :)

@Alexander 2018-12-17 18:46:29

Yes it can. Take a look at the answer I can. You use the set for fast answers to the question of "Have I already seen this element?"

@Eneko Alonso 2017-03-14 21:51:46

One more Swift 3.0 solution to remove duplicates from an array. This solution improves on many other solutions already proposed by:

  • Preserving the order of the elements in the input array
  • Linear complexity O(n): single pass filter O(n) + set insertion O(1)

Given the integer array:

let numberArray = [10, 1, 2, 3, 2, 1, 15, 4, 5, 6, 7, 3, 2, 12, 2, 5, 5, 6, 10, 7, 8, 3, 3, 45, 5, 15, 6, 7, 8, 7]

Functional code:

func orderedSet<T: Hashable>(array: Array<T>) -> Array<T> {
    var unique = Set<T>()
    return array.filter { element in
        return unique.insert(element).inserted
    }
}

orderedSet(array: numberArray)  // [10, 1, 2, 3, 15, 4, 5, 6, 7, 12, 8, 45]

Array extension code:

extension Array where Element:Hashable {
    var orderedSet: Array {
        var unique = Set<Element>()
        return filter { element in
            return unique.insert(element).inserted
        }
    }
}

numberArray.orderedSet // [10, 1, 2, 3, 15, 4, 5, 6, 7, 12, 8, 45]

This code takes advantage of the result returned by the insert operation on Set, which executes on O(1), and returns a tuple indicating if the item was inserted or if it already existed in the set.

If the item was in the set, filter will exclude it from the final result.

@Alain T. 2017-03-16 17:10:31

Not to be picky but you will be performing the insert and the membership test as many times as there are elements so you should count their cost as O(n) as well. This doesn't mean 3xO(n) however because these O's and don't have equal cost with the filter so the addition of O(n)'s is apples to oranges. If we consider set operations to be a O(1) part of the filter cost, the complexity is merely O(n), albeit with a larger "O". Pushing this to the limit, you could also avoid the insertions when the element is already in the set.

@Eneko Alonso 2017-03-16 17:41:14

You are right, using defer the code would do the set test operation twice, one with contains and one with insert. Further reading Swift documentation, I found that insert returns a tuple indicating if the element was inserted or not, so I've simplified the code removing the contains check.

@Cœur 2017-06-16 03:00:37

Nice. Your extension could be optimal by doing it on extension Sequence where Iterator.Element: Hashable { ... }

@Alexander 2018-12-16 20:44:07

@AlainT. Nope. Both insert and contains have O(1) complexity. O(1) + O(1) = O(1). These two operations are then done n times (once per call of the closure passed to filter, which is called once per element) I.e. if an operation takes a constant amount of time regardless of input size, then doing it twice still makes it take a constant time that is regardless of input size. The total complexity of this is O(n).

@Ciprian Rarau 2016-12-18 19:30:02

In Swift 3.0 the simplest and fastest solution I've found to eliminate the duplicated elements while keeping the order:

extension Array where Element:Hashable {
    var unique: [Element] {
        var set = Set<Element>() //the unique list kept in a Set for fast retrieval
        var arrayOrdered = [Element]() //keeping the unique list of elements but ordered
        for value in self {
            if !set.contains(value) {
                set.insert(value)
                arrayOrdered.append(value)
            }
        }

        return arrayOrdered
    }
}

@Alexander 2018-12-16 20:44:46

You can do the contains and insert in one shot: stackoverflow.com/a/46354989/3141234

@Antoine 2016-01-26 13:28:00

Many answers available here, but I missed this simple extension, suitable for Swift 2 and up:

extension Array where Element:Equatable {
    func removeDuplicates() -> [Element] {
        var result = [Element]()

        for value in self {
            if result.contains(value) == false {
                result.append(value)
            }
        }

        return result
    }
}

Makes it super simple. Can be called like this:

let arrayOfInts = [2, 2, 4, 4]
print(arrayOfInts.removeDuplicates()) // Prints: [2, 4]

Filtering based on properties

To filter an array based on properties, you can use this method:

extension Array {

    func filterDuplicates(@noescape includeElement: (lhs:Element, rhs:Element) -> Bool) -> [Element]{
        var results = [Element]()

        forEach { (element) in
            let existingElements = results.filter {
                return includeElement(lhs: element, rhs: $0)
            }
            if existingElements.count == 0 {
                results.append(element)
            }
        }

        return results
    }
}

Which you can call as followed:

let filteredElements = myElements.filterDuplicates { $0.PropertyOne == $1.PropertyOne && $0.PropertyTwo == $1.PropertyTwo }

@Lance Samaria 2016-09-24 03:23:00

I like your method to filter based on properties, it works! What happens to the duplicates and how would one put those into a separate array?

@Mostafa Mohamed Raafat 2016-10-04 00:08:34

@Antoine Thank you for the Filtering based on properties extension. It's really useful. But can you please explain how it works. It's too hard to understand for me. Thank you

@cbartel 2017-05-09 04:02:11

Updates for swift 3: func filterDuplicates(_ includeElement: (_ lhs:Element, _ rhs:Element) -> Bool) -> [Element]{

@Cœur 2017-06-15 09:27:09

The first part of this answer (extension Array where Element: Equatable) is being superseded by stackoverflow.com/a/36048862/1033581 which offers a more powerful solution (extension Sequence where Iterator.Element: Equatable).

@Duncan C 2018-09-03 16:01:19

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

@Alexander 2018-12-16 20:45:39

You should use a set to keep track of elements seen so far, to bring this terrible O(n²) complexity back down to O(n)

@n0_quarter 2016-07-13 12:00:26

Let me suggest an answer similar to Scott Gardner's answer but with more laconic syntax using reduce. This solution removes duplicates from an array of custom objects (keeping the initial order)

// Custom Struct. Can be also class. 
// Need to be `equitable` in order to use `contains` method below
struct CustomStruct : Equatable {
      let name: String
      let lastName : String
    }

// conform to Equatable protocol. feel free to change the logic of "equality"
func ==(lhs: CustomStruct, rhs: CustomStruct) -> Bool {
  return (lhs.name == rhs.name && lhs.lastName == rhs.lastName)
}

let categories = [CustomStruct(name: "name1", lastName: "lastName1"),
                  CustomStruct(name: "name2", lastName: "lastName1"),
                  CustomStruct(name: "name1", lastName: "lastName1")]
print(categories.count) // prints 3

// remove duplicates (and keep initial order of elements)
let uniq1 : [CustomStruct] = categories.reduce([]) { $0.contains($1) ? $0 : $0 + [$1] }
print(uniq1.count) // prints 2 - third element has removed

And just if you are wondering how this reduce magic works - here is exactly the same, but using more expanded reduce syntax

let uniq2 : [CustomStruct] = categories.reduce([]) { (result, category) in
  var newResult = result
  if (newResult.contains(category)) {}
  else {
    newResult.append(category)
  }
  return newResult
}
uniq2.count // prints 2 - third element has removed

You can simply copy-paste this code into a Swift Playground and play around.

@Cœur 2017-06-15 07:35:35

For Swift 4 you need to replace $0 with $0.0 and $1 with $0.1.

@Cœur 2017-06-15 07:39:05

Note that prior to Swift 4 (i.e. in Swift 3) it is discouraged to use reduce with a mutable struct type (here it's []), as the mutability is not preserved and reduce is creating an overhead of copying the struct each time.

@Alexander 2018-12-16 20:46:47

Generally you would want to encapsulate code like this into a function, rather than copy pasting it everywhere it's used. And reduce isn't an appropriate choice for this algorithm. It makes it O(n²)

@lammert 2015-12-18 09:33:31

I believe it would be good to offer a uniq() and uniqInPlace() function to mutate an Array by removing it's values. This works similar as the sort() and sortInPlace() function provided by Swift. Also since it's an Array it should keep it's original order of elements.

extension Array where Element: Equatable {

    public func uniq() -> [Element] {
        var arrayCopy = self
        arrayCopy.uniqInPlace()
        return arrayCopy
    }

    mutating public func uniqInPlace() {
        var seen = [Element]()
        var index = 0
        for element in self {
            if seen.contains(element) {
                removeAtIndex(index)
            } else {
                seen.append(element)
                index++
            }
        }
    }
}

You can only use uniqInPlace() on a variable Array (i.e. var) since you cannot mutate a constant Array (i.e. let).

Some usage examples:

var numbers = [1, 6, 2, 2, 4, 1, 5]
numbers.uniqInPlace() // array is now [1, 6, 2, 4, 5]

let strings = ["Y", "Z", "A", "Y", "B", "Y", "Z"]
let uniqStrings = strings.uniq() // uniqStrings is now ["Y", "Z", "A", "B"]

@Alexander 2018-12-16 20:49:45

An Array<Element> is not an appropriate choice for the type of seen. The repeated contains calls (each of which is O(n)) makes this algorithm at least O(n^2). Also, removeAtIndex) is also O(n) (because it causes every element after the remove element to have to be shifted left by 1). Instead, an algorithm like this would work better using var seen = Set<Element>(), and rather than "removing" elements, you "overwrite" them, by reading ahead until you see the next element that you need to keep.

@Alexander 2018-12-16 20:50:15

That way, you keep all the elements you want, and end up with a set of empty space at the end of array that can just be trimmed in one shot

@Scott Gardner 2015-11-29 15:14:08

Slightly more succinct syntax version of Daniel Krom's Swift 2 answer, using a trailing closure and shorthand argument name, which appears to be based on Airspeed Velocity's original answer:

func uniq<S: SequenceType, E: Hashable where E == S.Generator.Element>(source: S) -> [E] {
  var seen = [E: Bool]()
  return source.filter { seen.updateValue(true, forKey: $0) == nil }
}

Example of implementing a custom type that can be used with uniq(_:) (which must conform to Hashable, and thus Equatable, because Hashable extends Equatable):

func ==(lhs: SomeCustomType, rhs: SomeCustomType) -> Bool {
  return lhs.id == rhs.id // && lhs.someOtherEquatableProperty == rhs.someOtherEquatableProperty
}

struct SomeCustomType {

  let id: Int

  // ...

}

extension SomeCustomType: Hashable {

  var hashValue: Int {
    return id
  }

}

In the above code...

id, as used in the overload of ==, could be any Equatable type (or method that returns an Equatable type, e.g., someMethodThatReturnsAnEquatableType()). The commented-out code demonstrates extending the check for equality, where someOtherEquatableProperty is another property of an Equatable type (but could also be a method that returns an Equatable type).

id, as used in the hashValue computed property (required to conform to Hashable), could be any Hashable (and thus Equatable) property (or method that returns a Hashable type).

Example of using uniq(_:):

var someCustomTypes = [SomeCustomType(id: 1), SomeCustomType(id: 2), SomeCustomType(id: 3), SomeCustomType(id: 1)]

print(someCustomTypes.count) // 4

someCustomTypes = uniq(someCustomTypes)

print(someCustomTypes.count) // 3

@Will Richardson 2015-11-21 00:49:21

I used @Jean-Philippe Pellet's answer and made an Array extension that does set-like operations on arrays, while maintaining the order of elements.

/// Extensions for performing set-like operations on lists, maintaining order
extension Array where Element: Hashable {
  func unique() -> [Element] {
    var seen: [Element:Bool] = [:]
    return self.filter({ seen.updateValue(true, forKey: $0) == nil })
  }

  func subtract(takeAway: [Element]) -> [Element] {
    let set = Set(takeAway)
    return self.filter({ !set.contains($0) })
  }

  func intersect(with: [Element]) -> [Element] {
    let set = Set(with)
    return self.filter({ set.contains($0) })
  }
}

@Daniel Krom 2015-10-11 13:28:24

swift 2

with uniq function answer:

func uniq<S: SequenceType, E: Hashable where E==S.Generator.Element>(source: S) -> [E] {
    var seen: [E:Bool] = [:]
    return source.filter({ (v) -> Bool in
        return seen.updateValue(true, forKey: v) == nil
    })
}

use:

var test = [1,2,3,4,5,6,7,8,9,9,9,9,9,9]
print(uniq(test)) //1,2,3,4,5,6,7,8,9

@Nikolai Ruhe 2016-02-08 10:04:48

The Bool value obviously is redundant, as your code never reads it. Use a Set instead of a Dictionary and you get my upvote.

Related Questions

Sponsored Content

39 Answered Questions

[SOLVED] Loop through an array in JavaScript

79 Answered Questions

[SOLVED] How do I remove a particular element from an array in JavaScript?

  • 2011-04-23 22:17:18
  • Walker
  • 5661619 View
  • 7034 Score
  • 79 Answer
  • Tags:   javascript arrays

44 Answered Questions

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

33 Answered Questions

[SOLVED] For-each over an array in JavaScript?

54 Answered Questions

[SOLVED] Remove duplicate values from JS array

46 Answered Questions

31 Answered Questions

[SOLVED] Create ArrayList from array

35 Answered Questions

[SOLVED] PHP: Delete an element from an array

  • 2008-12-15 20:28:55
  • Ben
  • 2229603 View
  • 2214 Score
  • 35 Answer
  • Tags:   php arrays

30 Answered Questions

[SOLVED] How to append something to an array?

9 Answered Questions

[SOLVED] Swift Beta performance: sorting arrays

Sponsored Content