Jak skutecznie wyczyścić kolejkę std :: queue?


166

Do implementacji klasy JobQueue używam std :: queue. (Zasadniczo ta klasa przetwarza każde zadanie w sposób FIFO). W jednym scenariuszu chcę wyczyścić kolejkę za jednym zamachem (usunąć wszystkie zadania z kolejki). Nie widzę żadnej przejrzystej metody dostępnej w klasie std :: queue.

Jak efektywnie wdrożyć przejrzystą metodę dla klasy JobQueue?

Mam jedno proste rozwiązanie polegające na poppingu w pętli, ale szukam lepszych sposobów.

//Clears the job queue
void JobQueue ::clearJobs()
 {
  // I want to avoid pop in a loop
    while (!m_Queue.empty())
    {
        m_Queue.pop();
    }
}

3
Uwaga dequeobsługuje jasne
bobobobo

Odpowiedzi:


257

Popularnym idiomem do czyszczenia standardowych kontenerów jest zamiana na pustą wersję kontenera:

void clear( std::queue<int> &q )
{
   std::queue<int> empty;
   std::swap( q, empty );
}

Jest to również jedyny sposób na faktyczne wyczyszczenie pamięci przechowywanej w niektórych kontenerach (std :: vector)


41
Jeszcze lepiej std::queue<int>().swap(q). W przypadku idiomu kopiowania i zamiany wszystko to powinno być równoważne z q = std::queue<int>().
Alexandre C.

12
Chociaż std::queue<int>().swap(q)jest odpowiednikiem powyższego kodu, q = std::queue<int>()nie musi być równoważne. Ponieważ nie ma przeniesienia własności w przypisaniu przydzielonej pamięci, niektóre kontenery (takie jak wektor) mogą po prostu wywołać destruktory poprzednio trzymanych elementów i ustawić rozmiar (lub równoważną operację z przechowywanymi wskaźnikami) bez faktycznego zwalniania pamięci.
David Rodríguez - dribeas

6
queuenie ma swap(other)metody, więc queue<int>().swap(q)się nie kompiluje. Myślę, że musisz użyć generycznego swap(a, b).
Dustin Boswell

3
@ ThorbjørnLindeijer: W C ++ 03 masz rację, w C ++ 11 kolejki mają swap jako funkcję składową, a dodatkowo istnieje wolne przeciążenie funkcji, które zamieni dwie kolejki tego samego typu.
David Rodríguez - drybling

10
@ ThorbjørnLindeijer: Z punktu widzenia użytkowników oryginalnej kolejki te elementy nie istnieją. Masz rację co do tego, że zostaną one zniszczone jeden po drugim, a koszt jest liniowy, ale nie są dostępne dla nikogo poza lokalną funkcją. W środowisku wielowątkowym można by zablokować, zamienić nietymczasową kolejkę na oryginalną, odblokować (aby umożliwić równoczesny dostęp) i pozwolić, aby zamieniona kolejka umarła. W ten sposób możesz przenieść koszt zniszczenia poza krytyczną sekcję.
David Rodríguez - dribeas

46

Tak - trochę niedopasowanie klasy kolejki, IMHO. Tym się właśnie zajmuję:

#include <queue>
using namespace std;;

int main() {
    queue <int> q1;
    // stuff
    q1 = queue<int>();  
}

8
@Naszta Opisz, w jaki sposób swapjest „bardziej skuteczny”
bobobobo

@bobobobo:q1.swap(queue<int>());
Naszta

12
q1=queue<int>();jest krótszy i wyraźniejszy (tak naprawdę nie próbujesz .swap, próbujesz .clear).
bobobobo

28
Z nowym C ++ po prostu q1 = {}wystarczy
Mykoła Bogdiuk

2
Składnia @Ari (2) na inicjalizacji listy i (10) na przypisaniu operatora . Domyślny queue<T>konstruktor dopasowuje pustą listę argumentów {}i jest niejawny, więc jest wywoływany, a następnie q1.operator=(queue<T>&&)konsumuje nowo utworzonąqueue
Mykola Bogdiuk

26

