chap04.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 1,135 行 · 第 1/5 页
KBK
1,135 行
list so it can be sent to <B>stackOut( )</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You cannot iterate through a
<B>stack</B>; this emphasizes that you only want to perform <B>stack</B>
operations when you create a <B>stack</B>. You can get equivalent
“stack” functionality using a <B>vector</B> and its
<B>back( )</B>, <B>push_back( )</B> and <B>pop_back( )</B>
methods, and then you have all the additional functionality of the
<B>vector</B>. <B>Stack1.cpp</B> can be rewritten to show this:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Stack3.cpp</font>
<font color=#009900>// Using a vector as a stack; modified Stack1.cpp</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
ifstream in(<font color=#004488>"Stack3.cpp"</font>);
vector<string> textlines;
string line;
<font color=#0000ff>while</font>(getline(in, line))
textlines.push_back(line + <font color=#004488>"\n"</font>);
<font color=#0000ff>while</font>(!textlines.empty()) {
cout << textlines.back();
textlines.pop_back();
}
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You’ll see this produces the same
output as <B>Stack1.cpp</B>, but you can now perform <B>vector</B> operations as
well. Of course, <B>list</B> has the additional ability to push things at the
front, but it’s generally less efficient than using
<B>push_back( )</B> with <B>vector</B>. (In addition, <B>deque</B> is
usually more efficient than <B>list</B> for pushing things at the
front).</FONT><A NAME="_Toc519042039"></A><BR></P></DIV>
<A NAME="Heading227"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
queue</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>queue</B> is a restricted form of
a <B>deque</B> – you can only enter elements at one end, and pull them off
the other end. Functionally, you could use a <B>deque</B> anywhere you need a
<B>queue</B>, and you would then also have the additional functionality of the
<B>deque</B>. The only reason you need to use a <B>queue</B> rather than a
<B>deque</B>, then, is if you want to emphasize that you will only be performing
queue-like behavior.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>queue</B> is an adapter class like
<B>stack</B>, in that it is built on top of another sequence container. As you
might guess, the ideal implementation for a <B>queue</B> is a <B>deque</B>, and
that is the default template argument for the <B>queue</B>; you’ll rarely
need a different implementation.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Queues are often used when modeling
systems where some elements of the system are waiting to be served by other
elements in the system. A classic example of this is the “bank-teller
problem,” where you have customers arriving at random intervals, getting
into a line, and then being served by a set of tellers. Since the customers
arrive randomly and each take a random amount of time to be served,
there’s no way to deterministically know how long the line will be at any
time. However, it’s possible to simulate the situation and see what
happens.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A problem in performing this simulation
is the fact that, in effect, each customer and teller should be run by a
separate process. What we’d like is a multithreaded environment, then each
customer or teller would have their own thread. However, Standard C++ has no
model for multithreading so there is no standard solution to this problem. On
the other hand, with a little adjustment to the code it’s possible to
simulate enough multithreading to provide a satisfactory solution to our
problem.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Multithreading means you have multiple
threads of control running at once, in the same address space (this differs from
<I>multitasking</I>, where you have different processes each running in their
own address space). The trick is that you have fewer CPUs than you do threads
(and very often only one CPU) so to give the illusion that each thread has its
own CPU there is a <I>time-slicing</I> mechanism that says “OK, current
thread – you’ve had enough time. I’m going to stop you and go
give time to some other thread.” This automatic stopping and starting of
threads is called <I>pre-emptive </I>and it means you don’t need to manage
the threading process at all.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">An alternative approach is for each
thread to voluntarily yield the CPU to the scheduler, which then goes and finds
another thread that needs running. This is easier to synthesize, but it still
requires a method of “swapping” out one thread and swapping in
another (this usually involves saving the stack frame and using the standard C
library functions <B>setjmp( )</B> and <B>longjmp( )</B>; see my
article in the (XX) issue of Computer Language magazine for an example). So
instead, we’ll build the time-slicing into the classes in the system. In
this case, it will be the tellers that represent the “threads,” (the
customers will be passive) so each teller will have an infinite-looping
<B>run( )</B> method that will execute for a certain number of “time
units,” and then simply return. By using the ordinary return mechanism, we
eliminate the need for any swapping. The resulting program, although small,
provides a remarkably reasonable simulation:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:BankTeller.cpp</font>
<font color=#009900>// Using a queue and simulated multithreading</font>
<font color=#009900>// To model a bank teller system</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <iostream>
#include <queue>
#include <list>
#include <cstdlib>
#include <ctime>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>class</font> Customer {
<font color=#0000ff>int</font> serviceTime;
<font color=#0000ff>public</font>:
Customer() : serviceTime(0) {}
Customer(<font color=#0000ff>int</font> tm) : serviceTime(tm) {}
<font color=#0000ff>int</font> getTime() { <font color=#0000ff>return</font> serviceTime; }
<font color=#0000ff>void</font> setTime(<font color=#0000ff>int</font> newtime) {
serviceTime = newtime;
}
<font color=#0000ff>friend</font> ostream&
<font color=#0000ff>operator</font><<(ostream& os, <font color=#0000ff>const</font> Customer& c) {
<font color=#0000ff>return</font> os << '[' << c.serviceTime << ']';
}
};
<font color=#0000ff>class</font> Teller {
queue<Customer>& customers;
Customer current;
<font color=#0000ff>enum</font> { slice = 5 };
<font color=#0000ff>int</font> ttime; <font color=#009900>// Time left in slice</font>
<font color=#0000ff>bool</font> busy; <font color=#009900>// Is teller serving a customer?</font>
<font color=#0000ff>public</font>:
Teller(queue<Customer>& cq)
: customers(cq), ttime(0), busy(<font color=#0000ff>false</font>) {}
Teller& <font color=#0000ff>operator</font>=(<font color=#0000ff>const</font> Teller& rv) {
customers = rv.customers;
current = rv.current;
ttime = rv.ttime;
busy = rv.busy;
<font color=#0000ff>return</font> *<font color=#0000ff>this</font>;
}
<font color=#0000ff>bool</font> isBusy() { <font color=#0000ff>return</font> busy; }
<font color=#0000ff>void</font> run(<font color=#0000ff>bool</font> recursion = <font color=#0000ff>false</font>) {
<font color=#0000ff>if</font>(!recursion)
ttime = slice;
<font color=#0000ff>int</font> servtime = current.getTime();
<font color=#0000ff>if</font>(servtime > ttime) {
servtime -= ttime;
current.setTime(servtime);
busy = <font color=#0000ff>true</font>; <font color=#009900>// Still working on current</font>
<font color=#0000ff>return</font>;
}
<font color=#0000ff>if</font>(servtime < ttime) {
ttime -= servtime;
<font color=#0000ff>if</font>(!customers.empty()) {
current = customers.front();
customers.pop(); <font color=#009900>// Remove it</font>
busy = <font color=#0000ff>true</font>;
run(<font color=#0000ff>true</font>); <font color=#009900>// Recurse</font>
}
<font color=#0000ff>return</font>;
}
<font color=#0000ff>if</font>(servtime == ttime) {
<font color=#009900>// Done with current, set to empty:</font>
current = Customer(0);
busy = <font color=#0000ff>false</font>;
<font color=#0000ff>return</font>; <font color=#009900>// No more time in this slice</font>
}
}
};
<font color=#009900>// Inherit to access protected implementation:</font>
<font color=#0000ff>class</font> CustomerQ : <font color=#0000ff>public</font> queue<Customer> {
<font color=#0000ff>public</font>:
<font color=#0000ff>friend</font> ostream&
<font color=#0000ff>operator</font><<(ostream& os, <font color=#0000ff>const</font> CustomerQ& cd) {
copy(cd.c.begin(), cd.c.end(),
ostream_iterator<Customer>(os, <font color=#004488>""</font>));
<font color=#0000ff>return</font> os;
}
};
<font color=#0000ff>int</font> main() {
CustomerQ customers;
list<Teller> tellers;
<font color=#0000ff>typedef</font> list<Teller>::iterator TellIt;
tellers.push_back(Teller(customers));
srand(time(0)); <font color=#009900>// Seed random number generator</font>
clock_t ticks = clock();
<font color=#009900>// Run simulation for at least 5 seconds:</font>
<font color=#0000ff>while</font>(clock() < ticks + 5 * CLK_TCK) {
<font color=#009900>// Add a random number of customers to the</font>
<font color=#009900>// queue, with random service times:</font>
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i < rand() % 5; i++)
customers.push(Customer(rand() % 15 + 1));
cout << '{' << tellers.size() << '}'
<< customers << endl;
<font color=#009900>// Have the tellers service the queue:</font>
<font color=#0000ff>for</font>(TellIt i = tellers.begin();
i != tellers.end(); i++)
(*i).run();
cout << '{' << tellers.size() << '}'
<< customers << endl;
<font color=#009900>// If line is too long, add another teller:</font>
<font color=#0000ff>if</font>(customers.size() / tellers.size() > 2)
tellers.push_back(Teller(customers));
<font color=#009900>// If line is short enough, remove a teller:</font>
<font color=#0000ff>if</font>(tellers.size() > 1 &&
customers.size() / tellers.size() < 2)
<font color=#0000ff>for</font>(TellIt i = tellers.begin();
i != tellers.end(); i++)
<font color=#0000ff>if</font>(!(*i).isBusy()) {
tellers.erase(i);
<font color=#0000ff>break</font>; <font color=#009900>// Out of for loop</font>
}
}
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Each customer requires a certain amount
of service time, which is the number of time units that a teller must spend on
the customer in order to serve that customer’s needs. Of course, the
amount of service time will be different for each customer, and will be
determined randomly. In addition, you won’t know how many customers will
be arriving in each interval, so this will also be determined randomly.
</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>Customer </B>objects are kept in a
<B>queue<Customer></B>, and each <B>Teller</B> object keeps a reference to
that queue.<B> </B>When a <B>Teller</B> object is finished with its current
<B>Customer</B> object, that <B>Teller</B> will get another <B>Customer</B> from
the queue and begin working on the new <B>Customer</B>, reducing the
<B>Customer</B>’s service time during each time slice that the
<B>Teller</B> is allotted. All this logic is in the <B>run( )</B> member
function, which is basically a three-way <B>if</B> statement based on whether
the amount of time necessary to serve the customer is less than, greater than or
equal to the amount of time left in the teller’⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?