Objc DataStructure

我们将从“数据结构”和“数据类型”两个角度来分析

一、数据结构

Q: 什么是数据结构呢？
A: 数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。

数据结构通常分为以下八大类:

数组 - Array
堆 - Heap
栈 - Stack
队列 - Queue
链表 - Linked List
图 - Graph
散列表 - Hash哈希表
树 - Tree (字典树:这是一种高效的树形结构)

二、数据类型

Objective-C这门语言是C语言的严格超集，我们先来看看C里面有哪些数据类型。

C数据类型

基本数据类型
构造类型
指针类型
空类型

1. 基本数据类型

基本数据类型（fundamental data types）也叫原始数据类型（primitive data types）。包括: 整型、字符型、浮点型、枚举型, 其中枚举型在计算机内部以 int 类型存储。详见下表。

数据类型	16位编译器	32位编译器	64位编译器
char	1byte	1byte	1byte
int	2byte	4byte	4byte
float	4byte	4byte	4byte
double	8byte	8byte	8byte
short int	2byte	2byte	2byte
unsigned int	2byte	4byte	4byte
long	4byte	4byte	8byte
unsigned long	4byte	4byte	8byte
long long	8byte	8byte	8byte

2. 构造类型

构造类型包括: 数组类型, 结构体类型(struct), 共用/联合体类型(union)。其中union一般在对单片机等内存比较小的设备进行编程时才使用。

3. 指针类型

data_type *pointer_name

由于指针在实质上是一个内存地址，内存地址的长度跟CPU的寻址有关(与data_type无关), 所以在32位系统上, 指针占据4个字节；在64位系统上，指针占据8个字节.

4. 空类型

空类型一般用于函数的返回值，表示不需要返回任何类型。由于void类型只是一个抽象概念，并不会存在于内存中，自然就没有字节占用。

OC数据类型

前面提到过，Objective-C是C语言的严格超集，因为以上的数据类型也是OC的数据类型.相比于C, OC是一门面向对象语言, 如同C++一样支持用户定义类型Class。用户定义类型为Cocoa框架的诞生提供了可能。

OC数据类型, 实际上指的是C数据类型加上Cocoa框架集合（Foundation、UIKit等）中定义的的数据类型，也即Cocoa类（泛指所有基于Objective-C运行时且派生自根类NSObject的类）。

Foundation框架中定义的NSObject类是iOS中最重要的数据类型，用户定义的类都需要继承自它从而获得调用iOS系统资源的能力。Foundation中还有一个重要的集合（Collection）概念，其包含了NSArray、NSSet、NSDictionarry以及各自的可变类型；此外，还有NSString、NSMutabString、NSNumber等重要的类型。以上提及的类型均继承自NSObject，是用户定义类型（class）而并非构造类型（struct），它们在被赋值或者被传入函数或者方法时，不会发生值拷贝，而是传递现有实例的引用。

OC数据类型 = C数据类型 + Cocoa类型

OC数据类型
- C数据类型
  - 基本数据类型
    - 整型
    - 字符型
    - 浮点型
    - 枚举型
  - 构造类型
  - 指针类型
  - 空类型
- Cocoa类型
  - C基本数据类型-变名
    - CGFloat
    - NSInteger
    - NSUInteger
    - BOOL
  - NSObject对象数据类型
    - Collection
      - NSArray
      - NSMutableArray
      - NSSet
      - NSMutableSet
      - NSDictionary
      - NSMutableDictionary
    - NSString
    - NSMutableString
    - NSNumber

注：由于在OC中BOOL实际上是signed char类型的重命名，NSInteger等也大同小异，因而并没有将它们归为新的类型。

从可以知道OC中Class与NSObject都是基于Struct, 接下来我们将指针类型及构造类型中的结构体类型Struct挑出来重点分析

三、数据类型详解

Objective-C数据类型可以分为:基本数据类型、对象数据类型和 id类型 :

基本数据类型有：int、float、double和char类型。

对象类型就是类或协议所声明的指针类型，例如:

NSAutoreleasePool *pool ,其中，NSAutoreleasePool是一个类，NSAutoreleasePool *是它指针类型或叫对象类型。

