Standard template library
Author: Alexander Stepanov, Meng Lee
Translation: kary
"This article is not very understanding in some places. I didn't want to upload, just because some of the presents are now
It's too black. Some books have not much pages, so they have a masterpiece on the layout, such as using a giant font,
Or the half of the layout leaves a large blank, write some subtitles, like a white folk on the white face.
The price is also very expensive, I really don't know why this country regardless of it. Once in the bookstore, I heard the owner said there:
This is not unoccuring, the first version of this book is not good, the first version is to sell hundreds of blocks, but the second edition is only 35 yuan.
I looked at it, the owner said it is a book of AutoCAD. So I moved the liver and fire, and I saw myself.
Tiger Tiger, giving people a blushing thing.
Original source: http://upload.smiling.com.cn/file/67539/stl.pdf "
1 Overview
The standard template library provides a range of universal C components with good structures, which are closely collaborated to provide powerful features. The design of the standard library must ensure that all template algorithms can operate both the data type in the library, and can also operate the data type inherent in the C . For example, all algorithms are suitable for normal pointer types. The components in the library are independent, that is, programmers can design the data structure provided by the algorithm operation library, or use the standard library algorithm to operate the custom data type. The wide versatility of the library is based on this flexibility.
Another important feature of the standard library is its high efficiency. The reason for C success is that it has powerful functions and high efficiency. Each template component in the library has a large number of validation, and the efficiency and the corresponding manual coding are only several percentage points.
The third feature of the standard library is that it is very simple and easy to understand.
2 Structure of Standard Library
The standard library mainly includes five parts:
- Algorithm: Define the calculation process.
- Container: Manage data collection.
- iterator: Provides a way to traverse containers.
- Function object: Encaps the function in the object for other components.
- Adapter: Provides different interfaces to components.
Such a function is divided into effectively reduces the amount of code. For example, we do not need to provide search algorithms for each container, and as long as a algorithm that meets a certain basic rule is provided, this algorithm can be used to operate all containers.
The following example explains the structure of the standard library more clearly. If the software component is represented as a three-dimensional array, where the first dimension represents different data types (eg, int, double), the second dimension represents different containers (eg, vector, linches, files), and the third dimension represents different Algorithm (such as search, sort, rotation), assuming I, J, K are three dimensions. We need J * k versions by using a data type as a template parameter. If our algorithm can be applied to different containers, only J K is required. This greatly simplifies the software design and makes the components in the library and the user-defined components can be flexible. For example, a user can define a special container, sort it with the Sort function in the library, or provide a custom comparison function for the SORT function, which can be a normal function pointer or a function object. (The so-called function object is to define the object of the Operator () operator). If the user needs to traverse the container in the opposite direction, you can use the REVERSE_ITERATOR adapter.
The standard library expands C in a consistent manner, so C / C programmers can easily pick up. For example, the library contains a MERGE template function. If the user needs to merge two arrays A and B into an array C, it can do this: int A [1000];
Int B [2000];
INT C [3000];
...
MERGE (A, A 1000, B, B 2000, C);
// Note: Merge function operation: Place a smaller in front of the elements of the two arrays of A and B. But do not consider each
// The order in the array.
If the user wants to merge a vector and a linked list (both in the library is template class), and save the result to a piece of unmected memory, you can write:
Vector
List
...
Employee * c = allocate (a.size () b.size (), (EMPLOYEE *) 0);
Merge (A.Begin (), A.End (), B. Segin (), B.End (),
Raw_storage_iterator
Among this, begin () and end () are the members of the container class, which returns the corresponding type of iterator (similar to the object of the pointer). Raw_storage_iterator is an adapter. By calling the corresponding type of replication constructor, the MERGE algorithm copies the results directly into the unin-initial memory.
Sometimes it is necessary to traverse the input / output stream like traversing the normal data structure. For example, if you want to merge two data structures and save the results into a file, if you can save the results directly to the appropriate file, there is no need to create any auxiliary data structure, then it's more convenient! So the template library provides the ISTREAM_ITERATOR and the OSTREAM_ITERATOR template class. By these two classes, the algorithms in the library can also be applied to the I / O stream with the same data type collection. The following program reads the integer from the standard input, deletes all integers that can be specified, and output the result to the standard console:
Main (int Argc, char ** argv)
{
IF (argc! = 2)
Throw ("Usage: Remove_if_divides Integer / N");
REMOVE_COPY_IF (iStream_Iterator
iStream_iterator
Ostream_iterator
NOT1 (MOD2ND (MODULUS
);
}
All work is done by the remove_copy_if statement. The REMOVE_COPY_IF function accepts two input iterator parameters and an output iterator parameter and an assertion function parameter. This algorithm is written in a single standard console and will be written to the output stream through the integer of the test until the input iterator (first parameter) arrives at the flow end position iterator (second parameter). The stream end position iterator is created with a constructor without parameters. (Generally, all algorithms work in the way "from here", that is, accept two iterator parameters, indicating the start and end position of the input.) The output iterator is bundled on COUT. Remove_copy_of's last parameter is an assertion function (Predicate "Returns true or fake functions"). MODULUS
Main (int Argc, char **)
{
IF (argc! = 1) throw ("USAGE: shuffle / n");
Vector
Copy (istream_iterator
INSERTER (V, v.end ())))));
Random_shuffle (v.begin (), v.end ());
Copy (v.begin (), v.end (), ostream_iterator
}
Copy copies each line read from the standard input to a vector container. Since the vector container is not pre-assigned memory, the program uses the insert iterator "also called the Adapter" to insert each row string into the vector container. (This technique allows all replication functions to work in a normal coverage or insert mode.) Then Random_shuffle randomly arranges the container element, and copies all objects to the output stream with the COPY function.
3 rules
To ensure that different components in the library work together, these components must meet some basic rules. The expression of the rules should be as accurate as possible. For example, for "class X must define the statement such as member function operator ()", our description is "an object X, x, x," for class X (because we don't know if this action is a member function or global function. The rule uses a strict defined expression description and points out the type of compliance. For a rule set, use a table to specify legal expressions and its semantic collection. Any modal algorithm that meets these rules must be encoded in a legitimate expression based on its type parameters.
If we say that the complexity of an operation satisfies the linear time, it means that it can only cost the linear time. So a fixed time operation is also satisfied with this rule.
Sometimes we use C code description semantic rules. These codes are only used to describe similar code writing methods, not to illustrate the copy (although these code is undoubtedly a relatively good implementation).
4 core components
This section describes some of the most basic template functions and classes. They will be used in the rest of the library.
4.1 operator
To avoid repeated definitions, libraries will! = Operation (can be derived from == operation) and>, <=, and> = (can be derived from Template Inline Bool Operator! = (Const T1 & X, Const T2 & Y) { Return! (x == Y); } Template Inline Bool Operator> (Const T1 & X, Const T2 & Y) { Return Y } Template INLINE BOOL Operator <= (Const T1 & X, Const T2 & Y) { Return! (Y } Template Inline Bool Operator> = (Const T1 & X, Const T2 & Y) { Return! (x } 4.2 Pair Objects (PAIR) The library is given to different types of objects that appear to define templates: Template Struct pair { T1 first; T2 Second; PAIR () {} PAIR (Const T1 & X, Const T2 & Y): first (x), second (y) {} } Template Inline Bool Operator == (Const Pair Return X.first == Y.First && x. Second == y.second; } Template Inline Bool Operator <(Const Pair Return x.first X. Second } The library provides the corresponding template function Make_Pair to simplify the structure of objects. Therefore, we don't have to write this: Return Pair And just write as: Return Make_Pair (5, 3.1415926); // Types Are Deduced Template Inline Pair Return Pair }
