Jak utworzyć i używać kolejki w Objective-C?

107

Chcę użyć struktury danych kolejki w moim programie Objective-C. W C ++ użyłbym kolejki STL. Jaka jest równoważna struktura danych w Objective-C? Jak mogę wypchnąć / wyrzucić przedmioty?

MrDatabase
źródło

Odpowiedzi:

153

Wersja Bena to stos zamiast kolejki, więc trochę ją poprawiłem:

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

Po prostu zaimportuj plik .h tam, gdzie chcesz użyć nowych metod i wywołaj je tak, jak każdą inną metodę NSMutableArray.

Powodzenia i kontynuuj kodowanie!

Wolfcow
źródło
1
Dodałem zakomentowaną linię na początku usuwania z kolejki dla tych, którzy chcą zwrócić nil, zamiast zgłaszać wyjątek, gdy próbują usunąć z kolejki pustą kolejkę. IMO, zgodnie z zachowaniem NSMutableArray polegającym na zgłaszaniu wyjątku, jest bardziej spójne z Cocoa. W końcu możesz zadzwonić -countwcześniej, aby sprawdzić, czy są jakieś obiekty do usunięcia z kolejki. Tak naprawdę to kwestia preferencji.
Quinn Taylor
2
Dodałem ten kod do repozytorium github. Zapraszam do rozwidlenia lub daj mi znać, jeśli coś poszło nie tak: github.com/esromneb/ios-queue-object Dzięki !!!
portforwardpodcast
2
Czy coś mi brakuje, czy ta implementacja ma złożoność O (n) podczas usuwania z kolejki? To straszne. Byłoby znacznie lepiej z implementacją okrągłej tablicy. ta implementacja może działać, ale idea O (n) dequeue jest bolesna.
ThatGuy
11
@Wolfcow, kiedy usuniesz obiekt z indeksu 0, każdy obiekt w tablicy zostanie przesunięty o jeden w dół. Dlatego, aby usunąć pojedynczy element, jest to O (n). Prawdopodobnie dobrze dla małych kolejek, co jest prawdopodobnie 99% czasu w aplikacjach mobilnych, ale byłoby to straszne rozwiązanie dla dużych zbiorów danych w sytuacjach krytycznych czasowo. Nie znaczy to, że znajdziesz to w większości obiektywnych sytuacji w C.
ThatGuy,
2
@ThatGuy Trochę późno, ale NSArray jest zaimplementowany z buforem cyklicznym, więc środowisko wykonawcze nie będzie theta (N).
hhanesand
33

Nie powiedziałbym, że używanie NSMutableArray jest koniecznie najlepsze rozwiązaniem, szczególnie jeśli dodajesz metody z kategoriami, ze względu na kruchość, jaką mogą powodować kolizja nazw metod. W przypadku kolejki szybkiego i brudnego użyłbym metod dodawania i usuwania na końcu mutowalnej tablicy. Jeśli jednak planujesz ponowne użycie kolejki lub chcesz, aby kod był bardziej czytelny i zrozumiały, prawdopodobnie potrzebujesz dedykowanej klasy kolejki.

Cocoa nie ma wbudowanego, ale są inne opcje i nie musisz też pisać od zera. W przypadku prawdziwej kolejki, która tylko dodaje i usuwa z końców, cykliczna tablica buforów jest niezwykle szybką implementacją. Sprawdź CHDataStructures.framework , bibliotekę / framework w Objective-C, nad którym pracowałem. Ma wiele implementacji kolejek, a także stosów, deques, posortowanych zestawów itp. Do twoich celów CHCircularBufferQueue jest znacznie szybsze (tj. Możliwe do udowodnienia za pomocą testów porównawczych) i bardziej czytelne (wprawdzie subiektywne) niż użycie NSMutableArray.

