酷应用

iOS 数据结构之数组

百家作者：iOS开发 2018-09-01 11:59:50

点击上方“iOS开发”，选择“置顶公众号”

关键时刻，第一时间送达！

作者：大兵布莱恩特
链接：https://www.jianshu.com/p/af6803eb3fe3
iOS开发整理发布，转载请联系作者获得授权

数组是线性结构是容器类型,是一块连续的内存空间, 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 来存放一些数据

【点击成为源码大神】