bdlc_queue

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Abstract Representation
  • Performance
  • Usage
    • Example 1: Basic Usage

Purpose

Provide an in-place double-ended queue of T values.

Deprecated:

Use bsl::deque instead.

Classes

• bdlc::Queue: memory manager for in-place queue of T values

Description

This component implements an efficient, in-place, indexable, double-ended queue of T values, where T is a templatized, user-defined type. The functionality of a bdlc::Queue is relatively rich; it is almost a proper superset of a vector, with efficient implementations of front, back, pushFront, and popBack methods added. However, the queue does not provide a data method (yielding direct access to the underlying memory), because its internal organization is not array-like.

Typical usage involves pushing (appending) values to the back of the queue, popping (removing) values from the front of the queue, and retrieving (operator[]) values from a specified index; unlike the O[n] runtime cost for an insert(0, v), however, a pushFront has a constant average-case cost.

Note that appending, inserting, removing or pushing (back and front) elements potentially alters the memory address of other element in the queue, and there is no guarantee of contiguous storage of consecutive queued elements.

Abstract Representation

The logical organization of an indexable, in-place, double-ended bdlc::Queue object q is shown below, along with an illustration of some of its most common methods:

                                  QUEUE
               v = q.front()                          v = q.back()
                +------+------+------+------+--//--+------+
 q.popFront() <-|      |      |      |      |      |      |<- pushBack(v)
q.pushFront(v) ->|      |      |      |      |      |      |-> popBack()
                +------+------+------+------+--//--+------+
                  q[0]   q[1]                       q[n-1]
                <------------ n = q.length() --//--------->

Performance

The following characterizes the performance of representative operations using big-oh notation, O[f(N,M)], where the names N and M also refer to the number of respective elements in each container (i.e., its length). Here the average case, A[f(N)], is the amortized cost, which is defined as the cost of N successive invocations of the operation divided by N.

   Operation           Worst Case          Average Case
   ---------           ----------          ------------
   DEFAULT CTOR        O[1]
   COPY CTOR(N)        O[N]
   N.DTOR()            O[1]
   N.OP=(M)            O[M]
   OP==(N,M)           O[min(N,M)]
 
   N.pushFront(value)  O[N]                A[1]
   N.pushBack(value)   O[N]                A[1]
   N.popFront()        O[1]
   N.popBack()         O[1]
 
   N.append(value)     O[N]                A[1]
   N.insert(value)     O[N]
   N.replace(value)    O[1]
   N.remove(index)     O[N]
 
   N.OP@ref bdlc_queue             O[1]
   N.length()          O[1]

Usage

This section illustrates intended use of this component.

Example 1: Basic Usage

The following snippets of code illustrate how to create and use a queue. First, create an empty bdlc::Queue<double> q and populate it with two elements E1 and E2.

    const double E1 = 100.01;
    const double E2 = 200.02;
 
    bdlc::Queue<double> q;          assert( 0 == q.length());
 
    q.append(E1);                   assert( 1 == q.length());
                                    assert(E1 == q[0]);
                                    assert(E1 == q.front());
                                    assert(E1 == q.back());
 
    q.append(E2);                   assert( 2 == q.length());
                                    assert(E1 == q[0]);
                                    assert(E2 == q[1]);
                                    assert(E1 == q.front());
                                    assert(E2 == q.back());

Now, pop the first element (E1) from q and push the same value to the front of the queue.

    q.popFront();                   assert( 1 == q.length());
                                    assert(E2 == q[0]);
                                    assert(E2 == q.front());
                                    assert(E2 == q.back());
 
    q.pushFront(E1);                assert( 2 == q.length());
                                    assert(E1 == q[0]);
                                    assert(E2 == q[1]);
                                    assert(E1 == q.front());
                                    assert(E2 == q.back());

Then, pop the last element (E2) from the back of q and push a new value E3 at the end of the queue.

    const double E3 = 300.03;
 
    q.popBack();                    assert( 1 == q.length());
                                    assert(E1 == q[0]);
                                    assert(E1 == q.front());
                                    assert(E1 == q.back());
 
    q.pushBack(E3);                 assert( 2 == q.length());
                                    assert(E1 == q[0]);
                                    assert(E3 == q[1]);
                                    assert(E1 == q.front());
                                    assert(E3 == q.back());

Now, assign E2 to the first element (index position 0) of q.

    q[0] = E2;                      assert( 2 == q.length());
                                    assert(E2 == q[0]);
                                    assert(E3 == q[1]);

Then, insert a new value in the middle (index position 1) of q.

    const double E4 = 400.04;
 
    q.insert(1, E4);                assert( 3 == q.length());
                                    assert(E2 == q[0]);
                                    assert(E4 == q[1]);
                                    assert(E3 == q[2]);

Next, iterate over the elements in q, printing them in increasing order of their index positions, [0 .. q.length() - 1],

    bsl::cout << '[';
    int len = q.length();
    for (int i = 0; i < len; ++i) {
        bsl::cout << ' ' << q[i];
    }
    bsl::cout << " ]" << bsl::endl;

which produces the following output on stdout:

    [ 200.02 400.04 300.03 ]

Finally, remove the elements from queue q.

    q.remove(2);                    assert( 2 == q.length());
                                    assert(E2 == q[0]);
                                    assert(E4 == q[1]);
 
    q.remove(0);                    assert( 1 == q.length());
                                    assert(E4 == q[0]);
 
    q.remove(0);                    assert( 0 == q.length());

Note that, in general, specifying index positions greater than or equal to length() will result in undefined behavior.