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

问题描述

通常，mutable array类作为一个简单数组的包装来实现。当您添加一个元素超过结束时，包装器分配更多的内存。这是一种常见的数据结构，各种操作的性能是众所周知的。您可以获取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.

类集群由一个具体的私有子类支持， c> code> __ 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屋！