One of the generic programming and design of new thinking

One of the generic programming and design of new thinking

Xu Jingzhou

Foreword

Always remember, the purpose of writing code is to make it clear, don't use the remote features in the language, play smart, and important is to write the code you understand, understand the code you write, so you may do better.

--- Herb SUTTER

In 1998, the international C standard was officially passed, and the standardization of C is the most important contribution to "powerful abstraction concept" gives more powerful support to reduce the complexity of software, and C provides two powerful abstract methods: Object-oriented programming and generic programming. Object-oriented programming, you must be very familiar, here no longer. Remove generic programming, some people may not be familiar, but mentioned STL, you will have to hear. STL (Standard Template Library) is actually the implementation of generic programming, STL is developed by Alexander Stepanov (Father), David R Musser and Meng Lee, is incorporated into C standard procedures in 1994 Library. Although STL is relatively late to join the C standard library, it is the most revolutionary part of the C standard library, and is also the most important part of the C standard library. Because almost everything in the new C standard library is made by template, of course, STL will not exceed So, there is a need to first explain the concept of the template.

Template concept

The program can have better code reuse by using the template. Remember, the template is reused the source code, not by inheriting and combining reuse object code, when the user uses templates, the parameters are replaced by the compiler. The template consists of two parts of the class template and function template, with the description of the data type as the parameter is called class template, and the description of the data type is called a function template. Template parameters can be composed of type parameters or non-type parameters. The type parameters can be specified by Class and TypeName keywords. The two senses are the same, which means that the back parameter name represents a potential built-in or user-defined type, non-type parameters A normal parameter declaration composition. Here is a simple usage of class templates and function templates:

Template

Class queue // class template, where t1 is type parameters, size is non-type parameters

{

PUBLIC:

Explicit Queue (): SIZE_ (SIZE) {}; // Explicit constructor to avoid implicit conversion

......

Template Void Assign (T2 First, T2 Last); // Inline Function Template

Private:

T * TEMP_;

Int size_;

}

///-class function template COMPARE in the class template (such as external implementation outside the queue class)

Template Template

Void Queue :: Assign (T2 First, T2 Last) {};

// Template usage

INT IA [4] = {0, 1, 2, 3};

Queue QI;

Qi.assign (Ai, Ai 4);

Generic programming

Pan-type programming and object-oriented programming, it does not require you to call a function through additional indirect layers, which allows you to write fully and reused algorithms, the efficiency is the same as the algorithm designed for a particular data type. . Generic programming representative works STL is an efficient, generic, interactive software component. The so-called genericity refers to an integrated meaning on a variety of data types, which is similar to the template. STL is huge, and it can be expanded, which contains many computer basic algorithms and data structures, and the algorithm is fully separated from the data structure, where the algorithm is generic, not with any particular data structure or object type. STL is based on an iterators and container (Containers), which is a generic algorithms library, and the existence of containers makes these algorithms. STL contains various generic algorithms, generic pointers, generic containers, and Function Objects. STL is not only a collection of useful components, which is a formal and organized architecture that describes the abstract demand conditions of software components. Iterators is the core of STL, which is a generic pointer, an object that points to other objects (Objects), and iterator can traverse the interval formed by the object. The iterator allows us to separate the container (containers) to the algorithms on which most of the algorithms do not directly operate directly on the container, but is operated in the interval formed by the iterator. Iterator is generally divided into five: Input Iterator, Output Iterator, Forward Iterator, Bidirections Iterator and Random Access Iterator. Input Iterator is like only read data from the input interval, which belongs to one-way movement, such as ISTREAM_ITERATOR in STL. Output Iterator is just the opposite, only written to the output interval, with only written, belonging to the OSTREAM_ITERATOR in STL. The Forward Iterator also belongs to one-way, but the difference is that it has data read, write. Bidirections Iterator, such as name, supporting two-way movement, not only can accumulate ( ) to get the next element, but can be decremented (-) to take the previous elements, support read, write. The Random Access Iterator function is the strongest. In addition to the above iterator features, random elements access (P = N), subscript (P [n]), subtractive (P1-P2) and front-order relationship (P1 < P2), etc. Input Iterator and Output Iterator are the equivalents of two iterators, and Forward Iterator is a REFINEMENT. The Bidirections iterator is also strengthened, and the last Random Access Iterator is the Bidirections Iterator iterator. strengthen. The following simple example shows the function of Input Iterator, Forward Iterator, Bidirections Iterator, and Radom Access Iterator iterator (where input_iterator_tag and other tag strings are exclusive identifiers to different iterator):

