iOS 基础集合类

本文参阅 objc.io 文章 http://www.objc.io/issue-7/collections.html 而进行的总结。全文中文翻译:http://www.cocoachina.com/applenews/devnews/2014/0122/7735.html


测试环境设置: xcode5 ios7 64位 编译设置release为-Ofast;Vectorize loops and unroll loops 设置关闭

iOS  基础集合类

iOS  基础集合类


1、集合类一般都有两个版本:可变类型和不可变类型。其中不可变类型是完全线程安全的,而可变类型不能保证这一点。所以在API接口中,不应该返回可变类型的集合参数。有时候更有效的做法是:在程序内部保持一个可变类型的集合类对象,而返回一个复制的,不可变类型的集合类对象以供外部访问。

2、NSArray

①缩写的创建语法格式

  //这两种创建 NSArray 的方式是相同的
    NSArray *array_1 = @[@"hello",@"world"];
    NSArray *array_2 = [NSArray arrayWithObjects:@"hello",@"world", nil];

②NSArray的对集合元素的下标操作

  //这两种方式获取 NSArray 中元素是相同的
    NSLog(@"print = %@",array_1[0]);
    NSLog(@"print = %@",[array_1 objectAtIndex:0]);

③在通过对一个array复制来创建一个可变数组的时候,由于源数组array可能为nil,所以创建的时候要考虑到nil的情况。

其正确的创建方式有:

 NSArray *array = @[@"string1",@"string2"];
        //方式1
        NSMutableArray *mutableArray_1 = [array mutableCopy];
        if (!mutableArray_1) {
            mutableArray_1 = [NSMutableArray array];
        }
        //通过 三元运算符 ?: 简化方式1的写法
        NSMutableArray *mutableArray_2 = [array mutableCopy]?:[NSMutableArray array];
        
        //方式2
        NSMutableArray *mutableArray_3 = [NSMutableArray arrayWithArray:array];

④对于创建NSMatableArray,介于代码的可读性,不要使用NSMutableArray *mutableArray = [@[]mutableCopy];  这种方式创建;而要采用

NSMutableArray *mutableArray = [NSMutableArray array];这种形式。
⑤可以通过 NSArray* reverseArray = array_1.reverseObjectEnumerator.allObjects;获得一个数组的反序形式。
3、数组排序
大体上,OC中常用的数组排序有以下几种方法:sortedArrayUsingSelector: sortedArrayUsingComparator: sortedArrayUsingDescriptors:
①使用sortedArrayUsingSelector: 进行排序(简单排序)
NSArray *array = @[@"John Appleseed", @"Tim Cook", @"Hair Force One", @"Michael Jurewitz"];
        NSArray *sortedArray = [array sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];
        
        [sortedArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
            NSLog(@"%zi --- %@",idx,obj);
        }];
        
        
        NSArray *numbers = @[@9, @5, @11, @3, @1];
        NSArray *sortedNumbers = [numbers sortedArrayUsingSelector:@selector(compare:)];
        [sortedNumbers enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
            NSLog(@"%zi --- %@",idx,obj);
        }];
输出结果:
2014-01-24 10:26:24.270 Foundation[871:303] 0 --- Hair Force One
2014-01-24 10:26:24.273 Foundation[871:303] 1 --- John Appleseed
2014-01-24 10:26:24.275 Foundation[871:303] 2 --- Michael Jurewitz
2014-01-24 10:26:24.276 Foundation[871:303] 3 --- Tim Cook
2014-01-24 10:26:24.277 Foundation[871:303] 0 --- 1
2014-01-24 10:26:24.277 Foundation[871:1003] 1 --- 3
2014-01-24 10:26:24.277 Foundation[871:1907] 2 --- 5
2014-01-24 10:26:24.280 Foundation[871:303] 3 --- 9
2014-01-24 10:26:24.280 Foundation[871:1003] 4 --- 11

当然,除了使用字符串自带的compare 方法,也可以自定义实现compare方法,进行对象的比较。例如:
新建一个Person类:
#import <Foundation/Foundation.h>

@interface Person : NSObject

@property(nonatomic,strong)NSString* name;
@property(nonatomic)int age;

-(void)sortArray;
@end

#import "Person.h"

@implementation Person
+(Person*)personWithAge:(int)age withName:(NSString*)name
{
    Person* person = [[Person alloc]init];
    person.age = age;
    person.name = name;
    return person;
}

