bslstl_queue

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on CONTAINER
    • Required Types
    • Required Methods, Free Operators, and Free Functions
  • Requirements on VALUE
    • VALUE and CONTAINER::value_type
  • Memory Allocation
  • Usage
    • Example 1: Messages Queue

Purpose

Provide container adapter class template queue.

Classes

• bsl::queue: class template of a first-in-first-out data structure

Canonical header: bsl_queue.h

See also

bslstl_priorityqueue, bslstl_stack

Description

This component defines a class template, bsl::queue, holding a container (of a parameterized type CONTAINER containing elements of another parameterized type VALUE), and adapting it to provide a first-in-first-out queue data structure.

An instantiation of queue is an allocator-aware, value-semantic type whose salient attributes are its size (number of elements held) and the sequence of values (of held elements) in the order that they were pushed into the queue. If queue is instantiated with a parameterized type VALUE that is not itself value-semantic, then it will not retain all of its value-semantic qualities.

A queue meets the requirements of a container adaptor as described in the C++ standard [queue]. The queue implemented here adheres to the C++11 standard when compiled with a C++11 compiler, and makes the best approximation when compiled with a C++03 compiler. In particular, for C++03 we emulate move semantics, but limit forwarding (in emplace) to const lvalues, and make no effort to emulate noexcept or initializer-lists.

Requirements on CONTAINER

The bsl::queue adapter can accept for its (optional) CONTAINER template parameter bsl::deque (the default), bsl::vector, or other container classes that support the following types and methods.

Required Types

• value_type
• reference
• const_reference
• size_type
• allocator_type (if any queue constructor taking an allocator is used)

Required Methods, Free Operators, and Free Functions

• void push_back(const value_type&) (and variant taking rvalue reference)
• void pop_front()
• reference front()
• reference back()
• bool empty() const
• size_type size() const
• const_reference front() const
• const_reference back() const
• emplace_back
• copy-assignment and move-assignment operators
• free ==, !=, <, >, <=, >= operators
• free swap function (found via ADL with std::swap in the lookup set)

Requirements on VALUE

The following term is used to more precisely specify the requirements on template parameter types in function-level documentation:

equality-comparable: The type provides an equality-comparison operator that defines an equivalence relationship and is both reflexive and transitive.

VALUE and CONTAINER::value_type

When the CONTAINER template parameter is omitted the VALUE template parameter specifies the value_type of bsl::vector, the default container type. The VALUE template has no other role.

For C++17 and later, the behavior is undefined unless:

true == bsl::is_same<VALUE, typename CONTAINER::value_type>::value

Prior to C++17, CONTAINER::value_type determines the contained value type and VALUE is simply ignored. The resulting code may work with instances of VALUE (e.g., VALUE is convertible to CONTAINER::value_type) or not (compiler errors).

Memory Allocation

The type supplied as ALLOCATOR template parameter in some of queue constructors determines how the held container (of parameterized CONTAINER) will allocate memory. A queue supports allocators meeting the requirements of the C++11 standard [allocator.requirements] as long as the held container does. In addition it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma style allocators should use bsl::allocator as the ALLOCATOR template parameter, providing a C++11 standard-compatible adapter for a bslma::Allocator object.

Usage

In this section we show intended use of this component.

Example 1: Messages Queue

In this example, we will use the bsl::queue container adapter to implement a message processor in a server program that receives and displays messages from clients.

Suppose we want to write a server program that has two threads: one thread (receiving thread) receives messages from clients, passing them to a message processor; the other thread (processing thread) runs the message processor, printing the messages to the console in the same order as they were received. To accomplish this task, we can use bsl::queue in the message processor to buffer received, but as yet unprinted, messages. The message processor pushes newly received messages onto the queue in the receiving thread, and pops them off the queue in the processing thread.

First, we define a Message type:

struct Message {
    int         d_msgId;  // message identifier given by client
    const char *d_msg_p;  // message content (C-style string, not owned)
};

Then, we define the class MessageProcessor, which provides methods to receive and process messages:

class MessageProcessor {
    // This class receives and processes messages from clients.

Here, we define a private data member of bsl::queue<Message> type, which is an instantiation of bsl::queue that uses Message for its VALUE (template parameter) type and (by default) bsl::deque<Message> for its CONTAINER (template parameter) type:

    // DATA
    bsl::queue<Message> d_msgQueue;  // queue holding received but
                                     // unprocessed messages
    // ...
 
  public:
    // CREATORS
    explicit MessageProcessor(bslma::Allocator *basicAllocator = 0);
        // Create a message processor object.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.
 
    // MANIPULATORS
    void receiveMessage(const Message &message);
        // Enqueue the specified 'message' onto this message processor.
 
    void processMessages(int verbose);
        // Dequeue all messages currently contained by this processor,
        // and print them to the console if the specified 'verbose' flag
        // is not 0.
};

Next, we implement the MessageProcessor constructor:

MessageProcessor::MessageProcessor(bslma::Allocator *basicAllocator)
: d_msgQueue(basicAllocator)
{
}

Notice that we pass to the contained d_msgQueue object the bslma::Allocator* supplied to the MessageProcessor at construction.

Now, we implement the receiveMessage method, which pushes the given message onto the queue object:

void MessageProcessor::receiveMessage(const Message &message)
{
    // ... (some synchronization)
 
    d_msgQueue.push(message);
 
    // ...
}

Finally, we implement the processMessages method, which pops all messages off the queue object:

void MessageProcessor::processMessages(int verbose)
{
    // ... (some synchronization)
 
    while (!d_msgQueue.empty()) {
        const Message& message = d_msgQueue.front();
        if (verbose) {
            printf("Msg %d: %s\n", message.d_msgId, message.d_msg_p);
        }
        d_msgQueue.pop();
    }
 
    // ...
}

Note that the sequence of messages popped from the queue will be in exactly the same order in which they were pushed, due to the first-in-first-out property of the queue.