4

I am adding objects (NSNumbers in this case) to an NSMutableArray and I wanted to check what the best way is to check for duplicates in the array before adding. (i.e.)

Number to add
if (NSMutableArray does not contain Number) {
    add Number
}

EDIT:

Many thanks, I had a good luck at NSArray this morning but totally missed "containsObject". That would have done just fine, but having looked at NSMutableSet thats far more what I was looking for. One final question if I may:

while([mySet count] < 5) {
    NSNumber *numberToAdd = [NSNumber numberWithInt:random() %10];
    [mySet addObject:numberToAdd];
}

I don't think it actually matters, but is it better to check if the set "containsObject" or just throw away the duplicate and carry on.

while([mySet count] < 5) {
    NSNumber *numberToAdd = [NSNumber numberWithInt:random() %10];
    if(!mySet containsObject:numberToAdd) [mySet addObject:numberToAdd];
}

Again much appreciated, thats really cool and will save me a heap of time.

gary

Improve this question
1
  • 2
    This isn't really related to your question, but doing % 10 isn't going to give you a very even distribution of numbers. Since it's not prime, your set will be biased toward numbers less than 5, and you're virtually guaranteed to have 1 and 2 in your set. If you use a prime number, like % 11, you'll get a more even distribution. Commented Mar 29, 2010 at 16:24

5 Answers 5

Reset to default
15

Remember an NSMutableArray is an NSArray too.

if (![theArray containsObject:theNumber]) {
  // does not contain.
}

(If you want unique objects and don't care about insertion order, NSMutableSet is a more efficient container.)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

To answer your second question: no, you don't really need to check whether the set contains the object already. NSMutableSet will do this for you when you call addObject:. It may have a more efficient way of doing this (since it has access to the internal data structure), so you may actually end up with a slight performance benefit by letting NSMutableSet handle it.

If nothing else, it's less code you have to write, and that's always nice.

Improve this answer

Comments

1

This depends on how big your array is likely to get. You can check whether something's already in the array by using -containsObject:. This can be as bad as O(n*logn) on the length of the array and is thus no good for super big arrays, but keeps the code simple to maintain.

The generic way to do this though in general for arbitrary size data sets is to keep an NSMutableSet alongside the array. Check the set for the existence of the item before adding to the array. If it's already in the set, don't add it. If not, add it to both.

Of course, if you don't care about order and only uniqueness, then don't use the array at all, just use the Set.

Improve this answer

4 Comments

Actually it's worse than O(n). Apple's doc states "Linear search operations similarly have a worst-case complexity of O(N*log N), though typically the bounds will be tighter."
@Kenny: thanks, that's interesting and news to me (updated answer). Also seems a misnomer at that point to refer to it as a "linear search operation." :)
Wait… How can a sequential search be worse than O(n)? That doesn't make sense to me.
@9000: Because an NSArray isn't actually guaranteed to be (and generally isn't) backed by a pure linear C array. Apple's docs give a worst-case bound for any implementation of O(log n) for the getter, meaning a traversal of every item (to check existence) can be as bad as O(n log n). See this article for some graphs: ridiculousfish.com/blog/posts/array.html
1

I have a category on NSMutableArray

@interface NSMutableArray (CategoryName)

- (void)addObjectUnique:(id)anObject;

@end

@implementation NSMutableArray (CategoryName)

- (void)addObjectUnique:(id)anObject
{
  if ([self containsObject:anObject]) {
    return;
  }
  [self addObject:anObject];
}

@end
Improve this answer

Comments

0

Try this:

// Number to add is newNumber, myArray is your Mutable array
if(![myArray containsObject:newNumber])
{
  [myArray addObject:myNumber];
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.