Come faccio a creare e utilizzare una coda in Objective-C?

Question

Voglio usare una struttura di dati di coda nel mio programma Objective-C. In C ++ userei la coda STL. Qual è la struttura di dati equivalente in Objective-C? Come faccio a spingere / pop oggetti?

Answer 1

La versione di Ben è uno stack anziché una coda, quindi l'ho modificata un po ':

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

Importa semplicemente il file .h dove vuoi usare i tuoi nuovi metodi e chiamali come faresti con qualsiasi altro metodo NSMutableArray.

Buona fortuna e continua a programmare!

Answer 2

Non direi che l'utilizzo di NSMutableArray sia necessariamente la migliore soluzione, in particolare se si aggiungono metodi con categorie, a causa della fragilità che possono causare in caso di collisione dei nomi dei metodi. Per una coda quick-n-dirty, utilizzerei i metodi per aggiungere e rimuovere alla fine di un array mutabile. Tuttavia, se prevedi di riutilizzare la coda o se desideri che il tuo codice sia più leggibile ed evidente, una classe di coda dedicata è probabilmente ciò che desideri.

Il cacao non ne ha uno integrato, ma ci sono altre opzioni e non devi nemmeno scriverne uno da zero. Per una vera coda che aggiunge e rimuove solo dalle estremità, un array di buffer circolare è un'implementazione estremamente veloce. Scopri CHDataStructures.framework , una libreria / framework in Objective-C su cui sto lavorando . Ha una varietà di implementazioni di code, così come stack, deques, set ordinati, ecc. Ai tuoi scopi, CHCircularBufferQueue è significativamente più veloce (cioè dimostrabile con benchmark) e più leggibile (dichiaratamente soggettivo) rispetto all'utilizzo di un NSMutableArray.

Un grande vantaggio dell'utilizzo di una classe Objective-C nativa anziché di una classe STL C ++ è che si integra perfettamente con il codice Cocoa e funziona molto meglio con codifica / decodifica (serializzazione). Funziona perfettamente anche con la garbage collection e l'enumerazione rapida (entrambi presenti in 10.5+, ma solo quest'ultimo su iPhone) e non devi preoccuparti di cosa sia un oggetto Objective-C e di cosa sia un oggetto C ++.

Infine, sebbene NSMutableArray sia migliore di un array C standard quando si aggiunge e rimuove da entrambe le estremità, non è anche la soluzione più veloce per una coda. Per la maggior parte delle applicazioni è soddisfacente, ma se hai bisogno di velocità, un buffer circolare (o in alcuni casi un elenco collegato ottimizzato per mantenere calde le linee della cache) può facilmente troncare un NSMutableArray.

Answer 3

Per quanto ne so, Objective-C non fornisce una struttura di dati di coda. La soluzione migliore è creare un NSMutableArray , quindi utilizzare [array lastObject] , [array removeLastObject] per recuperare l'elemento e [array insertObject: o atIndex: 0] ...

Se lo fai molto, potresti voler creare una categoria Objective-C per estendere le funzionalità della classe NSMutableArray . Le categorie ti consentono di aggiungere dinamicamente funzioni alle classi esistenti (anche quelle per le quali non hai il sorgente) - potresti farne una coda come questa:

(NOTA: questo codice è in realtà per uno stack, non una coda. Vedere i commenti di seguito)

@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

Answer 4

Non esiste una vera classe di raccolte code, ma NSMutableArray può essere utilizzato per la stessa cosa in modo efficace. Puoi definire una categoria per aggiungere metodi pop / push come comodità se vuoi.

Answer 5

Sì, utilizzare NSMutableArray. NSMutableArray è in realtà implementato come albero 2-3 ; in genere non è necessario preoccuparsi delle caratteristiche prestazionali dell'aggiunta o della rimozione di oggetti da NSMutableArray in indici arbitrari.

Answer 6

re: Wolfcow - Ecco un'implementazione corretta del metodo di dequeue di Wolfcow

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

Answer 7

Le soluzioni che utilizzano una categoria su NSMutableArray non sono code vere, poiché NSMutableArray espone operazioni che sono un superset di code. Ad esempio, non dovresti essere autorizzato a rimuovere un elemento dal centro di una coda (poiché quelle soluzioni di categoria ti consentono ancora di farlo). È meglio incapsulare la funzionalità, un principio fondamentale nella progettazione orientata agli oggetti.

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

Answer 8

questa è la mia implementazione, spero che sia di aiuto.

È un po 'minimalista, quindi devi tenere traccia della testa salvando la nuova testa al pop e scartando la vecchia testa

@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

Answer 9

C'è qualche motivo particolare per cui non puoi semplicemente usare la coda STL? Objective C ++ è un superset di C ++ (basta usare .mm come estensione invece di .m per usare Objective C ++ invece di Objective C). Quindi è possibile utilizzare STL o qualsiasi altro codice C ++.

Un problema dell'uso della coda / vettore / elenco STL ecc. con gli oggetti Obiettivo C è che in genere non supportano la gestione della memoria di conservazione / rilascio / rilascio automatico. Questo può essere facilmente risolto con una classe di contenitori C ++ Smart Pointer che conserva il suo oggetto Objective C quando viene costruito e lo rilascia quando viene distrutto. A seconda di ciò che si sta inserendo nella coda STL, questo spesso non è necessario.

Answer 10

Usa NSMutableArray.