std :: queue iteration

78

Ich muss noch einmal iterieren std::queue. www.cplusplus.com sagt:

Wenn für eine bestimmte Warteschlangenklasse keine Containerklasse angegeben ist, wird standardmäßig die Standard-Deque der Containerklassenvorlage verwendet.

Kann ich also irgendwie zur zugrunde liegenden Deque der Warteschlange gelangen und darüber iterieren?

Jackhab
quelle

Antworten:

74

Wenn Sie über a iterieren müssen, benötigen queueSie mehr als eine Warteschlange. Bei den Standard-Containeradaptern geht es darum, eine minimale Schnittstelle bereitzustellen. Wenn Sie auch eine Iteration durchführen müssen, verwenden Sie stattdessen einfach eine Deque (oder Liste).

CB Bailey
quelle
127
Obwohl ich weiß, was Sie sagen, mochte ich diese Formulierung "etwas mehr als eine Warteschlange" immer nicht. Eine Warteschlange mit Aufzählung ist immer noch eine Warteschlange ... Beobachten Sie auch, wie dequedie Aufzählung nur völlig willkürlich unterstützt wird. Sie könnten genauso gut argumentieren, dass dequedies genauso puristisch sein sollte queueund die Iteration nicht unterstützen sollte, und wenn Sie es iterieren möchten, möchten Sie etwas "mehr"; zB a deque_enumerable. Es ist jedoch ein rutschiger Hang, und mein persönliches Gefühl ist, dass queuedies die Aufzählung an erster Stelle hätte unterstützen sollen.
Roman
7
@romkyns: Wäre es besser, wenn ich es umformulieren würde: "Sie benötigen etwas mit einer reichhaltigeren Schnittstelle als die queueSchnittstelle, also sollten Sie ein Objekt mit einer geeigneten Schnittstelle auswählen." Ob es queueIhnen gefällt oder nicht, die Iteration ist nicht Teil der Benutzeroberfläche. Wenn Sie also eine Iteration wünschen, müssen Sie etwas anderes auswählen.
CB Bailey
10
Weil mein Anwendungsfall eine Warteschlange erfordert, ich sie aber für Debug- und Protokollierungszwecke ausgeben muss. Es ist im Allgemeinen nicht konstruktiv anzunehmen, dass Poster nicht wissen, was sie tun.
EML
5
@RomanStarkov - Es scheint möglich gewesen queuezu sein, Vorwärtsiteratoren zu unterstützen, aber keine Rückwärtsiteratoren, ohne eine vernünftige Implementierung zu belasten, die mir einfällt . Ich denke, CS101-Profis haben sich vielleicht darüber beschwert ...
TED
4
@ EML - Mein Bedürfnis genau. Irgendwie werden Debugging-Anforderungen oft vernachlässigt, da sie nur von
Randwahnsinnigen
37

Obwohl ich anderen zustimme, dass die direkte Verwendung eines iterierbaren Containers eine bevorzugte Lösung ist, möchte ich darauf hinweisen, dass der C ++ - Standard eine ausreichende Unterstützung für eine Do-it-yourself-Lösung garantiert, falls Sie dies aus irgendeinem Grund wünschen.

Sie können nämlich von std::queueseinem geschützten Mitglied erben und verwenden, Container c;um auf begin () und end () des zugrunde liegenden Containers zuzugreifen (vorausgesetzt, solche Methoden sind dort vorhanden). Hier ist ein Beispiel, das in VS 2010 funktioniert und mit ideone getestet wurde :

#include <queue>
#include <deque>
#include <iostream>

template<typename T, typename Container=std::deque<T> >
class iterable_queue : public std::queue<T,Container>
{
public:
    typedef typename Container::iterator iterator;
    typedef typename Container::const_iterator const_iterator;

    iterator begin() { return this->c.begin(); }
    iterator end() { return this->c.end(); }
    const_iterator begin() const { return this->c.begin(); }
    const_iterator end() const { return this->c.end(); }
};

