Provide an in-place double-ended queue of T values.
More...
Namespaces |
| namespace | bdlc |
Detailed Description
- Outline
-
-
- 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[]() O[1]
N.length() O[1]
-
- 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());
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());
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());
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]);
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]);
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;
stdout: Finally, remove the elements from queue q. Note that, in general, specifying index positions greater than or equal to length() will result in undefined behavior.
