数组是线性结构是容器类型,是一块连续的内存空间, ios 中用 nsarray 和 nsmutablearray 集合类型,用来存放对象类型,其中 nsarray是不可变类型, nsmutablearray 是可变类型,能够对数组中元素进行增删改查.
本文作者本着学习的态度,决定仿照nsarray和nsmutablearray 自己实现一个数组类型,当然性能可能没有 nsarray和nsmutablearray 的好,插入100000万条数据,时间上是 nsmutablearray 的三倍左右 ,当然平时使用过程中很少100000次这样大的数据往数组里添加,因此性能方面可以忽略.
arraylist.h 主要方法声明 完全照搬 nsarray 和 nsmutablearray 的方法名称
先发下测试结果
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
dispatch_async(dispatch_get_global_queue(0, 0), ^{ person *p1 = [[person alloc] init]; nsmutablearray *array = [nsmutablearray arraywithcapacity:100000];// arraylist *array = [arraylist arraywithcapacity:100000]; cfabsolutetime starttime =cfabsolutetimegetcurrent(); for (int i = 0; i<100000; i++) { [array addobject:p1]; } cfabsolutetime linktime = (cfabsolutetimegetcurrent() - starttime); cftimeinterval duration = linktime * 1000.0f; nslog(@"linked in %f ms",duration); [self->_timearray addobject:@(duration)]; count++; });nsmutablearray 5.081740292635832 msarraylist 16.27591523257168 ms以下是 arraylist 的具体实现 ,内部是一个 c语言的数组用来存放对象//// arraylist.m// arraylist//// created by dzb on 2018/7/19.// copyright © 2018 大兵布莱恩特. all rights reserved.//#import "arraylist.h"static nsinteger const defaultcapacity = 10;typedef void * anyobject;@interface arraylist (){ anyobject *_array; nsinteger _size; nsinteger _capacity;}@end@implementation arraylist#pragma mark - init- (instancetype)init{ self = [super init]; if (self) { [self resetarray]; } return self;}+ (instancetype)array { return [[arraylist alloc] initwithcapacity:defaultcapacity];}+ (instancetype)arraywithcapacity:(nsuinteger)numitems { return [[arraylist alloc] initwithcapacity:numitems];}- (instancetype)initwithcapacity:(nsuinteger)numitems { _capacity = numitems; _array = calloc(_capacity,sizeof(anyobject)); _size = 0; return self;}/** 数组重置 */- (void) resetarray { _size = 0; if (_array != null) _array[_size] = null; free(_array); _capacity = defaultcapacity; _array = calloc(_capacity, sizeof(anyobject));}#pragma makr - 增加操作- (void)addobject:(id)anobject { [self insertobject:anobject atindex:_size];}- (void)insertobject:(id)anobject atindex:(nsuinteger)index { if (!anobject) { @throw [nsexception exceptionwithname:@"add object null." reason:@"object must be not null ." userinfo:nil]; return; } ///判越界 if ((index > _size)) { @throw [nsexception exceptionwithname:@"array is out of bounds" reason:@"out of bounds" userinfo:nil]; return; } if (_size == _capacity-1) { ///判断原来数组是否已经满了 如果满了就需要增加数组长度 [self resize:2*_capacity]; } ///交换索引位置 if (self.count > 0 ) { for(nsinteger i = _size - 1 ; i >= index ; i--) _array[i + 1] = _array[i]; } self->_array[index] = (__bridge_retained anyobject)(anobject); _size++;}#pragma mark - 删除操作- (void)removeallobjects { nsinteger i = _size-1; while (_size > 0) { [self removeobjectatindex:i]; i--; } [self resetarray];}- (void)removeobjectatindex:(nsuinteger)index { ///判断越界 if ((index > _size)) { @throw [nsexception exceptionwithname:@"array is out of bounds" reason:@"out of bounds" userinfo:nil]; return; } anyobject object =(_array[index]); cfrelease(object); for(nsinteger i = index + 1 ; i < _size ; i ++) _array[i - 1] = _array[i]; _size--; _array[_size] = null; ///对数组空间缩减 if (_size == _capacity/2) { [self resize:_capacity/2]; }}- (void)removeobject:(id)anobject { nsinteger index = [self indexofobject:anobject]; if (index == nsnotfound) return; [self removeobjectatindex:index];}- (void)removelastobject { if ([self isempty]) return; [self removeobjectatindex:_size-1];}#pragma mark - 修改操作- (void)replaceobjectatindex:(nsuinteger)index withobject:(id)anobject { if (!anobject) { @throw [nsexception exceptionwithname:@"add object null." reason:@"object must be not null ." userinfo:nil]; return; } ///判断越界 if ((index > _size)) { @throw [nsexception exceptionwithname:@"array is out of bounds" reason:@"out of bounds" userinfo:nil]; return; } _array[index] = (__bridge anyobject)(anobject);}#pragma mark - 查询操作- (bool) isempty { return (self->_size == 0);}- (bool) isfull { return (self->_size == self->_capacity-1);}- (id)objectatindex:(nsuinteger)index { if ((index > _size)) { @throw [nsexception exceptionwithname:@"array is out of bounds" reason:@"out of bounds" userinfo:nil]; return nil; } if ([self isempty]) { return nil; } anyobject obj = _array[index]; if (obj == null) return nil; return (__bridge id)(obj);}- (nsuinteger)indexofobject:(id)anobject { for (int i = 0; i<_size; i++) { id obj = (__bridge id)(_array[i]); if ([anobject isequal:obj]) return i; } return nsnotfound;}- (bool)containsobject:(id)anobject { for (int i = 0; i<_size; i++) { id obj = (__bridge id)(_array[i]); if ([anobject isequal:obj]) return yes; } return no;}- (id)firstobject { if ([self isempty]) return nil; return (__bridge id _nullable)(_array[0]);}- (id)lastobject { if ([self isempty]) return nil; return (__bridge id _nullable)(_array[_size]);}- (nsuinteger)count { return _size;}- (nsstring *)description { nsmutablestring *string = [nsmutablestring stringwithformat:@"\narraylist %p : [ \n" ,self]; for (int i = 0; i<_size; i++) { anyobject obj = _array[i]; [string appendformat:@"%@",(__bridge id)obj]; if (i<_size-1) { [string appendstring:@" , \n"]; } } [string appendstring:@"\n]\n"]; return string;}/** 对数组扩容 @param capacity 新的容量 */- (void) resize:(nsinteger)capacity { anyobject *oldarray = _array; anyobject *newarray = calloc(capacity, sizeof(anyobject)); for (int i = 0 ; i<_size; i++) { newarray[i] = oldarray[i]; } _array = newarray; _capacity = capacity; free(oldarray);}- (void)dealloc{ if (_array != null) [self removeallobjects]; free(_array);// nslog(@"arraylist dealloc");}@end |
经过测试 数组内部会对存入的对象 进行 retain 操作 其引用计数+1 ,当对象从数组中移除的时候 能够正常的使对象内存引用计数-1,因此不必担心对象内存管理的问题. 数组默认长度是10 , 如果在开发者不确定数组长度时候 ,其内部可以动态的扩容增加数组长度,当执行 remove 操作时候 也会对数组内部长度 进行相应的缩减
实现了 nsarray 和 nsmutablearray 等常用api,如果不是对性能特别在意的场景下 ,可以使用 arraylist 来存放一些数据
原文链接：http://www.cocoachina.com/ios/20180723/24275.html
