Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "what is C++ STL programming". In the operation of practical cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1 first acquaintance with STL: answer some questions

1.1 A question of greatest concern: what is STL

"what is STL?" If you still know very little about STL then I think you would like to know the answer to this question and frankly it is by no means easy to expect to explain it clearly in a few words. Therefore, if you still feel that you do not understand after reading this section, there is no need to worry. After reading the follow-up content, I believe your understanding of STL will be more clear, accurate and complete. But does that sound like an exoneration for your poor expression skills? :)

I don't know if you've ever had such an experience. When you are ready to complete the homework assigned by your data structure teacher, or when you add a new feature to a software project you are responsible for, you find that you need to use a linked list (List) or a mapping table (Map), but you do not have the ready-made code. So before you start to formally consider the functionality of the program, it is inevitable to implement List or Map manually.

So. At last you finished the task successfully. Maybe at this time, as a highly educated programmer, you won't give up (or a top student who likes to be lazy:), because you will think, what if you encounter such a situation in the future? There is no need to do the same thing again.

It may be an exaggeration to say that this happens every day. But it doesn't seem like an exaggeration to say that the entire software world has been fighting for one goal for decades-reusability. From the earliest process-oriented function libraries, to object-oriented programming ideas, to various component technologies (such as COM, EJB), to design patterns (design pattern), and so on. While STL is doing something similar, there is a new programming idea behind it-generalization design (generic programming).

Continuing with the example mentioned above, if you keep List or map intact, you are secretly complacent. Wait a minute, what if the next List contains integers instead of floating-point numbers? What if the Map you implement is always unsatisfactory in terms of efficiency and sometimes gives you some bug? How do you deal with these problems? Using STL is a good choice, and indeed, STL can beautifully solve the problems mentioned above, although you can look for other ways.

After talking for a long time, what on earth is STL?

STL (Standard Template Library), the standard template library, is an industrial strength and efficient C++ library. It is contained in the C++ standard library (C++ Standard Library) and is a revolutionary part of the ANSI/ISO C++ standard. The library contains many basic data structures and algorithms commonly used in the field of computer science. It provides an extensible application framework for C++ programmers, which highly reflects the reusability of the software. This phenomenon is somewhat similar to MFC (Microsoft Foundation Class Library) in Microsoft Visual C++ or VCL (Visual Component Library) in Borland C++ Builder, which must be familiar to all of you.

From the logical level, STL embodies the idea of generic programming (generic programming), and introduces many new nouns, such as requirements, concept, model, container, algorithmn, iterator and so on. Like polymorphism in OOP (object-oriented programming), generics are also a technology of software reuse.

From the implementation level, the whole STL is implemented in a way of type parameterization (type parameterized), which is based on a language feature that did not appear in previous C++ standards-templates (template). If you look at any version of the STL source code, you will find that templates as the cornerstone of the entire STL is a real thing. In addition, there are many new features of C++ that facilitate the implementation of STL.

I don't know how you feel about the sudden emergence of so many terms here. I hope it won't upset you. If you don't know much about most of them, please rest assured that these nouns will be discussed one by one in the following content. As mentioned at the beginning.

Interestingly, there is another explanation for STL-STepanov & Lee, the former refers to the founder of Alexander Stepanov,STL, while the latter is Meng Lee, who also contributed to the implementation of STL. They worked together to complete the finished STL. This term comes from an exclusive interview with Alexander Stepanov by Dr.Dobb's Journal special correspondent and famous technical book writer Al Stevens in March 1995.

1.2 tracing back to the Origin: the History of STL

When making new friends, most people can't help but want to know about each other's past. This section will take you through a brief review of STL's past.

Alexander Stepanov, known as the father of STL, was born in Moscow, Soviet Union. As early as the second half of the 1970s, he began to consider the possibility of abstracting the algorithm from many specific applications on the premise of ensuring efficiency. This is the embryonic form of generalization thought later. To test his ideas, he co-developed a language called Tecton with Deepak Kapur, a professor at the State University of New York, and David Musser, a professor at the Renzel Institute of Technology. Although this attempt did not achieve practical results in the end, it gave Stepanov a great inspiration.

In the following years, he and David Musser and others built a number of large libraries in Schema (a variant of Lisp) and Ada. In the meantime, Alexander Stepanov began to realize that there were some problems in the idea of object-oriented programming at that time, such as the shortcomings of the concept of abstract data types. Stepanov hopes to gradually form a conceptual framework of software design through the classification of various components in the software field.

