This article translated from SGI website, original named Introduction to Stand Template Library, link to http://www.sgi.com/tech/stl/. I feel helpful for understanding some related concepts and learning STL. Just translate it, it is a Chinese and English, because I don't dare to ensure that I can express the original meaning, just translate it according to my understanding, I hope to help everyone can help.
Standard Template Library Introduction (1)
Standard template library, or STL is a C class library containing container classes, algorithms, algorithms, and iterators. It provides basic algorithms and data structures in many computer science. STL is a Wild library, that is, its components are a large parameterized: almost every component in STL is a template. Before you start using STL, you should be sure that you understand that the template in C is How to operate.
Container and algorithm
Like many class libraries, STL includes container classes: Its purpose is to accommodate other objects. STL contains Vector, List, Deque, SET, MULTISET, MAP, MULTIMAP, HASH_SET, HASH_MULTIMAP, Hash_MAP, and Hash_MultiMap. These classes One is a template. You can be instantiated to accommodate any type of object. For example, you can use Vector
Vector
v [0] = 7;
v [1] = v [0] 3;
v [2] = v [0] v [1]; // v [0] = 7, v [1] = 10, v [2] = 17
STL also includes a large number of algorithms to manipulate data stored in the container. For example, by using the Reverse algorithm, you can reverse the element order in a vector.
Reverse (v.begin (), v.end ()); // v [0] = 17, v [1] = 10, v [2] = 7
Two points worth noting about Reverse. First, it is a full-time function, not a member function. Second, it accepts two parameters instead of one: it operate a series of elements, not a container. In this The element range is just the entire container V in the example.
The cause of these two facts is the same: Reverse, like other STL algorithms, is separated from the STL container class, that is, Reverse can not only be used to reverse the elements in the vector, but also can reverse LIST or even Elements in the c array. The following procedures are also effective:
Double A [8] = {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 (RANGE), just as an example in which a vector is reversed; the first parameter of Reverse is a start pointer to the range, and the second parameter points to the position of the last element of the range. This The range is marked in [a, A 6]; this asymmetric mark is used to remind that two endpoints are different, the first is the beginning of this range, the second is the position of the end of the range.
Iterators
In an example in which a c array is reversed, the parameter type of Reverse is Double *. But if it is reversed a vector or a list of the parameters of Reverse, what is the parameter declared by Reverse, and V What is. becom () and v.end () what is returned?
The answer is that the arguments to reverse are iterators, which are a generalization of pointers. Pointers themselves are iterators, which is why it is possible to reverse the elements of a C array. Similarly, vector declares the nested types iterator and const_iterator. In the example above, the type returned by v.begin () and v.end () is vector
Iterators are the mechanism that makes it possible to decouple algorithms from containers: algorithms are templates, and are parameterized by the type of iterator, so they are not restricted to a single type of container Consider, for example, how to write an algorithm that. Performs Linear Search THROUGH a Range. this is the stl's find algorithm.
Template
InputITerator Find (InputITerator First, InputITerator Last, Const T & Value) {
While (First! = Last && * first! = value) first;
Return first;
}
Itertors is a mechanism that separates the algorithm to the container as possible: algorithm is template, parameterized with the type of iterator, so they are not limited to single types of containers. For example, consider how to write one Algorithm for performing linear searches within a range. This is the STL's Find Algorithm.
Template
InputITerator Find (InputITerator First, InputITerator Last, Const T & Value) {
While (first! = Last && * fist! = Value) first;
Return first;
}
Find takes three arguments: two iterators that define a range, and a value to search for in that range It examines each iterator in the range [first, last), proceeding from the beginning to the end, and stops either when it finds an. Iterator That Points To Value or When It Reaches The End of The Range.Find Accepts three parameters: Two a range of iterators and a value value value value to search within this range. It is in [First, Last] range Check each iterator, from the beginning to the end, when it finds an iterator pointing to Value or stops when it reaches the end.
First and last are declared to be of type InputIterator, and InputIterator is a template parameter That is, there is not actually any type called InputIterator:. 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 area of type tent * and the third is of type int
INT * Find (int * first, int * last, const INT & value) {
While (First! = Last && * first! = value) first;
Return first;
}
First and LAST are declared as type INPUTITERATOR, it is a template parameter. That is, in fact, there is no type called InputItemrator: When you call Find, the compiler replaces the form type parameter InputIterator and T. If Find The first two parameter types are int * and the third parameter type is int, then you call the following functions:
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 about STL algorithms, is what the set of types is that may correctly be substituted for the formal template parameters. Clearly, for example, int * or double * may be substituted for find's . formal template parameter InputIterator Equally 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 this Typerence An Object of That Type To Obtain The Object That Points To, And So on. Concepts and Models
About a very important issue of template functions, not only about STL algorithms, is a collection of types of form template parameters that can be correctly replaced. It is obvious, for example, int * or double * can be used to replace Find form template parameter input INPUTITERATOR. Similar Obviously, int or double is not: Find uses expression * first, the Dereference operator does not make sense for the type INT or Double object. Therefore, the basic answer is defined by Find implicit. For type requirements, you can instantiate if these requirements are satisfied. No matter what type replaces the InputITerator, you must provide a certain operation: You must compare whether the type of the type is equal, you must be able to be able to be an object of this type. In addition, an object of this type must be able to parse reference operations to obtain objects that it points to.
Find is not 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.Find is not the only STL algorithm with this requirement; for_each and count, and other algorithms must meet the same requirements. These The requirements are quite important, so we give them a name: we call this type of requirements as a concept, and will call this special concept (Concept) as input_iterator. We say a type follows a concept, Or it is a model of a concept, if it satisfies all those requirements. We said that int * is a model of Input_iterator because INT * provides all the operations specified by 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 lists, vectors, C arrays, and many other types:. programming in terms of concepts Rather Than in Terms of To Reuse Software Components and to Combine Components TOGETHER. Concept is not part of the C language; there is no way to declare a concept in a program, or declare a specific type as a concept. Model. However, the concept is an extremely important part of the STL. The use concept makes the program that makes the interface to achieve a clearly separated procedure possible: find Simply consider the interface specified by the concept input_iterator instead of considering each possible type of the concept. Similarly, if you want to use Find, you only need to make sure that the parameters you pass are the model of the input_iterator. This is Why Find and Reverse can be used for List, Vector, C arrays, and many other types of reasons: Programming based on the concept (Concept) instead of a specific type, making us reuse software components and unite together.
