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

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();
    }
}

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)

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>();  
}

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();

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;
}

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

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

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.

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.

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.

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.

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

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';
}