Programming 版 (精华区)

发信人: xxxxx (因为寂寞), 信区: Programming
标  题: SGI c++ stl implemtation
发信站: 哈工大紫丁香 (2001年08月29日14:19:55 星期三), 站内信件

Introduction to the Standard Template Library
The Standard Template Library, or STL, is a C++ library of container classes
, algorithms, and iterators; it provides many of the basic algorithms and da
ta structures of computer science. The STL is a generic library, meaning tha
t its components are heavily parameterized: almost every component in the ST
L is a template. You should make sure that you understand how templates work
 in C++ before you use the STL.
Containers and algorithms
Like many class libraries, the STL includes container classes: classes whose
 purpose is to contain other objects. The STL includes the classes vector, l
ist, deque, set, multiset, map, multimap, hash_set, hash_multiset, hash_map,
 and hash_multimap. Each of these classes is a template, and can be instanti
ated to contain any type of object. You can, for example, use a vector<int> 
in much the same way as you would use an ordinary C array, except that vecto
r eliminates the chore of managing dynamic memory allocation by hand.
vector<int> v(3); // Declare a vector of 3 elements.
v[0] = 7;
v[1] = v[0] + 3;
v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
The STL also includes a large collection of algorithms that manipulate the d
ata stored in containers. You can reverse the order of elements in a vector,
 for example, by using the reverse algorithm.
reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
There are two important points to notice about this call to reverse. First, 
it is a global function, not a member function. Second, it takes two argumen
ts rather than one: it operates on a range of elements, rather than on a con
tainer. In this particular case the range happens to be the entire container
 v.
The reason for both of these facts is the same: reverse, like other STL algo
rithms, is decoupled from the STL container classes. This means that reverse
 can be used not only to reverse elements in vectors, but also to reverse el
ements in lists, and even elements in C arrays. The following program is als
o valid.
double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
reverse(A, A + 6);
for (int i = 0; i < 6; ++i)
cout << "A[" << i << "] = " << A[i];
This example uses a range, just like the example of reversing a vector: the 
first argument to reverse is a pointer to the beginning of the range, and th
e second argument points one element past the end of the range. This range i
s denoted [A, A + 6); the asymmetrical notation is a reminder that the two e
ndpoints are different, that the first is the beginning of the range and the
 second is one past the end of the range.
Iterators
In the example of reversing a C array, the arguments to reverse are clearly 
of type double*. What are the arguments to reverse if you are reversing a ve
ctor, though, or a list? That is, what exactly does reverse declare its argu
ments to be, and what exactly do v.begin() and v.end() return?
The answer is that the arguments to reverse are iterators, which are a gener
alization of pointers. Pointers themselves are iterators, which is why it is
 possible to reverse the elements of a C array. Similarly, vector declares t
he nested types iterator and const_iterator. In the example above, the type 
returned by v.begin() and v.end() is vector<int>::iterator. There are also s
ome iterators, such as istream_iterator and ostream_iterator, that aren't as
sociated with containers at all.
Iterators are the mechanism that makes it possible to decouple algorithms fr
om containers: algorithms are templates, and are parameterized by the type o
f iterator, so they are not restricted to a single type of container. Consid
er, for example, how to write an algorithm that performs linear search throu
gh a range. This is the STL's find algorithm.
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) 
{
while (first != last && *first != value) ++first;
return first;
}
Find takes three arguments: two iterators that define a range, and a value t
o search for in that range. It examines each iterator in the range [first, l
ast), proceeding from the beginning to the end, and stops either when it fin
ds an iterator that points to value or when it reaches the end of the range.

First and last are declared to be of type InputIterator, and InputIterator i
s a template parameter. That is, there isn't actually any type called InputI
terator: when you call find, the compiler substitutes the actual type of the
 arguments for the formal type parameters InputIterator and T. If the first 
two arguments to find are of type int* and the third is of type int, then it
 is as if you had called the following function.
int* find(int* first, int* last, const int& value) {
while (first != last && *first != value) ++first;
return first;
}
Concepts and Modeling
One very important question to ask about any template function, not just abo
ut STL algorithms, is what the set of types is that may correctly be substit
uted for the formal template parameters. Clearly, for example, int* or doubl
e* may be substituted for find's formal template parameter InputIterator. Eq
ually clearly, int or double may not: find uses the expression *first, and t
he dereference operator makes no sense for an object of type int or of type 
double. The basic answer, then, is that find implicitly defines a set of req
uirements on types, and that it may be instantiated with any type that satis
fies those requirements. Whatever type is substituted for InputIterator must
 provide certain operations: it must be possible to compare two objects of t
