NSMutableArray in Objective-C is a dynamic array, you don’t have to specify the length of the array to add elements to it, you don’t have to worry about overflows. There are many ways to realize dynamic data, such as encapsulation and expansion of static array or linked list, or even mixed use of a variety of ways, according to the size of the data to dynamically change their data structure. Here is the simplest way to dynamically expand according to static data to achieve a dynamic array.

In order to implement a complete set of custom data structures, the static array is wrapped with a custom static array, because objective-C doesn’t have a wrapped static array, it’s really just an array of Pointers that can hold Pointers and internally maintain an Objective-C reference count.

Custom dynamic array effect

JKRArrayList *array = [JKRArrayList new];
for (NSUInteger i = 0; i < 60; i++) {
    [array addObject:[Person personWithAge:i]];
}
NSLog(@"After adding %@", array); Print: - capacity: 16-24 -- -- -- -- -- - > capacity: 24-36 -- -- -- -- -- - > capacity: 36 - > -- -- -- -- -- - 54 expansion: 81-54 - > add after size = 60, {< Person: 0x10285ad50> <Person: 0x10285ae50> <Person: 0x10285ae70> ... <Person: 0x10285af30> <Person: 0x10285af50> <Person: 0x10285af70> } [array removeAllObjects]; NSLog(@"After clearing %@", array); Print: <Person: 0x100501070> dealloc <Person: 0x1005010B0 > Dealloc <Person: 0x1005010D0 > Dealloc... <Person: 0x10285b010> dealloc size=0, {}Copy the code

Basic functions of dynamic arrays

Dynamic array should provide functions modeled after NSMutableArray to design, because after will use a variety of linked lists to achieve dynamic array, so there will be a lot of the same processing logic and interface, here first define a dynamic array base class:

@interface JKRBaseList<ObjectType> : NSObject {@protected // Record the current length of the dynamic array NSUInteger _size; } - (NSUInteger)count; - (void)rangeCheckForAdd:(NSUInteger)index; - (void)rangeCheckForExceptAdd:(NSUInteger)index; - (void)addObject:(nullable ObjectType)anObject; - (BOOL)containsObject:(nullable ObjectType)anObject; - (nullable ObjectType)firstObject; - (nullable ObjectType)lastObject; - (void)removeFirstObject; - (void)removeLastObject; - (void)removeObject:(nullable ObjectType)anObject; - (_Nullable ObjectType)objectAtIndexedSubscript:(NSUInteger)idx; - (void)setObject:(_Nullable ObjectType)obj atIndexedSubscript:(NSUInteger)idx;

@end

@interface JKRBaseList<ObjectType> (JKRBaseList)

- (void)insertObject:(nullable ObjectType)anObject atIndex:(NSUInteger)index;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(nullable ObjectType)anObject;
- (nullable ObjectType)objectAtIndex:(NSUInteger)index;
- (NSUInteger)indexOfObject:(nullable ObjectType)anObject;
- (void)removeAllObjects;
- (void)enumerateObjectsUsingBlock:(void (^)(_Nullable ObjectType obj, NSUInteger idx, BOOL *stop))block;

@end
Copy the code

JKRBaseList is the base class of all dynamic arrays. The reason why some of the interfaces are written in the extension is to distinguish between them. The interfaces in the extension need to be implemented by subclasses, while the interfaces outside the extension need to be implemented in different ways. The advantage of using an extension that does not require a JKRBaseList implementation is that you do not need to write an implementation of the interface in JKRBaseList. M. The compiler will warn you if you define a method declaration that does not implement it. Writing it in two parts also makes it easier to distinguish which subclasses need to implement.

Both NSArray and NSMutableArray in the system allow you to store nil, so for the sake of functionality, you can pass in and store nil into data.

Let’s look at the member variables in JKRBaseList: NSUInteger _size; This variable is required for all dynamic arrays and is responsible for keeping track of the current dynamic array length. External visible because of the dynamic array length and the length of the internal real is not necessarily consistent, such as now we are going to implement the dynamic array encapsulated by static array, just began to initialize the dynamic array object of static array length can be kept within 16, while the length of the external display is 0, because haven’t add any elements. If you use a list to implement a dynamic array, you also need to record the length of the array, otherwise you have to iterate over all the nodes in the list to calculate the array length.

Let’s take a look at the logic in JKRBaseList that does not require subclasses to implement separately, and in turn, why they are common and how they are implemented.

Note: Some public interfaces need to call the interface that the subclass needs to rewrite to implement specific functions. Don’t worry about how the subclass is implemented, assuming that the subclass has been implemented, just need to call the complete function of the interface.

Implementation of a public interface

The following methods are all implemented in jkrBaselist. m and do not require subclass overrides.

Gets the length of the array

Because the length of the dynamic array is stored in the member variable _size, you only need to return _size

Time complexity: O(1)

- (NSUInteger)count {
    return _size;
}
Copy the code

Out-of-bounds checking when adding elements

Since dynamic arrays can add elements to the tail, the bounds check for adding elements should be: index > 0 && index <= _size. Index can be equal to the length of the array, which is equivalent to appending an element to the end of the array.

- (void)rangeCheckForAdd:(NSUInteger)index {// index can be equal to _sizeif (index < 0 || index > _size) {
        [self indexOutOfBounds:index];
    }
}