//自定义排序方法
-(NSComparisonResult)comparePerson:(Person *)person{
    //默认按年龄排序
    NSComparisonResult result = [[NSNumber numberWithInt:person.age] compare:[NSNumber numberWithInt:self.age]];
    //注意:基本数据类型要进行数据转换
    
    //如果年龄一样,就按照名字排序
    if (result == NSOrderedSame) {
        result = [self.name compare:person.name];
    }
    return result;
}

-(void)sortArray
{
    Person *p1 = [Person personWithAge:23 withName:@"zhangsan"];
    Person *p2 = [Person personWithAge:21 withName:@"lisi"];
    Person *p3 = [Person personWithAge:24 withName:@"wangwu"];
    Person *p4 = [Person personWithAge:24 withName:@"liwu"];
    Person *p5 = [Person personWithAge:20 withName:@"liwu"];
    NSArray *array = [NSArray arrayWithObjects:p1,p2,p3,p4,p5, nil];
    NSArray *sortedArray = [array sortedArrayUsingSelector:@selector(comparePerson:)];
    [sortedArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSLog(@"%zi --- %@ --- %d",idx,[obj name],[obj age]);
    }];
}

@end
调用执行 sortArray 方法。
运行结果:
2014-01-24 10:59:55.417 Foundation[1234:303] 0 --- liwu --- 24
2014-01-24 10:59:55.422 Foundation[1234:303] 1 --- wangwu --- 24
2014-01-24 10:59:55.424 Foundation[1234:303] 2 --- zhangsan --- 23
2014-01-24 10:59:55.425 Foundation[1234:303] 3 --- lisi --- 21
2014-01-24 10:59:55.425 Foundation[1234:303] 4 --- liwu --- 20
注意到上面排序结果中是年龄是降序的,那么如果想要是升序结果的话,需要修改的地方是:
NSComparisonResult result = [[NSNumber numberWithInt:self.age] compare:[NSNumber numberWithInt:person.age]];

②使用sortedArrayUsingComparator:进行排序(利用block语法)
利用block可以大大简化代码,例如:(接上面的例子)
-(void)sortArray_1
{
    Person *p1 = [Person personWithAge:23 withName:@"zhangsan"];
    Person *p2 = [Person personWithAge:21 withName:@"lisi"];
    Person *p3 = [Person personWithAge:24 withName:@"wangwu"];
    Person *p4 = [Person personWithAge:24 withName:@"liwu"];
    Person *p5 = [Person personWithAge:20 withName:@"liwu"];
    NSArray *array = [NSArray arrayWithObjects:p1,p2,p3,p4,p5, nil];
    
    NSArray *sortedArray = [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        NSComparisonResult result = [[NSNumber numberWithInt:[obj1 age]] compare:[NSNumber numberWithInt:[obj2 age]]];
        if (result == NSOrderedSame) {
            result = [[obj1 name] compare:[obj2 name]];
        }
        return result;
    }];
    
    [sortedArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSLog(@"%zi --- %@ --- %d",idx,[obj name],[obj age]);
    }];
}
运行输出结果:
2014-01-24 13:09:24.963 Foundation[1581:303] 0 --- liwu --- 20
2014-01-24 13:09:24.968 Foundation[1581:303] 1 --- lisi --- 21
2014-01-24 13:09:24.968 Foundation[1581:303] 2 --- zhangsan --- 23
2014-01-24 13:09:24.969 Foundation[1581:303] 3 --- liwu --- 24
2014-01-24 13:09:24.970 Foundation[1581:303] 4 --- wangwu --- 24


③使用sortedArrayUsingDescriptors: 进行排序(高级排序)
想象出现这样的一种排序情况:Person类里有另外一个类的变量,比如说Person类除了name,age变量,还有一辆车Car类型,Car类里有个name属性。对Person对象进行排序,有这样的要求:按照Car的name排序,如果是同一辆车,也就是Car的name相同,那么再按照年龄进行排序,如果年龄也相同,最后按照Person的name进行排序。
对于此类情况的排序,需要用到排序描述器。例如:
添加一个Car类
#import "Car.h"
@implementation Car

+(Car *)initWithName:(NSString *)name{
    Car *car = [Car alloc] init];
    car.name = name;
    return car;
}

@end

