objective c official Como faço e uso uma fila em Objective-C?



objective c c sharp (8)

Eu não diria que usar o NSMutableArray é necessariamente a melhor solução, particularmente se você estiver adicionando métodos com categorias, devido à fragilidade que eles podem causar se os nomes dos métodos colidirem. Para uma fila rápida, eu usaria os métodos para adicionar e remover no final de uma matriz mutável. No entanto, se você planeja reutilizar a fila ou se quiser que seu código seja mais legível e óbvio, uma classe de fila dedicada provavelmente é o que você deseja.

Cacau não tem um construído em, mas há outras opções, e você não tem que escrever um a partir do zero também. Para uma fila real que apenas adiciona e remove das extremidades, uma matriz de buffer circular é uma implementação extremamente rápida. Confira CHDataStructures.framework , uma biblioteca / estrutura no Objective-C em que estou trabalhando. Ele tem uma variedade de implementações de filas, bem como pilhas, deques, conjuntos de classificação, etc. Para seus propósitos, CHCircularBufferQueue é significativamente mais rápido (ou seja, provável com benchmarks) e mais legível (reconhecidamente subjetivo) do que usar um NSMutableArray.

Uma grande vantagem de usar uma classe Objective-C nativa em vez de uma classe STL C ++ é que ela se integra perfeitamente ao código Cocoa e funciona muito melhor com codificação / decodificação (serialização). Ele também funciona perfeitamente com coleta de lixo e enumeração rápida (ambos presentes em 10.5+, mas apenas o último no iPhone) e você não precisa se preocupar com o que é um objeto Objective-C e o que é um objeto C ++.

Por fim, embora o NSMutableArray seja melhor que uma matriz C padrão ao adicionar e remover de uma das extremidades, ele também não é a solução mais rápida para uma fila. Para a maioria das aplicações é satisfatório, mas se você precisar de velocidade, um buffer circular (ou, em alguns casos, uma lista encadeada otimizada para manter as linhas de cache quentes) pode facilmente atrapalhar um NSMutableArray.

Eu quero usar uma estrutura de dados de fila no meu programa Objective-C. Em C ++ eu usaria a fila STL. Qual é a estrutura de dados equivalente no Objective-C? Como faço para empurrar / pop itens?


Answer #1

Sim, use NSMutableArray. NSMutableArray é realmente implemented como árvore 2-3; você normalmente não precisa se preocupar com as características de desempenho de adicionar ou remover objetos do NSMutableArray em índices arbitrários.


Answer #2

As soluções que usam uma categoria no NSMutableArray não são filas verdadeiras, porque o NSMutableArray expõe operações que são um superconjunto de filas. Por exemplo, você não deve ter permissão para remover um item do meio de uma fila (como essas soluções de categoria ainda permitem). É melhor encapsular a funcionalidade, um princípio importante do design orientado a objetos.

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 #3

Existe alguma razão específica pela qual você não pode simplesmente usar a fila STL? Objective C ++ é um superconjunto de C ++ (apenas use .mm como a extensão em vez de .m para usar Objective C ++ em vez de Objective C). Então você pode usar o STL ou qualquer outro código C ++.

Uma questão de usar a fila / vetor / lista STL, etc, com objetos Objective C é que eles normalmente não suportam o gerenciamento de memória de retenção / liberação / autorelease. Isso é facilmente contornado com uma classe de contêiner C ++ Smart Pointer que retém seu objeto Objective C quando construído e o libera quando destruído. Dependendo do que você está colocando na fila STL, isso geralmente não é necessário.


Answer #4

esta é minha implementação, espero que ajude.

É meio minimalista, então você deve manter o controle da cabeça salvando a nova cabeça no pop e descartando a cabeça antiga

@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 #5

Use NSMutableArray.


Answer #6

A versão de Ben é uma pilha em vez de uma fila, então eu ajustei um pouco:

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

Basta importar o arquivo .h para onde você quiser usar seus novos métodos e chamá-los como faria com qualquer outro método NSMutableArray.

Boa sorte e continue codificando!


Answer #7

Não existe uma classe real de coleções de filas, mas o NSMutableArray pode ser usado efetivamente para a mesma coisa. Você pode definir uma category para adicionar métodos pop / push como uma conveniência, se desejar.





queue