STL Practice Guide

STL Practice Guidelines Practical Guide to STL Author: Jeff Bogan Translation: Zhou Xiang

Translator Note This is an article guided how you learn STL and practice in Microsoft Visual Studio. This article spoken from STL, step by step, gradually, involved in the method of STL writing code, STL code compilation, Namespace, ANSI / ISO string in STL, Various types In container, Template, Iterator, Algorithms, Allocator, container nested, etc., the author puts some suggestions in this article, and Point out the problem that should be noted when using STL. This article covers wide, and the perspective is comprehensive. It is not only suitable for beginners to learn STL, but also the practice guidelines for the readers using STL programming.

STL introduction

STL (Standard Template Library, Standard Template Library is a good technology that needs to master C programming today. I think everyone who first school STL should spend some time to familiarize it. For example, there will be a lot of learning curves in a sharp rise, and some name is not easy to remember, maybe I know. The name has been used in light), however, if you have a STL, you will not feel headache. STL is more complex and powerful than MFC. STL has some advantages:

It is convenient to easily implement a series of algorithms such as search data or sort of data; more secure and convenient when debugging procedures; even if people use STL, you can easily understand (because STL is cross-platform of).

background knowledge

Write this part is to let some beginner's readers have a good start in the challenging computer science field, not to understand the endless japanese terms and dull rules, just regarding those jars and rules here. STLER is used for self-entertainment creation.

The code used in this article is mainly guided in STL practice.

Some definitions of foundation concepts

