blocks|key|2749619|text|它是circular+buffer的包装器。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2749620|这既没有文档记录，也没有开源，但是this+blog+post在NSMutableArray上展示了一个令人惊叹的逆向工程工作，我认为您会发现这非常有趣。|style|CODE|2749621|NSMutableArray类集群由一个名为__NSArrayM的具体私有子类支持。|2749622|最大的发现是，NSMutableArray不是CFArray的薄薄包装器，正如人们可能合理地认为的那样：CFArray是开源的，并且它不使用循环缓冲区，而__NSArrayM使用循环缓冲区。|2749623|通读这篇文章的评论，似乎从iOS+4开始就是这样的，而在以前的SDK中，NSMutableArray实际上在内部使用了CFArray，而__NSArrayM甚至都不在那里。|2749624|直接从我上面提到的博客文章中|2749625|2749626|数据结构|blockquote|2749627|2749628|正如您可能已经猜到的那样，__NSArrayM使用循环缓冲区。这种数据结构非常简单，但比常规的数组/缓冲区稍微复杂一点。当到达任何一端时，循环缓冲区的内容都可以回绕。|2749629|循环缓冲区有一些非常酷的属性。值得注意的是，除非缓冲区已满，否则从两端插入/删除都不需要移动任何内存。|2749630|2749631|objectAtIndex:的伪代码如下：|2749632|-+(id)objectAtIndex:(NSUInteger)index+{
++++if+(_used+<=+index)+{
++++++++goto+ThrowException;
++++}

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

++++return+_list[realOffset];

ThrowException:
++++//+exception+throwing+code
}|code-block|syntax|javascript|2749633|其中ivars被定义为|2749634|2749635|_used：数组的元素数holds|unordered-list-item|2749636|_list：指向循环缓冲区的指针buffer|2749637|_size：缓冲区的大小buffer|2749638|_offset：数组的第一个元素的索引|2749639|2749640|2749641|再说一次，我不会把上面的所有信息都归功于任何人，因为它们直接来自这个amazing+blog+post+by+Bartosz+Ciechanowski。|2749642|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Circular_buffer|1|http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/|2^0|2|F|0|0|W|E|H|E|1|0|0|E|M|A|0|7|E|N|7|1G|7|25|A|0|10|E|1N|7|1W|A|0|0|0|0|0|D|A|0|0|0|0|E|0|0|0|0|0|5|0|0|5|0|0|5|0|0|7|0|0|0|Y|15|2|0^^$0|@$1|2|3|4|5|6|7|1X|8|@]|9|@$A|1Y|B|1Z|1|20]]|C|$]]|$1|D|3|E|5|6|7|21|8|@$A|22|B|23|F|G]]|9|@$A|24|B|25|1|26]]|C|$]]|$1|H|3|I|5|6|7|27|8|@$A|28|B|29|F|G]|$A|2A|B|2B|F|G]]|9|@]|C|$]]|$1|J|3|K|5|6|7|2C|8|@$A|2D|B|2E|F|G]|$A|2F|B|2G|F|G]|$A|2H|B|2I|F|G]|$A|2J|B|2K|F|G]]|9|@]|C|$]]|$1|L|3|M|5|6|7|2L|8|@$A|2M|B|2N|F|G]|$A|2O|B|2P|F|G]|$A|2Q|B|2R|F|G]]|9|@]|C|$]]|$1|N|3|O|5|6|7|2S|8|@]|9|@]|C|$]]|$1|P|3|-4|5|6|7|2T|8|@]|9|@]|C|$]]|$1|Q|3|R|5|S|7|2U|8|@]|9|@]|C|$]]|$1|T|3|-4|5|6|7|2V|8|@]|9|@]|C|$]]|$1|U|3|V|5|6|7|2W|8|@$A|2X|B|2Y|F|G]]|9|@]|C|$]]|$1|W|3|X|5|6|7|2Z|8|@]|9|@]|C|$]]|$1|Y|3|-4|5|6|7|30|8|@]|9|@]|C|$]]|$1|Z|3|10|5|6|7|31|8|@$A|32|B|33|F|G]]|9|@]|C|$]]|$1|11|3|12|5|13|7|34|8|@]|9|@]|C|$14|15]]|$1|16|3|17|5|6|7|35|8|@]|9|@]|C|$]]|$1|18|3|-4|5|6|7|36|8|@]|9|@]|C|$]]|$1|19|3|1A|5|1B|7|37|8|@$A|38|B|39|F|G]]|9|@]|C|$]]|$1|1C|3|1D|5|1B|7|3A|8|@$A|3B|B|3C|F|G]]|9|@]|C|$]]|$1|1E|3|1F|5|1B|7|3D|8|@$A|3E|B|3F|F|G]]|9|@]|C|$]]|$1|1G|3|1H|5|1B|7|3G|8|@$A|3H|B|3I|F|G]]|9|@]|C|$]]|$1|1I|3|-4|5|6|7|3J|8|@]|9|@]|C|$]]|$1|1J|3|-4|5|6|7|3K|8|@]|9|@]|C|$]]|$1|1K|3|1L|5|6|7|3L|8|@]|9|@$A|3M|B|3N|1|3O]]|C|$]]|$1|1M|3|-4|5|6|7|3P|8|@]|9|@]|C|$]]]|1N|$1O|$5|1P|1Q|1R|C|$1S|1T]]|1U|$5|1P|1Q|1R|C|$1S|1V]]|1W|$5|1P|1Q|1R|C|$1S|1V]]]]

