Verwenden der STL-Prioritätswarteschlange in C++

1. Verwenden von std::priority_queue zur Deklaration einer Prioritäts-Warteschlange in C++
2. Verwendung des Template-Arguments zur Angabe der Ordnungsfunktion in C++
3. Verwendung des benutzerdefinierten Komparators zum Festlegen der Elementreihenfolge in C++

In diesem Artikel werden mehrere Methoden zur Verwendung der STL-Prioritätswarteschlange in C++ veranschaulicht.

Verwenden von std::priority_queue zur Deklaration einer Prioritäts-Warteschlange in C++

Die Klasse std::priority_queue ist ein Container-Adapter, der eine Queue implementiert, aus der die Elemente nach ihrer Priorität gelesen werden. Beachten Sie, dass priority_queue intern jeden Sequenzcontainer für Elemente verwenden kann und der Benutzer den bevorzugten als zweiten Template-Parameter übergeben kann. Wird letzterer Parameter nicht angegeben, wird standardmäßig der Container vector verwendet.

Die Elemente von priority_queue werden mit den gleichen Funktionen wie der Container queue manipuliert. Die Memberfunktion push fügt ein neues Element in die Warteschlange ein und die Funktion top greift auf das oberste Element zu. Diese beiden Funktionen werden in der Funktion printQueue verwendet, um Elemente in den Stream cout auszugeben.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  for (int n : vec1) q1.push(n);

  printQueue(q1);

  return EXIT_SUCCESS;
}

Ausgabe:

8, 7, 6, 5, 3, 1,

Verwendung des Template-Arguments zur Angabe der Ordnungsfunktion in C++

Die Priorität für jedes Element wird mit Hilfe der Vergleichsfunktion bestimmt, die der Benutzer optional angeben kann. Andernfalls wird standardmäßig die absteigende Reihenfolge gewählt. Wir können die priority_queue aus dem vorherigen Beispielcode in umgekehrter Reihenfolge erstellen, indem wir das Funktionsobjekt std::greater als dritten Template-Parameter verwenden. Beachten Sie, dass ein neuer Warteschlangencontainer mit dem bereichsbasierten Konstruktor initialisiert wird.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  std::priority_queue<int, vector<int>, std::greater<>> q2(vec1.begin(),
                                                           vec1.end());
  printQueue(q2);

  return EXIT_SUCCESS;
}

Ausgabe:

1, 3, 5, 6, 7, 8,

Verwendung des benutzerdefinierten Komparators zum Festlegen der Elementreihenfolge in C++

Zuerst definieren wir einen Vektor von Strings, der verwendet wird, um eine priority_queue zu initialisieren. Als nächstes wird ein Lambda-Ausdruck definiert, um die Komparatorfunktion zu bilden. Letzteres vergleicht zwei Strings nach Länge. Jetzt können wir ein priority_queue-Objekt mit drei Vorlagenparametern deklarieren, die den Elementtyp, den zugrunde liegenden Containertyp bzw. die Vergleichsfunktion angeben. Der bereichsbasierte Konstruktor wird verwendet, um den Inhalt der Warteschlange zu initialisieren.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  vector vec2 = {"porro", "quisquam", "est", "qui", "dolorem", "ipsum", "quia"};
  auto compFunc = [](const string& s1, const string& s2) {
    return s1.length() < s2.length();
  };

  std::priority_queue<string, vector<string>, decltype(compFunc)> q3(
      vec2.begin(), vec2.end(), compFunc);

  printQueue(q3);

  return EXIT_SUCCESS;
}

Ausgabe:

quisquam, dolorem, ipsum, porro, quia, qui, est,