Autor tematu zapytał, jak „sprawnie” wyczyścić kolejkę, więc zakładam, że chce większej złożoności niż liniowa O (wielkość kolejki) . Formy podawane przez David Rodriguez , Anon mają taką samą złożoność: zgodnie z odpowiednim STL operator =ma złożoność O (kolejka wielkości) . IMHO to dlatego, że każdy element kolejki jest zarezerwowany osobno i nie jest przydzielany w jednym dużym bloku pamięci, jak w wektorze. Aby wyczyścić całą pamięć, musimy osobno usunąć każdy element. Zatem najprostszym sposobem na wyczyszczenie std::queuejest jedna linia:

while(!Q.empty()) Q.pop();

5
Nie możesz po prostu spojrzeć na złożoność operacji O, jeśli operujesz na rzeczywistych danych. Chciałbym wziąć O(n^2)algorytm nad O(n)algorytmem jeśli stałe na temat funkcjonowania liniowego zrobić to wolniej niż kwadratowego dla wszystkich n < 2^64, chyba że miałem pewne mocne podstawy, aby sądzić, musiałem szukać przestrzeni adresowej IPv6 lub jakiś inny problem konkretnego. W rzeczywistości wydajność jest dla mnie ważniejsza niż wydajność na granicy.
David Stone

2
To lepsza odpowiedź niż zaakceptowana odpowiedź, ponieważ wewnętrzna kolejka robi to tak, gdy zostaje zniszczona. Tak więc akceptowaną odpowiedzią jest O (n), a ponadto wykonuje dodatkowe alokacje i inicjalizacje dla zupełnie nowej kolejki.
Shital Shah

Pamiętaj, O (n) oznacza mniejszą lub równą n złożoności. Więc tak, w niektórych przypadkach, takich jak queue <vector <int>>, będzie musiał zniszczyć każdy element 1 na 1, co będzie powolne w obu przypadkach, ale w queue <int> pamięć jest przydzielana w jednym dużym bloku, dlatego nie musi niszczyć elementów wewnętrznych, więc destruktor kolejki może używać pojedynczej wydajnej operacji free (), która prawie na pewno zajmuje mniej niż O (n) czasu.
Benjamin

15

Najwyraźniej istnieją dwa najbardziej oczywiste sposoby na wyczyszczenie std::queue: zamiana z pustym obiektem i przypisanie do pustego obiektu.

Sugerowałbym użycie przypisania, ponieważ jest po prostu szybsze, bardziej czytelne i jednoznaczne.

Zmierzyłem wydajność za pomocą prostego kodu i odkryłem, że zamiana w wersji C ++ 03 działa o 70-80% wolniej niż przypisanie do pustego obiektu. Jednak w C ++ 11 nie ma różnicy w wydajności. W każdym razie pójdę z zadaniem.

#include <algorithm>
#include <ctime>
#include <iostream>
#include <queue>
#include <vector>

int main()
{
    std::cout << "Started" << std::endl;

    std::queue<int> q;

    for (int i = 0; i < 10000; ++i)
    {
        q.push(i);
    }

    std::vector<std::queue<int> > queues(10000, q);

    const std::clock_t begin = std::clock();

    for (std::vector<int>::size_type i = 0; i < queues.size(); ++i)
    {
        // OK in all versions
        queues[i] = std::queue<int>();

        // OK since C++11
        // std::queue<int>().swap(queues[i]);

        // OK before C++11 but slow
        // std::queue<int> empty;
        // std::swap(empty, queues[i]);
    }

    const double elapsed = double(clock() - begin) / CLOCKS_PER_SEC;

    std::cout << elapsed << std::endl;

    return 0;
}

8

W C ++ 11 możesz wyczyścić kolejkę, wykonując następujące czynności:

std::queue<int> queue;
// ...
queue = {};

4

Możesz utworzyć klasę, która dziedziczy z kolejki i bezpośrednio wyczyścić podstawowy kontener. To jest bardzo wydajne.

template<class T>
class queue_clearable : public std::queue<T>
{
public:
    void clear()
    {
        c.clear();
    }
};

