iOS 开发中经常使用到的数组为 NSArray 和 NSMutableArray ,这是 Foundation 给我们提供的数据结构.平时开发中使用 NSArray 和 NSMutableArray 是可以满足开发需要的.抱着学习的态度 小编对于数组这种数据结构的底层实现饶有兴趣,因此自己实现了一个数组.
https://github.com/ZhaoBingDong/iOS-DataStructures.git
image.png
//
// ArrayList.m
// ArrayList
//
// Created by dzb on 2018/7/19.
// Copyright © 2018 大兵布莱恩特. All rights reserved.
//
#import "ArrayList.h"
static NSInteger const defaultCapacity = 10;
typedef id _Nullable (*RFUNC)(id _Nonnull, SEL _Nonnull,...);
typedef void * AnyObject;
@interface ArrayList ()
{
@private
AnyObject *_array;
NSInteger _size;
NSInteger _capacity;
}
@end
@implementation ArrayList
#pragma mark - init
- (instancetype)init
{
self = [super init];
if (self) {
_size = 0;
_capacity = defaultCapacity;
_array = (AnyObject*)calloc(_capacity, sizeof(AnyObject));
}
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 = (AnyObject*)calloc(_capacity,sizeof(AnyObject));
_size = 0;
return self;
}
#pragma mark - 增加操作
- (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) { ///判断原来数组是否已经满了 如果满了就需要增加数组长度
[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 {
AnyObject *oldArray = _array;
NSInteger i = _size - 1;
while (i >= 0) {
AnyObject *obj = oldArray[i];
CFRelease(obj);
i--;
}
if (oldArray != NULL) { free(oldArray); }
_size = 0;
_capacity = defaultCapacity;
_array = (AnyObject*)calloc(_capacity, sizeof(AnyObject));
}
- (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 * 0.25 && (_capacity*0.25 != 0)) {
[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-1]);
}
- (NSUInteger)count {
return _size;
}
/**
对数组扩容
@param capacity 新的容量
*/
- (void) resize:(NSInteger)capacity {
_capacity = capacity;
AnyObject *oldArray = _array;
AnyObject *newArray = (AnyObject *)calloc(_capacity,sizeof(AnyObject));
size_t size = sizeof(AnyObject) * self.count;
memcpy(newArray,oldArray,size); ///对旧的数组进行值的拷贝
_array = newArray;
if (oldArray != NULL) {
free(oldArray);
oldArray = NULL;
}
}
/**
拷贝一个新的数组 使新数组内容 和 原来数组内容一样
@return ArrayList
*/
- (ArrayList *)copyNewArray {
AnyObject *oldArray = _array;
ArrayList *newArray = [ArrayList arrayWithCapacity:_capacity];
size_t size = sizeof(AnyObject) * _capacity;
memcpy(newArray->_array,oldArray, size);
return newArray;
}
- (void)dealloc
{
if (_array != NULL) {
NSInteger i = _size - 1;
while (i >= 0) {
AnyObject *obj = _array[i];
if (obj != NULL)
CFRelease(obj);
i--;
}
free(_array);
}
}
- (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;
}
- (id)copyWithZone:(NSZone *)zone {
return self;
}
- (id)mutableCopyWithZone:(NSZone *)zone {
return self;
}
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer count:(NSUInteger)len {
NSInteger count;
/* In a mutable subclass, the mutationsPtr should be set to point to a
* value (unsigned long) which will be changed (incremented) whenever
* the container is mutated (content added, removed, re-ordered).
* This is cached in the caller at the start and compared at each
* iteration. If it changes during the iteration then
* objc_enumerationMutation() will be called, throwing an exception.
* The abstract base class implementation points to a fixed value
* (the enumeration state pointer should exist and be unchanged for as
* long as the enumeration process runs), which is fine for enumerating
* an immutable array.
*/
state->mutationsPtr = (unsigned long *)&state->mutationsPtr;
count = MIN(len, [self count] - state->state);
/* If a mutation has occurred then it's possible that we are being asked to
* get objects from after the end of the array. Don't pass negative values
* to memcpy.
*/
if (count > 0)
{
IMP imp = [self methodForSelector: @selector(objectAtIndex:)];
int p = (int)state->state;
int i;
for (i = 0; i < count; i++, p++)
{
RFUNC funcPt =(RFUNC)imp;
id objc = funcPt(self,@selector(objectAtIndex:),p);
buffer[i] = objc;
}
state->state += count;
}
else
{
count = 0;
}
state->itemsPtr = buffer;
return count;
}
@end
/**
测试用例 对比 NSMutableArray 比 ArrayList 性能提升 2.42倍
ArrayList 16.90701246261597ms
NSMutableArray 6.979000568389893ms
*/
- (void) testArrayListAndNSArray {
_timeArray = [NSMutableArray array];
///10万次对比 NSMutableArray 和 ArrayList
int number = 100000;
Person *p = [Person new];
for (int i = 0; i<10; i++) {
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
ArrayList <Person *> *array = [ArrayList arrayWithCapacity:number];
for (int i = 0; i<number; i++) {
[array addObject:p];
}
[array removeAllObjects];
CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
CFTimeInterval duration = linkTime * 1000.0f;
// NSLog(@"Linked in %f ms",duration);
[self->_timeArray addObject:@(duration)];
[NSThread sleepForTimeInterval:0.3f];
}
NSLog(@"ArrayList time is %@",[_timeArray valueForKeyPath:@"@avg.self"]);
NSLog(@"********************************");
[_timeArray removeAllObjects];
for (int i = 0; i<10; i++) {
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
NSMutableArray <Person *> *array = [NSMutableArray arrayWithCapacity:number];
for (int i = 0; i<number; i++) {
[array addObject:p];
}
[array removeAllObjects];
CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
CFTimeInterval duration = linkTime * 1000.0f;
[self->_timeArray addObject:@(duration)];
[NSThread sleepForTimeInterval:0.3f];
}
NSLog(@"NSMutableArray time is %@",[_timeArray valueForKeyPath:@"@avg.self"]);
}
通过10万次添加数据的测试用例, ArrayList 的耗时是 NSMutableArray 的将近3-5倍 ,不过都是在毫秒级别的 ,比如 NSMutableArray 用时 6.979000568389893ms ms , 而 ArrayList 耗时在 16.90701246261597ms ms ,不过日常开发中很少有人一次往数组里加入10万条数据,大批量的数据都存放在数据库中,因此使用过程中这两者差距可以忽略不计 ,小编也在自己项目中有些功能模块使用 ArrayList 多个版本迭代 证明了其稳定性.
学习数据结构重要的是明白其底层实现原理, 平时开发中用系统给我们提供的数据结构也是很方便的
好了，我是大兵布莱恩特，欢迎加入博主技术交流群，iOS 开发交流群
QQ20180712-0.png
网友评论