Objective-C でキューを作成して使用するにはどうすればよいですか?
https://stackoverflow.com/questions/817469
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Objective-C プログラムでキュー データ構造を使用したいと考えています。C++ では STL キューを使用します。Objective-C の同等のデータ構造は何ですか?アイテムをプッシュ/ポップするにはどうすればよいですか?
解決
Benのバージョンはキューではなくスタックなので、少し調整しました：
NSMutableArray + QueueAdditions.h
@interface NSMutableArray (QueueAdditions)
- (id) dequeue;
- (void) enqueue:(id)obj;
@end
NSMutableArray + QueueAdditions.m
@implementation NSMutableArray (QueueAdditions)
// Queues are first-in-first-out, so we remove objects from the head
- (id) dequeue {
// if ([self count] == 0) return nil; // to avoid raising exception (Quinn)
id headObject = [self objectAtIndex:0];
if (headObject != nil) {
[[headObject retain] autorelease]; // so it isn't dealloc'ed on remove
[self removeObjectAtIndex:0];
}
return headObject;
}
// Add to the tail of the queue (no one likes it when people cut in line!)
- (void) enqueue:(id)anObject {
[self addObject:anObject];
//this method automatically adds to the end of the array
}
@end
新しいメソッドを使用する場所に.hファイルをインポートし、他のNSMutableArrayメソッドと同じように呼び出します。
頑張ってコーディングしてください！
他のヒント
NSMutableArrayを使用することが必ずしも最良のソリューションであるとは言いません。特に、メソッド名が衝突すると脆弱性が生じる可能性があるため、カテゴリを使用してメソッドを追加する場合です。 quick-n-dirtyキューの場合、メソッドを使用して、可変配列の最後に追加および削除します。ただし、キューを再利用する場合、またはコードをより読みやすく、自明にする場合は、おそらく専用のキュークラスが必要です。
Cocoaには組み込みのものはありませんが、他のオプションがあり、最初から作成する必要もありません。両端のみを追加および削除する真のキューの場合、循環バッファー配列は非常に高速な実装です。私が取り組んできたObjective-Cのライブラリ/フレームワークである CHDataStructures.framework をチェックしてください。 。スタック、デキュー、ソートされたセットなど、キューのさまざまな実装があります。目的のために、 CHCircularBufferQueue は、NSMutableArrayを使用するよりも大幅に高速（つまり、ベンチマークで証明可能）で、より読みやすい（明らかに主観的）。
C ++ STLクラスの代わりにネイティブのObjective-Cクラスを使用する大きな利点の1つは、Cocoaコードとシームレスに統合し、エンコード/デコード（シリアル化）との連携がはるかに優れていることです。また、ガベージコレクションと高速列挙（両方とも10.5以降に存在しますが、iPhoneには後者のみ）でも完全に機能し、Objective-CオブジェクトとC ++オブジェクトとは何であるかを心配する必要はありません。
最後に、NSMutableArrayは両端の追加と削除の際に標準のC配列よりも優れていますが、キューの最速の解決策でもありません。ほとんどのアプリケーションでは問題ありませんが、速度が必要な場合は、循環バッファー（または場合によってはキャッシュラインをホットに保つために最適化されたリンクリスト）でNSMutableArrayを簡単に切り捨てることができます。
私が知る限り、Objective-CはQueueデータ構造を提供していません。最善の策は、 NSMutableArray を作成し、 [array lastObject] 、 [array removeLastObject] を使用してアイテムを取得し、 [array insertObject：o atIndex：0] ...
これを頻繁に行う場合は、Objective-Cカテゴリを作成して、 NSMutableArray クラスの機能を拡張することができます。カテゴリを使用すると、既存のクラス（ソースを持たないクラスも含む）に動的に関数を追加できます。次のようなキューを作成できます。
（注：このコードは実際にはキューではなくスタック用です。以下のコメントを参照してください）
@interface NSMutableArray (QueueAdditions)
- (id)pop;
- (void)push:(id)obj;
@end
@implementation NSMutableArray (QueueAdditions)
- (id)pop
{
// nil if [self count] == 0
id lastObject = [[[self lastObject] retain] autorelease];
if (lastObject)
[self removeLastObject];
return lastObject;
}
- (void)push:(id)obj
{
[self addObject: obj];
}
@end
実際のキューコレクションクラスはありませんが、NSMutableArrayを使用して事実上同じことを行うことができます。 カテゴリを定義して、pop / pushメソッドを便利に追加できます。必要に応じて。
はい、NSMutableArrayを使用します。 NSMutableArrayは、実際には 2〜3ツリーとして実装されています;通常、任意のインデックスでNSMutableArrayにオブジェクトを追加または削除するパフォーマンス特性を気にする必要はありません。
re：Wolfcow-以下は、Wolfcowのdequeueメソッドの修正された実装です
- (id)dequeue {
if ([self count] == 0) {
return nil;
}
id queueObject = [[[self objectAtIndex:0] retain] autorelease];
[self removeObjectAtIndex:0];
return queueObject;
}
カテゴリを使用するソリューション NSMutableArray は真のキューではありません。 NSMutableArray キューのスーパーセットであるオペレーションを公開します。たとえば、キューの途中から項目を削除することは許可されるべきではありません (これらのカテゴリ ソリューションではまだ許可されていますが)。オブジェクト指向設計の主要原則である機能をカプセル化することが最善です。
StdQueue.h
#import <Foundation/Foundation.h>
@interface StdQueue : NSObject
@property(nonatomic, readonly) BOOL empty;
@property(nonatomic, readonly) NSUInteger size;
@property(nonatomic, readonly) id front;
@property(nonatomic, readonly) id back;
- (void)enqueue:(id)object;
- (id)dequeue;
@end
StdQueue.m
#import "StdQueue.h"
@interface StdQueue ()
@property(nonatomic, strong) NSMutableArray* storage;
@end
@implementation StdQueue
#pragma mark NSObject
- (id)init
{
if (self = [super init]) {
_storage = [NSMutableArray array];
}
return self;
}
#pragma mark StdQueue
- (BOOL)empty
{
return self.storage.count == 0;
}
- (NSUInteger)size
{
return self.storage.count;
}
- (id)front
{
return self.storage.firstObject;
}
- (id)back
{
return self.storage.lastObject;
}
- (void)enqueue:(id)object
{
[self.storage addObject:object];
}
- (id)dequeue
{
id firstObject = nil;
if (!self.empty) {
firstObject = self.storage.firstObject;
[self.storage removeObjectAtIndex:0];
}
return firstObject;
}
@end
これは私の実装です。役に立てば幸いです。
一種のミニマリストなので、ポップ時に新しいヘッドを保存し、古いヘッドを破棄することで、ヘッドの追跡を維持する必要があります
@interface Queue : NSObject {
id _data;
Queue *tail;
}
-(id) initWithData:(id) data;
-(id) getData;
-(Queue*) pop;
-(void) push:(id) data;
@end
#import "Queue.h"
@implementation Queue
-(id) initWithData:(id) data {
if (self=[super init]) {
_data = data;
[_data retain];
}
return self;
}
-(id) getData {
return _data;
}
-(Queue*) pop {
return tail;
}
-(void) push:(id) data{
if (tail) {
[tail push:data];
} else {
tail = [[Queue alloc]initWithData:data];
}
}
-(void) dealloc {
if (_data) {
[_data release];
}
[super release];
}
@end
STLキューを使用できない理由はありますか？ Objective C ++はC ++のスーパーセットです（Objective Cの代わりにObjective C ++を使用するには、.mの代わりに.mmを拡張子として使用します）。その後、STLまたはその他のC ++コードを使用できます。
Objective CオブジェクトでSTLキュー/ベクター/リストなどを使用する場合の問題の1つは、通常、保持/解放/自動解放メモリ管理をサポートしないことです。これは、構築時にObjective Cオブジェクトを保持し、破棄時に解放するC ++ Smart Pointerコンテナクラスで簡単に回避できます。 STLキューに何を入れているかにもよりますが、多くの場合これは必要ありません。
NSMutableArrayを使用します。
