30 minutes to master STL
Original source http://www.hoversoft.net/devinfo/0205doc/20stl/index.htm suggesting that you are a small book. The original name is "Using STL", I don't know who is written. But I feel very interesting, I will translate it in two nights. I didn't check the contents of the translated content. If you can't feel gaining in 30 minutes, then throw it. I saved a lot of things in the text. Distressed, waste me two nights. Translator: Kary Contact: KaryMay@163.NET STL Overview A important feature of STL is that the data structure and algorithm are separated. Although this is a simple concept, this separation does make STL become very common. For example, since STL's sort () function is fully universal, you can use it to operate almost any data set, including linked lists, containers, and arrays. The point STL algorithm is provided as a template function. In order to distinguish between the other components, the STL algorithm is coupled in this book, such as Sort (). Another important feature of STL is that it is not object-oriented. In order to have enough versatility, STL mainly depends on the template instead of package, inheritance, and virtual function (polymorphism) - OOP. You can't find any obvious inheritance relationships in STL. This seems to be a reverse, but this is exactly a wide veneer of the STL's components. In addition, since the STL is a template, the use of the inline function makes the generated code short and efficient. Tip Make sure that at least -O optimization is used in the program that uses STLs to ensure inline expansion. STL provides a large number of templates and functions that can be used in OOP and regular programming. About 50 algorithms of all STL are fully common and do not rely on any specific data type. The following section describes three basic STL components: 1) iterators provide methods for accessing objects in the container. For example, a pair of iterators can be used to specify certain ranges of objects in the List or VECTOR. The iterator is like a pointer. In fact, the C pointer is also an iterator. However, iterators can also be class objects that define Operator * () and other methods of operators similar to pointer. 2) The container is a data structure, such as List, Vector, and Deques, provided in a template class. In order to access the data in the container, it can be used by the iterator output from the container class. 3) The algorithm is a template function used to operate data in the container. For example, STL uses sort () to sort the data in a vector, search with the object in a list. The function itself has nothing to do with the structure and type of the data they operate, so they can be used on any data structure from a simple array to a highly complex container. In order to avoid conflicts with other header files, STL's header files no longer use conventional .h extensions. In order to include the standard String class, iterator and algorithm, with the following indicator: #include #include #include If you view the STL's header file, you can see Iterator.h and STL_ITerator.h This header file. Since these names may differ between various STL implementations, you should avoid using these names to reference these headers. In order to ensure portability, the file name of the corresponding no .h suffix is used. Table 1 lists the header files of the most commonly used containers. The table is incomplete, for other header files, I will introduce in this chapter and the next chapter.
Table 1. STL header and container class #include container class demary list
The pointer iterator is displayed as the micrographer below, and a pointer is also an iterator. The program also shows a main feature of the STL - it is not only available for its own class type, and can also be used for any C or C type. Listing 1, iterdemo.cpp, showing how to use the pointer as an iterator for the STL's Find () algorithm to search for a normal array. Table 1. IterDemo.cpp #include #include using namespace std; #define size 100 int aRray [size]; int main () {aRray [20] = 50; int * ip = find IARRAY, IARRAY SIZE, 50); if (ip == otray size) cout << "50 not found in array" << endl; else cout << * ip << "Found in array" << Endl; Return 0;} The program tells the compiler to use the STD namespace using the STD name space. This line using STD namespace is optional because it can be deleted that this line will not cause the name conflict. The overall number of sizes is defined in the program. Since it is a global variable, the runtime array automatically initials to zero. The following statement will be set to 50 at the point of index 20, and search value 50: IARRAY [20] = 50; int * ike = find (IAARRAY, IARRAY SIZE, 50); FIND The function accepts three parameters. The first two define the scope of the search. Because the C and C arrays are equivalent to the pointers, the expression IARRAY points to the first element of the array. The second parameter IARRAY size is equivalent to the last-the-End value, which is the back position of the last element in the array. The third parameter is the value to be positioned, that is, 50. The Find () function returns the same type of iterator as the first two parameters, which is a pointer IP pointing to integers. Tip The STL uses template. Therefore, the STL function automatically constructs according to the data type they use. In order to determine if the Find () is successful, the IP and the PAST-the-End value are tested in the example: if (ip == aRray size) ... If the expression is true, it means that there is no specified within the search. value. Otherwise, it is to point to a legal object's pointer. You can display :: cout << * IP << "Found in array" << endl; test function return value and NULL are incorrect. Don't use this below: int * ip = find (IARRAY, IARRAY SIZE, 50); if (ip! = Null) ... // ??? INCORRECT When using the STL function, you can only test whether IP is and PAST -THE-End value is equal. Although IP in this example is a C pointer, the usage must also comply with the rules of the STL iterator. Container iterators Although the C pointer is also an iterator, more is more than container iterators. The container iterator usage is the same as IterDemo.cpp, but the iterator is declared that the pointer variable is different, you can use the container class method to get an iterator object.
Two typical container methods are begin () and end (). They represent the entire container range in most containers. Some other containers also provide reverse iterators using Rbegin () and rend () methods to specify the range of objects in the reverse order. The following program creates a vector container (STL and array equivalent object) and searches for it using iterators. The program is the same as the program in the previous chapter. Listing 2. Vectdemo.cpp #include #include #include using namespace std; vector intVector (100); void main () {intVector [20] = 50; Vector < INT> :: item = find (intVector.begin (), intVector.end (), 50); if (intiter! = intVector.end ()) cout << "Vector contains value" << * intiter << Endl Else Cout << "Vector Does Not Contain 50 << Endl;} Note Searching data with the following method: cout <<" Vector contains value "<< * intiter << Endl; constant iterator and pointer You can assign an iterator. For example, first stipulate an iterator: Vector first; this statement creates an iterator of a Vector class. The following statement sets the iterator to the first object of INTVector and set it to 123 :: first = intVector.begin (); * first = 123; this assignment for most container classes It is allowed, except for read-only variables. In order to prevent the error from being assigned, it can be declaring iterators as: const vector :: iterator result; result = Find (intVector.egin (), intVector.end (), value); if (Result! = IntVector.end () ) * Result = 123; // ??? WARNING Another method of preventing data is changed to declare the container as a const type. "Yeah!" In the VC, the correct meaning is that the correct meaning is that the object it is constant instead of whether it points to the object is not allowed, like int * const p; It seems that this author doesn't understand "" Use iterators "Some of the iterator Example, now we will pay attention to how each particular iterator is used. Since the use iterator requires knowledge about STL container classes and algorithms, you may need to retrieve this chapter after reading the following two chapters. Enter an iterator input iterator is the most common type. The input iterator can be used at least == and! = Testing, etc.; use * to access data; use operation to recruit iterators to the next element or reach the PAST-the-End value.
To understand how iterators and STL functions use them, now look at the definition of the Find () template function: Template InputIterator Find (InputItitrator First, InputIte Last, Const T & Value) {While (First " ! = LAST && * first! = Value) first; returnax,} Note In the FIND () algorithm, note if first and last points to different containers, the algorithm may fall into a dead cycle. Output iterators Output iterators defaults are written only, usually used to copy data from one location to another. Since the output iterator cannot read objects, you will not use it in any search and other algorithms. To read a copy value, you must use another input iterator (or its inheritance iterator). Listing 3. Outiter.cpp #include #include // NEED COPY () #include // NEED Vector Using Namespace Std; Double Darray [10] = {1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9}; vector vdouble (10); int main () {vector :: item outputiterator = vdouble.begin (); copy (darray, darray 10, outputiterator); while (outputiterator! = Vdouble.end ()) {cout << * outputiterator << endl; outputiterator ;} return 0;} Note When using a copy () algorithm, you must ensure that the target container is sufficient Large space, or the container itself is automatically expanded. The prior to tendering the prior to the prior to read and write the data value and can advance to the next value. But it can't be decremented. The replace () algorithm shows the usage method of the prior gemold. template void replace (ForwardIterator first, ForwardIterator last, const T & old_value, const T & new_value); using replace () the [first, last] all objects is old_value in the range replaced new_value. : Replace (vdouble.begin (), vdouble.end (), 1.5, 3.14159); two-way iterator bidirectional iterator requirements can be increased.
The reverse () algorithm requires two bidirectional iterators as parameters: template void reverse (BidirectionalIterator first, BidirectionalIterator last); using the reverse () function to reverse the order of the containers: reverse (vdouble.begin (), vdouble .end ()); Random Access Iterator Random Access Itecher Accesses Data in any order, and can be used to read and write data (not C pointer is also random access iterators). STL sorting and search functions use random access iterators. Random access iterators can use the relationship operation comparison. The random_shuffle () function randomly disrupts the original order. Declaration is: Template void Random_shuffle (RandomaccessIitrator last); use method: random_shuffle (vdouble.begin (), vdouble.end ()); iterator technology To learn to use iterators and containers and algorithms, need Learn the new technology below. A lot of examples of flow and iterator This book uses the I / O state of statement to read and write data. For example: int value; cout << "Enter value:"; cin >> value; cout << "You entered" << value << endl; for iterators, there is another method using streaming and standard functions. The point of understanding is to treat the input / output stream as a container. Therefore, any algorithm that accepts iterator parameters can work with the stream.
Listing 4. Outstrm.cpp #include #include // NEED Random (), Srandom () #include // NEED TIME () #include //// NEED SORT (), COPY () #include // Need Vector Using Namespace Std; Void Display (Vector & V, Const Char * S); int main () {// seed the random number generator Srandom (Time (NULL); // Construct Vector and Fill with Random Integer Values Vector Collection (10); for (INT i = 0; i <10; i ) Collection [i] = random ()% 10000 ;; // Display, Sort, And Redisplay Display (Collection, "Before Sorting"); Sort (Collection.Begin (), Collection.end ()); Display (Collection, "After Sorting"); return 0;} // Display Label S and Contents of Integer Vector V Void Display (Vector & V, Const Char * S) {COUT << Endl << S << Endl; Copy (V.Begin (), v.end (), Ostream_Iterator (cout, "/ t"))); cout << Endl;} function display () shows how to use an output stream forced. The following statement is transferred to the value in the container to the COUT output stream object: COPY (v.begin (), v.end (), OST REAM_ITERATOR (cout, "/ t")); the third parameter instantiates the ostream_iterator type, and uses it as the output target iterator object of the COPY () function. The "/ t" string is a separator. Run Results: $ G Outstrm.cpp $ ./a.out Before Sorting 677 722 686 238 964 397 251 118 11 312 After Sorting 11 118 238 251 312 397 677 686 722 964 This is the magical side of STL "indeed magical". To define the output flow, STL provides template class OSTREAM_ITERATOR. This class's constructor has two parameters: an Ostream object and a string value. Therefore, it is possible to simply create an iterator object as follows: ostream_iterator (cout, "/ n") This iteration can be used with any function that accepts an output iterator. Insert an iterator Insert iterator is used to insert the value into the container. They are also called an adapter because they adapt to a container or converted into an iterator and is used in the algorithm such as copy ().
For example, a program defines a linked list and a vector container: list DList; Vector DVector; by using the Front_Inserter iterator object, you can complete the object inserted into the linked list using only a single copy () statement. Front end: Copy (DVector.begin (), DVector.end (), Front_INSERTER ()); three insert iterators are as follows: • The ordinary insert is inserted into the front of any object of the container. · Front INSERTERS inserts the object to the front of the dataset - for example, the linked list header. · Back INSERTERS is inserted into the tail of the collection - for example, the tail of the vector, causing the vector container extension. Using an inserting iterator may cause other objects in the container to move positions, thus makes existing iterators illegally. For example, inserting an object into the vector container will cause other values to move the position to make a space. In general, it is more effective in inserting an icon list because they do not cause other objects to move. Listing 5. Insert.cpp #include #include #include using namespace std; int otray [5] = {1, 2, 3, 4, 5}; void display (list < INT> & V, Const Char * S); int main () {list ilist; // copy IaRray Backwards INTO ILIST COPY (IARRAY, IARRAY 5, Front_Insert); Display (IList, "Before Find And Copy "); // Locate Value 3 in ilist list :: Iterator P = Find (IList.Begin (), IList.end (), 3); // Copy First Two IaRray Values To ilist ahead of P Copy (IaRray, IaRray 2, Inserter (ILIST, P)); Display (IList, "After Find and Copy"); Return 0; Void Display (List & a, const char * s) {COUT < (cout, "))); cout << Endl;} The results are as follows: $ g insert.cpp ./ A.out Before Find and Copy 5 4 3 2 1 After Find and Copy 5 4 1 2 3 2 1 You can replace the Front_INSERTER to try back_inserter. If you use Find () to find a value that does not exist in the list, for example, 99. Since Past-the-end value is set at this time. The final copy () function attached the value of the IARRAY to the rear of the linked list. The mixed iterator function is in operation involving the container and algorithm, and there are two iterator functions: · Advance () adds or decreases the iterator by specified number.
· Distance () Returns the number of operations required to reach an iterator (increment) operation. For example: List ilist; list :: Iterator P = Find (IList.Begin (), IList.end (), 2); cout << "before: p == << * p << Endl; Advance (p, 2); // Same AS P = P 2; cout << "after: p ==" << * P << endl; int K = 0; Distance (p, ilist.end) ), K); cout << "k ==" << k << endl; advance () function accepts two parameters. The second parameter is the number of advanced advancement. For the front gear, this value must be positive, and the value can be negative for the two-way iterator and the random access iterator. Use the discance () function to return to the steps you need to reach another iterator. Note that the distance () function is iterative, that is, it increments the third parameter. Therefore, you must initialize this parameter. This parameter is not initialized to fail. Functions and Function Objects STL, the function is called an algorithm, which is more common compared to the standard C library function. The STL algorithm is implemented as a template class or template function by overloading the Operator () function. These classes are used to create a function object, perform a wide variety of operations in the container. The following sections explain how to use functions and function objects. Functions and assertions often require user-defined operations in the container. For example, you might want to traverse all objects of all objects in a container can call our function.
For example #include #include // need random (), srandom () #include // need time () #include //ned Vector #include < Algorithm> // NEED for_each () #define vsize 24 // size of vector vector v (vsize); // vector Object // Function Prototypes void Initialize (long & ri); void show (constling & ri); bool ISminus (constical function int main () {srand (Time (NULL); // seed random generator for_each (v.begin (), v.end (), initialize; // call normal functions Cout << "Vector of Signed Long Integers << Endl; for_Each (v.begin (), v.end (), show); cout << endl; // use predicate function to count negative value // int count = 0; Vector :: Iterator P; p = find_if (v.begin (), v.end (), isminus); // call the assertion function while (p! = V.end ()) {count ; P = Find_if (p 1, v.end (), isminus);} cout << "Number of values:" << vsize << endl; cout << "Negative Values:" << count << Endl; Return 0 } // Set ri to a signed integer value void initialize (long & ri) {ri = (rand_max / 2); // ri = random ();} // Display value of ri void show (const long & ri) { Cout << ri << ";} // returns true if ri is less 0 BOOL ISMINUS (Const long & ri) {return (ri <0);} The so-called assertion function is a function that returns the BOOL value. In addition to sending a callback function to the STL algorithm, you may also need to pass a class object to perform more complex operations. Such an object is called a function object. In fact, the function object is a class, but it can be called with the callback function. For example, statistics can be retained each time the function object is called by the for_each () or FIND_IF () function. Function objects are implemented by overloading Operator () () ().
If tanyclass defines Opeator () (), you can use this: TanyClass Object; // Construct Object Object (); // Calls TanyClass: perator () Function for_Each (v.begin (), v.end ), Object); STL defines several function objects. Since they are templates, they can be used for any type, including the intrinsic data type inherent in C / C , such as long. Some function objects can see its use from the name, such as Plus () and multiplies (). Similar greater () and less-equal () are used to compare two values. Note that some versions of ANSI C define the Times () function object, while GNU C names menulies (). The header file must be included when using it. An application of a useful function object is an Accumulate () algorithm. This function calculates the sum of all values in the container. Remember that such a value is not necessarily a simple type, by overloading Operator () or class object. Listing 8. Accum.cpp #include #include // NEED Acumulate () #include // NEED Vector #include // NEED MULTIPLIPLIES () (or Times ()) #define max 10 Vector v (max); // vector Object int main () {// Fill Vector Using Convenctional Loop // for (INT i = 0; i ()); // Note this line cout << "Product of Values = = "<< Product << Endl; Return 0;} Compilation output is as follows: $ g accum.cpp $ ./a.out sum of values == 55 Product of values == 362800" Note Accumulate () using functions objects () Usage. Accumulate () Calculate the objects of the objects and the third parameter in each container as the parameters of the Multiplies function object, Multiplies (1, v).
The source code of these templates in the VC is as follows: // Template Function Accumulate Template inline _ty account (_ii _f, _ii _l, _ty _v) {for (; _f! = _L; _ f) _v = _V * _f; return (_v);} // template function Accumulate with binop template inline _ty account (_ii _f, _ii _l, _ty _v, _bop _b) {for _F = _L;! _ F) _V = _B (_V, * _F); return (_V);} // TEMPLATE sTRUCT binary_function template struct binary_function {typedef _A1 first_argument_type; typedef _A2 second_argument_type; typedef _R result_type;}; // TEMPLATE sTRUCT multiplies template struct multiplies: binary_function <_Ty, _Ty, _Ty> {_Ty operator () (const _Ty & _X, const _Ty & _Y) const {return (_X * _Y );}}; Introduction: If you want to know how STL is achieved, the best way is to write a simple program, put the template source code involved in the program to COPY, slightly finishing, you can understand . So there is no need to buy a book such as "STL source profiling", and those books may waste time. "Generator function object has a useful function object is" generator ". Such functions have their own memory, that is, it can remember a value from the previous call. For example, a random number generator function. Ordinary C programmers use static or global variables "Memory" last call results. But the disadvantage of this is that the function cannot be separated from its data. "There is also a disadvantage to use TLS to thread security." Obviously, use classes to encapsulate a piece: "Memory" is safer and reliable.
Let's take a look: Listing 9. randfunc.cpp #include #include // need random (), srandom () #include // need time () #include // Need Random_shuffle () #include // NEED Vector #include // NEED PTR_FUN () Using Namespace std; // Data to Randomize Irray [10] = {1, 2, 3 , 4, 5, 6, 7, 8, 9, 10}; Vector v (IaRray, IARRAY 10); // Function Prototypes Void Display (Vector & VR, Const Char * S); unsigned int randInt (const unsigned int n); int main () {srandom (time (NULL); // Seed random generator Display (v, "Before shuffle:"); pointer_to_unary_function ptr_RandInt = ptr_fun (randInt ); // pointer to randint () // Note this line Random_shuffle (v.begin (), v.end (), ptr_randint); Display (v, "after shuffle:"); return 0;} // Display Contents Of Vector VR Void Display (Vector & VR, Const Char * S) {COUT << Endl << S << Endl; Copy (Vr.Begin (), vr.end (), Ostream_IstRerator (cout, "")); cout << endl;} // return next random value in sequence modulo n unsigned int randint (const unsigned int n) {return random ()% n;} Compilation operation results are as follows: $ g Randfunc.cpp $ ./a.out before shuffle: 1 2 3 4 5 6 7 8 9 0 After shuffle: 6 7 2 8 3 5 10 1 9 4 First use the following statement to declare an object: Pointer_TO_UNARY_Function PTR_RANDINT = PTR_FUN (RANDINT); This use STL's single-grade function template defines a variable PTR_Randint, and initializes the address to our function randint (). A single-grade function accepts a parameter and returns a value. Now random_shuffle () can call: random_shuffle (v.begin (), v.end (), ptr_randint); In this example, the generator is just a simple calls the RAND () function.
A little hassle about constant references (not translated, the const removal of the Const) generator class object below describes the use of the generator function class object.
Listing 10. fiborand.cpp #include #include // Need random_shuffle () #include // Need vector #include // Need unary_function using namespace std; // Data to Randomize Int IaRay [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Vector v (IARRAY, IARRAY 10); // Function Prototype Void Display (Vector & vr, const char * s); // The Fiborand Template Function-Object Class Template Class Fiborand: Public Unary_Function {INT I, J; Arg Sequence [18]; public: Fiborand (); arg operator () (const arg & arg);}; void main () {FIBORAND Fibogen; // Construct Generator Object Cout << "Fibonacci Random Number Generator" << Endl; cout << "Using Random_shuffle and a function object "<< Endl; Display (v," before shuffle: "); random_shuffle (v.begin (), v.end (); display (v," after shuffle: ");} // Display Contents of Vector VR Void Display (Vector & VR, Const Char * S) {COUT << Endl << << Endl; Copy (vr.begin (), vr.end (), ostream_iterator )); cout << end1;} // fiborand class constructor template Fiborand :: fiborand () = 1; sequence [16] = 2; for (int N = 15; n> 0; n-) sequence [n] = sequence [n 1] sequence [n 2]; i = 17; j = 5;} // fiborand class function operator template arg fiborand : peerator () (const arg & arg) {arg k = sequence [i] sequence [j] ; Sequence [i] = k; I -; J -;
IF (i == 0) i = 17; if (j == 0) j = 17; Return K% arg;} Compile operation output is as follows: $ g fiborand.cpp $ ./a.out fibonacci random number generator using random_shuffle And A Function Object Before Shuffle: 1 2 3 4 5 6 7 8 5 4 3 7 10 1 9 This program uses rand_shuffle with a complete method. The Fibonacci generator package is in a class, which can remember the results from previous "use". In this example, class FIBORAND maintains an array and two index variables I and J. FIBORAND class inherits from unary_function () template: Template Class Fiborand: public unary_function {... arg is a user-defined data type. This class also sets two member functions, one is a constructor, and the other is an Operator () () function that allows the Random_shuffle () algorithm as "call" a Fiborand object like a function. Binder Function Object A binder uses another function object F () and parameter values V Create a function object. The bound function object must be a binocular function, that is, there are two parameters, A and B. STLs are: • Bind1st () Create a function object that will value the value V as the first parameter A. · BIND2ND () Creates a function object that will value Value V as the second parameter B. Examples are as follows: Listing 11. Binder.cpp #include #include #include #include using namespace std; // data int aRray [10] = {1, 2, 3 , 4, 5, 6, 7, 8, 9, 10}; List Alist (IARRAY, IARRAY 10); int Main () {INT K = 0; count_if (alist.begin (), alist.end (), Bind1st (Greater (),, k); cout << "Number Elements <8 ==" << k << endl; return 0;} Algorithm count_if () calculates the number of elements that meet specific conditions This is achieved by bundling a function object and a parameter into an object, and implements the object as the third parameter of the algorithm. Note this expression: bind1st (Greater (), the expression will Greater () and a parameter value 8 bundle into a function object. Since bind1st () is used, the function is equivalent to calculating the following expression: 8> Q Expression q is an object in the container. therefore, Complete expression count_if (alist.egin (), alist.end (), bind1st (Greater (),, k); calculates the number of objects that are less than or equal to 8.