id类型可以表示任何类型，一般只是表示对象类型，不表示基本数据类型，所以刚才的变量可以声明 pool 也可以声明为 id pool。类型解释:

1. C基本数据类型

1.1. 整型 int

int类型代表整数，它的十六进制表示方式:OxFFED0D.
在使用NSLog函数中格式化字符串使用%i表示十进制的整数，%o(字母o)表示8进制整数，%#x表示十六进制整数，它的取值范围是与设备相关的，无法一概而论。

1.2. 字符型 chart

char类型代表字符类型，存放点个字符，用单引号引用起来。如:’A’,如果要表示一些特殊字符，要使用转义字符“\”。
NSLog函数中格式化字符串:%c。

1.3. 布尔 bool

在计算机内部以int类型存储, 布尔类型是_Bool(别名BOOL),取值范围是1或0，其中1可以用TURE和YES表示，0可以用FALSE和NO表示。

1.4. 枚举类型 enum

枚举类型(在计算机内部以int类型存储):如果需要定义一组相关常量，可以采用枚举类型，把这些常量定义成一个类型，例如游戏在上、下、左、右方向，可以枚举类型:enum direction{up,down,left,right}.其中，up从0开始，down是1，以此类推加1。如果不想从0开始，也可以指定初始值，如:enum direction{up=1,down,left,right}。

1.5. 单精度浮点型 float

float类型表示代表单精度浮点数，可以在数值后面加上f或者F，例如：13.5f。float浮点数也可以用科学计数法表示，例如:1.7e4。
NSLog函数中格式化字符串:%f表示浮点数(会保留后面6位小数)，%e表示科学计数法，%g表示浮点数。

1.6. 双精度浮点型 double

double类型代表双精度浮点数，与float数相似，占用的字节空间double类型大体上是float类型的两倍。大多数计算机是使用64位，表示double类型。
NSLog函数中格式化字符串，与float的%f、%e和%g相同。

1.7. 数据类型的专用限定词: 那些大牛专用技术型文件爱标注这些"技术类限定词"。

可以在int、float和double、char类型前面加上限定词，限定词有:long、longlong、short、unsigned和signed，这些限定词从而增强了基本类型。

long int:在大部分计算机中代表32位整数，在整数后面加L(或l)表示，如:long int numberOfPoints = 1310L.NSLog函数中格式化字符串使用%li表示。
long long int:可以指定更加宽泛的整数类型，保证变量至少64位宽度。NSLog函数中格式化字符串使用%lli表示。
long double:可以指定更为宽泛的double类型，要显示这个可以在尾部使用L(大小写)表示，1.23+7L.NSLog函数中格式化字符串使用%Lf、%Le和%Lg表示。
short int:用来指定存放相对小得整数，一般式占用int类型的一半。大部分计算机是16位。
unsigned int(无符号整数):告诉编译器只是接受整数，在数值之后存放字母u(或U)表示，例如:0x00ffU;在编写整数的时候，可以将字母u(或U)和l(或L)组合起来，例如:100UL.
signed char(char在计算机中存的也是整数，所以有符号和无符号之分。)：代表的字符和编译器有关，一般也作为无符号整数使用。

2. C构造类型

结构体类型

(a).C语言本身提供的数据类型很少，那么C语言是如何构造复杂的数据类型呢?有三种方法：结构体、指针、数组。 (b).结构体和指针在iOS编程是至关重要的，在OC中很少需要C的数组，因为OC有它自己的NSArray类型。 (c).C的结构体是一个混合数据类型，在这个类型中包含了多种数据类型（也可以是另一个结构体），它能够作为单个的实体被传递。其中的元素通过点符号来访问。例如：

一个CGPoint定义如下:

struct CGRect{
CGRect x;
CGRect y;
};

typedef struct CGPoint

3. C指针类型

4. C空类型

5. OC基本数据类型

6. OC对象数据类型

类型转换

有了数据类型必然有各类型数据之间的转换:

1.按照数据类型占用存储不同可以自动类型转换或强制类型转换，总的原则是小存储容量类型可以自动转换成大存储容量数据类型。

2.不同类型数据间按照下面关系的从左到右(从低到高)自动转换。如下:

_Bool、char、short int、枚举类型——>int——>long int——>long long int

——>float——>double——>long double.

