Comment effacer efficacement la file d'attente std ::?

J'utilise std :: queue pour implémenter la classe JobQueue. (Fondamentalement, cette classe traite chaque travail de manière FIFO). Dans un scénario, je souhaite effacer la file d'attente d'un seul coup (supprimer tous les travaux de la file d'attente). Je ne vois aucune méthode claire disponible dans la classe std :: queue.

Comment implémenter efficacement la méthode clear pour la classe JobQueue?

J'ai une solution simple de sauter dans une boucle mais je cherche de meilleures façons.

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

Un idiome courant pour effacer les conteneurs standard consiste à échanger avec une version vide du conteneur:

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

C'est aussi le seul moyen d'effacer réellement la mémoire contenue dans certains conteneurs (std :: vector)

Oui - un peu d'un dysfonctionnement de la classe de file d'attente, à mon humble avis. C'est ce que je fais:

#include <queue>
using namespace std;;

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

L'auteur du sujet a demandé comment effacer la file d'attente "efficacement", donc je suppose qu'il veut une meilleure complexité que O linéaire (taille de la file d'attente) . Les méthodes servies par David Rodriguez , anon, ont la même complexité: selon la référence STL, operator =a la complexité O (taille de la file d'attente) . À mon humble avis, c'est parce que chaque élément de la file d'attente est réservé séparément et qu'il n'est pas alloué dans un gros bloc de mémoire, comme dans le vecteur. Donc, pour effacer toute la mémoire, nous devons supprimer chaque élément séparément. Donc, la façon la plus directe de supprimer std::queueest une ligne:

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

Apparemment, il existe deux façons les plus évidentes de supprimer std::queue: permutation avec un objet vide et affectation à un objet vide.

Je suggérerais d'utiliser l'affectation parce que c'est simplement plus rapide, plus lisible et sans ambiguïté.

J'ai mesuré les performances en utilisant le code simple suivant et j'ai trouvé que l'échange dans la version C ++ 03 fonctionne 70 à 80% plus lentement que l'assignation à un objet vide. En C ++ 11, il n'y a cependant aucune différence de performances. Quoi qu'il en soit, j'irais avec une mission.

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

Dans C ++ 11, vous pouvez effacer la file d'attente en procédant comme suit:

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

Vous pouvez créer une classe qui hérite de la file d'attente et effacer directement le conteneur sous-jacent. C'est très efficace.

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

Peut-être que votre implémentation permet également à votre objet Queue (ici JobQueue) d'hériter std::queue<Job>au lieu d'avoir la file d'attente comme variable membre. De cette façon, vous auriez un accès direct à c.clear()vos fonctions membres.

En supposant que votre m_Queuecontient des entiers:

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

Sinon, s'il contient par exemple des pointeurs vers des Jobobjets, alors:

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

De cette façon, vous permutez une file d'attente vide avec votre m_Queue, devenant ainsi m_Queuevide.

Je préfère ne pas compter sur swap()ou définir la file d'attente sur un objet de file d'attente nouvellement créé, car les éléments de la file d'attente ne sont pas correctement détruits. L'appel pop()appelle le destructeur de l'objet d'élément respectif. Cela peut ne pas être un problème dans les <int>files d'attente, mais peut très bien avoir des effets secondaires sur les files d'attente contenant des objets.

Par conséquent, une boucle avec while(!queue.empty()) queue.pop();semble malheureusement être la solution la plus efficace au moins pour les files d'attente contenant des objets si vous voulez éviter d'éventuels effets secondaires.

Je fais ceci (en utilisant C ++ 14):

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

Cette méthode est utile si vous avez un type de file d'attente non trivial pour lequel vous ne souhaitez pas créer d'alias / typedef. Je m'assure toujours de laisser un commentaire sur cette utilisation, cependant, pour expliquer aux programmeurs sans méfiance / de maintenance que ce n'est pas fou et que ce n'est pas une clear()méthode réelle .

L'utilisation d'un unique_ptrpeut être acceptable.
Vous le réinitialisez ensuite pour obtenir une file d'attente vide et libérer la mémoire de la première file d'attente. Quant à la complexité? Je ne suis pas sûr - mais je suppose que c'est O (1).

Code possible:

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

Une autre option consiste à utiliser un simple hack pour obtenir le conteneur sous-jacent std::queue::cet l'appeler clear. Ce membre doit être présent std::queueconformément à la norme, mais l'est malheureusement protected. Le hack ici a été tiré de cette réponse .

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