drdobbs-interview.html

这个帮助文档就不需要解释了

an object with a copy constructor out of another object, the two
objects should be equal.  C++ does not mandate this, but this is
one of the fundamental laws that we must obey.  Assignment has to
create equal objects.  So I presented a bunch of axioms that
connected these basic operations.  I talked a little bit about
axioms of iterators and showed some of the generic algorithms
working on iterators.  It was a two-hour talk and, I thought,
rather dry.  However, it was very well received.  I didn't think
at that time about using this thing as a part of the standard
because it was commonly perceived that this was some kind of
advanced programming technique which would not be used in the
"real world".  I thought there was no interest at all in any of
this work by practical people.
</P>

<P>
     I gave this talk in November, and I didn't think about ANSI
at all until January.  On January 6 I got a mail message from
Andy Koenig, who is the project editor of the standard document,
saying that if I wanted to make my library a part of the
standard, I should submit a proposal by January 25.  My answer
was, &quot;Andy, are you crazy?&quot; to which he answered, &quot;Well, yes I am
crazy, but why not try it?&quot;
</P>

<P>
    At that point there was a lot of code but there was no
documentation, much less a formal proposal.  Meng and I spent 80-hour 
weeks to come up with a proposal in time for the mailing
deadline.  During that time the only person who knew it was
coming was Andy.  He was the only supporter and he did help a lot
during this period.  We sent the proposal out, and waited.  While
doing the proposal we defined a lot of things.  When you write
things down, especially when you propose them as a standard, you
discover all kinds of flaws with your design.  We had to re-implement every single piece of code in the library, several
hundred components, between the January mailing and the next
meeting in March in San Diego.  Then we had to revise the
proposal, because while writing the code, we discovered many
flaws.
</P>





<P>
<B>
Can you characterize the discussions and debate in the committee
following the proposal?  Was there immediate support?
Opposition?
</B>
</P>





<P>
     We did not believe that anything would come out of it.  I
gave a talk, which was very well received.  There were a lot of
objections, most of which took this form: this is a huge
proposal, it's way too late, a resolution had been passed at the
previous meeting not to accept any major proposals, and here is
this enormous thing, the largest proposal ever, with a lot of
totally new things.  The vote was taken, and, interestingly
enough, an overwhelming majority voted to review the proposal at
the next meeting and put it to a vote at the next meeting in
Waterloo, Ontario.
</P>





<P>
     Bjarne Stroustrup became a strong supporter of STL.  A lot
of people helped with suggestions, modifications, and revisions.
Bjarne came here for a week to work with us.  Andy helped
constantly.  C++ is a complex language, so it is not always clear
what a given construct means.  Almost daily I called Andy or
Bjarne to ask whether such-and-such was doable in C++.  I should
give Andy special credit.  He conceived of STL as part of the
standard library.  Bjarne became the main pusher of STL on the
committee.  There were other people who were helpful:  Mike
Vilot, the head of the library group, Nathan Myers of Rogue Wave,
Larry Podmolik of Andersen Consulting.  There were many others.
</P>

<P>
     The STL as we proposed it in San Diego was written in
present C++.  We were asked to rewrite it using the new ANSI/ISO
language features, some of which are not implemented.  There was
an enormous demand on Bjarne's and Andy's time trying to verify
that we were using these non-implemented features correctly.
</P>

<P>
    People wanted containers independent of the memory model,
which was somewhat excessive because the language doesn't include
memory models.  People wanted the library to provide some
mechanism for abstracting memory models.  Earlier versions of STL
assumed that the size of the container is expressible as an
integer of type <tt>size_t</tt> and that the distance between two
iterators is of type <tt>ptrdiff_t</tt>. And now we were told, why don't
you abstract from that?  It's a tall order because the language
does not abstract from that; C and C++ arrays are not
parameterized by these types.  We invented a mechanism called
&quot;allocator,&quot; which encapsulates information about the memory
model.  That caused grave consequences for every component in the
library.  You might wonder what memory models have to do with
algorithms or the container interfaces.  If you cannot use things
like <tt>size_t</tt>, you also cannot use things like <tt>T*</tt>  because of
different pointer types (<tt>T*</tt>, <tt>T huge *</tt>, etc.).  Then you cannot
use references because with different memory models you have
different reference types.  There were tremendous ramifications
on the library.
</P>

