]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <HTML> |
2 | <!-- | |
3 | Copyright (c) Jeremy Siek 2000 | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. | |
6 | (See accompanying file LICENSE_1_0.txt or copy at | |
7 | http://www.boost.org/LICENSE_1_0.txt) | |
8 | --> | |
9 | <Head> | |
10 | <Title>Buffer</Title> | |
11 | </HEAD> | |
12 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
13 | ALINK="#ff0000"> | |
14 | <IMG SRC="../../../boost.png" | |
15 | ALT="C++ Boost" width="277" height="86"> | |
16 | ||
17 | <BR Clear> | |
18 | ||
19 | <h3>Buffer Concept</h3> | |
20 | ||
21 | A Buffer is something in which items can be put and removed. | |
22 | The Buffer <i>concept</i> has very few requirements. It does | |
23 | not require any particular ordering of how the items are stored or in | |
24 | what order they will appear when removed, however, there is typically | |
25 | some sort of ordering policy. | |
26 | ||
27 | <h3>Notation</h3> | |
28 | ||
29 | <table> | |
30 | <tr> <td> <tt>B</tt> </td> <td> is a type that models Buffer. </td></tr> | |
31 | <tr> <td> <tt>T</tt> </td> <td> is the value type of <tt>B</tt>. </td></tr> | |
32 | <tr> <td> <tt>t</tt> </td> <td> is an object of type <tt>T</tt>. </td></tr> | |
33 | </table> | |
34 | ||
35 | ||
36 | <h3>Members</h3> | |
37 | ||
38 | For a type to model the Buffer concept it must have the following members. | |
39 | ||
40 | <p> | |
41 | ||
42 | <table border="1"> | |
43 | ||
44 | <tr> <td><b>Member</b></td> <td><b>Description</b></td> </tr> | |
45 | ||
46 | <tr> <td> <tt>value_type</tt> </td> | |
47 | <td> The type of object stored in the Buffer. The value type | |
48 | must be <A href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>.</td> | |
49 | </tr> | |
50 | ||
51 | <tr> <td> <tt>size_type</tt> </td> | |
52 | <td> An unsigned integral type for representing the number of | |
53 | objects in the Buffer.</td> | |
54 | </tr> | |
55 | ||
56 | <tr> <td> <tt>void push(const T& t)</tt> </td> | |
57 | <td> Inserts <tt>t</tt> into the Buffer. <tt>size()</tt> will be | |
58 | incremented by one.</td> | |
59 | </tr> | |
60 | ||
61 | <tr> <td> <tt>void pop()</tt> </td> | |
62 | <td> Removes an object from the Buffer. <tt>size()</tt> will be | |
63 | decremented by one. Precondition: <tt>empty()</tt> | |
64 | is <tt>false</tt>. </td> | |
65 | </tr> | |
66 | ||
67 | <tr> <td> <tt>T& top()</tt> </td> | |
68 | <td> Returns a mutable reference to some object in the Buffer. | |
69 | Precondition: <tt>empty()</tt> is <tt>false</tt>.</td> | |
70 | </tr> | |
71 | ||
72 | <tr> <td> <tt>const T& top() const</tt> </td> | |
73 | <td> Returns a const reference to some object in the Buffer. | |
74 | Precondition: <tt>empty()</tt> is <tt>false</tt>.</td> | |
75 | </tr> | |
76 | ||
77 | <tr> <td> <tt>size_type size() const</tt> </td> | |
78 | <td> Returns the number of objects in the Buffer. | |
79 | Invariant: <tt>size() >= 0</tt>. </td> | |
80 | </tr> | |
81 | ||
82 | <tr> <td> <tt>bool empty() const</tt> </td> | |
83 | <td> Equivalent to <tt>b.size() == 0</tt>.</td> | |
84 | </tr> | |
85 | ||
86 | </table> | |
87 | ||
88 | <h3>Complexity Guarantees</h3> | |
89 | ||
90 | <UL> | |
91 | ||
92 | <LI> <tt>push()</tt>, <tt>pop()</tt>, and <tt>size()</tt> must be at | |
93 | most linear time complexity in the size of the Generalized Queue. | |
94 | ||
95 | <LI> <tt>top()</tt> and <tt>empty()</tt> must be amortized constant time. | |
96 | ||
97 | </UL> | |
98 | ||
99 | <h3>Models</h3> | |
100 | ||
101 | <UL> | |
102 | <LI><a href="http://www.sgi.com/tech/stl/stack.html"><tt>std::stack</tt></a> | |
103 | <LI><a href="../../../boost/pending/mutable_queue.hpp"><tt>boost::mutable_queue</tt></a> | |
104 | </UL> | |
105 | ||
106 | <p> | |
107 | ||
108 | <br> | |
109 | <HR> | |
110 | <TABLE> | |
111 | <TR valign=top> | |
112 | <TD nowrap>Copyright © 2000-2001</TD><TD> | |
113 | <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University and C++ Library & Compiler Group/SGI (<A HREF="mailto:jsiek@engr.sgi.com">jsiek@engr.sgi.com</A>) | |
114 | </TD></TR></TABLE> | |
115 | ||
116 | </BODY> | |
117 | </HTML> | |
118 |