NSMutableArray 背后的数据结构是什么? [英] What is the data structure behind NSMutableArray?

问题描述

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

Usually, a "mutable array" class is implemented as a wrapper around a simple array. The wrapper allocates more memory when you add an element past the end. This is a common data structure and the performance of the various operations is well known. You get O(1) element access, O(N) insert and remove, or O(1) (on average) insert and remove at the end of the array. But NSMutableArray is something else. For example the docs say [emphasis mine]:

注意:对数组的大多数操作需要恒定时间:访问一个元素，在任一端添加或删除一个元素，并替换一个元素.将元素插入数组中间需要线性时间.

Note: Most operations on an array take constant time: accessing an element, adding or removing an element at either end, and replacing an element. Inserting an element into the middle of an array takes linear time.

那么，NSMutableArray 到底是什么?这是在某处记录的吗?

So, what exactly is NSMutableArray? Is this documented somewhere?

推荐答案

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

这既没有记录也没有开源，但是这篇博文 展示了对 NSMutableArray 的惊人逆向工程工作，我认为您会发现它非常有趣.

This is neither documented nor open-sourced, but this blog post shows an amazing reverse-engineer job over NSMutableArray, which I think you'll find very interesting.

NSMutableArray 类簇由一个名为 __NSArrayM 的具体私有子类支持.

The NSMutableArray class cluster is backed by a concrete private subclass called __NSArrayM.

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

The greatest discovery is that NSMutableArray is not a thin wrapper around a CFArray, as one may reasonably think: CFArray is open-sourced and it doesn't use a circular buffer, whereas __NSArrayM does.

阅读文章的评论，似乎从iOS 4开始就这样了，而在以前的SDK中NSMutableArray实际上在内部使用了CFArray和__NSArrayM 甚至不存在.

Reading through the comments of the article, it appears that it started to be this way since iOS 4, whereas in previous SDKs NSMutableArray actually used CFArray internally and __NSArrayM wasn't even there.

直接来自我上面提到的博文

Straight from the blog post I mentioned above

你可能已经猜到了，__NSArrayM 使用了循环缓冲区.这个数据结构极其简单，但是有点多比常规数组/缓冲区复杂.通函内容到达任一端时缓冲区可以环绕.

Data Structure

As you might have guessed, __NSArrayM makes use of circular buffer. This data structure is extremely simple, but a little bit more sophisticated than regular array/buffer. The contents of circular buffer can wrap around when either end is reached.

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

Circular buffer has some very cool properties. Notably, unless the buffer is full, insertion/deletion from either end doesn’t require any memory to be moved.

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 定义为

where the ivars are defined as

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

• _used: the number of elements the array holds
• _list: the pointer to the circular buffer
• _size: the size of the buffer
• _offset: the index of first element of array in the buffer

再说一次，我对上述所有信息不以为然，因为它们直接来自此Bartosz Ciechanowski 的精彩博文.

Again, I don't take any credit for all the information above, as they come straight from this amazing blog post by Bartosz Ciechanowski.

这篇关于NSMutableArray 背后的数据结构是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！