在Person类中添加一个Car对象。
+(Person *)personWithAge:(int)age withName:(NSString *)name withCar:(Car *)car{
    Person *person = [[Person alloc] init];
    person.age = age;
    person.name = name;
    person.car = car;
    return person;
}
主要代码如下:
-(void)sortArray_2
{
    //首先来3辆车,分别是奥迪、劳斯莱斯、宝马
    Car *car1 = [Car initWithName:@"Audio"];
    Car *car2 = [Car initWithName:@"Rolls-Royce"];
    Car *car3 = [Car initWithName:@"BMW"];
    
    //再来5个Person,每人送辆车,分别为car2、car1、car1、car3、car2
    Person *p1 = [Person personWithAge:23 withName:@"zhangsan" withCar:car2];
    Person *p2 = [Person personWithAge:21 withName:@"zhangsan" withCar:car1];
    Person *p3 = [Person personWithAge:24 withName:@"lisi" withCar:car1];
    Person *p4 = [Person personWithAge:23 withName:@"wangwu" withCar:car3];
    Person *p5 = [Person personWithAge:23 withName:@"wangwu" withCar:car2];
    
    //加入数组
    NSArray *array = [NSArray arrayWithObjects:p1,p2,p3,p4,p5, nil];
    
    //构建排序描述器
    NSSortDescriptor *carNameDesc = [NSSortDescriptor sortDescriptorWithKey:@"car.name" ascending:YES];
    NSSortDescriptor *personNameDesc = [NSSortDescriptor sortDescriptorWithKey:@"name" ascending:YES];
    NSSortDescriptor *personAgeDesc = [NSSortDescriptor sortDescriptorWithKey:@"age" ascending:YES];
    
    //把排序描述器放进数组里,放入的顺序就是你想要排序的顺序
    //我这里是:首先按照年龄排序,然后是车的名字,最后是按照人的名字
    NSArray *descriptorArray = [NSArray arrayWithObjects:personAgeDesc,carNameDesc,personNameDesc, nil];
    
    NSArray *sortedArray = [array sortedArrayUsingDescriptors: descriptorArray];
    [sortedArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSLog(@"%zi --- %@ --- %d --- %@",idx,[obj name],[obj age],[[obj car] name]);
    }];
}
运行输出结果:
2014-01-24 13:04:06.008 Foundation[1552:303] 0 --- zhangsan --- 21 --- Audio
2014-01-24 13:04:06.012 Foundation[1552:303] 1 --- wangwu --- 23 --- BMW
2014-01-24 13:04:06.013 Foundation[1552:303] 2 --- wangwu --- 23 --- Rolls-Royce
2014-01-24 13:04:06.014 Foundation[1552:303] 3 --- zhangsan --- 23 --- Rolls-Royce
2014-01-24 13:04:06.016 Foundation[1552:303] 4 --- lisi --- 24 --- Audio

*补充:数组的遍历方式
NSArray *array = @[@"string1",@"string2",@"string3"];
        //方式一:普通的for循环
        for (int i=0; i < [array count]; i++) {
            NSLog(@"%zi --- %@",i,[array objectAtIndex:i]);
        }
        
        //方式二:快输for循环
        for (id obj in array) {
            NSLog(@"%zi --- %@",[array indexOfObject:obj],obj);
        }
        //方式三:使用block
        //1: enumerateObjectsUsingBlock 正序遍历
        [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
            NSLog(@"%zi --- %@",idx,obj);
        }];
        
        //2: enumerateObjectsUsingBlock 正序遍历:NSEnumerationConcurrent  反序遍历:NSEnumerationReverse
        [array enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
            NSLog(@"%zi --- %@",idx,obj);
        }];
        
        [array enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
            NSLog(@"%zi --- %@",idx,obj);
        }];
        
        //方式四:利用枚举
        NSEnumerator* en = [array objectEnumerator];
        id obj = NULL;
        while (obj = [en nextObject]) {
            NSLog(@"%zi --- %@",[array indexOfObject:obj],obj);
        }

4、二分查找(要求数组已经排序)
typedef NS_OPTIONS(NSUInteger, NSBinarySearchingOptions) {
        NSBinarySearchingFirstEqual     = (1UL << 8),
        NSBinarySearchingLastEqual      = (1UL << 9),
        NSBinarySearchingInsertionIndex = (1UL << 10),
};

- (NSUInteger)indexOfObject:(id)obj 
              inSortedRange:(NSRange)r 
                    options:(NSBinarySearchingOptions)opts 
            usingComparator:(NSComparator)cmp;

用法示例:
NSArray *sortedArray = ... // must be sorted
id searchObject = ...
NSRange searchRange = NSMakeRange(0, [sortedArray count]);
NSUInteger findIndex = [sortedArray indexOfObject:searchObject 
                                inSortedRange:searchRange
                                      options:NSBinarySearchingFirstEqual
                              usingComparator:^(id obj1, id obj2)
                              {
                                  return [obj1 compare:obj2];
                              }];