Dużą zaletą korzystania z natywnej klasy Objective-C zamiast klasy C ++ STL jest to, że integruje się ona bezproblemowo z kodem Cocoa i działa znacznie lepiej z kodowaniem / dekodowaniem (serializacja). Działa również doskonale ze zbieraniem śmieci i szybkim wyliczaniem (oba obecne w 10.5+, ale tylko w tym drugim na iPhonie) i nie musisz się martwić, co jest obiektem Objective-C, a co obiektem C ++.

Wreszcie, chociaż NSMutableArray jest lepsze niż standardowa tablica C podczas dodawania i usuwania z dowolnego końca, nie jest również najszybszym rozwiązaniem dla kolejki. W przypadku większości aplikacji jest to zadowalające, ale jeśli potrzebujesz szybkości, cykliczny bufor (lub w niektórych przypadkach lista połączona zoptymalizowana pod kątem utrzymywania gorących linii pamięci podręcznej) może z łatwością przebić NSMutableArray.

Quinn Taylor
źródło
2
Cieszę się, że ktoś faktycznie odpowiedział, podając prawdziwe rozwiązanie kolejki
Casebash
Wszystkie linki są zepsute - skąd wziąć ten framework? Przeczytałem wiele dobrych rzeczy na ten temat, ale nie mogę znaleźć właściwego kodu!
amok
Struktura wygląda obiecująco, ale linki do SVN są nadal zepsute. Jakaś szansa na zdobycie gdzieś kodu? EDYCJA: Mam to z mac.softpedia.com/progDownload/ ... ale nie widzę, czy to jest aktualna wersja
Kay
Klon repozytorium Git Dave'a DeLonga wydaje się być obecnie najlepszym repozytorium.
Regexident,
29

O ile wiem, Objective-C nie zapewnia struktury danych kolejki. Najlepiej jest utworzyć plik NSMutableArray, a następnie użyć go [array lastObject], [array removeLastObject]aby pobrać przedmiot i [array insertObject:o atIndex:0]...

Jeśli często to robisz, możesz chcieć utworzyć kategorię Cel-C, aby rozszerzyć funkcjonalność NSMutableArrayklasy. Kategorie pozwalają dynamicznie dodawać funkcje do istniejących klas (nawet tych, dla których nie masz źródła) - możesz utworzyć kolejkę w ten sposób:

(UWAGA: ten kod w rzeczywistości dotyczy stosu, a nie kolejki. Zobacz komentarze poniżej)

@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
źródło
7
Czy wiesz, że zaimplementowałeś tutaj stos, a nie kolejkę?
Jim Puls
Ahh - przepraszam! - zobacz poniżej modyfikacje Wolfcowa.
Ben Gotow,
Zgodzę się, jeśli zastąpisz „najlepszy zakład” „najprostszą opcją”. :-) Puryści struktury danych i obsesorzy wydajności woleliby prawdziwą kolejkę, ale NSMutableArray może z łatwością zastąpić kolejkę.
Quinn Taylor
3
+1 do ben, ponieważ chciałem mieć rozwiązanie
stackowe,
Jedyne o czym mogę myśleć to ból. Wstawiasz obiekt na początku tablicy, a następnie za każdym razem, gdy wstawiasz, musisz skopiować każdy element na 1 spację. W takim przypadku lista z linkami będzie działać znacznie lepiej.
TheM00s3
8

Nie ma prawdziwej klasy kolekcji kolejek, ale NSMutableArray można skutecznie wykorzystać do tego samego. Jeśli chcesz, możesz zdefiniować kategorię, aby dodać metody pop / push jako wygodę.

Marc Charbonneau
źródło
To prawda, że ​​NSMutableArray tworzy całkiem przyzwoitą kolejkę, chociaż usuwanie z przodu nie jest czymś, co wyróżnia struktura tablicy. Mimo to w przypadku małych kolejek wydajność i tak nie jest głównym problemem. Mój
Quinn Taylor
7

