Static array implementation in Objective-C environment

The reason for customizing static arrays

For one reason, the Objective-C guy didn’t have one, so he had to build his own.

Internal implementation scheme

Create an array object, JKRArray, that inherits directly from NSObject. First of all, the custom array should be compatible with the Objective-C native language, so our static array should hold Pointers to objects just like NSArray, except that the custom static array needs to be initialized with a specified length, and when initialized, it’s an empty array, In addition, elements can be directly inserted and removed by subscript at any position within the array length. For example, after initializing an array of length 3, the internal structure of the array should be:

[nil, nil, nil]
Copy the code

After inserting an @1 directly into array[1] by subscript, the internal structure of the array should look like this:

[nil, 1, nil]
Copy the code

Because arrays need to hold Pointers to objects, and because of the limited functionality, we have to have our own static array to hold Pointers. Objective-c doesn’t have this functionality, so we can only use C++ arrays to do this. Change the jkrarray. m file to jkrarray. mm and add -fno-objC-arc to the Compiler Flags of jkrarray. mm in the TARGETS- buildPhase-compile Sources of the project.

Object encapsulation

Here, try to imitate the interface design style of the official Objective-C language to achieve the purpose of easy to remember the interface and easy to use.

{
@protected
    void ** _array;
    NSUInteger _length;
}

- (instancetype)init __unavailable;
+ (instancetype)new __unavailable;

+ (instancetype)arrayWithLength:(NSUInteger)length;

- (instancetype)initWithLength:(NSUInteger)length;
- (NSUInteger)length;
- (void)setObject:(nullable ObjectType)object AtIndex:(NSUInteger)index;
- (nullable ObjectType)objectAtIndex:(NSUInteger)index;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (NSUInteger)indexOfObject:(nullable ObjectType)object;
- (BOOL)containsObject:(ObjectType)object;

@end

@interface JKRArray<ObjectType> (JKRExtendedArray)

- (void)enumerateObjectsUsingBlock:(void (^)(_Nullable ObjectType obj, NSUInteger idx, BOOL *stop))block;
- (_Nullable ObjectType)objectAtIndexedSubscript:(NSUInteger)idx;
- (void)setObject:(_Nullable ObjectType)obj atIndexedSubscript:(NSUInteger)idx;

@end

@interface JKRArray<ObjectType> (NSGenericFastEnumeraiton) <NSFastEnumeration>

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained _Nullable [_Nonnull])buffer count:(NSUInteger)len;

@end
Copy the code

Interface definition and function, and the official NSArray all maintain the same, so most of the interface will not explain, here one by one to illustrate some NSArray exist single and not commonly used and our custom interface.

{// The access to the following two member variables is set to private, because they should not be changed @private // The pointer to the object added to the array void ** _array; // The length of the array NSUInteger _length; } // The following is defined so that our array can only be created by specifying a length, since static data must be specified with a length - (instanceType)init __unavailable; + (instancetype)new __unavailable; + (instancetype)arrayWithLength:(NSUInteger)length; - (instancetype)initWithLength:(NSUInteger)length; /// The following two methods are declared and implemented so that our custom array class can be implemented with [] values and assignments, for example id obj = array[10], array[3] = [NSObject new]. - (_Nullable ObjectType)objectAtIndexedSubscript:(NSUInteger)idx; - (void)setObject:(_Nullable ObjectType)obj atIndexedSubscript:(NSUInteger)idx; // The <NSFastEnumeration> protocol and this method are for implementationfor inRapid traverse - (NSUInteger) countByEnumeratingWithState: (NSFastEnumerationState *) state objects: (id __unsafe_unretained _Nullable  [_Nonnull])buffer count:(NSUInteger)len;Copy the code

Interface implementation

Initialize the interface implementation

At the time of initialization, an array of Pointers is created with the length passed in by the initializer.

#pragma mark - Initializes+ (instancetype)arrayWithLength:(NSUInteger)length {// manually managing class methods to create objects requires calling autoreleasereturn[[[self alloc] initWithLength:length] autorelease]; } - (instancetype)initWithLength:(NSUInteger)length { self = [super init]; _length = length; _array = new void*[length]();return self;
}
Copy the code

The border check

Encapsulate a method that checks for out of bounds before all methods on index are executed

#pragma mark - Border checking
- (void)checkRangeWithIndex:(NSUInteger)index {
    if (index < 0 || index >= _length) NSAssert(NO, @"Index: %zd, Length: %zd", index, _length);
}
Copy the code

Add the element at index

Time complexity: O(1)

#pragma mark - Adds elements
- (void)setObject: (id) Object AtIndex: (NSUInteger) index {/ / check whether incoming index is outside the range of the array [self checkRangeWithIndex: index]; OldObject = [self objectAtIndex:index]; // If the added element is the same as the original element, it is returned directly.if (oldObject == object) return; // If the added element is a new element, the old element reference count is -1if(oldObject ! = nil) [oldObject release]; // Add new element reference count +1if(object) [object retain]; *(_array + index) = (__bridge void *)object; }Copy the code

Delete elements by index

Time complexity: O(1)

#pragma mark - Removes elements- (void) removeObjectAtIndex: (NSUInteger) index {/ / check whether the incoming index is more than the scope of the array [self checkRangeWithIndex: index]; Object = (__bridge id)(*(_array + index)); // Remove reference count -1 (+1 when added)if (object) [object release];
    *(_array + index) = 0;
}
Copy the code