Template - macro (Macro) of a class (and various data types and functions such as structures). Sometimes called a cookie cutter, a regular name should be called a generic - a class template called the generic class, and a function of a function is naturally called a modest function ( Generic function. STL - Standard Template Library, some of the intelligent people written some templates now have become part of the standard C language used by each person. Container - template class that can accommodate some data. There are versors such as VECTOR, SET, MAP, MULTIMAP and DEQUE in STL. Vector - Basic Array Template, which is a container. Cursor (Iterator) - This is a strange thing, it is a pointer to point to the elements in the STL container, or to other elements.

Hello World Program

I am willing to write my programs here: a Hello World program. This program transmits a string to a character vector and then displays one of the characters in the vector. The vector is like a garden that is growing, and half of all STL containers is based on the vector. If you have the program, you will almost master half the entire STL. // Program: Vector Demonstration One // Purpose: Understand the vector in STL

// #include "stdafx.h" - If you use the precompiled header file, you contain this header file #include

// STL vector header file. There is no ".h" here.

#include

/ / Contain the header file of the COUT object.

Using namespace std; // guarantees that members in the STD namespace can be used in the program.

Char * szhw = "Hello World"; // This is an array of characters and ends with "/ 0".

INT Main (int Argc, char * argv []) {Vector

Vec; // Declare a character vector vector (array in STL)

/ / Define a cursor Iterator for the character array. Vector

:: Iterator vi;

// Initialize the character vector, loop the entire string, // is used to fill the data into the character vector until "/ 0" is encountered. Char * cptr = szhw; // points a pointer to "Hello World" string while (* cptr! = '/ 0') {vec.push_back (* cptr); CPTR ;} // push_back function put data in vector The tail.

// Display the characters in the vector in the console for (vi = vec.begin (); vi! = Vec.end (); vi ) // This is the standardized start of the STL loop - usually " ! = ", Not" <"// because" <"is not defined in some containers. // begin () Returns the cursor of the vector starting element (Ite () returns the cursor (Iterator) of the vectors of the vector. {Cout << * vi;} // Use operator "*" to extract data from the cursor pointer. Cout << Endl; //

Return 0;}

Push_back is a standard function that puts data into a Vector (vector) or Deque (two-end queue). INSERT is a similar function, however it can be used in all containers, but usage is more complicated. End () is actually taking the end of the end (the previous elements at the end of the container) so that the loop is correctly run - it returns the pointer to the most close-to-array boundary. Just like an array in a normal cycle, such as for (i = 0; i <6; i ) {ar ​​[i] = i;} --ar [6] does not exist, this element does not reach this element in the loop. Therefore, there will be no problem in the cycle.

One of the troubles of STL - initialization

STL is annoying place to initialize it. The initialization of the containers in the STL is more troublesome than that of the C / C array. You can only be an element, or first initialize a normal array and then fill in the container by transformation. I think people can usually do this:

// Program: Initialization Demo // Objective: To illustrate how the vector in STL is initialized.

#include

//

with

the same

#include

Using namespace std; int Ar [10] = {12, 45, 234, 64, 12, 35, 63, 23, 12, 55}; char * str = "Hello World";

INT Main (int Argc, char * argv []) {Vector

VEC1 (Ar, Ar 10);

Vector

VEC2 (STR, STR STRLEN (STR);

Return 0;

}

In programming, there are many ways to complete the same job. Another way to fill the filler is to use more familiar square brackets, such as the following procedures:

// Program: Vector Demo 2 // Purpose: Understand the STL vector with array subscript and square brackets

#include

#include

#include

Using namespace std;

Char * szhw = "Hello World"; int Main (int Argc, char * argv []) {Vector

VEC (Strlen); / / / / Distribute memory space

INT I, K = 0;

Char * cptr = szhw;

While (* CPTR! = '/ 0')

{VEC [K] = * CPTR; CPTR ; K ;}

For (i = 0; i

{Cout << vec [i];

Cout << Endl;

Return 0;

}

This example is clearer, but the operation of the cursor is less, and the additional shape is defined as the subscript, and you must clearly explain how much memory space is displayed in the program. Namespace (Namespace) is related to STL is Namespace. STL is defined in the STD namespace. There are three ways to declare the namespace used: 1. Use this namespace using this namespace, on the top of the file, but add: USING NAMESPACE STD; this method is the simplest method for a single project, this method can limit your code In the STD namespace. 2. Declaration of each object to be used before each template (just like originalization): use std :: cout; using std :: endl; using std :: flush; using std :: set; using std :: inserter Although there is a certain length of rotation, it can be more favorable for the function of memory usage, and you can easily declare and use members in other namespaces. 3. Using the STD domain identifier when using the template in the STD namespace. For example: typedef std :: Vector

VEC_STR;

This method is relatively long, but is the best way to mix the use of multiple namespaces. Some STL's fanatics have been using this method and regard those who do not use this method as a heterogeneous. Some people will build some macro simplified issues through this approach.

In addition, you can add Using Namespace STD to any domain, such as the head or a control cycler of the function. Some suggestions To avoid annoying warnings in debug mode, using the following compiler command: #pragma Warning (Disable: 4786) Another thing to note is that you must ensure that between two angle brackets or sharp brackets And the name is spaced between space because it is to avoid confusion with the ">>" shift operator. Such as vector> veclis;

This will write an error, but write this: Vector

> VECLIS;

Avoid errors. STL Practice Guidelines Practical Guide to STL Author: Jeff Bogan Translation: Zhou Xiang (Continued papers) Another vessel - a collection (set) which is Microsoft's help documentation to explain the collection (set): "The description of a control variable Objects of long element sequences (Note: Key and Value in Sets are key types, while Key and Value in Map are two components of a pair structure), each element contains a sort button (Sort Key) and a value (Value). You can find, insert, and delete any of the elements in the sequence, while the time to complete these operations is a ratio of the number of elements in this sequence, and when the binder points When a deleted element, the deletion operation is invalid. "And a corrected and more actual definition should be: A collection (SET) is a container, which is unique in which the value of the elements included is unique. This is useful when collecting a specific value of a data. The elements in the collection are arranged in a certain order and are used as an example in the collection. If you need a key / value pair (PAIR) to store data, MAP is a better choice. A collection is organized through a linked list, which is slower than the vector (Vector), but finds or adds the end of the elements. Here is an example: // Program: SET Demo // Purpose: Understand the collection of STLs (SET) #include

#include

#include

Using namespace std;

INT Main (int Argc, char * argv []) {set

STRSET;

set

:: Iterator Si;

StRSET.INSERT ("Cantaloupes");

strSet.insert ("Apple");

STRSET.INSERT ("Orange");

STRSET.INSERT ("banana");

STRSET.INSERT ("grapes");

STRSET.INSERT ("grapes");

For (Si = strset.begin (); si! = strSet.end (); Si )

{Cout << * si << ""

Cout << Endl;

Return 0;

}

// Output: Apple Banana Cantaloupes grapes Orange // Note: The elements in the output of the output are arranged in the order of alphabetically, and each value is not repeated. If you are interested, you can replace the output loop with the following code: Copy (strSet.Begin (), strset.end (), ostream_iterator (cout, "));

Although the collection (SET) is more powerful, I personally think that it is unclear, and it is easier to make mistakes. If you understand this, you will know what to do with a collection (SET). All STL container containers' concept appeared earlier than template, which was originally an important concept in a computer science area, but here, its concepts were mixed together. Below is the 7 containers that appear in STL: Vector - STL is secure array. Can only add data in the "front" of the Vector. DEQUE (Double-end queue double-ended queue) - is similar to the vector, but data can be added to the front and rear ends. List (list) - The cursor can only be moved at a time. If you are already familiar with the list, then the LIST in the STL is a two-way linked list (each node has two pointers that are forwarded and pointing to the successive subsequent). Set (Collection) - contains sorted data, which must be unique. Map (mapping) -Rolded binary groups, each element in MAP consists of two values, where the key (key value, key value in a map must be unique) Use when sorting or searching, it can be re-acquired in the container; and the other value is the value associated with the element. For example, in addition to the AR [43] = "Overripe" finds a data, the MAP can also find a data via Ar [Banana "] =" Overripe ". If you want to get the element information, you can easily implement the full name of the input element. MultiSet - and Collection (SET) are similar, but the values ​​are not required to be unique (ie, repetition). MultiMap - and Mapp (MAP) are similar, however, the key value is not required (that is, you can have repetition). Note: If you read Microsoft's help documentation, you will encounter a statement on the efficiency of each container. For example: LOG (N * n) insertion time. The impact of these times can be ignored unless you have to handle a lot of data. If you find that your program has obvious hysteresis or requires time critical things, you can learn more about various container operational efficiency. How to use classes in a map? MAP is a template class that gets value (value) through the Key. Another problem is that you want to use your own classes in Map, not existing data types, such as INT that has been used now. Create a "Template-Ready" class, you must ensure that some member functions and overload operators are included in this class. Some members of the following are must:

The default constructor (usually empty) copy constructor overload "=" operator you should overload as many operators as possible to meet the needs of a particular template, for example, if you want to define a class as MAP Key (key), you must overload the relevant operator. But there is no discussion of overload operators here. // Program: Map the custom class. // Objective: Describe how to use custom classes in MAP. # include # include

#include

#include

Using namespace std;

Class cstudent {public: int nStudentId; int nage; public: // Default constructor - usually empty cstudent () {} // complete constructor cstudent (int nsid, int NA) {nStudentId = nsid; NAGE = Na;} // copy constructor cstudent (const cstract & ob) {nStudentId = ob.nstudentID; Nage = ob.nage;} // Reserved "=" void operator = (const cstudent & ob) {nstudentId = ob.nstudentId; Nage = ob.nage;}}; int main (int Argc, char * argv []) {map

Mapstudent;

MapStudent ["Joe Lennon"] = CSTUDENT (103547, 22); MapStudent ["Phil McCartney"] = CStudent (100723, 22); MapStudent ["Raoul Starr"] = CStudent (107350, 24); Mapstudent ["Gordon Hamilton "] = CSTUDENT (102330, 22); // Access the member COUT <<" The Student Number for Joe Lennon IS "in the CStudent class through the name << (MapStudent [Joe Lennon"]. NstudentID) << ENDL; Return 0;} typedef If you like to use the typedef keyword, the following is an example: TypeDef Set

Set_int;

TYPEDEF SET_INT :: Iterator Set_INT_ITER

A habit of writing code is to use uppercase letters and underscores to name data types. ANSI / ISO String ANSI / ISO string is used in the STL container. This is a standard string class and has been widely advocated, but problems will be issued in the absence of format declaration. You must use the "<<" and input and output streams (such as DEC, Width, etc.) to link the string. The character pointer can be re-obtained using c_str () when necessary.

STL Practice Guidelines Practical Guide to STL Author: Jeff Bogan Translation: Zhou Xiang

(Connected)

Iterator

I said that the cursor is a pointer, but it is not just a pointer. The cursors and pointers are very similar, and the functions are very like pointers, but in fact, the cursor returns a value from the container in the container. Store these values ​​in the container is not a good idea, because every new value is added to the container or has a value deleted from the container, these values ​​will be invalid. To a certain extent, the cursor can be regarded as a handle (HANDLE). Normally, the type of ITATOR can vary, so that the container will also have several different ways: Iterator - For any other container other than the Vector, you can use this cursor in a container in a container Take a step in the direction of the front. This means that you can only use the " " operator for this kind of cursor. And you can't use the "-" or " =" operator. For the container of Vector, you can use " =", "-", " ", "=", and "<", "<=", ">", Comparison operators such as "> =", "==", "! =". Reverse_iterator - If you want to use the coming direction instead of the forward direction, you can traverse the elements in the container outside the vector, you can use the reverse_iterator to reverse the direction of traversal, you can also use rbegin () Instead of begin (), replace end (), while the " " operator is traversed in the direction behind. Const_iterator - a cursor in forward direction that returns a constant value. You can use this type of cursor to point to a read-only value. Const_reverse_iterator - a cursor traversed in the opposite direction that returns a constant value. Sort in Set and Map

In addition to type and value, templates contain other parameters. You can pass a callback function (usually the statement "predicate" - this is a function with a parameter returns a Boolean value). For example, if you want to automatically create a collection, the elements in the collection are arranged in ascending order, you can build a set class with a concise method:

set

> set1

Greater

It is another template function (norm function) that is used to sort these values ​​when the value is placed in the container. If you want to arrange these values ​​in descending, you can write this:

set

> set1

When implementing an algorithm, a lot of situations are passed as a parameter into a STL template class, and these situations will be described in detail below.

STL's troubles - Error information

Names of these templates need to be expanded to the compiler, so when the compiler fails, it will list a long error message, and these error messages are difficult to understand. I don't think there is a good way to deal with this problem. But the best way is to find and carefully study the end of the code segment. Another trouble is: When you double-click the error message, it will correct the internal code of the template library, and these code is more difficult to read. Under normal circumstances, the best way to correct the correctment is to re-check your code and ignore all warning messages when running.

Algorithms

The algorithm is a function used in the template. This really begins to reflect the power of STL. You can learn some of the algorithms that can be used in most template containers so you can sort, find, exchange, etc. in the easiest way. The STL contains a series of functions of a series of implementation algorithms. For example: sort (vec.begin () 1, vec.end () - 1) enables the ordering operation of other elements of the first and last elements. The container itself cannot use an algorithm, but the cursor in the two containers can define an element using algorithm in the container. In this case, the algorithm is not directly limited by the container, but by using a cursor, the algorithm can be supported. In addition, many times you will encounter a function that is ready (previously mentioned: Predicate) as a parameter, you can also pass the previous old value. The following example demonstrates how to use algorithms: // Program: Test score statistics // purpose: How to use algorithm by operating the score saved in the vector

#include

// If you want to use an algorithm function, you have to include this header file.

#include

/ / Contain the header file of the ACCULATE function

#include

#include

Using namespace std;

INT testscore [] = {67, 56, 24, 78, 99, 87, 56};

/ / Judging whether a grade passes the test bool passed_test (int N) {return (n> = 60);

/ / Judge whether a grade does not have a BOOL FAILED_TEST (INT N) {Return (N <60);

INT Main (int Argc, char * argv []) {int total; // Initialization vector, enable it to load the elements in the Testscore array

VECTESTSCORE (Testscore,

Testscore SizeOf (Testscore) / sizeof (int));

Vector

:: Iterator vi;

// Sort and display the data in the vector sort (vectestscore.begin (), vectestscore.end ()); cout << "sorted test score: << Endl; for (vi = vectestscore.begin (); vi! = VECTESTSCORE.END (); vi ) {cout << * vi << ",";} cout << endl;

// Display statistics

// min_element returns a _iterator_ type object that points the minimum value of the value. // "*" operator extracts the value in the element. Vi = min_egin (), vectestscore.end ()); cout << "The lowest score was" << * vi << "." << endl;

// Similar to Min_Element, MAX_ELEMENT is the maximum value. Vi = max_element (vectestscore.begin (), vectestscore.end ()); cout << "" The highest score was "<< * vi <<". "<< Endl;

// Use the declaration function (Predicate function, refer to VECTESTSCORE.BEGIN () and vectestscore.end () to determine the number of people through the exam. Cout << count_ifin (), vectestscore.egin (), passed_test) << "out of" << vectestscore.size () << "students passed the test" << Endl; // Determine how many people The exam hung (vectestscore.begin (), vectestscore.end (), filed_test) << "out of" << vectestscore.size () "students failed the test" <<

// Calculate the sum of grades Total = Accum (), vectestscore.egin (), vectestscore.egin (), 0); // calculate the average grade COUT << "Average Score WAS" << (Total / (INT) (vectestscore.size ())) << ENDL;

Return 0;}

ALLOCATOR (Distributor)

Allocator is used in the initial phase of the template, which is a template class that assigns memory space and release space operations for objects and arrays. It plays a very mysterious role in a variety of situations, which is concerned about the optimization of high-level memory, and for black box testing, using allocator is the best choice. Typically, we don't need to specify it because they are usually arguable as the default parameters that do not have to be added. If Allocator appears in a professional test, you'd better understand what it is.

Embed Templates and Derive Templates Whenever you use an ordinary class, you can use a STL class in it. It can be embedded:

Class CParam {string name; string unit; vector

Vecdata;

}

Or use it as a base class:

Class CParam: Public Vector

{

String name;

String unit;

}

The STL template class needs to be cautious as the base class. This requires you to adapt to this programming.

Template in the template

To build a complex data structure, you can implant a template into another template (ie "template nested"). The general method is to define a template type using the TypeDef keyword in front of the program.

// Program: Demo in the vector in vector. // Objective: To explain how to use nested STL containers.

#include

#include

Using namespace std;

TypedEf Vector

VEC_INT;

INT INP [2] [2] = {{1, 1}, {2, 0}}; // To put the regular array of 2x2 in the template

INT Main (int Argc, char * argv [],,;; vector

Vecvec;

// If you want to implement such a nested in a sentence, you can write this:

// vector

> VECVEC;

// Fill the array in vector VEC_INT V0 (INP [0], INP [0] 2);

/ / Pass two pointers

/ / Copy the value in the array into the vector

VEC_INT V1 (INP [1], INP [1] 2);

VECVEC.PUSH_BACK (V0); VECVEC.PUSH_BACK (V1);

For (i = 0; i <2; i ) {for (j = 0; j <2; j ) {cout << VECVEC [i] [j] << ";} cout << Endl;} Return 0 }

// Output: // 1 1 // 2 0

Although it is troublesome when initialization, once you bring the data, you will have a long expandable two-dimensional array (size can be expanded until the memory is used). Depending on the actual needs, nested combinations of various containers can be used.

Summary STL is useful, but difficulties and trouble during use are inevitable. Just like the Chinese said: "If you master it, it is like a tiger to add."

Related Links: Josuttis Website: http://www.josuttis.com/pretty Good Initialization Library: http://www.codeproject.com/vcpp/stl/pgil.asp

(Full text)