- (void)indexOutOfBounds:(NSUInteger)index {
    NSAssert(NO, @"index: %zd, size: %zd", index, _size);
}
Copy the code

Out of bounds checks in addition to additions

In all cases other than addition, the index of the array should be within the array length range: index > 0 && index < _size.

- (void)rangeCheckForExceptAdd:(NSUInteger)index {
    if(index < 0 || index >= _size) { [self indexOutOfBounds:index]; }}Copy the code

Tail append element

Append an element to the end of an array is equivalent to inserting an element at index=_size. The interface for inserting the element is implemented by subclasses.

- (void)addObject:(id)anObject {
    [self insertObject:anObject atIndex:_size];
}
Copy the code

Contains elements or not

Check whether it contains elements by looking for the element index. IndexOfObject is implemented by subclasses, and returns NSUIntegerMax if not found, the same as NSArray.

- (BOOL)containsObject:(id)anObject {
    return[self indexOfObject:anObject] ! = NSUIntegerMax; }Copy the code

Returns the first/last element

This can be done by referring to the objectAtIndex interface. The difference is that when the array length is 0, it returns nil, rather than calling objectAtIndex to cross the line (same as NSArray).

- (id)firstObject {
    if (_size == 0) {
        return nil;
    }
    return [self objectAtIndex:0];
}

- (id)lastObject {
    if (_size == 0) {
        return nil;
    }
    return [self objectAtIndex:_size - 1];
}
Copy the code

Delete the first/last element

As with returning the first element, the world is returned when the array length is 0 and is not handled by removeObjectAtIndex to raise an error. RemoveObjectAtIndex is implemented by subclasses.

- (void)removeFirstObject {
    if (_size == 0) {
        return;
    }
    [self removeObjectAtIndex:0];
}

- (void)removeLastObject {
    if (_size == 0) {
        return;
    }
    [self removeObjectAtIndex:_size - 1];
}
Copy the code

Delete an element

The indexOfObject interface is called to get the index of the element, and the removeObjectAtIndex interface is called to remove the element.

- (void)removeObject:(id)anObject {
    NSUInteger index = [self indexOfObject:anObject];
    if (index != NSUIntegerMax) {
        [self removeObjectAtIndex:index];
    }
}
Copy the code

Supports the [] operator for arrays

