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

Je souhaite utiliser une structure de données de 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 en Objective-C? Comment pousser / faire apparaître des éléments?

La version de Ben est une pile au lieu d'une file d'attente, alors je l'ai 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 là où vous souhaitez utiliser vos nouvelles méthodes et appelez-les comme vous le feriez pour toute autre méthode NSMutableArray.

Bonne chance et continuez à coder!

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 si les noms de méthodes entrent en collision. Pour une file d'attente rapide et sale, j'utiliserais les méthodes pour ajouter et supprimer à la fin d'un tableau mutable. Cependant, si vous prévoyez de réutiliser la file d'attente, ou si vous voulez que votre code soit plus lisible et plus évident, une classe de file 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 non plus à en écrire une à partir de zéro. Pour une vraie file d'attente qui ajoute et supprime uniquement des extrémités, un tableau de tampons circulaire est une implémentation extrêmement rapide. Découvrez CHDataStructures.framework , une bibliothèque / framework en Objective-C sur laquelle j'ai travaillé. Il a une variété d'implémentations de files d'attente, ainsi que des piles, des deques, des ensembles triés, etc. Pour vos besoins, CHCircularBufferQueue est beaucoup plus rapide (c'est-à-dire prouvable avec des benchmarks) et plus lisible (certes subjectif) que l'utilisation d'un NSMutableArray.

Un gros avantage de l'utilisation d'une classe Objective-C native au lieu d'une classe C ++ STL est qu'elle s'intègre parfaitement au code Cocoa et fonctionne beaucoup mieux avec l'encodage / décodage (sérialisation). Cela fonctionne également parfaitement avec le garbage collection et l'énumération rapide (tous deux présents dans 10.5+, mais uniquement ce dernier sur iPhone) et vous n'avez pas à vous soucier de ce qu'est un objet Objective-C et de ce qu'est un objet C ++.

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

Autant que je sache, Objective-C ne fournit pas de structure de données de file d'attente. Votre meilleur pari est de créer un NSMutableArray, et utiliser ensuite [array lastObject], [array removeLastObject]pour aller chercher l'élément, et [array insertObject:o atIndex:0]...

Si vous faites beaucoup cela, vous voudrez peut-être créer une catégorie Objective-C pour étendre les fonctionnalités de la NSMutableArrayclasse. Les catégories vous permettent d'ajouter dynamiquement des fonctions aux classes existantes (même celles dont vous n'avez pas la source) - vous pouvez en créer une comme celle-ci:

(REMARQUE: ce code est en fait pour 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

Il n'y a pas de vraie 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 si vous le souhaitez.

Oui, utilisez NSMutableArray. NSMutableArray est en fait implémenté sous la forme d'un arbre 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.

re: Wolfcow - Voici une implémentation corrigée de la méthode de file d'attente de Wolfcow

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

Les solutions qui utilisent une catégorie sur NSMutableArrayne sont pas de vraies files d'attente, car elles NSMutableArrayexposent des 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 ces solutions de catégorie vous le permettent toujours). Il est préférable d'encapsuler la fonctionnalité, un 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

c'est ma mise en œuvre, j'espère que cela aide.

Est un peu minimaliste, vous devez donc garder la trace de la tête en sauvegardant la nouvelle tête au pop et en jetant l'ancienne 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

Y a-t-il une raison particulière pour laquelle vous ne pouvez pas simplement utiliser 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 d'Objective C). Ensuite, vous pouvez utiliser la STL ou tout autre code C ++.

Un problème lié à l'utilisation de la file d'attente / vecteur / liste STL avec des objets Objective C est qu'ils ne prennent généralement pas en charge la gestion de la mémoire de conservation / libération / libération automatique. Cela est facilement contourné avec une classe de conteneur C ++ Smart Pointer qui conserve son objet Objective C lorsqu'il est construit 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.

Utilisez NSMutableArray.