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

107

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

MrDatabase
fonte

Respostas:

153

A versão de Ben é uma pilha em vez de uma fila, então 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 quiser usar seus novos métodos e chamá-los como faria com qualquer outro método NSMutableArray.

Boa sorte e continue codificando!

Wolfcow
fonte
1
Eu adicionei uma linha comentada no início do desenfileiramento para aqueles que desejam retornar nil em vez de levantar uma exceção ao tentar desenfileirar de uma fila vazia. IMO, seguindo o comportamento NSMutableArray de levantar uma exceção é mais consistente com Cocoa. Afinal, você pode ligar com -countantecedência para verificar se há algum objeto para retirar da fila. É uma questão de preferência, na verdade.
Quinn Taylor
2
Eu adicionei este código a um repositório github. Sinta-se à vontade para fazer o fork ou me avise se eu entendi algo errado: github.com/esromneb/ios-queue-object Obrigado !!!
portforwardpodcast
2
Estou faltando alguma coisa ou esta implementação tem complexidade O (n) no desenfileiramento? Isso é terrível. Você ficaria muito melhor com uma implementação de array circular. essa implementação pode funcionar, mas a ideia de O (n) dequeue é dolorosa.
ThatGuy
11
@Wolfcow, quando você remove um objeto do índice 0, cada objeto no array é deslocado um para baixo. Portanto, para remover um único item, é O (n). Provavelmente bom para filas pequenas, o que provavelmente é 99% do tempo em aplicativos móveis, mas essa seria uma solução terrível para grandes conjuntos de dados em situações críticas. Novamente, não que você encontrasse isso na maioria das situações C objetivas.
ThatGuy de
2
@ThatGuy Um pouco tarde, mas o NSArray é implementado com um buffer circular, então o tempo de execução não será theta (N).
Hanes
33

Eu não diria que usar 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 e suja, eu usaria os métodos para adicionar e remover no final de um array mutável. No entanto, se você planeja reutilizar a fila, ou se deseja que seu código seja mais legível e evidente, uma classe de fila dedicada é provavelmente o que você deseja.

O Cocoa não tem um integrado, mas existem outras opções, e você também não precisa escrever um do zero. Para uma fila verdadeira que apenas adiciona e remove das extremidades, uma matriz de buffer circular é uma implementação extremamente rápida. Confira CHDataStructures.framework , uma biblioteca / framework em Objective-C que venho trabalhando. Ele tem uma variedade de implementações de filas, bem como pilhas, deques, conjuntos classificados, etc. Para seus propósitos, CHCircularBufferQueue é significativamente mais rápido (ou seja, comprovável com benchmarks) e mais legível (admitidamente 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). Também funciona perfeitamente com coleta de lixo e enumeração rápida (ambos presentes no 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 último, embora NSMutableArray seja melhor do que um array C padrão ao adicionar e remover de qualquer extremidade, também não é a solução mais rápida para uma fila. Para a maioria dos aplicativos, é satisfatório, mas se você precisar de velocidade, um buffer circular (ou, em alguns casos, uma lista vinculada otimizada para manter as linhas de cache quentes) pode facilmente derrubar um NSMutableArray.

Quinn Taylor
fonte
2
Que bom que alguém realmente respondeu com uma solução de fila verdadeira
Casebash
Todos os links estão quebrados - onde posso obter essa estrutura? Eu li muitas coisas boas sobre isso, mas não consigo encontrar o código real!
amok
A estrutura parece promissora, mas os links para o SVN ainda estão quebrados. Alguma chance de obter o código em algum lugar? EDIT: Peguei em mac.softpedia.com/progDownload/… mas não consigo ver se esta é a versão atual
Kay
O clone de repositório Git de Dave DeLong parece ser o repositório ideal atualmente.
Regexident
29

Até onde eu sei, Objective-C não fornece uma estrutura de dados Queue. Sua melhor aposta é criar um NSMutableArraye, em seguida [array lastObject], usar [array removeLastObject]para buscar o item e [array insertObject:o atIndex:0]...

Se você está fazendo muito isso, pode criar uma categoria Objective-C para estender a funcionalidade da NSMutableArrayclasse. As categorias permitem adicionar funções dinamicamente a classes existentes (mesmo aquelas para as quais você não tem a fonte) - você pode fazer uma fila como esta:

(NOTA: Este código é, na verdade, para uma pilha, não uma fila. Veja os comentários abaixo)

@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
fonte
7
Você está ciente de que implementou uma pilha aqui, não uma fila?
Jim Puls de
Ahh - desculpe! - veja as modificações do Wolfcow abaixo.
Ben Gotow
Eu concordaria se você substituir "melhor aposta" por "opção mais simples". :-) Puristas de estrutura de dados e obsessores de desempenho prefeririam uma fila verdadeira, mas um NSMutableArray pode facilmente substituir uma fila.
Quinn Taylor
3
+1 para ben porque eu queria uma solução de pilha, embora uma fila fosse solicitada :)
whitneyland
Só consigo pensar na dor. Você está inserindo um objeto no início de uma matriz, então você precisa copiar cada elemento em 1 espaço cada vez que você inserir. Nesse caso, uma lista vinculada terá um desempenho muito melhor.
TheM00s3
8

