Wie erstelle und verwende ich eine Warteschlange in Objective-C?

107

Ich möchte eine Warteschlangendatenstruktur in meinem Objective-C-Programm verwenden. In C ++ würde ich die STL-Warteschlange verwenden. Was ist die äquivalente Datenstruktur in Objective-C? Wie kann ich Artikel pushen / platzen lassen?

MrDatabase
quelle

Antworten:

153

Bens Version ist ein Stapel anstelle einer Warteschlange, also habe ich sie ein wenig optimiert:

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

Importieren Sie einfach die .h-Datei, wo immer Sie Ihre neuen Methoden verwenden möchten, und rufen Sie sie wie alle anderen NSMutableArray-Methoden auf.

Viel Glück und weiter codieren!

Wolfskuh
quelle
1
Ich habe zu Beginn der Warteschlange eine auskommentierte Zeile für diejenigen hinzugefügt, die null zurückgeben möchten, anstatt eine Ausnahme auszulösen, wenn sie versuchen, aus einer leeren Warteschlange aus der Warteschlange zu entfernen. IMO ist nach dem Verhalten von NSMutableArray beim Auslösen einer Ausnahme konsistenter mit Cocoa. Schließlich können Sie -countvorher anrufen , um zu überprüfen, ob Objekte in die Warteschlange gestellt werden müssen. Es ist wirklich eine Frage der Präferenz.
Quinn Taylor
2
Ich habe diesen Code einem Github-Repo hinzugefügt. Fühlen Sie sich frei zu teilen oder lassen Sie mich wissen, wenn ich etwas falsch gemacht habe: github.com/esromneb/ios-queue-object Danke !!!
Portforwardpodcast
2
Vermisse ich etwas oder hat diese Implementierung eine O (n) -Komplexität bei der Warteschlange? Das ist schrecklich. Mit einer zirkulären Array-Implementierung wären Sie viel besser dran. Diese Implementierung mag funktionieren, aber die Idee der O (n) -Dequeue ist schmerzhaft.
ThatGuy
11
@Wolfcow, wenn Sie ein Objekt aus Index 0 entfernen, wird jedes Objekt im Array um eins nach unten verschoben. Um ein einzelnes Element zu entfernen, ist es daher O (n). Wahrscheinlich in Ordnung für kleine Warteschlangen, was in mobilen Anwendungen wahrscheinlich 99% der Zeit ist, aber dies wäre eine schreckliche Lösung für große Datenmengen in zeitkritischen Situationen. Wieder nicht, dass Sie das in den meisten objektiven C-Situationen finden würden.
ThatGuy
2
@ThatGuy Etwas spät, aber NSArray wird mit einem Ringpuffer implementiert, sodass die Laufzeit nicht Theta (N) ist.
Hhanesand
33

Ich würde nicht sagen, dass die Verwendung von NSMutableArray unbedingt die beste Lösung ist, insbesondere wenn Sie Methoden mit Kategorien hinzufügen, da diese bei der Kollision von Methodennamen fragil sein können. Für eine Quick-n-Dirty-Warteschlange würde ich die Methoden verwenden, um am Ende eines veränderlichen Arrays etwas hinzuzufügen und zu entfernen. Wenn Sie jedoch vorhaben, die Warteschlange wiederzuverwenden, oder wenn Sie möchten, dass Ihr Code besser lesbar und selbstverständlich ist, ist wahrscheinlich eine dedizierte Warteschlangenklasse genau das, was Sie möchten.

In Cocoa ist keine integriert, aber es gibt andere Optionen, und Sie müssen auch keine von Grund auf neu schreiben. Für eine echte Warteschlange, die nur an den Enden hinzugefügt und entfernt wird, ist ein kreisförmiges Pufferarray eine extrem schnelle Implementierung. Schauen Sie sich CHDataStructures.framework an , eine Bibliothek / ein Framework in Objective-C, an dem ich gearbeitet habe. Es verfügt über eine Vielzahl von Implementierungen von Warteschlangen sowie von Stapeln, Deques, sortierten Mengen usw. Für Ihre Zwecke CHCircularBufferQueue ist erheblich schneller (dh mit Benchmarks nachweisbar) und lesbarer (zugegebenermaßen subjektiv) als die Verwendung eines NSMutableArray.

