bslstl_deque

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on VALUE_TYPE
  • Glossary
  • Memory Allocation
    • bslma-Style Allocators
  • Operations
  • Exceptional Behavior
  • Usage
    • Example 1: Using a deque to Implement a Laundry Queue

Purpose

Provide an STL-compliant deque class.

Classes

• bsl::deque: STL-compliant deque template

Canonical header: bsl_deque.h

See also

bslstl_vector

Description

This component defines a single class template, bsl::deque, implementing the standard sequential container, std::deque, holding a dynamic sequence of values of a template parameter type.

An instantiation of deque is an allocator-aware, value-semantic type whose salient attributes are its size (number of contained elements) and the (ordered) sequence of values the deque contains. If deque is instantiated with a value type that is not value-semantic, then the deque will not retain all of its value-semantic qualities. In particular, if a value type cannot be tested for equality, then a deque containing elements of that type cannot be tested for equality. It is even possible to instantiate deque with a value type that does not have a copy-constructor, in which case the deque will not be copyable.

A deque meets the requirements of a sequential container with random access iterators in section [deque] of the C++ standard. The deque 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 VALUE_TYPE

A deque is a fully Value-Semantic Type (see bsldoc_glossary ) only if the supplied VALUE_TYPE template parameter is fully value-semantic. It is possible to instantiate a deque with a VALUE_TYPE parameter that does not have a full set of value-semantic operations, but then some methods of the container may not be instantiable. The following terminology, adopted from the C++11 standard, is used in the function documentation of deque to describe a function's requirements for the VALUE_TYPE template parameter. These terms are also defined in section [17.6.3.1] of the C++11 standard. Note that, in the context of a deque instantiation, the requirements apply specifically to the deque's entry type, value_type, which is an alias for VALUE_TYPE.

Glossary

Legend
------
'X'    - denotes an allocator-aware container type (e.g., 'deque')
'T'    - 'value_type' associated with 'X'
'A'    - type of the allocator used by 'X'
'm'    - lvalue of type 'A' (allocator)
'p',   - address ('T *') of uninitialized storage for a 'T' within an 'X'
'rv'   - rvalue of type (non-'const') 'T'
'v'    - rvalue or lvalue of type (possibly 'const') 'T'
'args' - 0 or more arguments

The following terms are used to more precisely specify the requirements on template parameter types in function-level documentation.

default-insertable: T has a default constructor. More precisely, T is default-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p)

move-insertable: T provides a constructor that takes an rvalue of type (non-const) T. More precisely, T is move-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p, rv)

copy-insertable: T provides a constructor that takes an lvalue or rvalue of type (possibly const) T. More precisely, T is copy-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p, v)

move-assignable: T provides an assignment operator that takes an rvalue of type (non-const) T.

copy-assignable: T provides an assignment operator that takes an lvalue or rvalue of type (possibly const) T.

emplace-constructible: T is emplace-constructible into X from args means that the following expression is well-formed: allocator_traits<A>::construct(m, p, args)

erasable: T provides a destructor. More precisely, T is erasable from X means that the following expression is well-formed: allocator_traits<A>::destroy(m, p)

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

Memory Allocation

The type supplied as a deque's ALLOCATOR template parameter determines how that deque will allocate memory. The deque template supports allocators meeting the requirements of the C++03 standard, in addition it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma style allocators should use the template's default ALLOCATOR type: The default type for the ALLOCATOR template parameter, bsl::allocator, provides a C++11 standard-compatible adapter for a bslma::Allocator object.

bslma-Style Allocators

If the (template parameter) type ALLOCATOR of a deque instantiation' is bsl::allocator, then objects of that deque type will conform to the standard behavior of a bslma-allocator-enabled type. Such a deque accepts an optional bslma::Allocator argument at construction. If the address of a bslma::Allocator object is explicitly supplied at construction, it is used to supply memory for the deque throughout its lifetime; otherwise, the deque will use the default allocator installed at the time of the deque's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, a deque supplies that allocator's address to the constructors of contained objects of the (template parameter) VALUE_TYPE if it defines the bslma::UsesBslmaAllocator trait.

Operations

This section describes the run-time complexity of operations on instances of deque:

Legend
------
'V'                - (template parameter) 'VALUE_TYPE' of the deque
'a', 'b'           - two distinct objects of type 'deque<V>'
'rv'               - modifiable rvalue of type 'deque<V>'
'n', 'm'           - number of elements in 'a' and 'b', respectively
'i'                - valid index into the deque
'k'                - non-negative integer
'al                - an STL-style memory allocator
'i1', 'i2'         - two iterators defining a sequence of 'V' objects
'il'               - object of type 'std::initializer_list<V>'
'lil'              - length of 'il'
'vt'               - object of type 'VALUE_TYPE'
'rvt'              - modifiable rvalue of type 'VALUE_TYPE'
'p1', 'p2'         - two 'const_iterator's belonging to 'a'
'distance(i1, i2)' - number of elements in the range '[i1 .. i2)'
'minHalf(p1)'      - 'min(distance(a.begin(), p1), distance(p1, a.end()))'
'args'             - 0 or more arguments
 