Não há nenhuma classe de coleção de fila real, mas NSMutableArray pode ser usado efetivamente para a mesma coisa. Você pode definir uma categoria para adicionar métodos pop / push como uma conveniência, se desejar.

Marc Charbonneau
fonte
É verdade que um NSMutableArray cria uma fila bem decente, embora remover da frente não seja algo em que uma estrutura de array se destaque. Mesmo assim, para filas pequenas, o desempenho não é uma grande preocupação. Um amigo meu postou em um blog sobre esse assunto há algum tempo ... sg80bab.blogspot.com/2008/05/…
Quinn Taylor
7

Sim, use NSMutableArray. NSMutableArray é realmente implementado 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.

a coruja da geladeira
fonte
1
NSArray (e NSMutableArray por extensão) é um cluster de classe, o que significa que tem várias implementações privadas que podem ser usadas alternadamente nos bastidores. O que você obtém geralmente depende do número de elementos. Além disso, a Apple está livre para alterar os detalhes de qualquer implementação a qualquer momento. No entanto, você está correto ao dizer que geralmente é muito mais flexível do que um array padrão.
Quinn Taylor
5

re: Wolfcow - Aqui está uma implementação corrigida do método de desenfileiramento do Wolfcow

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

As soluções que usam uma categoria em NSMutableArraynão são filas verdadeiras, porque NSMutableArrayexpõ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
Pwner
fonte
pode-se argumentar que com certas técnicas (isto é, KVC) o array de armazenamento interno pode ser acessado e manipulado diretamente, mas muito melhor do que usar uma categoria.
vikingosegundo
3

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

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

@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
fonte
2

Existe algum motivo específico pelo qual você não pode simplesmente usar a fila STL? Objective C ++ é um superconjunto de C ++ (apenas use .mm como 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 ++.

Um problema de usar a fila / vetor / lista STL etc. com objetos Objective C é que eles normalmente não suportam gerenciamento de memória de retenção / liberação / liberação automática. 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.

Peter N Lewis
fonte
1
Isso realmente não parece uma boa ideia ... só porque você pode fazer algo, não significa que deveria. Puxar todo o ecossistema STL e C ++ apenas para uma classe de fila é definitivamente um exagero.
extropic-engine
3
Na verdade, desde que foi postado, essa ideia se tornou muito melhor. Objective C ++ / ARC significa que você pode usar contêineres STL com ponteiros de objeto Objective C e tudo funciona. O ARC cuida do gerenciamento de memória automaticamente para você dentro das estruturas C ++. Eu também geralmente argumentaria que C ++, sendo um C muito melhor, torna Objective-C ++ uma escolha melhor em geral do que Objective C simples (fornecendo coisas como classe enum, por exemplo). E eu duvido muito que adicionar STL / C ++ tenha qualquer impacto perceptível no tamanho de qualquer aplicativo do mundo real.
Peter N Lewis
1

Use NSMutableArray.

Nuoji
fonte