3.强制类型转换:

如果遵守类型转换是右到左情况，就需要强制类型转换了。强制类型转换语法形式上很简单，就是在数据前面加上(目标类型)，但是这种转换是存在风险的，有可能造成数据的丢失，需要谨慎进行。

/* SEL就是对方法的一种包装。 */

(1).方法的存储位置

@interface Person：NSObject

（void）test1； (void )test2; @end

Person *person = [[Person alloc]init];

(2)在内存中如下：在内存中每个类的方法都存储在类对象中，每个方法都有一个与之对应的SEL类型的数据，根据一个SEL数据就可以找到对应的方法地址，进而调用方法。

SEL类型的定义：typedef struct objc_selector *SEL.

SEL对象的创建

SEL s1 = @selector（test1）；

SEL s2 = NSSelectorFromString（@“test1”）

注意:(a).SEL类型是OC中用来定义方法的关键字，和其他语言不同的是SEL类型虽然是方法定义，但却不从属于任何类实例，其值是通过@selector进行计算，可以把它当做一个函数指针来使用，当然它实际上并不是一个函数指针，而是const char*。

(b).SEL类型可以在编译时通过@selector()直接创建，也可以用NSSelectorString()函数创建，这个函数允许你通过名字调用方法。例如：

[object performSelector:@selector(doSomething)]];

它和如下代码等价：[object doSomething];

(3).各种语言都有传递函数的方法:C语言使用函数指针，C++中有函数引用，OC使用选择器selector和block。

/* nil、NULL、NSNull */

首先要说明的是，nil、Nil、NULL三个关键字和NSNull类都是表示空，它们本质上都是一样的，都是(void *)0，既然写法不同,那么代表用处也不一样，这样做的意义是为了区分不同的数据类型，比如你一看到用到了NULL就知道这是个C指针，看到nil就知道这是个Objective-C对象，看到Nil就知道这是个Class类型的数据。具体的区别如下：

(a).nil用来给对象赋值（OC的任何对象都属于id类型),Null则给任何指针赋值，NULL和nil不能互换，nil用于类指针赋值(在OC中类是一个对象，是类的meta-class的实例)，而NSNull则用于集合操作，虽然它们表示的都是空值，但使用场合不同。

(b).OC有个特性，就是当发送消息给nil对象使，系统返回0值而不是引起异常，这和Java的NullPointerException以及C/C++的程序直接崩溃的处理完全不同，因为nil是对象的合法值,nil对象同样可以接收消息。

(c).nil被定义为空对象，也就是值为0的对象。

/* id */

(a).在OC中最普遍的3种类型就是id、Class和SEL, id就是指向OC对象的指针，它等价于C语言中的void *,可以映射任何对象指针类型指向它，或者映射它指向其他的对象。当然，也可以传递任何消息给id，但如果该id不支持这个消息就会返回一个运行时异常。

(b).id数据类型可存储任何类型的对象。从某种意义上说，它是一般对象类型。如果要用基本类型代替，需要对基本数据类型进行封装。

(c).id是一个指向任何一个继承了Object(或者NSObject)类的对象。需要注意的是,id

是一个指针，所以在使用id的时候不需要加星号。例如:

id foo = nil;

(d).在OC中，id取代了int类型成为默认的数据类型（在C语言上的函数返回值，int是默认的返回类型）。

/* Bool */

(a).在OC中的布尔类型是BOOL,其值可以是YES或NO,也可以赋值为TRUE和FALSE。YES和TRUE等价，都是非零值；NO和FALSE等价，都是零值。

(b).在调试的时候可以通过打印数字的方式（格式为%d）输出其值，代码如下：

BOOL loginResult = YES;

NSLog(@"LoginResult is %d",loginResult);

(c).布尔变量的值为YES/NO或1/0.YES和1代表真。

/* 结构体 */

(a).C语言本身提供的数据类型很少，那么C语言是如何构造复杂的数据类型呢?有三种方法：结构体、指针、数组。

(b).结构体和指针在iOS编程是至关重要的，在OC中很少需要C的数组，因为OC有它自己的NSArray类型。

(c).C的结构体是一个混合数据类型，在这个类型中包含了多种数据类型（也可以是另一个结构体），它能够作为单个的实体被传递。其中的元素通过点符号来访问。例如：