|-----------------------------------------+-------------------------------|
| Operation                               | Complexity                    |
|=========================================+===============================|
| deque<V> a       (default construction) | O[1]                          |
| deque<V> a(al)                          |                               |
|-----------------------------------------+-------------------------------|
| deque<V> a(b)    (copy construction)    | O[n]                          |
| deque<V> a(b, al)                       |                               |
|-----------------------------------------+-------------------------------|
| deque<V> a(rv)   (move construction)    | O[1] if 'a' and 'rv' use the  |
| deque<V> a(rv, al)                      | same allocator; O[n] otherwise|
|-----------------------------------------+-------------------------------|
| deque<V> a(k)                           | O[k]                          |
| deque<V> a(k, al)                       |                               |
|-----------------------------------------+-------------------------------|
| deque<V> a(k, vt)                       | O[k]                          |
| deque<V> a(k, vt, al)                   |                               |
|-----------------------------------------+-------------------------------|
| deque<V> a(i1, i2)                      | O[distance(i1, i2)]           |
| deque<V> a(i1, i2, al)                  |                               |
|-----------------------------------------+-------------------------------|
| deque<V> a(il)                          | O[lil]                        |
| deque<V> a(il, al)                      |                               |
|-----------------------------------------+-------------------------------|
| a.~deque<V>()   (destruction)           | O[n]                          |
|-----------------------------------------+-------------------------------|
| a.assign(k, vt)                         | O[k]                          |
|-----------------------------------------+-------------------------------|
| a.assign(i1, i2)                        | O[distance(i1, i2)]           |
|-----------------------------------------+-------------------------------|
| a.assign(il)                            | O[lil]                        |
|-----------------------------------------+-------------------------------|
| get_allocator()                         | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.begin(), a.end()                      | O[1]                          |
| a.cbegin(), a.cend()                    |                               |
| a.rbegin(), a.rend()                    |                               |
| a.crbegin(), a.crend()                  |                               |
|-----------------------------------------+-------------------------------|
| a.size()                                | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.max_size()                            | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.resize(k)                             | O[k]                          |
| a.resize(k, vt)                         |                               |
|-----------------------------------------+-------------------------------|
| a.empty()                               | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.reserve(k)                            | O[k]                          |
|-----------------------------------------+-------------------------------|
| a.shrink_to_fit()                       | O[n]                          |
|-----------------------------------------+-------------------------------|
| a[i]                                    | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.at(i)                                 | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.front()                               | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.back()                                | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.push_back(vt)                         | O[1]                          |
| a.push_front(vt)                        |                               |
|-----------------------------------------+-------------------------------|
| a.push_back(rvt)                        | O[1]                          |
| a.push_front(rvt)                       |                               |
|-----------------------------------------+-------------------------------|
| a.pop_back()                            | O[1]                          |
| a.pop_front()                           |                               |
|-----------------------------------------+-------------------------------|
| a.emplace_back(args)                    | O[1]                          |
| a.emplace_front(args)                   |                               |
|-----------------------------------------+-------------------------------|
| a.emplace(p1, args)                     | O[1 + minHalf(p1)]            |
|-----------------------------------------+-------------------------------|
| a.insert(p1, vt)                        | O[1 + minHalf(p1)]            |
|-----------------------------------------+-------------------------------|
| a.insert(p1, rvt)                       | O[1 + minHalf(p1)]            |
|-----------------------------------------+-------------------------------|
| a.insert(p1, k, vt)                     | O[k + minHalf(p1)]            |
|-----------------------------------------+-------------------------------|
| a.insert(p1, i1, i2)                    | O[distance(i1, i2)            |
|                                         |                + minHalf(p1)] |
|-----------------------------------------+-------------------------------|
| a.insert(p1, il)                        | O[lil + minHalf(p1)]          |
|-----------------------------------------+-------------------------------|
| a.erase(p1)                             | O[1 + minHalf(p1)]            |
|-----------------------------------------+-------------------------------|
| a.erase(p1, p2)                         | O[distance(p1, p2)            |
|                                         |  + min(distance(a.begin, p1), |
|                                         |        distance(p2, a.end())] |
|-----------------------------------------+-------------------------------|
| a.swap(b), swap(a, b)                   | O[1] if 'a' and 'b' use the   |
|                                         | same allocator; O[n + m]      |
|                                         | otherwise                     |
|-----------------------------------------+-------------------------------|
| a.clear()                               | O[n]                          |
|-----------------------------------------+-------------------------------|
| a = b;           (copy assignment)      | O[n]                          |
|-----------------------------------------+-------------------------------|
| a = rv;          (move assignment)      | O[1] if 'a' and 'rv' use the  |
|                                         | same allocator; O[n] otherwise|
|-----------------------------------------+-------------------------------|
| a = il;                                 | O[lil]                        |
|-----------------------------------------+-------------------------------|
| a == b, a != b                          | O[n]                          |
|-----------------------------------------+-------------------------------|
| a < b, a <= b, a > b, a >= b            | O[n]                          |
|-----------------------------------------+-------------------------------|

Exceptional Behavior

Since this component is below the BSL STL, we centralize all the exceptional behavior into a bslstl::StdExceptUtil class, which has a dual purpose:

• Remove the dependency of this header on the <exception> header, so that this implementation can offer an exception handler with the native exceptions, and so that all the C-strings may be defined in a single library (bsl) and not in all the translation units including this header.
• Allow installation of exception handlers at a higher level to throw BSL STL exceptions (which differ from the native exceptions) and thus establish a full standard compliance for this component when used as bsl::deque in the BSL STL.

Usage

In this section we show intended usage of this component.

Example 1: Using a deque to Implement a Laundry Queue

Suppose we want to define a class to maintain a process queue of names of customers who are dropping off their laundry at a drop-off laundry service. We can accomplish this by defining a new class characterizing a laundry-process queue that uses bsl::deque in its implementation.

The process queue provides two methods, push and expeditedPush, for inserting names of customers onto the queue. When calling the push method, the customer's name will be inserted at the back of the queue – his laundry will be done after the laundry of customers previously on the queue. The expeditedPush method is reserved for customers who have bribed the merchant for expedited service. When calling the expeditedPush method, the customer's name will be inserted onto the front of the queue – his laundry will be done before customers previously on the queue.

When the workers are ready to do some laundry, they call the next method of the queue, which returns the name of the customer whose laundry is to be done next. For brevity of the usage example, we do not show how customers are track while or after their laundry is being done.

In addition, the laundry queue also provides the find method, which returns a bool to indicate whether a given customer is still in the queue.

First, we declare a class LaundryQueue based on a deque, to store names of customers at a drop-off laundry:

// This `class` keeps track of customers enqueued to have their laundry
// done by a laundromat.
class LaundryQueue {
 
    // DATA
    bsl::deque<bsl::string> d_queue;
 
  public:
    // CREATORS
 
    /// Create a `LaundryQueue` object using the specified
    /// `basicAllocator`.  If `basicAllocator` is not provided, use the
    /// default allocator.
    LaundryQueue(bslma::Allocator *basicAllocator = 0);
 
    // MANIPULATORS
 
    /// Add the specified `customerName` to the back of the laundry
    /// queue.
    void push(const bsl::string& customerName);
 
    /// Add the specified `customerName` to the laundry queue at the
    /// front.
    void expeditedPush(const bsl::string& customerName);
 
    /// Return the name from the front of the queue, removing it from
    /// the queue.  If the queue is empty, return `(* empty *)` which is
    /// not a valid name for a customer.
    bsl::string next();
 
    // ACCESSORS
 
    /// Return `true` if `customerName` is in the queue, and `false`
    /// otherwise.
    bool find(const bsl::string& customerName);
};

Then, we define the implementation of the methods of LaundryQueue

// CREATORS
LaundryQueue::LaundryQueue(bslma::Allocator *basicAllocator)
: d_queue(basicAllocator)
{
    // Note that the allocator is propagated to the underlying `deque`,
    // which will use the default allocator is `0 == basicAllocator`.
}
 
// MANIPULATORS
void LaundryQueue::push(const bsl::string& customerName)
{
    d_queue.push_back(customerName);     // note constant time
}
 
void LaundryQueue::expeditedPush(const bsl::string& customerName)
{
    d_queue.push_front(customerName);    // note constant time
}
 
bsl::string LaundryQueue::next()
{
    if (d_queue.empty()) {
        return "(* empty *)";
    }
 
    bsl::string ret = d_queue.front();   // note constant time
 
    d_queue.pop_front();                 // note constant time
 
    return ret;
}
 
// ACCESSORS
bool LaundryQueue::find(const bsl::string& customerName)
{
    // Note `d_queue.empty() || d_queue[0] == d_queue.front()`
 
    for (size_t i = 0; i < d_queue.size(); ++i) {
        if (customerName == d_queue[i]) {    // note '[]' is constant time
            return true;
        }
    }
 
    return false;
}