Tak, użyj NSMutableArray. NSMutableArray jest faktycznie zaimplementowany jako 2-3 drzewo; zazwyczaj nie musisz zajmować się charakterystyką wydajności dodawania lub usuwania obiektów z NSMutableArray w dowolnych indeksach.

sowa z lodówki
źródło
1
NSArray (i NSMutableArray przez rozszerzenie) jest klastrem klas, co oznacza, że ​​ma kilka prywatnych implementacji, które mogą być używane zamiennie za kulisami. Ten, który otrzymasz, zależy zwykle od liczby elementów. Ponadto Apple może w dowolnym momencie zmienić szczegóły dowolnej implementacji. Jednak masz rację, że jest zwykle znacznie bardziej elastyczny niż standardowa tablica.
Quinn Taylor
5

re: Wolfcow - Oto poprawiona implementacja metody dequeue Wolfcowa

- (id)dequeue {
    if ([self count] == 0) {
        return nil;
    }
    id queueObject = [[[self objectAtIndex:0] retain] autorelease];
    [self removeObjectAtIndex:0];
    return queueObject;
}
DougW
źródło
4

Rozwiązania, które używają kategorii na, NSMutableArraynie są prawdziwymi kolejkami, ponieważ NSMutableArrayujawniają operacje, które są nadzbiorem kolejek. Na przykład nie powinieneś mieć możliwości usunięcia pozycji ze środka kolejki (ponieważ te rozwiązania kategorii nadal pozwalają). Najlepiej jest hermetyzować funkcjonalność, główną zasadę projektowania obiektowego.

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
źródło
można by argumentować, że przy pewnych technikach (np. KVC) wewnętrzna tablica pamięci może być dostępna i manipulowana bezpośrednio, ale znacznie lepiej niż przy użyciu kategorii.
vikingosegundo
3

to jest moja realizacja, mam nadzieję, że to pomoże.

Jest trochę minimalistyczny, więc musisz śledzić głowę, zapisując nową głowę w popie i odrzucając starą

@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
źródło
2

Czy jest jakiś szczególny powód, dla którego nie możesz po prostu użyć kolejki STL? Objective C ++ jest nadzbiorem języka C ++ (po prostu użyj .mm jako rozszerzenia zamiast .m, aby użyć Objective C ++ zamiast Objective C). Następnie możesz użyć kodu STL lub dowolnego innego kodu C ++.

Jednym z problemów związanych z używaniem kolejki / wektora / listy STL itp. Z obiektami celu C jest to, że zazwyczaj nie obsługują one zarządzania pamięcią typu retain / release / autorelease. Można to łatwo obejść dzięki klasie kontenera C ++ Smart Pointer, która zachowuje swój obiekt Objective C po skonstruowaniu i zwalnia go po zniszczeniu. W zależności od tego, co umieszczasz w kolejce STL, często nie jest to konieczne.

Peter N Lewis
źródło
1
To nie wydaje się być dobrym pomysłem ... tylko dlatego, że możesz coś zrobić, nie oznacza, że ​​powinieneś. Pobieranie całego ekosystemu STL i C ++ tylko dla klasy kolejki to zdecydowanie przesada.
silnik ekstopowy
3
Właściwie, odkąd to zostało opublikowane, stało się to znacznie lepszym pomysłem. Objective C ++ / ARC oznacza, że ​​możesz używać kontenerów STL ze wskaźnikami obiektu Objective C i wszystko po prostu działa. ARC automatycznie zajmie się zarządzaniem pamięcią w ramach struktur C ++. Generalnie argumentowałbym również, że C ++, będąc znacznie lepszym C, sprawia, że ​​Objective-C ++ jest ogólnie lepszym wyborem niż zwykły Objective C (na przykład podając takie rzeczy jak klasa wyliczenia). I bardzo wątpię, czy dodanie STL / C ++ ma jakikolwiek zauważalny wpływ na rozmiar dowolnej aplikacji w świecie rzeczywistym.
Peter N Lewis
1

Użyj NSMutableArray.

Nuoji
źródło