Generic Programming and design of the new thinking: Xu Jing Zhou
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
Private:
T * TEMP_;
Int size_;
}
///-class function template COMPARE in the class template (such as external implementation outside the queue class)
Template
Void Queue
// Template usage
INT IA [4] = {0, 1, 2, 3};
Queue
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
{
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 Set Set_union (a.begin (), a.end (), b.begin (), B.End (), Ostream_iterator 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 5 is partitioned in the segment, separately sorted, so that the elements behind the sort 5 are greater than 5 (the rear interval is not sorted), // then output int main () { INT A [] = {7, 2, 6, 4, 5, 8, 9, 3, 1}; Const int n = sizeof (a) / sizeof (int); Vector 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.push_back (0); L1.push_front (1); L1.INSERT ( L1.Begin, 3); L1.SORT (); Copy (l1.begin (), l1.end (), ostream_iterator } Output: 0 1 3 3, DEQUE int main () { DEQUE Q.push_back (3); Q.push_front (1); Q.insert (q.begin () 1, 2); Copy (q.begin (), q.end (), ostream_iterator Output: 1 2 3 4, MAP use int main () { Map 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 Copy (a.begin (), a.end (), ostream_iterator } Output: 1 1 3 4 5 New thinking Combining design modes, generic programming, and object-oriented programming (Object-Oriented Programming) form new thinking. Among them, the design model is a refined outstanding design method, and it is a reasonable and reusable solution for many situations; generic programming is a model of paradigm, focusing on type abstraction , Form a fine set in terms of functional requirements, and utilize these requirements to implement algorithms, the same algorithm can be used in a wide range of types, so-called generics, it is possible to operate in a variety of data types; The polymorphism and template (Templates) such as object program are combined to obtain a high level of generic components. The generic components advance the design module in advance, allowing users to specify types and behaviors to form reasonable design, mainly feature flexible, universal, and easy to use. Policies and Policy classes are an important class design technology that is used to define a class or class template interface that consists of the following or all of the following: internal type definitions, member functions, and member variables. The POLICY-based class consists of many small classes (called policies), each such small classes are only responsible for some aspects of behavior or structures. The Policies mechanism consists of templates and multiple inherits, which can be mixed with each other, thereby forming a diversity of design, but can customize behavior through the PLICY class, but also can be customized. The following is a simple example of the use of generalized thinking and object-oriented thinking in some design modes. Singletons Design Mode Ultrafining Singleton mode is a guaranteed an object (Class) only one entity and provides a global access point. Singleton is an improved global variable that is only available in the program, which focuses on generating and managing a separate object, and does not allow another such object. Let's take a look at the basic technique of general C implementation, the following is the source code: // Singleton.h file Class Singleton { PUBLIC: Static Singleton & Instance () { IF (! pinstance _) { if (destroyed _) {// Is the reference to fail? ONDEADREFERENCE (); Else { Create (); // Create an instance when the first time } } Return * Pinstance_; } Private: Singleton (); // Prohibits default configuration Singleton (Const Singleton &); // Prohibits Copy Construction Singleton & Operator = (const singleton); // Prohibition of assignment operation Static void create () // Send an instance reference to create { STATIC Singleton theinstance; Pinstance_ = & theinstance; } Static void ONDEADREFERENCE () { Throw std :: runtime_ERROR ("instance is unfair to destroy"); } Virtual ~ Singleton () { PINSTANCE- = 0; DESTROYED_ = True; } Static Singleton * Pinstance_; Static bool destroyed_; } // Singleton.cpp initialization in static member variables Singleton * Singleton :: Pinstance_ = 0; Bool Singleton :: destroyed_ = false; As shown above, only one public member instance () in the Singleton mode implementation is used to create a single instance when used for the first time. When the second use, the static variable will have been set, and the instance will not be created again. The default constructor, copy constructor, and assignment operator are also placed in Private, and the location is not allowed to use them. In addition, in order to avoid instantiation after instance unexpected destruction, the static Boolean variable destroy_ is added to determine whether it is wrong to achieve stability. It can be seen from the above general implementation that the Singleton mode implementation is mainly in creating aspects and LifeTime, which can create Singleton through various methods. Creation inevitably creates and destroys objects, inevitably open these two corresponding functions, will be created as an independent policy to separate, so you can create polymorphism objects, so the generalization Singleton does not have Creator objects, it Placed in the CreationPolicy Here is a simple generalization of Singleton mode (not considering thread factors) Template < Class T, Template Template > Classs Singletonholder { PUBLIC: Static T & Instance () { IF (! pinstance_) { IF (Destroyed_) { LifetimePolicy DESTROYED_ = FALSE; } Pinstance_ = CREATIONPOLICY LifetimePolicy } Return * Pinstance_; } Private: static void destroySinleton () { Assert (! destroyed_); CreationPlicy PINSTANCE_ = 0; DESTROYED_ = True; } SingletonHolder (); SingletonHolder (Const SingletonHolder &); SingletonHolder & Operator = (const singletonholder); Static T * pinstance_; Static bool destroyed_; } Instance () is the only PUBLIC function open by SingletonHold, which creates a housing in CreationPolicy, LifetimePolicy. Among them, the template parameter type T, receive the class name, and both of the class of Singleton needs. The class template within the template parameter default parameter createusingNew refers to the object by the New operator and the default constructor, and the defaultlifetime is used to manage the life period through the C rules. There are two member functions in LifetimePolicy The following is the use of the above generalized Singleton mode: 1, apply one Class a {}; Typedef Singletonhold 2, apply two Class a {}; Class Derived: Public a {}; Template { Static t * create () { Return new deerid; } Static Void Destroy (T * Pinstance) { Delete Pinstance; } } Typedef Singletonhold As can be seen from the example, SingletonHold is implemented based on a PLICY design, which decomposes the Singleton object into several policies, CreationPolicy and LifetimePolicy in the template parameter class, equivalent to two policies package. Using them can assist fabrications to customize the Singleton object, but also reserved the space for adjustment and extension. From this, generic components are a pluggable design template that combines templates and patterns that create new methods for creating expanded design in C , providing a simple transition from design to code, Help us write clear, flexible, highly reused code. references
