iOS 数据结构之数组的操作方法
程序员文章站
2023-12-16 13:05:40
数组是线性结构是容器类型,是一块连续的内存空间, ios 中用 nsarray 和 nsmutablearray 集合类型,用来存放对象类型,其中 nsarray是不可变类...
数组是线性结构是容器类型,是一块连续的内存空间, ios 中用 nsarray 和 nsmutablearray 集合类型,用来存放对象类型,其中 nsarray是不可变类型, nsmutablearray 是可变类型,能够对数组中元素进行增删改查.
本文作者本着学习的态度,决定仿照nsarray和nsmutablearray 自己实现一个数组类型,当然性能可能没有 nsarray和nsmutablearray 的好,插入100000万条数据,时间上是 nsmutablearray 的三倍左右 ,当然平时使用过程中很少100000次这样大的数据往数组里添加,因此性能方面可以忽略.
arraylist.h 主要方法声明 完全照搬 nsarray 和 nsmutablearray 的方法名称
先发下测试结果
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 ms arraylist 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 来存放一些数据