Ein großer Vorteil der Verwendung einer nativen Objective-C-Klasse anstelle einer C ++ STL-Klasse besteht darin, dass sie sich nahtlos in Cocoa-Code integriert und beim Codieren / Decodieren (Serialisierung) viel besser funktioniert. Es funktioniert auch perfekt mit Garbage Collection und schneller Aufzählung (beide in 10.5+ vorhanden, aber nur letztere auf dem iPhone) und Sie müssen sich keine Gedanken darüber machen, was ein Objective-C-Objekt und was ein C ++ - Objekt ist.

Obwohl NSMutableArray beim Hinzufügen und Entfernen an beiden Enden besser als ein Standard-C-Array ist, ist es auch nicht die schnellste Lösung für eine Warteschlange. Für die meisten Anwendungen ist es zufriedenstellend, aber wenn Sie Geschwindigkeit benötigen, kann ein zirkulärer Puffer (oder in einigen Fällen eine verknüpfte Liste, die optimiert ist, um die Cache-Zeilen heiß zu halten) ein NSMutableArray leicht ausschalten.

Quinn Taylor
quelle
2
Ich bin
Alle Links sind defekt - woher bekomme ich diesen Rahmen? Ich habe viele gute Sachen darüber gelesen, kann aber den tatsächlichen Code nicht finden!
Amok
Das Framework klingt vielversprechend, aber die Links zu SVN sind immer noch unterbrochen. Gibt es eine Chance, den Code irgendwo zu bekommen? EDIT: Habe es von mac.softpedia.com/progDownload/… bekommen, aber ich kann nicht sehen, ob dies die aktuelle Version ist
Kay
Dave DeLongs Git- Repo-Klon scheint heutzutage das erste Repo zu sein.
Regexident
29

Soweit ich weiß, bietet Objective-C keine Warteschlangendatenstruktur. Ihre beste Wette ist es, einen zu erstellen NSMutableArrayund dann zu verwenden [array lastObject], [array removeLastObject]um den Gegenstand zu holen, und [array insertObject:o atIndex:0]...

Wenn Sie dies häufig tun, möchten Sie möglicherweise eine Objective-C-Kategorie erstellen, um die Funktionalität der NSMutableArrayKlasse zu erweitern. Mit Kategorien können Sie vorhandenen Klassen dynamisch Funktionen hinzufügen (auch solchen, für die Sie keine Quelle haben). Sie können eine Warteschlange wie folgt erstellen:

(HINWEIS: Dieser Code ist eigentlich für einen Stapel, nicht für eine Warteschlange. Siehe Kommentare unten)

@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
Ben Gotow
quelle
7
Ist Ihnen bewusst, dass Sie hier einen Stapel implementiert haben, keine Warteschlange?
Jim Puls
Ahh - Entschuldigung! - siehe Wolfcows Modifikationen unten.
Ben Gotow
Ich würde zustimmen, wenn Sie "beste Wette" durch "einfachste Option" ersetzen. :-) Datenstruktur-Puristen und Performance-Obsessoren würden eine echte Warteschlange bevorzugen, aber ein NSMutableArray kann leicht für eine Warteschlange stehen.
Quinn Taylor
3
+1 zu ben, weil ich eine
Stapellösung
Ich kann nur an den Schmerz denken. Wenn Sie ein Objekt am Anfang eines Arrays einfügen, müssen Sie jedes Element bei jedem Einfügen über 1 Leerzeichen kopieren. In diesem Fall ist eine verknüpfte Liste viel leistungsfähiger.
TheM00s3
8

Es gibt keine echte Warteschlangensammlungsklasse, aber NSMutableArray kann effektiv für dasselbe verwendet werden. Sie können eine Kategorie definieren , um Pop / Push-Methoden hinzuzufügen, wenn Sie möchten.

Marc Charbonneau
quelle
Es stimmt, ein NSMutableArray stellt eine ziemlich anständige Warteschlange dar, obwohl das Entfernen von vorne nichts ist, was eine Array-Struktur auszeichnet. Trotzdem ist die Leistung bei kleinen Warteschlangen ohnehin kein großes Problem. Ein Freund von mir hat vor einiger Zeit über dieses Thema gebloggt
Quinn Taylor
7