5、枚举数组 Enumeration
// First variant, using `indexesOfObjectsWithOptions:passingTest:`.
NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:NSEnumerationConcurrent 
                                                   passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
    return testObj(obj);
}];
NSArray *filteredArray = [randomArray objectsAtIndexes:indexes];

// Filtering using predicates (block-based or text)    
NSArray *filteredArray2 = [randomArray filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id obj, NSDictionary *bindings) {
    return testObj(obj);
}]];

// Block-based enumeration 
NSMutableArray *mutableArray = [NSMutableArray array];
[randomArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}];

// Classic enumeration
NSMutableArray *mutableArray = [NSMutableArray array];
for (id obj in randomArray) {
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}

// Using NSEnumerator, old school.
NSMutableArray *mutableArray = [NSMutableArray array];
NSEnumerator *enumerator = [randomArray objectEnumerator];
id obj = nil;
while ((obj = [enumerator nextObject]) != nil) {
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}

// Using objectAtIndex: (via subscripting)
NSMutableArray *mutableArray = [NSMutableArray array];
for (NSUInteger idx = 0; idx < randomArray.count; idx++) {
    id obj = randomArray[idx];
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}

各种枚举数组元素的效率比较:
Enumeration Method / Time [ms] 10.000.000 elements 10.000 elements
indexesOfObjects:, concurrent 1844.73 2.25
NSFastEnumeration (for in) 3223.45 3.21
indexesOfObjects: 4221.23 3.36
enumerateObjectsUsingBlock: 5459.43 5.43
objectAtIndex: 5282.67 5.53
NSEnumerator 5566.92 5.75
filteredArrayUsingPredicate: 6466.95 6.31
6、NSDictionary
//创建 字典 的两种方式
        NSDictionary *dic_1 = [NSDictionary dictionaryWithObjectsAndKeys:@"value",@"key",@"value2",@"key2", nil];
        NSDictionary *dic_2 = @{@"key": @"value",@"key2":@"value2"};

//根据key访问value的两种方式
        NSLog(@"%@",[dic_1 objectForKey:@"key"]);
        NSLog(@"%@",dic_1[@"key"]);

7、枚举字典
// Using keysOfEntriesWithOptions:passingTest:,optionally concurrent
NSSet *matchingKeys = [randomDict keysOfEntriesWithOptions:NSEnumerationConcurrent 
                                               passingTest:^BOOL(id key, id obj, BOOL *stop) 
{
    return testObj(obj);
}];
NSArray *keys = matchingKeys.allObjects;
NSArray *values = [randomDict objectsForKeys:keys notFoundMarker:NSNull.null];
__unused NSDictionary *filteredDictionary = [NSDictionary dictionaryWithObjects:values 
                                                                        forKeys:keys];    
    
// Block-based enumeration.
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
[randomDict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
    if (testObj(obj)) {
        mutableDictionary[key] = obj;
    }
}];

// NSFastEnumeration
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
for (id key in randomDict) {
    id obj = randomDict[key];
    if (testObj(obj)) {
        mutableDictionary[key] = obj;
    }
}

 // NSEnumeration
 NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
 NSEnumerator *enumerator = [randomDict keyEnumerator];
 id key = nil;
 while ((key = [enumerator nextObject]) != nil) {
       id obj = randomDict[key];
       if (testObj(obj)) {
           mutableDictionary[key] = obj;
       }
 }

// C-based array enumeration via getObjects:andKeys:
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
id __unsafe_unretained objects[numberOfEntries];
id __unsafe_unretained keys[numberOfEntries];
[randomDict getObjects:objects andKeys:keys];
for (int i = 0; i < numberOfEntries; i++) {
    id obj = objects[i];
    id key = keys[i];
    if (testObj(obj)) {
       mutableDictionary[key] = obj;
    }
 }
