Comment créer et utiliser une file d'attente dans Objective-C?

Question

Je souhaite utiliser une structure de données en file d'attente dans mon programme Objective-C. En C ++, j'utiliserais la file d'attente STL. Quelle est la structure de données équivalente dans Objective-C? Comment puis-je pousser / sauter des éléments?

Answer 1

La version de Ben est une pile au lieu d'une file d'attente, je l'ai donc légèrement modifiée:

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

Importez simplement le fichier .h où vous voulez utiliser vos nouvelles méthodes et appelez-le comme n'importe quelle autre méthode NSMutableArray.

Bonne chance et continuez à coder!

Answer 2

Je ne dirais pas que l'utilisation de NSMutableArray est nécessairement la meilleure solution, en particulier si vous ajoutez des méthodes avec des catégories, en raison de la fragilité qu'elles peuvent causer en cas de collision des noms de méthodes. Pour une file d'attente rapide, j'utiliserais les méthodes pour ajouter et supprimer à la fin d'un tableau mutable. Toutefois, si vous envisagez de réutiliser la file d'attente ou si vous souhaitez que votre code soit plus lisible et plus évident, une classe de files d'attente dédiée est probablement ce que vous voulez.

Cocoa n’en a pas intégré, mais il existe d’autres options et vous n’avez pas à en écrire une de toutes pièces. Pour une vraie file d'attente qui ajoute et supprime seulement les extrémités, un tableau de mémoire tampon circulaire est une mise en œuvre extrêmement rapide. Consultez CHDataStructures.framework , une bibliothèque / infrastructure en Objective-C sur laquelle j'ai travaillé . Il comporte diverses implémentations de files d'attente, ainsi que de piles, de machines, de jeux triés, etc. Pour vos besoins, CHCircularBufferQueue est nettement plus rapide (preuve possible avec des points de repère) et plus lisible (certes subjectif) que d'utiliser un NSMutableArray.

L’utilisation d’une classe native Objective-C au lieu d’une classe C ++ STL présente un grand avantage: elle s’intègre parfaitement au code Cocoa et fonctionne beaucoup mieux avec le codage / décodage (sérialisation). Il fonctionne également parfaitement avec la récupération de place et l'énumération rapide (les deux présents dans 10.5+, mais seulement le dernier sur iPhone) et vous n'avez pas à vous soucier de ce qu'est un objet Objective-C et de ce qui est un objet C ++.

Enfin, bien que NSMutableArray soit meilleur qu'un tableau C standard lors de l'ajout et de la suppression, ce n'est pas non plus la solution la plus rapide pour une file d'attente. Pour la plupart des applications, il est satisfaisant, mais si vous avez besoin de rapidité, un tampon circulaire (ou, dans certains cas, une liste chaînée optimisée pour conserver les lignes de cache en permanence) peut facilement remplacer un NSMutableArray.

Answer 3

Autant que je sache, Objective-C ne fournit pas de structure de données en file d'attente. La meilleure solution consiste à créer un NSMutableArray , puis à utiliser [array lastObject] , [array removeLastObject] pour extraire l'élément et [array insertObject: o atIndex: 0] ...

Si vous le faites souvent, vous pouvez créer une catégorie Objective-C pour étendre les fonctionnalités de la classe NSMutableArray . Les catégories vous permettent d’ajouter dynamiquement des fonctions aux classes existantes (même celles pour lesquelles vous n’avez pas de source) - vous pouvez créer une file d’attente comme celle-ci:

(REMARQUE: ce code concerne en fait une pile, pas une file d'attente. Voir les commentaires ci-dessous.

@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

Il n'y a pas de véritable classe de collections de files d'attente, mais NSMutableArray peut être utilisé pour la même chose. Vous pouvez définir une catégorie pour ajouter des méthodes pop / push à votre convenance. si tu veux.

Answer 5

Oui, utilisez NSMutableArray. NSMutableArray est en réalité implémenté sous forme d'arborescence 2-3 ; vous n'avez généralement pas besoin de vous préoccuper des caractéristiques de performance de l'ajout ou de la suppression d'objets de NSMutableArray à des index arbitraires.

Answer 6

re: Wolfcow - Voici une implémentation corrigée de la méthode de dequeue de Wolfcow

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

Answer 7

Les solutions qui utilisent une catégorie sur NSMutableArray ne sont pas de véritables files d'attente, car NSMutableArray expose les opérations qui sont un sur-ensemble de files d'attente. Par exemple, vous ne devriez pas être autorisé à supprimer un élément du milieu d'une file d'attente (comme les solutions de catégorie vous le permettent encore). Il est préférable d’encapsuler les fonctionnalités, principe majeur de la conception orientée objet.

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

C’est ma mise en œuvre, espérons que cela aide.

Est un peu minimaliste, vous devez donc garder la trace de la tête en sauvant la nouvelle tête et en jetant la vieille tête

@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

Y a-t-il une raison particulière pour laquelle vous ne pouvez pas utiliser simplement la file d'attente STL? Objective C ++ est un sur-ensemble de C ++ (utilisez simplement .mm comme extension au lieu de .m pour utiliser Objective C ++ au lieu de Objective C). Ensuite, vous pouvez utiliser la STL ou n’importe quel autre code C ++.

L’utilisation de la file / du vecteur / de la liste STL avec des objets Objective C, par exemple, tient au fait qu’ils ne prennent généralement pas en charge la gestion de la mémoire conservation / libération / libération automatique. Ceci est facilement contourné avec une classe de conteneur C ++ Smart Pointer qui conserve son objet Objective C lors de sa construction et le libère lorsqu'il est détruit. En fonction de ce que vous mettez dans la file d'attente STL, cela n'est souvent pas nécessaire.

Answer 10

Utilisez NSMutableArray.