int main() {
    iterable_queue<int> int_queue;
    for(int i=0; i<10; ++i)
        int_queue.push(i);
    for(auto it=int_queue.begin(); it!=int_queue.end();++it)
        std::cout << *it << "\n";
    return 0;
}
Alexey Kukanov
quelle
4
@Deqing: richtig; Das Iterieren über den zugrunde liegenden Container wäre jedoch nicht in der Prioritätsreihenfolge.
Alexey Kukanov
1
Warum eine neue Klasse neu definieren und nicht dequedirekt verwenden?!
Alexis Wilke
@ Deqing siehe auch diese Frage
Peter K
@AlexeyKukanov Dies ist keine Prioritätswarteschlange, sondern nur eine normale FIFO-Warteschlange. Dies ist also die richtige Iterationsreihenfolge
Erik Brendel,
@ErikBrendel, das war eine Antwort auf einen jetzt gelöschten Kommentar, in dem gefragt wurde, ob dieselbe Technik mit priority_queue verwendet werden kann.
Alexey Kukanov
14

Sie können die ursprüngliche Warteschlange in einer temporären Warteschlange speichern. Dann machen Sie einfach Ihren normalen Pop in der temporären Warteschlange, um die ursprüngliche zu durchlaufen, zum Beispiel:

queue tmp_q = original_q; //copy the original queue to the temporary queue

while (!tmp_q.empty())
{
    q_element = tmp_q.front();
    std::cout << q_element <<"\n";
    tmp_q.pop();
} 

Am Ende ist tmp_q leer, aber die ursprüngliche Warteschlange bleibt unberührt.

Ich Idiot
quelle
3
std::queuescheint keine .top()Methode zu haben
Killzone Kid
1
@ KillzoneKid Das ist richtig, denn std::queuedie richtige Methode ist.front()
Paul Stelian
4

Eine indirekte Lösung kann darin bestehen, stattdessen std :: deque zu verwenden. Es unterstützt alle Operationen der Warteschlange und Sie können sie einfach mit iterieren for(auto& x:qu). Es ist viel effizienter als die Verwendung einer temporären Kopie der Warteschlange für die Iteration.

Tejas Patil
quelle
2

Warum nicht einfach eine Kopie der Warteschlange erstellen, über die Sie iterieren möchten, und Elemente einzeln entfernen und sie dabei ausdrucken? Wenn Sie beim Iterieren mehr mit den Elementen tun möchten, ist eine Warteschlange die falsche Datenstruktur.

Futter
quelle
6
Äh, nein. Das Kopieren und dann das Zerstören einer Warteschlange ist weitaus aufwändiger als nötig. Deshalb wurden Iteratoren erfunden.
Mac
1
Einfacher: Leere Warteschlange erstellen. Pop jedes Element aus Ihrer Hauptwarteschlange, bis es leer ist, verarbeiten Sie es wie gewünscht und schieben Sie es in die leere Warteschlange. Wenn Sie fertig sind, stellen Sie die Hauptwarteschlange so ein, dass sie der leeren Warteschlange entspricht. Funktioniert auch für priority_queue. Vorsichtsmaßnahme: Nicht threadsicher, wenn ein anderer Thread gleichzeitig versucht, auf die Warteschlange zuzugreifen. Wenn Ihr Original einem Heap zugewiesen wurde (erstellt über malloc/ new), stellen Sie sicher, dass free/ deleteit vorhanden ist , da sonst Speicherplatz verloren geht.
Darrel Hoffman
-1: Ich habe tatsächlich eine zu niedrige Framerate für SEHR kleine Warteschlangen, die ich kopiere (ich bekomme nicht 60 FPS, weil solche Bilder jeden Frame mit SEHR wenigen Objekten kopieren - etwas, das meine GPU mit mehr als 300 FPS unterstützen sollte mit deaktiviertem VSync). Ich brauche einen Weg, um es zu wiederholen, ohne zu kopieren
Paul Stelian
0

Während die Antwort von Alexey Kukanov effizienter sein kann, können Sie eine Warteschlange auch auf ganz natürliche Weise durchlaufen, indem Sie jedes Element von der Vorderseite der Warteschlange entfernen und dann nach hinten verschieben:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    //populate queue
    queue<int> q;
    for (int i = 0; i < 10; ++i) q.push(i);

    // iterate through queue
    for (size_t i = 0; i < q.size(); ++i) {
        int elem = std::move(q.front());
        q.pop();
        elem *= elem;
        q.push(std::move(elem));
    }

    //print queue
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
}