Around 1987, Alexander Stepanov, who works at Bell Labs, began to study generic software libraries in C++. Unfortunately, the syntax of template was not introduced into the C++ language at that time, and now we can clearly see how important the template concept is to the STL implementation. Because of the time, there is no choice to adopt the inheritance mechanism. Nevertheless, Stepanov has developed a huge library of algorithms.

At the same time, in working with gurus such as Andrew Koenig (former chairman of the C++ Standardization Committee of ISO) and Bjarne Stroustrup (founder of the C++ language), Stepanov began to notice the potential advantage of the Cmax Cure + language in implementing its generics idea. For example, the pointer in Chammer Cure + is flexible and efficient, which makes the later STL maintain high efficiency while realizing generalization. In addition, the concept of iterator, which occupies a very important position in STL, is derived from the abstraction of the original pointer (native pointer) in Cstroke.

Alexander Stepanov started working at Hewlett-Packard's Palo Alto lab in 1988 and spent the next four years working on disk drives. It was not until 1992 when he participated in and presided over a research project on algorithms established by Bill Worley, the director of the laboratory, that he returned to the research of generalization algorithms.

Since the establishment of the project, the number of participants has gradually decreased from the initial eight, leaving only two people-Stepanove himself and Meng Lee. After a long period of hard work, belief and sweat are finally exchanged for a huge runtime with a large number of data structures and algorithmic components. This is the prototype of the current STL (and an implementation version of STL-HP STL).

In 1993, I was very excited to see Stepanove's research results at Andrew Koenig at Bell Labs. With his encouragement and help, Stepanove gave a speech (entitled "The Science of C++ Programming") to the ANSI/ISO C++ Standards Committee in San Jose in September of that year, telling members about his ideas. Then, at a meeting in San Diego the following March, a proposal was submitted to the committee to make STL part of the C++ standard library. Although the proposal was so large that it reduced the likelihood of adoption, the vote postponed the decision on the proposal by an overwhelming majority because of the new ideas it contained.

Then, with the help of others, including Bjarne Stroustrup, Stepanove made improvements to STL. At the same time, an abstract module encapsulating memory pattern information, that is, allocator in STL, is added, which makes most of the implementation of STL independent of the specific memory mode and thus independent of the specific platform. At the Waterloo meeting in the summer of the same year, with 80 per cent in favor and 20 per cent against, the committee finally adopted a proposal to formally include STL in the standardization process of C++, and then STL was put into the working paper of the meeting. Since then, STL has finally become an important member of the C++ family.

Since then, with the continuous improvement of C++ standard, STL is also constantly making corresponding evolution. Until 1998, the ANSI/ISO C++ standard was formally finalized, and STL has always been an indispensable part of the C++ standard.

1.3 inextricably linked

After you learn about the past of STL, some nouns begin to come to your mind, such as STL, C++, C++ standard function library, generic programming, object-oriented programming. What do these concepts mean? What is the relationship between them? If you want to know some details, here may be the answer you want.

1.3.1 STL and C++

It is no exaggeration to say that there would be no STL without C++. Generally speaking, STL, as a generic library of data structures and algorithms, does not involve a specific language (of course, in C++, it is called STL). In other words, if conditions permit, it can be achieved in other languages. The condition mentioned here mainly refers to the grammatical mechanism such as "template". If you haven't skipped the previous section, you can see that Alexander Stepanov used a variety of programming languages long before choosing C++ as its implementation tool.