Get the element by index

Time complexity: O(1)

#pragma mark - Gets elements- (id)objectAtIndex:(NSUInteger)index { [self checkRangeWithIndex:index]; Id object = (__bridge ID)(*(_array + index));return object;
}
Copy the code

Enumerate all elements

#pragma mark - enumeration- (void)enumerateObjectsUsingBlock:(void (^)(id _Nullable, NSUInteger, BOOL * _Nonnull))block { BOOL stop = NO; // Traverses all index values in the length rangefor (NSUInteger i = 0; i < _length && !stop; i++) {
        id object = [self objectAtIndex:i];
        block(object, i, &stop);
    }
}
Copy the code

Gets the index of the element

Time complexity: O(N)

#pragma mark - The first subscript of the element stored in the array- (NSUInteger)indexOfObject:(id)object {// if no index is found, __block NSUInteger index = NSUIntegerMax; __block NSUInteger index = NSUIntegerMax; // Start with index 0, Find the first meet the index [self enumerateObjectsUsingBlock: ^ (id _Nullable obj, NSUInteger independence idx, BOOL * _Nonnull stop) {if (object == obj) {
            index = idx;
            *stop = YES;
        } else if([object isEqual:obj]){ index = idx; *stop = YES; }}];return index;
}
Copy the code

Returns whether an array contains an element

Time complexity: O(N)

#pragma mark - Whether to include- (BOOL)containsObject:(id)object {// check the index of the element, NSUInteger index = [self indexOfObject:object];return index < _length;
}
Copy the code

Return array length

Time complexity: O(1)

#pragma mark - Returns the length
- (NSUInteger)length {
    return _length;
}
Copy the code

Support for array operators

#pragma mark - Supports array operators
- (id)objectAtIndexedSubscript:(NSUInteger)idx {
    return [self objectAtIndex:idx];
}

- (void)setObject:(id)obj atIndexedSubscript:(NSUInteger)idx {
    [self setObject:obj AtIndex:idx];
}

Copy the code

Support for in fast traversal

#pragma mark - Fast traversal
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id  _Nullable [])buffer count:(NSUInteger)len {
    if (state->state > 0) return 0;
    state->mutationsPtr = (unsigned long*)self;
    NSUInteger retCount = state->extra[0];
    state->itemsPtr = (id *)(_array + state->extra[1]);
    if (retCount == 0) retCount = _length;
    if (retCount > len) {
        state->extra[0] = retCount - len;
        state->extra[1] += len;
        retCount = len;
    } else {
        state->state++;
    }
    return retCount;
}
Copy the code

Override dealloc

#pragma mark - dealloc- (void)dealloc {// Before dealloc, the element reference count must be restored (-1). Otherwise, memory leaks will occurfor (NSUInteger i = 0; i < _length; i++) {
        id object = [self objectAtIndex:i];
        if (object) [object release];
    }
    delete _array;
    [super dealloc];
}
Copy the code

Overriding the description method

We’re going to make it possible for custom arrays to be printed as arrays, just like NSArray

- (NSString *)description {
    NSMutableString *mutableString = [NSMutableString string];
    [mutableString appendString:[NSString stringWithFormat:@"<%@: %p>: \nlength: %zd\n{\n", self.class, self, _length]];
    for (NSUInteger i = 0; i < _length; i++) {
        if (i) [mutableString appendString:@"\n"];
        id object = [self objectAtIndex:i];
        if (object) {
            [mutableString appendString:@""];
            [mutableString appendString:[object description]];
        } else {
            [mutableString appendString:@""];
            [mutableString appendString:@"Null"];
        }
    }
    [mutableString appendString:@"\n}"];
    return mutableString;
}
Copy the code

Testing capabilities

Initialization test

JKRArray *array = [JKRArray arrayWithLength:6];
NSLog(@"% @", array); Print: <JKRArray: 0x102107CB0 >: length: 6 {Null Null Null Null Null Null}Copy the code

Insert the test

array[2] = [Person new];
NSLog(@"% @", array); Print: <JKRArray: 0x1006079f0>: Length: 6 {Null Null <Person: 0x10286bc60> Null Null Null}Copy the code

Delete the test

array[2] = nil;
NSLog(@"% @", array); <Person: 0x100713400> dealloc <JKRArray: 0x100607e20>: Length: 6 {Null Null Null Null Null Null Null}Copy the code

The source code

Click to view source code

Static array implementation in Objective-C environment

The reason for customizing static arrays

Internal implementation scheme

Object encapsulation

Interface implementation

Testing capabilities

The source code

Related Posts

S01E23: Analysis of error sources in computational geometry

Your payment authorization failed. Please check your information and try again, or try another payment method. Please contact you. The solution

OpenGL ES: Vertex shaders and slice shaders (OpenGL transition OpenGL ES)