一个CGPoint定义如下:

struct CGRect{

CGRect x;

CGRect y;

};

typedef struct CGPoint

作者：孙卓卓链接：https://www.jianshu.com/p/bb36b7394a3c 来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

指针类型

指针函数指针指针函数

结构体类型Struct

struct是oc的基础结构体初始化后不能在定义

既然是类，我们就可以实例化一个对象 NSString *s = [NSString new]; 1）分配空间 2）初始化 3）返回地址

NSArray

排序

逆序，array.reverseObjectEnumerator.allObjects
数组中是字符串对象排序首选sortedArrayUsingSelector:

NSArray *array = @[@"John Appleseed", @"Tim Cook", @"Hair Force One", @"Michael Jurewitz"];
NSArray *sortedArray = [array sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];

存储内容是数字

NSArray *numbers = @[@9, @5, @11, @3, @1];
NSArray *sortedNumbers = [numbers sortedArrayUsingSelector:@selector(compare:)];

使用函数指针sortedArrayHint排序

- (NSData *)sortedArrayHint;
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
     context:(void *)context;
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
     context:(void *)context hint:(NSData *)hint;

基于block的排序方法

- (NSArray *)sortedArrayUsingComparator:(NSComparator)cmptr;
- (NSArray *)sortedArrayWithOptions:(NSSortOptions)opts
     usingComparator:(NSComparator)cmptr;

性能比较selector最快

Sorting 1000000 elements. selector: 4947.90[ms] function: 5618.93[ms] block: 5082.98[ms].

更快的二分查找

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;

//Time to search for 1000 entries within 1000000 objects. Linear: 54130.38[ms]. Binary: 7.62[ms]

枚举

使用indexesOfObjectsWithOptions:passingTest:

NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:NSEnumerationConcurrent
     passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
     return testObj(obj);
}];
NSArray *filteredArray = [randomArray objectsAtIndexes:indexes];

传统的枚举

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

block方式枚举

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

通过下标objectAtIndex:

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

使用比较传统的学院派NSEnumerator

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

使用predicate

NSArray *filteredArray2 = [randomArray filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id obj, NSDictionary *bindings) {
     return testObj(obj);
}]];

各个方法枚举时间参考，indexesOfObjectsWithOptions在开启了并发枚举的情况下比NSFastEnumeration快一倍。

枚举方法 / 时间 [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

NSDictionary

性能

同样数目的值，NSDictionary比NSArray要花费多得多的内存空间

排序

使用NSArray的排序方法将键数组排序为新的对象

- (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator;
- (NSArray *)keysSortedByValueUsingComparator:(NSComparator)cmptr;
- (NSArray *)keysSortedByValueWithOptions:(NSSortOptions)opts
     usingComparator:(NSComparator)cmptr;

枚举

keysOfEntriesWithOptions:passingTest:，可并行

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];

getObjects:andKeys: 枚举，基于c数组

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

block枚举

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

各个方法枚举时间参考

枚举方法 / 时间 [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

参考链接

iOS 数据结构总结
 iOS-数据结构
 iOS有哪些数据类型/基本数据类型？
基础数据类型和它的转化
 C语言和OC的结构体(struct)
iOS中编写高效能结构体的7个要点
 OC底层原理之《内存对齐原则》
iOS_NSSet与NSArray的区别
 iOSNSSet 和 NSArray的区别

Objc DataStructure

一、数据结构

二、数据类型

C数据类型

1. 基本数据类型

2. 构造类型

3. 指针类型

4. 空类型

OC数据类型

三、数据类型详解

1. C基本数据类型

1.1. 整型 int

1.2. 字符型 chart

1.3. 布尔 bool

1.4. 枚举类型 enum

1.5. 单精度浮点型 float

1.6. 双精度浮点型 double

1.7. 数据类型的专用限定词: 那些大牛专用技术型文件爱标注这些"技术类限定词"。

2. C构造类型

结构体类型

3. C指针类型

4. C空类型

5. OC基本数据类型

6. OC对象数据类型

类型转换

指针类型

结构体类型Struct

NSArray

排序

枚举

NSDictionary

性能

排序

枚举

参考链接

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!