STL learning summary (original: Sang Yishuo)

STLs that provide types of safety, efficient and easy-to-use features are undoubtedly the most worth C programmer pride. Every C programmer should learn STL :).

STL (Standard Template Library Standard Template) is an important part of the C standard library. It is first developed by Stepanov and Lee et al. It is developed with C almost simultaneously; a start STL selection ADA is used as an implementation language. But ADA is a bit uncomfortable, and finally they have chosen C , one reason, C already has a template. Later, STL was added to the C library. In 1996, Hewlett-Packard also publicly disclosed STL, which has made great contributions to STL promotion.

STL generally includes Container, Algorithm (Algorithm), and Iterator (iterator), containers, and algorithms that can be seamless through iterators.

STL reflects the idea of ​​model programming, which has high reusability, high performance, high graft. The programmer does not need to think about the specific implementation process, as long as the skilled application is OK. (Interested research is implemented, you can see "STL source code analysis" edited by Mr. Houjie, which can put energy in other aspects of program development.

I admire those computers and mathematics elites for STL. Because they have made a very hard thing - abstract concept. The STL is by using the container abstraction to a unified interface, the algorithm uses this interface, and manipulate the container through iterators. Because the interface is constant, the implemented container can be changed at will. In this way, it is convenient for programming, debugging and extension. Maybe one day, we can also think that DIY is as simple as the software, just get the corresponding implementation module, you can create a software through simple assembly and commissioning. What kind of exciting thing is ^ _ ^. However, when it is, there may be many programmers to be unemployed. Oh, after all, there is no need to write a class library.

Although STL is not object-oriented, I think everyone will be excited and convincing for its creativity and high performance.

First, the container is the most important component of STL - container, divided into vector, double-end queue, table (list), queue, stack, collection (SET), multiple collections (MULTISET), Mapp (MAP), MultiMap.

The header file vector of the container feature can use constant time to access and modify any element. When inserted and deleted at the end of the sequence, there is a constant time complexity, and the insertion and deletion of any item and the distance from the end. Compared to the proportion of the added and deleted cost of the number, it is a highly dual-end queue Deque basically the same as the vector, the only difference is that it also has a constant time complex in the sequence head insertion and deletion. The Table List is proportional to the distance between any element and the distance to both ends, but the cost of inserting and deleting an item in a certain location is a constant time. Queue Insert can only be performed on the tail, delete, retrieve, and modifications only allow for the head. According to the principle of advanced first. Stack Stack Stack is a limited sequence of items, and the items that are deleted, retrieved, and modified in the sequence can only be an item that is recently inserted. That is, according to the principle of the first out, the set of red black trees consisting of nodes, each node contains an element, and the node is arranged in some kind of predicate, no two different elements can be With the same order, it has a fast lookup. However, it is basically the same as the multi-set MultiSet and collection of the hypothesis of the efficiency of the sacrificial insertion vehicle, but can support repeated elements with fast lookup capability mapping MAP consisting of {keys, value}. Align in a predicate that acts on the bob. Have fast lookup capability

Second, the algorithm part is mainly composed of header file , and . is the largest in all STL header files, which is composed of a large stack of mode functions, which can be considered to be independent, in which the functional ranges commonly used are compared, exchange , Find, traverse operation, copy, modification, removal, reverse, sort, merge, etc. The size is small, including only a few template functions that make simple mathematics operations above the sequence, including some of the operations on the sequence. defines some template classes to declare function objects.

STL's algorithm is also very good. Most of them are classics, basically used C templates to implement, so many similar functions don't write it yourself, just use the function template to OK.

When we use algorithms, we have to target different containers, such as: For collection, do not use common functions for Find (), it is very poor performance when used, it is best to bring your own Find ( The function, it is optimized for the collection, and the performance is very high.

Third, iterator is in , we can completely understand how it is implemented, it is not a problem with the pointer, which is an iterator. It is also an iterator), but it will never do this completely.

Iterator Function (Abilities Of Iterator Gategories) Enter the Iterator Input Iterator to Read the Reads Forward IteaM Output Iterator Output Iterator Write Forward Ostream, Inserter Forward iterator Forward Iterator Read and write Read and Writes Forward two-way iterator Bidirectional Iterator Reads Read and Writes Forward and Backward List, Set, MultiSet, Map, Mul Timap Random Iterator Random Access Iterator Random Read and Write Read and Write with Random Access Vector, Deque, Array, String This is visible, The pointer and iterators are still very different. The closest to the pointer is to random access iterators. Below is a small example I have written: The function is to insert an array, vector, table, and multiple collections, plug in 1 million random integers for each container;

#include #include #include #include #include #include #include #include using namespace std; template < TypeName T> Void ArrayInsert (t * a, t * s, long size) // Insert data {// for (long i = 0; i <10; i ) // // image array supports less than 1 million , Even if the 100,000 // final will multiply the results in 10, // {for (long k = 0; k Void VectorInsert (Vector * V, T * S, Long Size) // Insert data {for (int i = 0; i <10; i ) {for (long k = 0; K push_back (s [k]);}}} template Void ListInsert (List * L, T * S, long size) // Insert data { For (int i = 0; i <10; i ) {for (long k = 0; k push_back (s [k]);}}} template void multisetinsert MultiSet * S1, T * S, long size) // Insert data {for (int i = 0; i <10; i ) {for (long k = 0; k INSERT (s [k]);}}} int * GenintData (LO Ng size) // Generate random number {INT * DATA = new int [size]; generate (& data [0], & data [size], rand); return data;} int main (void) {constlun size = 100000; INT * S_DATA, ARRAY1 [SIZE]; Double Begin, End; S_Data = GenintData (Size); Vector Vector1; List MultiSet1; Clock (); cout << "?" < (array1, s_data, size); end = (double) clock () / clk_tck;

COUT << "?" << (end-begin) << Endl; getch (); begin = (double) clock () / clk_tck; vectorinsert (& vector1, s_data, size); end = (double) Clock () / clk_tck; cout << "??" << (end-begin) << Endl; getch (); begin = (double) clock () / clk_tck; listinsert (& List1, s_data, size) END = (Double) Clock () / clk_tck; cout << "??" << (end-begin) << Endl; getch (); begin = (double) clock () / clk_tck; multisetinsert & MultiSet1, S_Data, Size; End = (Double) Clock () / CLK_TCK; COUT << "?" << (end-begin) << Endl; getch (); free (s_data); return 0;} The program clearly shows the difference between these containers between insertion speeds, of course, each container is not universal, can't be a good better. For example, multi-episodes in finding advantages are unparalleled in other sequence containers. Also, it is best not to try to exceed STL, because: 1, STL implementation is the best algorithm. It is almost perfect. 2, STL implementation designers are usually experts in the corresponding field. 3. Experts in various fields are committed to providing flexible, powerful and efficient libraries. This is their primary task. For the rest of our people, developing reusable containers and algorithms only counts the second goal. Our primary task is to deliver the applying the subject. In most cases, we don't have time and specialized technology to compare with those experts.

However, Beyond STL is not impossible. But in general, you can only improve performance by sacrificing portability, which is very bad for many situations. For, beyond STL, we have to work very much effort. Moreover, it is best to know something that STL experts don't know, we can have targeted optimization, otherwise our efforts are completely possible.

Facing such an excellent library and it is free. Our C programmers have no reason to reject it, even to develop a library.