Ausgabe:

0 1 4 9 16 25 36 49 64 81 
Vaelus
quelle
-1

Kurzum: Nein.

Es gibt einen Hack, verwenden Sie den Vektor als unterlegten Container, geben Sie also queue::fronteine gültige Referenz zurück und konvertieren Sie ihn in einen Zeiger und eine Iteration bis <=queue::back

Dewfy
quelle
2
Sie können deque auch direkt verwenden - das enthält alle erforderlichen Methoden als Warteschlange, unterstützt aber auch die Iteration
Dewfy
-1

Ich benutze so etwas. Nicht sehr raffiniert, sollte aber funktionieren.

    queue<int> tem; 

    while(!q1.empty()) // q1 is your initial queue. 
    {
        int u = q1.front(); 

        // do what you need to do with this value.  

        q1.pop(); 
        tem.push(u); 
    }


    while(!tem.empty())
    {
        int u = tem.front(); 
        tem.pop(); 
        q1.push(u); // putting it back in our original queue. 
    }

Es wird funktionieren, denn wenn Sie etwas aus q1 entfernen und in tem verschieben, wird es das erste Element von tem. Am Ende wird tem also eine Nachbildung von q1.

shamiul97
quelle
Diese Lösung ist sehr problematisch, da sie die Warteschlange während der Iteration ändert. Stellen Sie sich vor, was passieren würde, wenn Sie es in einem Multithread-Programm verwenden oder wenn Sie die Iteration in der Mitte stoppen.
Jackhab
@ Jackhab danke. Du hast recht. Das könnte ein Problem sein. Wir könnten jedoch Semaphor oder Mutex verwenden, um dieses Problem zu lösen (wie ich es in meiner Betriebssystemzuweisung von IPC und pthread tue).
Shamiul97
-2

Wenn Sie eine Warteschlange iterieren müssen ... ist die Warteschlange nicht der Container, den Sie benötigen.
Warum hast du eine Warteschlange ausgewählt?
Warum nimmst du nicht einen Container, über den du iterieren kannst?


1.Wenn Sie eine Warteschlange auswählen, möchten Sie einen Container in eine Warteschlangenschnittstelle einbinden: - Front - Back - Push - Pop - ...

Wenn Sie auch iterieren möchten, hat eine Warteschlange eine falsche Schnittstelle. Eine Warteschlange ist ein Adapter, der eine eingeschränkte Teilmenge des ursprünglichen Containers bereitstellt

2. Die Definition einer Warteschlange ist ein FIFO und per Definition ist ein FIFO nicht iterierbar

TimW
quelle
36
Ich bin nicht der OP, aber hier sind meine Antworten, falls jemand neugierig ist: 1) Ich habe eine Warteschlange ausgewählt, weil ich eine Warteschlange möchte. Ich möchte an einem Ende in die Warteschlange und am anderen Ende aus der Warteschlange aussteigen. Ist das nicht eine vernünftige Wahl? 2) Es ist nicht offensichtlich, dass eine "Warteschlange" nicht aufzählbar ist und welche Struktur stattdessen verwendet werden soll. Ihre Antwort wäre hilfreicher gewesen, wenn Sie erklärt hätten, welchen Container Sie stattdessen verwenden sollten.
Roman Starkov
-2

std::queueist ein Containeradapter, und Sie können den verwendeten Container angeben (standardmäßig wird a verwendet deque). Wenn Sie darüber hinaus Funktionen im Adapter benötigen, verwenden Sie einfach einen dequeoder einen anderen Container direkt.

Johnmacd
quelle
4
Obwohl Ihre Antwort korrekt ist, war dies absolut nicht erforderlich, da diese 2 Jahre alte Frage bereits zwei Antworten enthält, die genau dasselbe sagen (wobei eine davon die akzeptierte Antwort ist).
Christian Rau