clearly, int or double may not: find uses the expression *first , and the 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 requirements on types, and that it may be instantiated with any type that satisfies those requirements. Whatever type is substituted for InputIterator must provide certain operations: it must be possible to compare two objects of that type for equality, it must be possible to increment an object of that type, 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 arguments to for_each and count, and other algorithms, must satisfy the same requirements. These requirements are sufficiently important that we give them a name: we call such a set of type requirements a concept , and we call this particular concept Input Iterator. we say that a type conforms to a concept , or that it is a model of a concept , if it satisfies all of those requirements. We say that int* is a model of Input Iterator because int* provides all 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 concept in a program, or to declare that a particular type is a model of a concept. Nevertheless, concepts are an extremely important part of the STL. Using concepts makes it possible to write programs that cleanly separate interface from implementation: the author of find only has to consider the interface specified by the concept Input Iterator, rather than the implementation of 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 models of Input Iterator.this is the reason why find and reverse can be used with list s, vector s, C arrays, and many other types: programming in terms of concepts, rather than in terms of specific types, makes it possible to reuse software components and to combine components together.
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 arithmetic (it must be possible to increment an Input Iterator using prefix and postfix operator+ +), but need not support all operations of pointer arithmetic. This is sufficient for find, but some other algorithms require that their arguments satisfy additional requirements. Reverse , for example, must be able to decrement its arguments as well as increment them; it uses the expression --last. In terms of concepts, we say that reverse 's arguments must be models of Bidirectional Iterator rather than Input Iterator.
The Bidirectional Iterator concept is very similar to the Input Iterator concept: it simply imposes some additional requirements. The types that are models of Bidirectional Iterator are a subset of the types that are models ofInput 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 Bidirectional Iterator and a model of Input Iterator, but istream_iterator, is only a model of Input Iterator: it does not conform to the more stringent Bidirectional Iterator requirements.
We describe the relationship between Input Iterator and Bidirectional Iterator by saying that Bidirectional Iterator is a refinement of Input Iterator. Refinement of concepts is very much like inheritance of C++ classes; the main reason we use a different word, instead of just calling it 'inheritance', is to emphasize that refinement applies to concepts rather than to actual types.
There are actually three more iterator concepts in addition to the two that we have already discussed: the five iterator concepts are Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator; Forward Iterator is a refinement of Input Iterator, Bidirectional Iterator is a refinement of Forward Iterator, and Random Access Iterator is a refinement of Bidirectional Iterator. (Output Iterator is related to the other 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 other iterator concepts are refinements of it.) The Iterator Overview has more information about iterators in general.
Container classes, like iterators, are organized into a hierarchy of concepts. All containers are models of the concept Container; more refined concepts, such as Sequence and Associative Container, describe specific types of containers.
If you understand algorithms, iterators, and containers, then you understand almost everything there is to know about the STL. The STL does, however, include 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 Assignable, for example, describes types that have assignment operators and copy constructors; almost all STL classes are models of Assignable, and almost all stl algorithms require their arguments to be models of Assignable.
Second, the STL includes some low-level mechanisms for allocating and deallocating memory. Allocators are very specialized, and you can safely ignore them 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 objects are a generalization of functions: a function object is anything that you can call using the ordinary function call syntax. There are several different concepts relating to function objects, including Unary Function (a function 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 that 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 objects, but also over the operations that are being performed.
How to use the STL documentation
This site documents all of the components (classes, functions, and concepts) in the SGI Standard Template
