bslstl_stack

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
  • bslma-Style Allocators
  • Operations
  • Usage
    • Example 1: Household Chores To Do List

Purpose

Provide an STL-compliant stack class.

Classes

• bsl::stack: STL-compliant stack template

Canonical header: bsl_stack.h

See also

bslstl_deque, bslstl_vector, bslstl_list, bslstl_queue, bslstl_priorityqueue

Description

This component defines a single class template, bsl::stack, a container adapter that takes an underlying container and provides a stack interface which the user accesses primarily through push, pop, and top operations. A deque (the default), vector, or list may be used, but any container which supports push_back, pop_back , back, and size, plus a template specialization uses_allocator::type, may be used.

A stack meets the requirements of a container adaptor as described in the C++ standard [stack]. The stack 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::stack adapter can accept for its (optional) CONTAINER template parameter bsl::deque (the default), bsl::vector, bsl::list, or other container classes that support the following types and methods.

Required Types

• value_type
• reference
• const_reference
• size_type
• allocator_type (if any stack 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_back()
• reference back()
• size_type size() 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

No memory allocator template arg is directly supplied to this class, the allocator type used is the allocator specified for the container class. Some functions of this template only exist if type CONTAINER::allocator_type exists, and if it does exist it is assumed to be the allocator type used by CONTAINER, and that CONTAINER supports constructors of this type.

bslma-Style Allocators

The constructors of this class take, as optional parameters, allocators of the object's parameterized CONTAINER::allocator_type type, and allocators of this type are propagated to all constructors of the underlying container. In the case of container types bsl::deque (the default type), bsl::vector, and bsl::list, CONTAINER::allocator_type is bsl::allocator which is implicitly convertible from bslma::Allocator *, and which can be converted to a bslma::Allocator * through the mechanism accessor.

Hence if the underlying container takes bsl::allocator, then the stack object can take bslma::Allocator *s to supply memory allocation. If no allocator is specified, allocator() is used, which winds up using bslma::Default::allocator(0).

Operations

Below is a list of public methods of the bsl::stack class that effectively forward their implementations to corresponding operations in the held container (referenced as c) which is here assumed to be either bsl::deque, or bsl::vector, or bsl::list.

Legend
------
'C'             - (template parameter) type 'CONTAINER' of the stack
'V'             - (template parameter) type 'VALUE'     of the stack
's', 't'        - two distinct objects of type 'stack<V, C>'
 
'nc'            - number of elements in container 'c'
'n', 'm'        - number of elements in 's' and 't', respectively
'al'            - STL-style memory allocator
'v'             - an object of type 'V'
 
+----------------------------------------------------+--------------------+
| Note: the following estimations of operation complexity assume the      |
| underlying container is a 'bsl::deque', 'bsl::vector', or 'bsl::list'.  |
+----------------------------------------------------+--------------------+
| Operation                                          | Complexity         |
+====================================================+====================+
| stack<V, C> s;    (default construction)           | O(1)               |
| stack<V, C> s(al);                                 |                    |
+----------------------------------------------------+--------------------+
| stack<V, C> s(c);                                  | O(nc)              |
| stack<V, C> s(c, al);                              |                    |
+----------------------------------------------------+--------------------+
| stack<V, C> s(t);                                  | O(n)               |
| stack<V, C> s(t, al);                              |                    |
+----------------------------------------------------+--------------------+
| s.~stack(V, C>(); (destruction)                    | O(n)               |
+----------------------------------------------------+--------------------+
| s = t;          (assignment)                       | O(n)               |
+----------------------------------------------------+--------------------+
| s.push(v)                                          | O(1)               |
+----------------------------------------------------+--------------------+
| s.pop()                                            | O(1)               |
+----------------------------------------------------+--------------------+
| s.top()                                            | O(1)               |
+----------------------------------------------------+--------------------+
| s == t, s != t                                     | O(n)               |
+---------------------------------------------------+--------------------+
| s < t, s <= t, s > t, s >= t                       | O(n)               |
+----------------------------------------------------+--------------------+
| s.swap(t), swap(s,t)                               | depends on the     |
|                                                    | container; for     |
|                                                    | deque, vector, and |
|                                                    | list:              |
|                                                    | O(1) if 's' and    |
|                                                    | 't' use the same   |
|                                                    | allocator,         |
|                                                    | O(n + m) otherwise |
+----------------------------------------------------+--------------------+
| s.size()                                           | O(1) if 'C' is     |
|                                                    | deque or vector    |
+----------------------------------------------------+--------------------+
| s.empty()                                          | O(1)               |
+----------------------------------------------------+--------------------+

Usage

In this section we show intended use of this component.

Example 1: Household Chores To Do List

Suppose someone wants to keep track of chores their partner has asked them to do. Over the years, they have noticed that their partner generally wants the most recently requested task done first. If the partner has a new task in mind that is low-priority, they will avoid asking for it until higher priority tasks are finished. When they have finished all tasks, they report to their partner that they are ready for more.

First, we define the class implementing the to-do list.

class ToDoList {
    // DATA
    bsl::stack<const char *> d_stack;
 
  public:
    // MANIPULATORS
 
    /// Add the specified `task`, a string describing a task, to the
    /// list.  Note the lifetime of the string referred to by `task`
    /// must exceed the lifetime of the task in this list.
    void enqueueTask(const char *task);
 
    /// Remove the current task from the list.  Return `true` if a task
    /// was removed and it was the last task on the list, and return
    /// `false` otherwise.
    bool finishTask();
 
    // ACCESSORS
 
    /// Return the string representing the current task.  If there
    /// is no current task, return the string "<EMPTY>", which is
    /// not a valid task.
    const char *currentTask() const;
};
 
// MANIPULATORS
void ToDoList::enqueueTask(const char *task)
{
    d_stack.push(task);
}
 
bool ToDoList::finishTask()
{
    if (!d_stack.empty()) {
        d_stack.pop();
 
        return d_stack.empty();
    }
 
    return false;
};
 
// ACCESSORS
const char *ToDoList::currentTask() const
{
    if (d_stack.empty()) {
        return "<EMPTY>";
    }
 
    return d_stack.top();
}

Then, create an object of type ToDoList.

ToDoList toDoList;

Next, a few tasks are requested:

toDoList.enqueueTask("Change the car's oil.");
toDoList.enqueueTask("Pay the bills.");

Then, they watch the Yankee's game on TV. Upon returning to the list they consult the list to see what task is up next:

assert(!strcmp("Pay the bills.", toDoList.currentTask()));

Next, they see that they have to pay the bills. When the bills are finished, they flush that task from the list:

assert(false == toDoList.finishTask());

Then, they consult the list for the next task.

assert(!strcmp("Change the car's oil.", toDoList.currentTask()));

Next, they see that they have to change the car's oil. Before they can get started, another request comes in:

toDoList.enqueueTask("Get some hot dogs.");
assert(!strcmp("Get some hot dogs.", toDoList.currentTask()));

Then, they drive the car to the convenience store and picks up some hot dogs and buns. Upon returning home, they give the hot dogs to their partner, update the list, and consult it for the next task.

assert(false == toDoList.finishTask());
assert(!strcmp("Change the car's oil.", toDoList.currentTask()));

Next, they finish the oil change, update the list, and consult it for the next task.

assert(true == toDoList.finishTask());
assert(!strcmp("<EMPTY>", toDoList.currentTask()));

Finally, their partner has now been informed that everything is done, and they make another request:

toDoList.enqueueTask("Clean the rain gutters.");