NSMutableArray背后的数据结构是什么？

Question

通常,"可变数组"类被实现为简单数组的包装器.当您在结尾添加元素时,包装器会分配更多内存.这是一种常见的数据结构,各种操作的性能是众所周知的.你得到O(1)元素访问,O(N)插入和删除,或O(1)(平均)插入和删除数组的末尾.但是NSMutableArray还有别的.例如,文档说[强调我的]:

注意:数组上的大多数操作都需要花费一些时间:访问元素,在任一端添加或删除元素,以及替换元素.将元素插入数组的中间需要线性时间.

那究竟是NSMutableArray什么？这是在某处记录的吗？

Answer 1

它是循环缓冲区的包装器.

这既没有记录也没有开源,但这篇博文显示了一个惊人的逆向工程工作NSMutableArray,我认为你会发现它非常有趣.

该NSMutableArray级集群由称为混凝土专用子类的支持__NSArrayM.

最大的发现是,NSMutableArray不是一个薄的包装器CFArray,正如人们可能合理地认为的那样:CFArray是开源的,它不使用循环缓冲器,而__NSArrayM确实如此.

阅读文章的评论,它似乎从iOS 4开始就是这种方式,而以前的SDK NSMutableArray实际上是在CFArray内部使用的,__NSArrayM甚至不存在.

直接从我上面提到的博客文章

数据结构

您可能已经猜到了,__NSArrayM使用循环缓冲区.这种数据结构非常简单,但比常规数组/缓冲区稍微复杂一些.当到达任何一端时,循环缓冲区的内容可以环绕.

循环缓冲区有一些非常酷的属性.值得注意的是,除非缓冲区已满,否则从任一端插入/删除不需要移动任何内存.

伪代码objectAtIndex:如下:

- (id)objectAtIndex:(NSUInteger)index {
    if (_used <= index) {
        goto ThrowException;
    }

    NSUInteger fetchOffset = _offset + index;
    NSUInteger realOffset = fetchOffset - (_size > fetchOffset ? 0 : _size);

    return _list[realOffset];

ThrowException:
    // exception throwing code
}

ivars定义为

• _used:数组包含的元素数
• _list:指向循环缓冲区的指针
• _size:缓冲区的大小
• _offset:缓冲区中数组的第一个元素的索引

同样,我对上述所有信息都不予理睬,因为它们直接来自Bartosz Ciechanowski撰写的这篇精彩博文.