//: C07:PriorityQueue7.cpp
// A priority queue that will hand you a vector
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <queue>
using namespace std;
template<class T, class Compare>
class PQV {
vector<T> v;
Compare comp;
public:
// Don't need to call make_heap(); it's empty:
PQV(Compare cmp = Compare()) : comp(cmp) {}
void push(const T& x) {
// Put it at the end:
v.push_back(x);
// Re-adjust the heap:
push_heap(v.begin(), v.end(), comp);
}
void pop() {
// Move the top element to the last position:
pop_heap(v.begin(), v.end(), comp);
// Remove that element:
v.pop_back();
}
const T& top() { return v.front(); }
bool empty() const { return v.empty(); }
int size() const { return v.size(); }
typedef vector<T> TVec;
TVec vector() {
TVec r(v.begin(), v.end());
// It’s already a heap
sort_heap(r.begin(), r.end(), comp);
// Put it into priority-queue order:
reverse(r.begin(), r.end());
return r;
}
};
int main() {
PQV<int, less<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
const vector<int>& v = pqi.vector();
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, " "));
cout << "\n-----------\n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~
The PQV class template follows the same form as the STL’s priority_queue, but has the additional member vector( ), which creates a new vector that’s a copy of the one in PQV (which means that it’s already a heap). It then sorts that copy (leaving PQV’s vector untouched), and reverses the order so that traversing the new vector produces the same effect as popping the elements from the priority queue.
You may observe that the approach of deriving from priority_queue used in PriorityQueue4.cpp could be used with the above technique to produce more succinct code:
//: C07:PriorityQueue8.cpp
// A more compact version of PriorityQueue7.cpp
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <queue>
using namespace std;
template<class T>
class PQV : public priority_queue<T> {
public:
typedef vector<T> TVec;
TVec vector() {
TVec r(c.begin(), c.end());
// c is already a heap
sort_heap(r.begin(), r.end(), comp);
// Put it into priority-queue order:
reverse(r.begin(), r.end());
return r;
}
};
int main() {
PQV<int> pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
const vector<int>& v = pqi.vector();
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, " "));
cout << "\n-----------\n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~
The brevity of this solution makes it the simplest and most desirable, plus it’s guaranteed that the user will not have a vector in the unsorted state. The only potential problem is that the vector( ) member function returns the vector<T> by value, which might cause some overhead issues with complex values of the parameter type T.
Holding bits
Because C was a language that purported to be "close to the hardware," many have found it dismaying that there was no native binary representation for numbers. Decimal, of course, and hexadecimal (tolerable only because it’s easier to group the bits in your mind), but octal? Ugh. Whenever you read specs for chips you’re trying to program, they don’t describe the chip registers in octal or even hexadecimal—they use binary. And yet C won’t let you say 0b0101101, which is the obvious solution for a language close to the hardware.
Although there’s still no native binary representation in C++, things have improved with the addition of two classes: bitset and vector<bool>, both of which are designed to manipulate a group of on-off values.[100] The primary differences between these types are:
1.Each bitset holds a fixed number of bits. You establish the quantity of bits in the bitset template argument. The vector<bool> can, like a regular vector, expand dynamically to hold any number of bool values.
2.The bitset template is explicitly designed for performance when manipulating bits, and is not a "regular" STL container. As such, it has no iterators. The number of bits, being a template parameter, is known at compile time and allows the underlying integral array to be stored on the runtime stack. The vector<bool> container, on the other hand, is a specialization of a vector and so has all the operations of a normal vector—the specialization is just designed to be space efficient for bool.
There is no trivial conversion between a bitset and a vector<bool>, which implies that the two are for very different purposes. Furthermore, neither is a traditional "STL container." The bitset template class has an interface for bit-level operations and in no way resembles the STL containers we’ve discussed up to this point. The vector<bool> specialization of vector is similar to an STL-like container, but it differs as discussed below.
bitset<n>
The template for bitset accepts an unsigned integral template argument that is the number of bits to represent. Thus, bitset<10> is a different type than bitset<20>, and you cannot perform comparisons, assignments, and so on between the two.
A bitset provides the most commonly used bitwise operations in an efficient form. However, each bitset is implemented by logically packing bits in an array of integral types (typically unsigned longs, which contain at least 32 bits). In addition, the only conversion from a bitset to a numerical value is to an unsigned long (via the function to_ulong( )).
100
Chuck designed and provided the original reference implementations for bitset and also bitstring, the precursor to vector<bool>, while an active member of the C++ standards committee in the early 1990s.