It's a wrapper around a <a href="http://en.wikipedia.org/wiki/Circular_buffer" rel="noreferrer">circular buffer</a>.

This is neither documented nor open-sourced, but <a href="http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/" rel="noreferrer">this blog post</a> shows an amazing reverse-engineer job over <code>NSMutableArray</code>, which I think you'll find very interesting.

The <code>NSMutableArray</code> class cluster is backed by a concrete private subclass called <code>__NSArrayM</code>.

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

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

Straight from the blog post I mentioned above

<blockquote>
 <h1>Data Structure</h1>
 
 As you might have guessed, <code>__NSArrayM</code> 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.
</blockquote>

The pseudo-code for <code>objectAtIndex:</code> goes as follows:

<pre><code>- (id)objectAtIndex:(NSUInteger)index {
 if (_used &lt;= index) {
 goto ThrowException;
 }

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

 return _list[realOffset];

ThrowException:
 // exception throwing code
}
</code></pre>

where the ivars are defined as

<ul>
<li><code>_used</code>: the number of elements the array holds</li>
<li><code>_list</code>: the pointer to the circular buffer</li>
<li><code>_size</code>: the size of the buffer</li>
<li><code>_offset</code>: the index of first element of array in the buffer</li>
</ul>

<hr>

Again, I don't take any credit for all the information above, as they come straight from this <a href="http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/" rel="noreferrer">amazing blog post by Bartosz Ciechanowski</a>.

blocks|key|161355|text|做了一些测量:从一个空数组开始，添加@"Hello“100,000次，然后删除它100,000次。不同的模式:在结尾处、开始处、中间添加/删除，接近开始处(可能时在索引20处)，接近结束处(可能时远离结束处20个索引)，以及在接近开始处和结束处交替添加/删除。以下是100,000个对象的时间(在Core+2+Duo上测量)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|161356|Adding+objects+=+0.006593+seconds
Removing+objects+at+the+end+=+0.004674+seconds
Adding+objects+at+the+start+=+0.003577+seconds
Removing+objects+at+the+start+=+0.002936+seconds
Adding+objects+in+the+middle+=+3.057944+seconds
Removing+objects+in+the+middle+=+3.059942+seconds
Adding+objects+close+to+the+start+=+0.010035+seconds
Removing+objects+close+to+the+start+=+0.007599+seconds
Adding+objects+close+to+the+end+=+0.008005+seconds
Removing+objects+close+to+the+end+=+0.008735+seconds
Adding+objects+close+to+the+start+/+end+=+0.008795+seconds
Removing+objects+close+to+the+start+/+end+=+0.008853+seconds|code-block|syntax|javascript|161357|因此，每次添加/删除的时间与数组开头或结尾的距离成正比，以较近者为准。在中间添加东西是很昂贵的。您不必完全在结尾工作；删除靠近开头/结尾的元素也是非常便宜的。|161358|建议的循环列表实现忽略了一个重要的细节:在最后一个和第一个数组元素的位置之间有一个可变大小的间隙。当添加/删除数组元素时，该间隙的大小会发生变化。当间隙消失并添加更多对象时，需要分配更多的内存，并且需要移动对象指针；当间隙变得太大时，可以缩小数组，并且需要移动对象指针。一个简单的更改(允许间隙位于任何位置，而不仅仅是最后一个元素和第一个元素之间)将允许在任何位置进行快速更改(只要是相同的位置)，并将使“精简”阵列的操作更快。|161359|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Did some measurements: Starting with an empty array, added @"Hello" 100,000 times, then removed it 100,000 times. Different patterns: Adding/removing at the end, at the start, in the middle, close to the start (at index 20 when possible), close to the end (20 indexes away from the end when possible), and one where I alternated between close to the start and the end. Here's the times for 100,000 objects (measured on Core 2 Duo): 

<pre><code>Adding objects = 0.006593 seconds
Removing objects at the end = 0.004674 seconds
Adding objects at the start = 0.003577 seconds
Removing objects at the start = 0.002936 seconds
Adding objects in the middle = 3.057944 seconds
Removing objects in the middle = 3.059942 seconds
Adding objects close to the start = 0.010035 seconds
Removing objects close to the start = 0.007599 seconds
Adding objects close to the end = 0.008005 seconds
Removing objects close to the end = 0.008735 seconds
Adding objects close to the start / end = 0.008795 seconds
Removing objects close to the start / end = 0.008853 seconds
</code></pre>

So the time for each add / remove is proportional the distance to the beginning or end of the array, whichever is closer. Adding things in the middle is expensive. You don't have to work exactly at the end; removing elements close to the start / end is also quite cheap. 

The suggested implementation as a circular list omits an important detail: There is a gap of variable size between the location of the last and the first array element. As array elements are added / removed, the size of that gap changes. More memory needs to be allocated and object pointers need to be moved when the gap disappears and more objects are added; the array can be shrunk and object pointers need to be moved when the gap becomes too large. A simple change (allowing the gap to be located at any location, not just between last and first element) would allow changes at any location to be fast (as long as it is the same location), and would make operations that "thin out" the array faster.

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 <code>NSMutableArray</code> is something else. For example the <a href="https://developer.apple.com/library/mac/documentation/Cocoa/Conceptual/Collections/Articles/Arrays.html" rel="noreferrer">docs</a> say [emphasis mine]:

<blockquote>
 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.
</blockquote>

So, what exactly is <code>NSMutableArray</code>? Is this documented somewhere?

What is the data structure behind NSMutableArray?

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

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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