Być może Twoja implementacja pozwala również JobQueuedziedziczyć obiekt Queue (tutaj ) std::queue<Job>zamiast mieć kolejkę jako zmienną składową. W ten sposób będziesz miał bezpośredni dostęp do c.clear()swoich funkcji członkowskich.


9
Kontenery STL nie są przeznaczone do dziedziczenia z. W tym przypadku prawdopodobnie wszystko jest w porządku, ponieważ nie dodajesz żadnych dodatkowych zmiennych składowych, ale ogólnie nie jest to dobre.
bstamour

2

Zakładając, że m_Queuezawiera liczby całkowite:

std::queue<int>().swap(m_Queue)

W przeciwnym razie, jeśli zawiera np. Wskaźniki do Jobobiektów, to:

std::queue<Job*>().swap(m_Queue)

W ten sposób zamieniasz pustą kolejkę na swoją m_Queuei m_Queuestaje się ona pusta.


1

Wolałbym nie polegać swap()ani ustawiać kolejki na nowo utworzony obiekt kolejki, ponieważ elementy kolejki nie są odpowiednio niszczone. Wywołanie pop()wywołuje destruktor dla odpowiedniego obiektu elementu. Może to nie być problemem w <int>kolejkach, ale bardzo dobrze może mieć skutki uboczne w kolejkach zawierających obiekty.

Dlatego pętla z while(!queue.empty()) queue.pop();wydaje się niestety najbardziej wydajnym rozwiązaniem, przynajmniej dla kolejek zawierających obiekty, jeśli chcesz zapobiec możliwym efektom ubocznym.


3
swap()lub przypisanie wywołuje destruktor w nieistniejącej już kolejce, która wywołuje destruktory wszystkich obiektów w kolejce. Teraz, jeśli w Twojej kolejce znajdują się obiekty, które w rzeczywistości są wskaźnikami, jest to inna kwestia - ale prostota też pop()Ci w tym nie pomoże.
jhfrontz

Dlaczego niestety? Jest elegancka i prosta.
OS2

1

Robię to (używając C ++ 14):

std::queue<int> myqueue;
myqueue = decltype(myqueue){};

Ten sposób jest przydatny, jeśli masz nietrywialny typ kolejki, dla którego nie chcesz budować aliasu / typedef. Zawsze jednak upewniam się, że zostawiam komentarz na temat tego zastosowania, aby wyjaśnić niczego nie podejrzewającym / konserwującym programistom, że to nie jest szalone i zrobione zamiast rzeczywistej clear()metody.


Dlaczego jawnie podajesz typ w operatorze przypisania? Zakładam, że myqueue = { };to zadziała dobrze.
Joel Bodenmann

0

Używanie a unique_ptrmoże być OK.
Następnie resetujesz ją, aby uzyskać pustą kolejkę i zwolnić pamięć pierwszej kolejki. Co do złożoności? Nie jestem pewien - ale domyślam się, że to O (1).

Możliwy kod:

typedef queue<int> quint;

unique_ptr<quint> p(new quint);

// ...

p.reset(new quint);  // the old queue has been destroyed and you start afresh with an empty queue

Jeśli zdecydujesz się opróżnić kolejkę, usuwając ją, to w porządku, ale nie o to chodzi i nie rozumiem, dlaczego pojawia się unique_ptr.
manuell

0

Inną opcją jest skorzystanie z prostego hackowania, aby zdobyć podstawowy kontener std::queue::ci wywołać cleargo. Ten członek musi być obecny std::queuezgodnie ze standardem, ale niestety jest protected. Hack tutaj pochodzi z tej odpowiedzi .

#include <queue>

template<class ADAPTER>
typename ADAPTER::container_type& get_container(ADAPTER& a)
{
    struct hack : ADAPTER
    {
        static typename ADAPTER::container_type& get(ADAPTER& a)
        {
            return a .* &hack::c;
        }
    };
    return hack::get(a);
}

template<typename T, typename C>
void clear(std::queue<T,C>& q)
{
    get_container(q).clear();
}

#include <iostream>
int main()
{
    std::queue<int> q;
    q.push(3);
    q.push(5);
    std::cout << q.size() << '\n';
    clear(q);
    std::cout << q.size() << '\n';
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.