But why was C++ lucky to take on this historic task in the end? The reason lies not only in the aforementioned condition, but also in the superior characteristics of C++ in some aspects, such as efficient and flexible pointers. But if you look at C++ as an OOP (Object-Oriented Programming) language (in fact, we generally think so, don't we? Its powerful inheritance mechanism does not help the implementation of STL very much There are not too many complex inheritance relationships in the STL source code.

The idea of inheritance, or even object-oriented thinking, is not enough to implement generic libraries like STL. Only after C++ introduced the "template" did it directly lead to the birth of STL. This is an important reason why generics cannot be implemented in other object-oriented languages that are purer than C++. Of course, things are always changing, like Java in this respect, is a good example, jdk1.4 has added generics features.

In addition, STL has also played a role in promoting the development of C++, especially the template mechanism. For example: template function partial specialization of template functions, which is used to provide a series of specialized versions of general template functions in specific applications. This feature was proposed by Bjarne and Stepanov after STL was adopted by the ANSI/ISO C++ Standards Committee, and the proposal was finally adopted by Bjarne. This makes some algorithms in STL can choose a non-general way when dealing with special cases, thus ensuring the efficiency of execution.

1.3.2 STL and C++ standard function library

STL is a subset of C++ 's standard function library, a huge subset that accounts for about 80% of the library. Templates, which play a key role in the implementation of STL, fill almost the entire C++ standard function library. Here, it is necessary to take a look at what is contained in the C++ standard function library, and which belong to the standard template library (STL).

The C++ standard function library provides an extensible basic framework for C++ programmers. We can get great convenience from it, and we can also extend it by inheriting existing classes and compiling containers, algorithms and iterators that conform to the interface specification. It roughly consists of the following components:

The C standard function library basically maintains a good compatibility with the original C language library, although there are some slight changes. People can't help but miss the good old days, and if you've ever been a C programmer, you must know a lot about this. It may surprise you that there are two sets of C libraries in the C++ standard library, one with the .h extension (for example) and the other without (for example). They really don't have much difference.

The language support (language support) section contains definitions of standard types and other features that are used elsewhere in the standard library or in specific applications.

The diagnostics section provides functions for program diagnosis and error reporting, including exception handling (exception handling), assertion (assertions), and error code (error number codes).

General tools (general utilities) section, which provides support for other parts of the C++ standard library, of course, you can also call the corresponding functions in your own programs. For example: dynamic memory management tools, date / time processing tools. Remember, the content here has also been generalized (that is, a template mechanism is used).

The string part, which is used to represent and process text. It provides a wealth of features. In fact, the text is a string object, which can be thought of as a sequence of characters, the character type may be char, or wchar_t, and so on. String can be converted to a char* type so that it can coexist peacefully with the previously written C _ innate code. Because there was nothing but char*, at that time.

In the internationalization part, as one of the OOP features, the encapsulation mechanism plays a role in eliminating cultural and regional differences. Using locale and facet can provide a lot of internationalization support for the program, including support for various character sets, date and time representation, numerical and currency processing, and so on. After all, people's habit of saying dates is different in China and the United States.

The containers part, an important part of STL, covers many data structures, such as the linked list mentioned earlier, as well as: vector (similar to an array whose size can be dynamically increased), queue (queue), stack (stack). String can also be thought of as a container, and the methods that apply to containers also apply to string. Now you can easily finish your homework for the data structure course.

The algorithms part, an important part of STL, contains about 70 general algorithms for manipulating various containers as well as built-in arrays. For example, find is used to find elements in the container that are equal to a specific value, for_each is used to apply a function to various elements in the container, and sort is used to sort the elements in the container. All of these operations are done on the premise of ensuring efficiency, so if the program becomes efficient after you use these algorithms, don't doubt the algorithms themselves and check the rest of the program carefully.

The iterators part is an important part of STL. Without the matching of iterators, containers and algorithms cannot be combined in such a way. In fact, each container has its own iterator, and only the container knows how to access its own elements. It is a bit like a pointer, and the algorithm uses iterators to locate and manipulate elements in the container.

The numerics part contains some mathematical operation functions and provides support for complex operation.

The input / output (input/output) part is the iostream part of the templated original standard library, which provides the basic support for the input and output of C++ programs. Functional compatibility with the original iostream is maintained, exception handling mechanism is added, and internationalization (internationalization) is supported.

Generally speaking, in the C++ standard function library, STL mainly includes containers, algorithms and iterators. String can also be counted as part of STL.

Figure 1:STL and C++ standard function library

1.3.3 STL and GP,GP and OOP

As mentioned earlier, behind STL lies the idea of generalized programming (GP), in which most basic algorithms are abstracted, generalized, independent of their corresponding data structures, and used to deal with different situations in the same or similar way. This idea is different from the object-oriented programming idea (OOP), because the OOP pays more attention to the abstraction of the data, that is, the so-called abstract data type (Abstract Data Type), and the algorithm is usually attached to the data type.

Almost everything can be regarded as a class or an object (that is, an instance of a class). Usually, the algorithms we see are included in the class (class) as a member function (member function), and classes and classes constitute an intricate inheritance system.

Although in programming languages like C++, you can also use global functions to represent algorithms, in pure object-oriented languages like Java, global functions have been "forbidden".

Therefore, it is quite difficult to simulate the idea of GP with Java. If you are still impressed by the aforementioned history of STL, you should remember that Alexander Stepanove also tried to implement the idea of GP in an OOP-based language, but the results were not good, including C++ before the introduction of templates. Standing on the shoulders of giants, we can come to the conclusion that the ideas embodied in OOP are indeed different from those of GP. C++ is not a pure object-oriented programming language, its wonderful place is that it not only satisfies OOP, but also achieves GP.

For the latter, the template has made great contributions. In addition, it should be pointed out that although there are many differences between GP and OOP, the difference is not to the extent that fire and water are incompatible. And, in practical application, the combination of the two can often make the solution of the problem more effective. STL, as an example of GP thought, is a good example. Without inheritance, you don't know what STL would be like. No one seems to have done such an experiment.

1.4 different implementation versions of STL

I believe that your perceptual understanding of STL should be improved, and it is time to do some practical work, so let's first take a look at the different implementation versions of STL. STL in ANSI/ISO C++ file is a standard described only on paper. For many C++ compilers, it is necessary to have their own actual STL, which more or less implements the content described in the standard, so that it can be used by us. The reason why there are different implementation versions, there are many reasons, there are historical reasons, but also the reasons of their respective compiler manufacturers. Here are several common versions of STL implementations.

1.4.1 HP STL

HP STL is the root of all other STL implementations. It was done with Meng Lee when Alexander Stepanov, the father of STL, worked with Meng Lee at HP's Palo Alto lab, and was an implementation of * STL (see Section 1.2). This STL is open source, so it allows anyone to use, copy, modify, distribute and sell the software and related documents free of charge, provided that HP STL version information and license information are included in all relevant files. This version of STL is rarely used directly these days.

1.4.2 P.J. Plauger STL

P. J. Plauger STL is a personal work, implemented by P. J. Plauger himself, and is an inherited version of HP STL, so all its header files contain the relevant notice of HP STL, as well as the copyright notice of P. J. Plauger himself. P. J. Plauger was the early implementer of the stdio library in Standard C, and is now the editor-in-chief of Candlespace + User's Journal, and maintains a good relationship with Microsoft. P. J. Plauger STL is used in Microsoft's Visual C++. In the similar version under the Windows platform, its performance is good, but the efficiency of the queue component (queue, a container) is not ideal, and because Visual C++ does not support the C++ language standard very well (at least until VC6.0), it affects the performance of P. J. Plauger STL to some extent.

In addition, the source code of this version is less readable, and you can find all the source files in the VC subdirectory (for example: C:\ Program Files\ Microsoft Visual Studio\ VC98\ Include). Because it is not open source, this source code cannot be modified and sold, and P.J. Plauger STL is currently provided by Dinkumware. It is said that the Visual C++.NET (VC7.0) in Visual Studio.NET has improved support for the C++ standard, and there are more map containers, multimap containers and set containers based on hash table.

1.4.3 Rouge Wave STL

Rouge Wave STL is implemented by Rouge Wave and is an inherited version of HP STL. In addition to the relevant notice of HP STL, there is also a copyright notice of Rouge Wave. At the same time, it is not open source, so it cannot be modified and sold. This version is used by Borland C++ Builder, and you can find all the header files in the included subdirectory of C++ Builder (for example: C:\ Program Files\ Borland\ Cbuilder5\ Include). Although the performance of Rouge Wave STL is not very good, its performance has been improved to some extent because C++ Builder supports the C++ language standard fairly well.

In addition, its source code is readable. Unfortunately, this version has not been updated for some time and does not fully meet the standards. Therefore, in Borland C++ Builder 6.0, its position has been replaced by another implementation version of STL, STLport (see later). However, C++ Builder 6.0 retains Rouge Wave STL for compatibility with previous versions, but you need to find it in a different directory if you want to view its source code (for example, C:\ Program Files\ Borland\ Cbuilder6\ Include\ oldstl).

1.4.4 STLport

STLport originally originated from a Russian Boris Fomitchev development project, mainly used to port the basic code of SGI STL to other mainstream compilers such as C++Builder or Visual C++. Because SGI STL is open source, STLport has the right to do so. Currently, the * version of STLport is 4.5. STLport has been accepted as an industry standard by the CumberCraft + Technical Committee and is supported on many platforms.

According to the efficiency of testing STLport is faster than STL in VC. It is more up to standard and easier to migrate than Rouge Wave STL. Borland C++ Builder has added support for STLport in its version 6.0, which uses version 4.5 of STLport. C++ Builder 6.0 also provides instructions for using STLport. You can find all the header files in the Include\ Stlport subdirectory of C++ Builder (for example: C:\ Program Files\ Borland\ Cbuilder6\ Include\ Stlport).

1.4.5 SGI STL

SGI STL is implemented by Silicon Graphics Computer System, Inc, whose designers and writers include Alexander Stepanov and Matt Austern. It is also an inherited version of HP STL. It is open source, so you can modify and sell it. SGI STL is adopted by GCC (the C++ compiler under linux), and you can find all the header files in the included subdirectory of GCC (for example: C:\ cygnus\ cygwin-b20\ include\ include +\ header). Because GCC supports the C++ language standard very well, the performance of SGI STL on the linux platform is quite excellent. In addition, its source code is also very readable.

The pedigree of the 2:STL family

This is the end of the content of "what is C++ STL programming"? thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.