15.7.3. priority_queue Adapter

Class priority_queue (from header <queue>) provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure. By default, a priority_queue’s elements are stored in a vector. When elements are added to a priority_queue, they’re inserted in priority order, such that the highest-priority element (i.e., the largest value) will be the first element removed from the priority_queue. This is usually accomplished by arranging the elements in a data structure called a heap (not to be confused with the heap for dynamically allocated memory) that always maintains the largest value (i.e., highest-priority element) at the front of the data structure. We use the Standard Library’s heap algorithms in Section 16.3.12. The comparison of elements is performed with comparator function object less<T> by default, but you can supply a different comparator.

There are several common priority_queue operations. Function push inserts an element at the appropriate location based on priority order of the priority_queue (implemented by calling function push_back of the underlying container, which then reorders the elements in priority order. Function pop removes the highest-priority element of the priority_queue (implemented by calling function pop_back of the underlying container after removing the top element of the heap). top gets a reference to the top element of the priority_queue (implemented by calling function front of the underlying container). empty determines whether the priority_queue is empty (implemented by calling function empty of the underlying container). size gets the number of elements in the priority_queue (implemented by calling function size of the underlying container).

Figure 15.21 demonstrates the priority_queue adapter class. Line 9 instantiates a priority_queue that stores double values and uses a vector as the underlying data structure. Lines 12–14 use function push to add elements to the priority_queue. The while statement in lines 19–23 uses function empty (available in all containers) to determine whether the priority_queue is empty (line 19). While there are more elements, line 21 uses priority_queue function top to retrieve the highest-priority element (i.e., the largest value) in the priority_queue for output. Line 22 removes the highest-priority element in the priority_queue with function pop (available in all adapter classes).

Click here to view code image

 1   // Fig. 15.21: fig15_21.cpp
 2   // Standard Library priority_queue adapter class.
 3   #include <iostream>
 4   #include <queue> // priority_queue adapter definition
 5   using namespace std;
 6
 7   int main()
 8   {
 9      priority_queue< double > priorities; // create priority_queue
10
11      // push elements onto priorities
12      priorities.push( 3.2 );         
13      priorities.push( 9.8 );         
14      priorities.push( 5.4 );         
15
16      cout << "Popping from priorities: ";
17
18      // pop element from priority_queue
19      while ( !priorities.empty() )
20      {
21         cout << priorities.top() << ' '; // view top element
22         priorities.pop(); // remove top element             
23      } // end while
24
25      cout << endl;
26   } // end main

Popping from priorities: 9.8 5.4 3.2

Fig. 15.21. Standard Library priority_queue adapter class.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.147.84.62