• Choose a category
• All
• Classic-Fiction

The queue also supports size(), empty() and swap(). See the Standard Library Reference resource on the website for details.

queue Example: A Network Packet Buffer

When two computers communicate over a network, they send information to each other divided up into discrete chunks called packets. The networking layer of the computer’s operating system must pick up the packets and store them as they arrive. However, the computer might not have enough bandwidth to process all of them at once. Thus, the networking layer usually buffers, or stores, the packets until the higher layers have a chance to attend to them. The packets should be processed in the order they arrive, so this problem is perfect for a queue structure. The following is a small PacketBuffer class, with comments explaining the code, that stores incoming packets in a queue until they are processed. It’s a template so that different layers of the networking layer can use it for different kinds of packets, such as IP packets or TCP packets. It allows the client to specify a maximum size because operating systems usually limit the number of packets that can be stored, so as not to use too much memory. When the buffer is full, subsequently arriving packets are ignored.

template

class PacketBuffer

{

public:

// If maxSize is 0, the size is unlimited, because creating

// a buffer of size 0 makes little sense. Otherwise only

// maxSize packets are allowed in the buffer at any one time.

PacketBuffer(size_t maxSize = 0);

// Stores a packet in the buffer.

// Returns false if the packet has been discarded because

// there is no more space in the buffer, true otherwise.

bool bufferPacket(const T& packet);

// Returns the next packet. Throws out_of_range

// if the buffer is empty.

T getNextPacket() throw(std::out_of_range);

protected:

std::queue mPackets;

int mMaxSize;

};

template

PacketBuffer::PacketBuffer(size_t maxSize/* = 0 */)

: mMaxSize(maxSize)

{

}

template

bool PacketBuffer::bufferPacket(const T& packet)

{

if (mMaxSize > 0 && mPackets.size() == mMaxSize) {

// No more space. Drop the packet.

return false;

}

mPackets.push(packet);

return true;

}

template

T PacketBuffer::getNextPacket() throw(std::out_of_range)

{

if (mPackets.empty()) {

throw std::out_of_range("Buffer is empty");

}

// retrieve the head element

T temp = mPackets.front();

// pop the head element

mPackets.pop();

// return the head element

return temp;

}

Code snippet from PacketBuffer\PacketBuffer.h

A practical application of this class would require multiple threads. C++11 provides synchronization classes to allow thread-safe access to shared objects. Without explicit synchronization provided by the programmer, no STL class can be used safely in multiple threads. Synchronization is discussed in Chapter 22. However, here is a quick single-threaded example of the PacketBuffer:

class IPPacket

{

public:

IPPacket(int id) : mID(id) {}

int getID() const { return mID; }

protected:

int mID;

};

int main()

{

PacketBuffer ipPackets(3);

// Add 4 packets

for (int i = 1; i <= 4; ++i) {

if (!ipPackets.bufferPacket(IPPacket(i)))

cout << "Packet " << i << " dropped (queue is full)." << endl;

}

while (true) {

try {

IPPacket packet = ipPackets.getNextPacket();

cout << "Processing packet " << packet.getID() << endl;

} catch (const out_of_range&) {

cout << "Queue is empty." << endl;

break;

}

}

return 0;

}

Code snippet from PacketBuffer\PacketBufferTest.cpp

The output of this program is as follows:

Packet 4 dropped (queue is full).

Processing packet 1

Processing packet 2

Processing packet 3

Queue is empty.

priority_queue

A priority queue is a queue that keeps its elements in sorted order. Instead of a strict FIFO ordering, the element at the head of the queue at any given time is the one with the highest priority. This element could be the oldest on the queue or the most recent. If two elements