:其中注意到使用了 __unused 修饰,在被__unused 修饰的字段的方法,在程序中没有被使用到时,编译器不会报警告。
效率比较:
Filtering/Enumeration Method Time [ms], 50.000 elements 1.000.000 elements
keysOfEntriesWithOptions:, concurrent 16.65 425.24
getObjects:andKeys: 30.33 798.49*
keysOfEntriesWithOptions: 30.59 856.93
enumerateKeysAndObjectsUsingBlock: 36.33 882.93
NSFastEnumeration 41.20 1043.42
NSEnumeration 42.21 1113.08
8、NSSet 和 NSMutableSet
NSSet 和 NSMutableSet 是保存无序对象的集合类。其中:
NSSet它是一组单值对象的集合,且NSSet实例中元素是无序,同一个对象只能保存一个;NSSet 对象创建之后就不能对NSSet对象进行添加和删除操作。
NSMutableSet 是可变集合NSMutableSet有几个很强大的方法,例如intersectSet:,minusSet:和unionSet:
iOS  基础集合类

基本的用法:

一.不可变集合NSSet

1.NSSet的初始化

创建一个集合

NSSet *set1 = [[NSSet alloc] initWithObjects:@"one", @"two", nil];

通过数组的构建集合

NSArray *array = [NSArrayWithObjects:@"1", @"2", @"3", nil];

NSSet *set2 = [[NSSet alloc] initWithArray:array];

通过已有集合构建集合

NSSet *set3 = [[NSSet alloc] initWithSet:set2];

2.NSSet常用方法

集合中对象的个数

int count = [set3 count];

以数组的形式返回集合中所有的对象

NSArray *allObjects = [set3 allObjects];

返回集合中的任意一个对象

id object = [set3 anyObject];

判断两个集合的元素中有包含的对象,包含返回YES,否则为NO

BOOL isContain = [set4 containsObject:@"2"];

判断两个集合的元素是否有相等的对象,存在返回YES,否则为NO

BOOL isIntersect = [set4 intersectsSet:set2];

判断两个集合的元素是否完全匹配,匹配返回YES,否则为NO

BOOL isEqual = [set4 isEqualToSet:set5];

集合4是否是集合5的子集合,如果是返回YES,否则为NO

BOOL isSubset = [set4 isSubsetOfSet:set5];

创建一个新的集合2,集合2有两个对象

NSSet *set1 = [NSSet setWithObjects:@"a",nil];

NSSet *set2 = [set1 setByAddingObject:@"b"];

通过已有的两个集合,创建新的一个集合

NSSet *set7 = [NSSet setWithObjects:@"a",nil];

NSSet *set8 = [NSSet setWithObjects:@"z",nil];

NSSet *set9 = [set7 setByAddingObjectsFromSet:set8];

通过已有的集合和数组对象,创建一个新的集合

NSArray *array = [NSArray arrayWithObjects:@"a",@"b",@"c",nil];

NSSet *set10 = [NSSet setWithObjects:@"z",nil];

NSSet *set11 = [set10 setByAddingObjectsFromArray:array];


二、可变集合NSMutableSet

常用方法

创建一个空的集合

NSMutableSet *set1 = [NSMutableSet set];

NSMutableSet *set2 = [NSMutableSet setWithObjects:@"1",@"2",nil];

NSMutableSet *set3 = [NSMutableSet setWithObjects:@"a",@"2",nil];

集合2减去集合3中的元素,集合2最后元素只有1个

[set2 minusSet:set3];

集合2与集合3中元素的交集,集合2最后元素只有1个

[set2 intersectSet:set3];

集合2与集合3中的元素的并集,集合2最后元素只有3个

[set2 unionSet:set3];

将空集合1设置为集合3中的内容

[set1 setSet:set3];

根据数组的内容删除集合中的对象

[set2 addObjectsFromArray:array];

[set2 removeObject:@"1"];

[set]2 removeAllObjects];


9、NSIndexSet 和 NSMutableIndexSet :存储一组无符号整数的集合

It can save a collection of unsigned integers in a very efficient way, especially if it’s only one or a few ranges. As the name “set” already implies, each NSUInteger is either in the index set or isn’t. If you need to store an arbitrary number of integers that are not unique, better use an NSArray.

将一个整数数组转换为NSIndexSet:

NSIndexSet *PSPDFIndexSetFromArray(NSArray *array) {
    NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet];
    for (NSNumber *number in array) {
        [indexSet addIndex:[number unsignedIntegerValue]];
    }
    return [indexSet copy];
}

使用block语法从NSIndexSet中获取索引:
NSArray *PSPDFArrayFromIndexSet(NSIndexSet *indexSet) {
    NSMutableArray *indexesArray = [NSMutableArray arrayWithCapacity:indexSet.count];
    [indexSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
       [indexesArray addObject:@(idx)];
    }];
    return [indexesArray copy];
}



iOS 基础集合类

上一篇:AcWing 377. 泥泞的区域


下一篇:UVALive - 3693 Balancing the Scale