<P>
    The second major thing was to extend our original set of data
structures with associative data structures.  That was easier,
but coming up with a standard is always hard because we needed
something which people would use for years to come for their
containers.  STL has from the point of view of containers, a very
clean dichotomy.  It provides two fundamental kinds of container
classes: sequences and associative containers.  They are like
regular memory and content-addressable memory. It has a clean
semantics explaining what these containers do.
</P>

<P>
    When I arrived at Waterloo, Bjarne spent a lot of time
explaining to me that I shouldn't be concerned, that most likely
it was going to fail, but that we did our best, we tried, and we
should be brave.  The level of expectation was low.  We expected
major opposition.  There was some opposition but it was minor.
When the vote was taken in Waterloo, it was totally surprising
because it was maybe 80% in favor and 20% against.  Everybody
expected a battle, everybody expected controversy.  There was a
battle, but the vote was overwhelming.
</P>




<P>
<B>
What effect does STL have on the class libraries published in the
ANSI/ISO February 1994 working paper?
</B>
</P>



<P>
     STL was incorporated into the working paper in Waterloo.
The STL document is split apart, and put in different places of
the library parts of the working paper.  Mile Vilot is
responsible for doing that.  I do not take active part in the
editorial activities.  I am not a member of the committee but
every time an STL-related change is proposed, it is run by me.
The committee is very considerate.
</P>





<P>
<B>
Several template changes have been accepted by the committee.
Which ones have impact on STL?
</B>
</P>





<P>
     Prior to the acceptance of STL there were two changes that
were used by the revised STL.  One is the ability to have
template member functions.  STL uses them extensively to allow
you to construct any kind of a container from any other kind of a
container.  There is a single constructor that allows you to
construct vectors out of lists or out of  other containers.
There is a templatized constructor which is templatized on the
iterator, so if you give a pair of iterators to a container
constructor, the container is constructed out of the elements
which are specified by this range.  A range is a set of elements
specified by a pair of iterators, generalized pointers, or
addresses.  The second significant new feature used in STL was
template arguments which are templates themselves, and that's how
allocators, as originally proposed, were done.
</P>





<P>
<B>
Did the requirements of STL influence any of the proposed
template changes?
</B>
</P>



<P>
     In Valley Forge, Bjarne proposed a significant addition to
templates called &quot;partial specialization,&quot; which would allow many
of the algorithms and classes to be much more efficient and which
would address a problem of code size.  I worked with Bjarne on
the proposal and it was driven by the need of making STL even
more efficient. Let me explain what partial specialization is.
At present you can have a template function parameterized by
class T called <tt>swap(T&amp;, T&amp;)</tt>  and swaps them.  This is the most
generic possible <tt>swap</tt>.  If you want to specialize <tt>swap</tt> and do
something different for a particular type, you can have a
function <tt>swap(int&amp;, int&amp;)</tt>, and which does integer swapping in
some different way.  However it was not possible to have an
intermediate partial specialization, that is, to provide a
template function of the following form:

<pre>
  template &lt;class T&gt; void swap(vector&lt;T&gt;&amp;, vector&lt;T&gt;&amp;);
</pre>