hat type for equality, it must be possible to increment an object of that ty
pe, it must be possible to dereference an object of that type to obtain the 
object that it points to, and so on.
Find isn't the only STL algorithm that has such a set of requirements; the a
rguments to for_each and count, and other algorithms, must satisfy the same 
requirements. These requirements are sufficiently important that we give the
m a name: we call such a set of type requirements a concept, and we call thi
s particular concept Input Iterator. We say that a type conforms to a concep
t, or that it is a model of a concept, if it satisfies all of those requirem
ents. We say that int* is a model of Input Iterator because int* provides al
l of the operations that are specified by the Input Iterator requirements.
Concepts are not a part of the C++ language; there is no way to declare a co
ncept in a program, or to declare that a particular type is a model of a con
cept. Nevertheless, concepts are an extremely important part of the STL. Usi
ng concepts makes it possible to write programs that cleanly separate interf
ace from implementation: the author of find only has to consider the interfa
ce specified by the concept Input Iterator, rather than the implementation o
f every possible type that conforms to that concept. Similarly, if you want 
to use find, you need only to ensure that the arguments you pass to it are m
odels of Input Iterator. This is the reason why find and reverse can be used
 with lists, vectors, C arrays, and many other types: programming in terms o
f concepts, rather than in terms of specific types, makes it possible to reu
se software components and to combine components together.
Refinement
Input Iterator is, in fact, a rather weak concept: that is, it imposes very 
few requirements. An Input Iterator must support a subset of pointer arithme
tic (it must be possible to increment an Input Iterator using prefix and pos
tfix operator++), but need not support all operations of pointer arithmetic.
 This is sufficient for find, but some other algorithms require that their a
rguments satisfy additional requirements. Reverse, for example, must be able
 to decrement its arguments as well as increment them; it uses the expressio
n --last. In terms of concepts, we say that reverse's arguments must be mode
ls of Bidirectional Iterator rather than Input Iterator.
The Bidirectional Iterator concept is very similar to the Input Iterator con
cept: it simply imposes some additional requirements. The types that are mod
els of Bidirectional Iterator are a subset of the types that are models of I
nput Iterator: every type that is a model of Bidirectional Iterator is also 
a model of Input Iterator. Int*, for example, is both a model of Bidirection
al Iterator and a model of Input Iterator, but istream_iterator, is only a m
odel of Input Iterator: it does not conform to the more stringent Bidirectio
nal Iterator requirements.
We describe the relationship between Input Iterator and Bidirectional Iterat
or by saying that Bidirectional Iterator is a refinement of Input Iterator. 
Refinement of concepts is very much like inheritance of C++ classes; the mai
n reason we use a different word, instead of just calling it "inheritance", 
is to emphasize that refinement applies to concepts rather than to actual ty
pes.
There are actually three more iterator concepts in addition to the two that 
we have already discussed: the five iterator concepts are Output Iterator, I
nput Iterator, Forward Iterator, Bidirectional Iterator, and Random Access I
terator; Forward Iterator is a refinement of Input Iterator, Bidirectional I
terator is a refinement of Forward Iterator, and Random Access Iterator is a
 refinement of Bidirectional Iterator. (Output Iterator is related to the ot
her four concepts, but it is not part of the hierarchy of refinement: it is 
not a refinement of any of the other iterator concepts, and none of the othe
r iterator concepts are refinements of it.) The Iterator Overview has more i
nformation about iterators in general.
Container classes, like iterators, are organized into a hierarchy of concept
s. All containers are models of the concept Container; more refined concepts
, such as Sequence and Associative Container, describe specific types of con
tainers.
Other parts of the STL
If you understand algorithms, iterators, and containers, then you understand
 almost everything there is to know about the STL. The STL does, however, in
clude several other types of components.
First, the STL includes several utilities: very basic concepts and functions
 that are used in many different parts of the library. The concept Assignabl
e, for example, describes types that have assignment operators and copy cons
tructors; almost all STL classes are models of Assignable, and almost all ST
L algorithms require their arguments to be models of Assignable.
Second, the STL includes some low-level mechanisms for allocating and deallo
cating memory. Allocators are very specialized, and you can safely ignore th
em for almost all purposes.
Finally, the STL includes a large collection of function objects, also known
 as functors. Just as iterators are a generalization of pointers, function o
bjects are a generalization of functions: a function object is anything that
 you can call using the ordinary function call syntax. There are several dif
ferent concepts relating to function objects, including Unary Function (a fu
nction object that takes a single argument, i.e. one that is called as f(x))
 and Binary Function (a function object that takes two arguments, i.e. one t
hat is called as f(x, y)). Function objects are an important part of generic
 programming because they allow abstraction not only over the types of objec
ts, but also over the operations that are being performed.

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: alioth.hit.edu.cn]