Ja, verwenden Sie NSMutableArray. NSMutableArray ist tatsächlich als 2-3-Baum implementiert . In der Regel müssen Sie sich nicht mit den Leistungsmerkmalen des Hinzufügens oder Entfernens von Objekten zu NSMutableArray an beliebigen Indizes befassen.

die Kühlschrank Eule
quelle
1
NSArray (und NSMutableArray als Erweiterung) ist ein Klassencluster, dh es verfügt über mehrere private Implementierungen, die hinter den Kulissen austauschbar verwendet werden können. Diejenige, die Sie normalerweise erhalten, hängt von der Anzahl der Elemente ab. Außerdem kann Apple die Details einer bestimmten Implementierung jederzeit ändern. Sie haben jedoch Recht, dass es normalerweise viel flexibler ist als ein Standardarray.
Quinn Taylor
5

re: Wolfcow - Hier ist eine korrigierte Implementierung der Dequeue-Methode von Wolfcow

- (id)dequeue {
    if ([self count] == 0) {
        return nil;
    }
    id queueObject = [[[self objectAtIndex:0] retain] autorelease];
    [self removeObjectAtIndex:0];
    return queueObject;
}
DougW
quelle
4

Die Lösungen, für die eine Kategorie verwendet wird, NSMutableArraysind keine echten Warteschlangen, daNSMutableArray Operationen verfügbar gemacht werden, die eine Obermenge von Warteschlangen darstellen. Beispielsweise sollte es Ihnen nicht gestattet sein, ein Element aus der Mitte einer Warteschlange zu entfernen (wie dies bei diesen Kategorielösungen weiterhin möglich ist). Es ist am besten, die Funktionalität zu kapseln, ein Hauptprinzip des objektorientierten Designs.

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
Pwner
quelle
Man könnte argumentieren, dass mit bestimmten Techniken (dh KVC) das interne Speicherarray direkt aufgerufen und manipuliert werden kann, aber viel besser als die Verwendung einer Kategorie.
Vikingosegundo
3

Dies ist meine Implementierung, hoffe es hilft.

Ist irgendwie minimalistisch, also müssen Sie die Spur des Kopfes behalten, indem Sie den neuen Kopf beim Pop speichern und den alten Kopf wegwerfen

@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
Moxor
quelle
2

Gibt es einen bestimmten Grund, warum Sie die STL-Warteschlange nicht einfach verwenden können? Objective C ++ ist eine Obermenge von C ++ (verwenden Sie einfach .mm als Erweiterung anstelle von .m, um Objective C ++ anstelle von Objective C zu verwenden). Dann können Sie die STL oder einen anderen C ++ - Code verwenden.

Ein Problem bei der Verwendung der STL-Warteschlange / des Vektors / der Liste usw. mit Objective C-Objekten besteht darin, dass sie normalerweise die Speicherverwaltung für Aufbewahrung / Freigabe / Autorelease nicht unterstützen. Dies lässt sich leicht mit einer C ++ Smart Pointer-Containerklasse umgehen, die ihr Objective C-Objekt beim Erstellen beibehält und es bei Zerstörung freigibt. Je nachdem, was Sie in die STL-Warteschlange stellen, ist dies häufig nicht erforderlich.

Peter N Lewis
quelle
1
Das scheint keine gute Idee zu sein ... nur weil du etwas tun kannst , heißt das nicht, dass du es tun sollst. Das gesamte STL- und C ++ - Ökosystem nur für eine Warteschlangenklasse zu nutzen, ist definitiv übertrieben.
Extropic-Motor
3
Seitdem ist dies eine viel bessere Idee geworden. Objective C ++ / ARC bedeutet, dass Sie STL-Container mit Objective C-Objektzeigern verwenden können und alles funktioniert. ARC übernimmt die Speicherverwaltung automatisch für Sie in C ++ - Strukturen. Ich würde auch allgemein argumentieren, dass C ++, da es ein viel besseres C ist, Objective-C ++ im Allgemeinen zu einer besseren Wahl macht als einfaches Objective C (z. B. Enum-Klasse). Und ich bezweifle sehr, dass das Hinzufügen von STL / C ++ einen spürbaren Einfluss auf die Größe einer realen App hat.
Peter N Lewis
1

Verwenden Sie NSMutableArray.

Nuoji
quelle