This form provides a special way to swap vectors.  This is an
important problem from an efficiency point of view.  If you swap
vectors with the most generic <tt>swap</tt>, which uses three assignments,
vectors are copied three times, which takes linear time.
However, if we have this partial specialization of <tt>swap</tt> for
vectors that swap two vectors, then you can have a fast, constant
time operation, that moves a couple of pointers in the vector
headers.  That would allow <tt>sort</tt>, for example, to work on vectors
of vectors much faster.  With the present STL, without partial
specialization, the only way to make it work faster is for any
particular kind of <tt>vector</tt>, such as <tt>vector&lt;int&gt;</tt>, to define its own
<tt>swap</tt>, which can be done but which puts a burden on the
programmer.  In very many cases, partial specialization would
allow algorithms to be more effective on some generic classes.
You can have the most generic <tt>swap</tt>, a less generic <tt>swap</tt>, an even
less generic <tt>swap</tt>, and a totally specific <tt>swap</tt>.  You can do
partial specialization, and the compiler will find the closest
match.  Another example is <tt>copy</tt>.  At present the <tt>copy</tt> algorithm
just goes through a sequence of elements defined by iterators and
copies them one by one.  However, with partial specialization we
can define a template function:

<pre>
  template &lt;class T&gt; T ** copy(T**,T**,T**);
</pre>

This will efficiently copy a range of pointers by using <tt>memcpy</tt>,
because when we're copying pointers we don't have to worry about
construction and destruction and we can just move bits with
<tt>memcpy</tt>.  That can be done once and for all in the library and the
user doesn't need to be concerned.  We can have particular
specializations of algorithms for some of the types.  That was a
very important change, and as far as I know it was favorably
received in Valley Forge and will be part of the Standard.
</P>



<P>
<B>
What kinds of applications beyond the standard class libraries
are best served by STL ?
</B>
</P>



<P>
     I have hopes that STL will introduce a style of programming
called generic programming.  I believe that this style is
applicable to any kind of application, that is, trying to write
algorithms and data structures in the most generic way.
Specifying families or categories of such structures satisfying
common semantic requirements is a universal paradigm applicable
to anything.  It will take a long time before the technology is
understood and developed.  STL is a starting point for this type
of programming.
</P>

<P>
     Eventually we will have standard catalogs of generic
components with well-defined interfaces, with well-defined
complexities.  Programmers will stop programming  at the micro
level.  You will never need to write a binary search routine
again. Even now,  STL provides several binary search algorithms
written in the most generic way.  Anything that is binary-searchable 
can be searched by those algorithms.  The minimum
requirements that the algorithm assumes are the only requirements
that the code uses.  I hope that the same thing will happen for
all software components.  We will have standard catalogs and
people will stop writing these things.
</P>

<P>
    That was Doug McIlroy's dream when he published a famous
paper talking about component factories in 1969.  STL is an
example of the programming technology which will enable such
component factories.  Of course, a major effort is needed, not
just research effort, but industrial effort to provide
programmers with such catalogs, to have tools which will allow
people to find the components they need, and to glue the
components together, and to verify that their complexity
assumptions are met.
</P>





<P>
<B>
STL does not implement a persistent object container model.  The
<tt>map</tt> and <tt>multimap</tt> containers are particularly good candidates for
persistent storage containers as inverted indexes into persistent
object databases.  Have you done any work in that direction or
can you comment an such implementations?
</B>
</P>





<P>
     This point was noticed by many people.  STL does not
implement persistence for a good reason.  STL is as large as was
conceivable at that time.  I don't think that any larger set of
components would have passed through the standards committee.
But persistence is something that several people thought about.
During the design of STL and especially during the design of the
allocator component, Bjarne  observed that allocators, which
encapsulate memory models, could be used to encapsulate a
persistent memory model. The insight was Bjarne's, and it is an
important and interesting insight.  Several object database
companies are looking at that. In October 1994 I attended a
meeting of the Object Database Management Group. I gave a talk on
STL,  and there was strong interest there to make the containers
within their emerging interface to conform to STL. They were not
looking at the allocators as such. Some of the members of the
Group are, however, investigating whether allocators can be used
to implement persistency. I expect that there will be persistent
object stores with STL-conforming interfaces fitting into the STL
framework within the next year.
</P>




<P>
<B>
<tt>Set</tt>,<tt> multiset</tt>, <tt>map</tt>, and <tt>multimap</tt> are implemented with a red-black
tree data structure. Have you experimented with other structures
such as B*trees?
</B>
</P>