objective-c - NSSet の実装

Question

この質問は単なる好奇心からですが、NSSet はどのように実装されているのでしょうか? その背後にあるデータ構造と、要素を追加および削除するためのアクセス時間は? 推測する必要がある場合、それはある種のハッシュテーブル/辞書データ構造であると言えますが、その場合、なぜ NSSet と NSMutableSet を区別するのでしょうか?

Answer 1

Bavarous がコメントで指摘したように、Apple の実際の CoreFoundation ソースは公開されており、閲覧することもできます。NSSetは の上に実装されCFSet、そのコードは ( のコードと同様にCFDictionary) ハッシュ テーブル テンプレートから生成されCFBasicHash、作業を行うために使用されます。

可変性と不変性の違いは、構造体 ( の 91 行目CFBasicHash.h)のフラグの問題であるように思われCFBasicHashAddValueます。可変性の簡単なチェックがあります。ただし、2 つの間のコピー/保持動作については、Cobbal が正しいようです (私はまだそこまで読んでいません)。

前:実装の詳細について疑問に思っているときに、 GNUstep
のソース を熟読することは、時折興味深いことであり、教育的であると思います。もちろん、Apple が行った方法で実装されることはまったく保証されていませんが、場合によっては役立つことがあります。Foundation のバージョン: http://gnu.ethz.ch/debian/gnustep/gnustep-base-1.20.0/Headers/Foundation/ (これが最新バージョンであることを願っています。そうでない場合は、誰かが私を修正してください。)

Answer 2

あなたの質問の後半に答えるために:変更不可能なバージョンを使用する利点の 1 つは、retain を呼び出すだけの非常に高速なコピー メソッドを使用できることです。

Answer 3

このリンクは、あなたの質問に対する興味深い回答だと思います。Apple のデータ構造 ( NSArray、NSSet、NSDictionaryなど) は、単純な「標準的な方法」では実装されていません。ほとんどの場合、これらは他のセットと同じように機能しますが、全体として、最高のパフォーマンスを得るために自動的に最適化されます。ですから、実際には、言うのはかなり難しいです。Apple はCFArray.h(s に相当するNSArray) の配列の効率に関するドキュメントを提供していますが、セットの効率に関するそのようなドキュメントは提供していません/System/Library/Frameworks/CoreFoundation.framework/Headers/。

さらに、NSStringと、 、 およびと(とりわけ)との間に区別があるのと同様に、セットとその変更可能な対応物には区別が必要です。データ構造と文字列 (およびその他のいくつかのクラス) については、Apple は一般性を保持するためにクラスの「読み取り専用」バージョンと、操作用の標準の「変更可能な」バージョンを提供しています。これは単に Apple の標準的な慣行です。NSMutableStringNSArrayNSMutableArrayNSDictionaryNSMutableDictionary