- (id)objectAtIndexedSubscript:(NSUInteger)idx {
    return[self objectAtIndex:idx]; } // there is a distinction between - (void)setObject:(id)obj atIndexedSubscript:(NSUInteger)idx {// if idx==_size, add an element to the end of the arrayif (idx == _size) {
        [self insertObject:obj atIndex:idx];
    } else{// otherwise replace the element at index position [self replaceObjectAtIndex:idx withObject:obj]; }}Copy the code

A subclass requires a separate interface to implement

First, create a subclass of JKRBaseList, JKRArrayList, and implement the following interfaces in jkrArrayList.m:

- (void)insertObject:(nullable ObjectType)anObject atIndex:(NSUInteger)index;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(nullable ObjectType)anObject;
- (nullable ObjectType)objectAtIndex:(NSUInteger)index;
- (NSUInteger)indexOfObject:(nullable ObjectType)anObject;
- (void)removeAllObjects;
- (void)enumerateObjectsUsingBlock:(void (^)(_Nullable ObjectType obj, NSUInteger idx, BOOL *stop))block;
Copy the code

Dynamic array internal member variable

The dynamic array holds this static array and creates static data at initialization, specifying its length.

#define JKRARRAY_LIST_DEFAULT_CAPACITY (1<<4)

@interface JKRArrayList ()

@property (nonatomic, strong) JKRArray *array;

@end

@implementation JKRArrayList

+ (instancetype)array {
    return [[self alloc] initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

+ (instancetype)arrayWithCapacity:(NSUInteger)capacity {
    return [[self alloc] initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

- (instancetype)init {
    return [self initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

- (instancetype)initWithCapacity:(NSUInteger)capacity {
    self = [super init];
    self.array = [JKRArray arrayWithLength:capacity > JKRARRAY_LIST_DEFAULT_CAPACITY ? capacity : JKRARRAY_LIST_DEFAULT_CAPACITY];
    return self;
}
Copy the code

Insert elements

Instead of simply inserting the element at the index position of the static array, let’s say we have an array of length 6 and we want to insert 71 at index 1, as shown below:

If you simply replace 71 with index 1, the array element becomes:

This does not increase the number of elements, the number of elements in the static array does not change, and 32 is missing where index was 1.

The correct way to do this is to move each element back one bit from the last position to the index position, leaving the index position empty, and then putting the index position in the new element:

The code is as follows:

// time complexity O(n) // tail append element O(1) - (void)insertObject:(id)anObject atIndex:(NSUInteger)index {// check the out-of-bounds [self rangeCheckForAdd:index]; / / if the need to increase the capacity [self ensureCapacityWithCapacity: _size + 1]; // Add elementsfor(NSUInteger i = _size; i > index; i--) { self.array[i] = self.array[i - 1]; } self.array[index] = anObject; // After the element is added, _size is added by 1 _size++; }Copy the code

When adding elements dynamically, it is certain that the static array capacity cannot meet the situation, this is the need to expand the static array capacity, the next implementation of expansion operation.

capacity

When inserting an element, check whether the current static array has sufficient capacity to store the newly added element. The number of elements in the current dynamic array is _size. Therefore, the length of the static array must be at least _size + 1, that is, _array.length >= _size + 1. If the static array is not large enough, you expand it by creating a larger static array, copying all of the original data into the new array, and then adding new elements.

The specific code is as follows:

/ / time complexity complexity O (n) - (void) ensureCapacityWithCapacity: (NSUInteger) capacity {NSUInteger oldCapacity = self. The array. The length;if (oldCapacity >= capacity) {
        return;
    }
    NSUInteger newCapacity = oldCapacity + (oldCapacity >> 1);
    NSLog(@"-- expand capacity: %zd -> %zd --", oldCapacity, newCapacity);
    JKRArray *newArray = [JKRArray arrayWithLength:newCapacity];
    for (NSUInteger i = 0; i < _size; i++) {
        newArray[i] = self.array[i];
    }
    self.array = newArray;
}
Copy the code

Remove elements

Deleting elements also requires moving nodes:

/ / time complexity complexity O (n) / / remove the rear element complexity O (1) - (void) removeObjectAtIndex: (NSUInteger) index {[self rangeCheckForExceptAdd: index];for (NSUInteger i = index + 1; i < _size; i++) {
        self.array[i - 1] = self.array[i];
    }
    self.array[--_size] = nil;
}
Copy the code

Gets the index of the element

Getting the index of an element requires traversing all the nodes of the static array, finding the elements that match, and returning the index of each element.

  • The final node of the traversal should not be the length of the static array, but the length of the dynamic array _size.
  • Since custom arrays allow nil to be passed in and stored, we need to do a separate processing of the index that looks up nil and return the index corresponding to the first nil.
// time complexity O(n) - (NSUInteger)indexOfObject:(id)anObject {if(! anObject) {for (NSUInteger i = 0; i < _size; i++) {
            if (self.array[i] == nil) {
                returni; }}}else {
        for (NSUInteger i = 0; i < _size; i++) {
            if ([anObject isEqual:self.array[i]]) {
                returni; }}}return NSUIntegerMax;
}
Copy the code

Empty array

O(n) - (void)removeAllObjects {if (_size == 0) return;
    for (NSUInteger i = 0; i < _size; i++) {
        self.array[i] = nil;
    }
    _size = 0;
}
Copy the code

Get the element by index

/ / time complexity O (1) - (id) objectAtIndex: (NSUInteger) index {[self rangeCheckForExceptAdd: index];return self.array[index];
}
Copy the code

Rewrite print

- (NSString *)description {
    NSMutableString *string = [NSMutableString string];
    [string appendString:[NSString stringWithFormat:@"size=%zd, {\n", _size]];
    [self enumerateObjectsUsingBlock:^(id  _Nullable obj, NSUInteger idx, BOOL * _Nonnull stop) {
        if (idx) {
            [string appendString:@"\n"];
        }
        [string appendString:[NSString stringWithFormat:@"% @", obj]];
    }];
    [string appendString:@"\n}"];
    return string;
}
Copy the code

The source code

Click to view source code