Как мне создать и использовать очередь в Objective-C?
Я хочу использовать структуру данных очереди в моей программе Objective-C. В C++ я бы использовал очередь STL. Какова эквивалентная структура данных в Objective-C? Как мне пушить / высовывать предметы?
10 ответов
Версия Бена - стек, а не очередь, поэтому я немного подправил:
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
Просто импортируйте файл.h, где бы вы ни хотели использовать ваши новые методы, и вызывайте их так же, как и любые другие методы NSMutableArray.
Удачи и продолжайте кодировать!
Я бы не сказал, что использование NSMutableArray - обязательно лучшее решение, особенно если вы добавляете методы с категориями из-за хрупкости, которую они могут вызвать, если имена методов сталкиваются. Для быстрой-грязной очереди я бы использовал методы для добавления и удаления в конце изменяемого массива. Однако, если вы планируете повторно использовать очередь или хотите, чтобы ваш код был более читабельным и самоочевидным, вероятно, вам нужен выделенный класс очереди.
Какао не имеет встроенного, но есть и другие варианты, и вам не нужно писать с нуля. Для истинной очереди, которая только добавляет и удаляет с концов, кольцевой буферный массив является чрезвычайно быстрой реализацией. Ознакомьтесь с CHDataStructures.framework, библиотекой / структурой в Objective-C, над которой я работал. Он имеет множество реализаций очередей, а также стеков, запросов, отсортированных наборов и т. Д. Для ваших целей CHCircularBufferQueue значительно быстрее (то есть доказуемо с помощью тестов) и более читабелен (предположительно субъективен), чем использование NSMutableArray.
Одним из больших преимуществ использования собственного класса Objective-C вместо класса C++ STL является то, что он легко интегрируется с кодом Какао и намного лучше работает с кодированием / декодированием (сериализацией). Он также отлично работает с сборкой мусора и быстрым перечислением (оба представлены в 10.5+, но только в последних на iPhone), и вам не нужно беспокоиться о том, что является объектом Objective-C и чем является объектом C++.
Наконец, хотя NSMutableArray лучше, чем стандартный массив C, при добавлении и удалении с любого конца, это также не самое быстрое решение для очереди. Для большинства приложений это удовлетворительно, но если вам нужна скорость, циклический буфер (или в некоторых случаях связанный список, оптимизированный для поддержания горячих строк кэша) может легко нарушить NSMutableArray.
Насколько я знаю, Objective-C не предоставляет структуру данных Queue. Лучше всего создать NSMutableArray, а затем использовать [array lastObject], [array removeLastObject] чтобы получить предмет, и [array insertObject:o atIndex:0]...
Если вы делаете это много, вы можете создать категорию Objective-C, чтобы расширить функциональность NSMutableArray учебный класс. Категории позволяют вам динамически добавлять функции в существующие классы (даже те, для которых у вас нет источника) - вы можете создать очередь, подобную этой:
(ПРИМЕЧАНИЕ. Этот код на самом деле предназначен для стека, а не для очереди. См. Комментарии ниже)
@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
Реального класса коллекций очередей не существует, но NSMutableArray можно эффективно использовать для одной и той же вещи. Вы можете определить категорию для добавления методов pop/push для удобства, если хотите.
Да, используйте NSMutableArray. NSMutableArray фактически реализован как 2-3 дерева; вам обычно не нужно заботиться о характеристиках производительности добавления или удаления объектов из NSMutableArray по произвольным индексам.
Re:Wolfcow - Вот исправленная реализация метода dequeue Wolfcow
- (id)dequeue {
if ([self count] == 0) {
return nil;
}
id queueObject = [[[self objectAtIndex:0] retain] autorelease];
[self removeObjectAtIndex:0];
return queueObject;
}
Решения, которые используют категорию на NSMutableArray не настоящие очереди, потому что NSMutableArray выставляет операции, которые являются надмножеством очередей. Например, вам не должно быть разрешено удалять элемент из середины очереди (так как решения с категориями все еще позволяют это делать). Лучше всего инкапсулировать функциональность, основной принцип объектно-ориентированного проектирования.
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
Это моя реализация, надеюсь, это поможет.
Это своего рода минимализм, поэтому вы должны следить за головой, сохраняя новую голову на месте и отбрасывая старую голову
@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
Есть ли какая-то особая причина, по которой вы не можете просто использовать очередь STL? Objective C++ - это расширенный набор C++ (просто используйте.mm в качестве расширения вместо.m, чтобы использовать Objective C++ вместо Objective C). Затем вы можете использовать STL или любой другой код C++.
Одной из проблем использования очереди / вектора / списка STL и других объектов Objective C является то, что они обычно не поддерживают управление сохранением / освобождением / автоматическим выпуском памяти. Это легко обойти с помощью контейнерного класса C++ Smart Pointer, который сохраняет объект Objective C при создании и освобождает его при уничтожении. В зависимости от того, что вы помещаете в очередь STL, это часто не требуется.