1, INPUTITERATOR

Template

Void Advance (INPUTITERATOR & I, DISTANCE N, INPUT_ITERATOR_TAG) {

For (; n> 0; - N, i) {} // inputiterator has

}

2, ForwardItemrator

Template

Void Advance (ForwardItemrator & I, Distance N, Forward_Iterator_tag)

{

Advance (i, n, infut_iterator_tag ());

}

3, BidirectionAliterator

Template

Void Advance (BidirectionAliterator & i, distanceAnce n, bidirectional_iterator_tag)

{

IF (n> = 0) // has ,-sex

For (; N> 0; - N, i) {}

Else

For (; n> 0; n, - i) {}

}

4, RandomaccessIitrator

Template

Void Advance (RandomaccessIitrator & I, Distance N, Random_Access_iterator_tag)

{

i = n; // has , -, = equivalent

}

Function Object also is also called an imitation function (FUNCTOR), is an object that calls syntax in general functions. Function Pointer is a function object, all member functions with Operator () operator overload. It is also a function object. Function objects are generally divided into three forms of unary function (unary function), binary function, which can be f (), f (x) and f (x, y) The form is called, and all other function objects defined by STL are enhanced in these three concepts. Simply exemplify the implementation of several forms:

1, unnense (Generator)

Struct Counter

{

Typedef int result_type;

Counter (result_type init = 0): n (init) {}

Result_type operator () {return n ;}

Result_type n;

}

2, unary function form

Template struct evenu // function object Even, find the first even number

{

Bool Operator () (Number X) const {return (x & 1) == 0;}

}

// Use the algorithm find_if in the interval A to A N to find the element that satisfies the function object Even

INT A [] = {1,0,3,4};

Const int n = sizeof (a) / sizeof (int);

Find_if (A, A N, Even ());

3, binary function form

Struct ltstr

{

BOOL Operator () (const char * s1, const char * s2) const {return strcmp (S1

}

// Use the function object LTSTR, output the pane of A and B in the SET container

Const int N = 3

Const char * a [n] = {"xjz", "xzh", "gh"};

Const char * b [n] = {"jzx", "zhx", "abc"}

Set a (a, a n);

Set b (b, b n);

Set_union (a.begin (), a.end (), b.begin (), b.end (), ostream_iterator (cout, "), ltstr ());

Container is an object that can contain and manage other objects, and provide an iterators to address elements they contain. According to the different types of iterators, the container is also divided into a few, with the general Container for the Iterator iterator, with the Forward Iterator as an iterator, the Reversible Container, which is the Random Access Iterator, based on the Random Access Iterator as iterator. The Random Access Container of the device. STL defines two sizes of variable containers: Sequence Container and Associative Container Sequence containers include Vector, List, and Deque, associated containers include SET, MAP, MULTISET, and MULTIMAP. The following example illustrates the use of some containers:

1, Vector

/ / The element is divided into the element 5 as the segmentation point, respectively, so that the elements behind the sort 5 are greater than 5 (the rear interval is not sorted), and then output

int main ()

{

INT A [] = {7, 2, 6, 4, 5, 8, 9, 3, 1};

Const int n = sizeof (a) / sizeof (int);

Vector V (A, A N);

Partial_sort (V, V 5, V N);

Copy (v, v n, ostream_iterator );

Cout << Endl;

}

Output may be: 1 2 3 4 5 8 9 7 6

2, List use

// Generate an empty list, order after inserting the element, then output

int main ()

{

List L1;

L1.push_back (0);

L1.push_front (1);

L1.INSERT ( L1.Begin, 3);

L1.SORT ();

Copy (l1.begin (), l1.end (), ostream_iterator (cout, "));

}

Output: 0 1 3

3, DEQUE

int main ()

{

DEQUE q;

Q.push_back (3);

Q.push_front (1);

Q.insert (q.begin () 1, 2);

Copy (q.begin (), q.end (), ostream_iterator (cout, "));

}

Output: 1 2 3

4, MAP use

int main ()

{

Map m; m.insert (Make_Pair ("A", 11);

Pair

IF (p.second)

Cout << p.first-> second << endl;

}

Output: 5

5, MultiSet

int main ()

{

Const int n = 5;

INT A [n] = {4, 1, 1, 3, 5};

MultiSet a (a, a n);

Copy (a.begin (), a.end (), ostream_iterator (cout, "));

}

Output: 1 1 3 4 5