欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

iOS 数据结构之数组的操作方法

程序员文章站 2023-12-10 15:20:40
数组是线性结构是容器类型,是一块连续的内存空间, ios 中用 nsarray 和 nsmutablearray 集合类型,用来存放对象类型,其中 nsarray是不可变类...

数组是线性结构是容器类型,是一块连续的内存空间, ios 中用 nsarray 和 nsmutablearray 集合类型,用来存放对象类型,其中 nsarray是不可变类型, nsmutablearray 是可变类型,能够对数组中元素进行增删改查.

本文作者本着学习的态度,决定仿照nsarray和nsmutablearray 自己实现一个数组类型,当然性能可能没有 nsarray和nsmutablearray 的好,插入100000万条数据,时间上是 nsmutablearray 的三倍左右 ,当然平时使用过程中很少100000次这样大的数据往数组里添加,因此性能方面可以忽略.

arraylist.h 主要方法声明 完全照搬 nsarray 和 nsmutablearray 的方法名称

iOS 数据结构之数组的操作方法 

先发下测试结果

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 来存放一些数据