1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
The ti(queue) class implements a i(queue data structure). Before using a
tt(queue) container the header file tthi(queue) must be included.
A queue is depicted in figure ref(queueFig).
figure(containers/queue)(A queue data-structure)(queueFig)
In figure ref(queueFig) it is shown that a queue has one point (the
em(back)) where items can be added to the queue, and one point (the em(front))
where items can be removed (read) from the queue. A tt(queue) is therefore
also called a emi(FIFO) data structure, for emi(first in, first out). It is
most often used in situations where events should be handled in the same order
as they are generated.
The following constructors, operators, and member functions are available
for the tt(queue) container:
itemization(
it() hi(queue) Constructors:
itemization(
it() The copy and move constructors are available;
it() A tt(queue) may be constructed empty:
verb( queue<string> object;)
As with the tt(vector), it is an error to refer to an element of an
empty queue.
)
it() The tt(queue) container only supports the basic container operators.
it() The following hi(member function)member functions are available for
queues:
itemization(
ithtq(back)(Type &back())(returns a
reference to the last element in the queue. It is the
i(responsibility of the programmer) to use the member only if the queue is
not empty.)
ithtq(emplace)(value_type &emplace(Args &&...args))
(a tt(value_type) object is constructed from the member's
arguments, and the newly created element is inserted beyond the
end of the queue, returning a reference to (or copy of) the newly
added element.)
ithtq(empty)(bool empty())(returns
tt(true) if the queue contains no elements.)
ithtq(front)(Type &front())(returns a
reference to the first element in the queue. It is the responsibility of the
programmer to use the member only if the queue is not empty.)
COMMENT(verbinclude(-a queue/front.cc))
ithtq(pop)(void pop())(removes the element at the front of
the queue. Note that the element is em(not) returned by this member.
Avoid calling this member on an empty queue: although nothing is returned its
internally maintained count of number of available elements is reduced,
causing the queue's tt(size()) member to return the (when cast to tt(int))
value -1, and then -2, etc., etc. One might wonder why
tt(pop) returns tt(void), instead of a value of type tt(Type)
(cf. tt(front)). One reason is found in the principles of good software
design: functions should perform one task. Combining the removal and return of
the removed element breaks this principle. Moreover, when this principle is
abandoned tt(pop)'s implementation is always flawed. Consider the
prototypical implementation of a tt(pop) member that is expected to return the
queue's front-value:
verb( Type queue::pop()
{
Type ret{ front() };
erase_front();
return ret;
})
Since tt(queue) has no control over tt(Type)'s behavior the first statement
(tt(Type ret{ front() })) might throw. Although this still supports the
'commit or roll-back' principle, tt(queue) cannot guarantee that tt(Type)
offers copy-construction. Hence, tt(pop) does not return the queue's
front-value, but simply erases that element:
verb( Type queue::pop()
{
erase_front();
})
Note that tt(push) doesn't require copy construction: tt(push) can also be
implemented when move-construction is supported. E.g.,
verb( void queue::push(Type &&tmp)
{
d_data.push_back(std::move(tmp)); // uses move construction
})
Because of all this, we must first use tt(front) and then tt(pop) to
obtain and remove the queue's front element.)
ithtq(push)(void push(value))(this member
adds tt(value) to the back of the queue.)
ithtq(size)(size_t size())(returns the
number of elements in the queue.)
)
)
Note that the queue does not support iterators or an index operator. The
only elements that can be accessed are its front and back element. A queue
can be emptied by:
itemization(
it() repeatedly removing its front element;
it() assigning an empty queue using the same data type to it;
it() having its destructor called.
)
|
