当前位置:网站首页>Introduction to STL

Introduction to STL

2021-01-23 17:40:49 Southeast Asian monsoon

One 、 Basic concepts

STL(Standard Template Library, Standard template library ) It's a collection of software developed by HP Labs . Now it mainly appears in C++ in , But before being introduced C++ The technology has been around for a long time .

STL In a broad sense, it can be divided into three categories :algorithm( Algorithm )、container( Containers ) and iterator( iterator ), Containers and algorithms can be seamlessly connected through iterators . Almost all the code takes In the way of template class and template function , This provides better code reuse opportunities than traditional libraries of functions and classes .

stay C++ In the standard ,STL It's all over the world C++ In the header file , That is, it is not provided in the form of binary code , But in the form of source code .STL Organized as 13 A headline Pieces of :<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> and <utility>.

STL In detail, the six components :

  1. Containers : Various data structures , Such as vector、list、deque、set、map etc. , For storing data , From the perspective of implementation ,STL A container is a kind of class template.
  2. Algorithm : Various commonly used algorithms , Such as sort、find、copy、for_each. From an implementation point of view ,STL Algorithm is a kind of function tempalte.
  3. iterator : Acts as the glue between the container and the algorithm , There are five types , From the perspective of implementation , An iterator is a kind of operator* , operator-> , operator++,operator– Overloaded with pointer related operations class template. all STL Each container comes with its own iterator , Only the designer of a container knows how to traverse its own elements . Native pointers (native pointer) It's also an iterator .
  4. functor : It behaves like a function , It can be used as a strategy for algorithms . From the perspective of implementation , Functors are overloaded operator() Of class perhaps class template
  5. Adapter : Something used to decorate the interface of a container or a functor or iterator .
  6. Space configurator : Responsible for space configuration and management . From the perspective of implementation , Configurator is an implementation of dynamic spatial configuration 、 Space management 、 Space releases class tempalte.

STL The interaction of the six components , The container obtains the data storage space through the space configurator , The algorithm stores the contents of the container through iterators , The affine function can help the algorithm to complete the change of different strategies , The adapter can modify the functor

Two 、STL advantage

1)STL yes C++ Part of , So you don't have to install anything extra , It's built into your compiler .

2)STL One of the most important features of is the separation of data structure and algorithm . Although it's a simple concept , But this separation does make STL Become very versatile .

for example , stay STL Of vector In the container , You can put in elements 、 Basic data type variables 、 Address of element ;

STL Of sort() Functions can be used to manipulate vector,list Equal container .

3) Programmers don't have to think STL Specific implementation process , As long as you can use it skillfully STL Just OK 了 . So they can focus on other aspects of program development .

4) STL Highly reusable , High performance , High portability , Advantages of cross platform .

  • High reusability :STL Almost all the code in is implemented by template class and template function , This provides better code reuse opportunities than traditional libraries of functions and classes . Knowledge of templates , I've already introduced .
  • High performance : Such as map It can efficiently find out the specified records from 100000 records , because map It's a variant of the red black tree .( Red black tree is a kind of horizontal binary tree )
  • High portability : As in the project A On the use of STL Write modules , It can be ported directly to the project B On .
  • Cross platform : If used windows Of Visual Studio The code can be written in Mac OS Of XCode Compile directly on .

5) Programmers don't have to think STL Specific implementation process , As long as you can use it skillfully STL Just OK 了 . So they can focus on other aspects of program development .

6) come to know STL These benefits of , We know STL It's definitely the most worthwhile C++ Part of the pride of programmers . every last C++ Programmers should study hard STL. Only be able to use it skillfully STL The programmer , That's what's good C++ The programmer .

7) All in all : In recruitment , I often meet C++ Programmer pairs STL I don't really know . Most of them have a general image , However, I feel at a loss about which container and algorithm should be used under what circumstances .STL yes C++ An indispensable basic skill of a programmer , Mastering it is important for ascension C++ Programming helps a lot .

3、 ... and 、 Introduction to the three components

Containers

It can almost be said , Any particular data structure is designed to implement a particular algorithm .STL Container is to implement some of the most widely used data structures .

Commonly used data structures : Array (array) , Linked list (list), tree( Trees ), Stack (stack), queue (queue), aggregate (set), The mapping table (map), According to the arrangement characteristics of the data in the container , These data are divided into sequential containers and associative containers .

  • Sequential containers (Sequence containers)

    Each element has a fixed position -- It depends on the time and place of insertion , It has nothing to do with the element value . Such as :Vector Containers 、Deque Containers 、List Container, etc .

  • Associative containers (Associated containers)

    The position of the elements depends on the specific sorting criteria , It has nothing to do with the insertion order . Relational containers are nonlinear tree structures , More precisely, binary tree structure . There is no strict physical order between the elements , That is to say, elements in the container do not keep the logical order of elements when they are placed in the container . Another notable feature of relational containers is : Select a value from the values as the keyword key, This keyword acts as an index to the value , Easy to find .Set/multiset Containers Map/multimap Containers

data structure describe Implementation header file
vector (vector) Continuously stored elements <vector>
list (list) A two-way linked list composed of nodes , Each node contains an element <list>
Double queue (deque) An array of continuously stored pointers to different elements <deque>
aggregate (set) A red black tree made up of nodes , Each node contains an element , The nodes are arranged by some kind of predicate acting on the pair of elements , No two different elements can have the same order <set>
Multiple sets (multiset) Two sets of elements of equal order are allowed <set>
Stack (stack) The arrangement of last in first out values <stack>
queue (queue) First in, first out arrangement <queue>
Priority queue (priority_queue) The order of elements is a queue determined by some predicate acting on the stored value pair <queue>
mapping (map) from { key , value } For the set of components , In some sort of predicate arrangement acting on key pairs <map>
Multiple mapping (multimap) A mapping that allows key pairs to have equal order <map>

iterator

Iterator is the most basic part in function , But it's harder to understand than both . There is a basic principle in software design , All problems can be simplified by introducing an indirect layer , This simplification can be found in STL This is done with iterators . In a nutshell , Iterator in STL Used to associate algorithms with containers , It acts as a glue . almost STL All the algorithms provided are universal Working through an iterator accessing a sequence of elements , Each container defines its own unique iterator , To access the elements in the container .

The iterator part is mainly composed of header files <utility>,<iterator> and <memory> Group become .<utility> It's a very small header file , It includes throughout use in STL Declaration of several templates in ,<iterator> Iterators are provided in Many of the methods used , And for <memory> It's very difficult to describe , It allocates storage space for the elements in the container in an unusual way , At the same time, it also generates Temporary objects provide a mechanism for ,<memory> The main part of is the template class allocator, It is responsible for generating default allocators in all containers .

Types of iterators :

iterator function describe
Input iterator Provides read-only access to data read-only , Support ++、==、!=
Output iterator Provides write only access to data Just write , Support ++
Forward iterator Provides read and write operations , And can push iterators forward Reading and writing , Support ++、==、!=
Bidirectional iterator Provides read and write operations , And can operate forward and backward Reading and writing , Support ++、–,
Random access iterator Provides read and write operations , And can access any data of the container in a jump way , It's the most powerful iterator Reading and writing , Support ++、–、[n]、-n、<、<=、>、>=

Algorithm

The choice of data type in function library plays an important role in its reusability . for instance , A function for finding the root of a square , Reusability in the case of floating-point numbers as their parameter types is definitely better than Using integer as its parameter is more classy . and C++ The mechanism of templates allows you to postpone the selection of certain types , Until you really want to use templates or specialize them ,STL I took advantage of this to say A lot of useful algorithms are provided . It completes these algorithms in an effective framework —— All types can be divided into a few categories , Then you can replace the same type in the template parameters Other types in the class .

STL Provides about 100 A template function to implement the algorithm , Such as the algorithm for_each The specified function is called for each element in the specified sequence ,stable_sort Sort the sequence according to the rules you specify . thus , As long as I'm familiar STL after , A lot of code can be greatly simplified , Just call one or two algorithm templates , You can do what you need And greatly improve efficiency .

The algorithm is mainly composed of header files <algorithm>,<numeric> and <functional> Group become .<algorithm> It's all STL The largest of the header files ( Although it's easy to understand ), It's made up of a bunch of template functions , It can be said that each function is to a large extent They're all independent , Among them, the commonly used functional scope involves comparison 、 In exchange for 、 lookup 、 Traversal operation 、 Copy 、 modify 、 remove 、 reverse 、 Sort 、 Merger and so on .<numeric> The volume is very Small , There are only a few template functions that perform simple mathematical operations on the sequence , It includes some operations of addition and multiplication on sequences .<functional> Some template classes are defined in , To declare function objects .

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//STL  In the container   Algorithm   iterator 
void test01(){
	vector<int> v; //STL  One of the standard containers in  : The dynamic array 
	v.push_back(1); //vector  The method of inserting data provided by the container 
	v.push_back(5);
	v.push_back(3);
	v.push_back(7);
	// iterator 
	vector<int>::iterator pStart = v.begin(); //vector  The container provides  begin() Method   Returns the iterator pointing to the first element 
	vector<int>::iterator pEnd = v.end(); //vector  The container provides  end() Method   Returns the iterator pointing to the next position of the last element 
	// Traversal by iterator 
	while (pStart != pEnd){
		cout << *pStart << " ";
		pStart++;
	}
	cout << endl;
	// Algorithm  count  Algorithm   Used to count the number of elements 
	int n = count(pStart, pEnd, 5);
	cout << "n:" << n << endl;
}
//STL  Containers can not only store basic data types , You can also store class objects 
class Teacher
{
public:
	Teacher(int age) :age(age){};
	~Teacher(){};
public:
	int age;
};
void test02(){
	vector<Teacher> v; // Storage  Teacher  Container for type data 
	Teacher t1(10), t2(20), t3(30);
	v.push_back(t1);
	v.push_back(t2);
	v.push_back(t3);
	vector<Teacher>::iterator pStart = v.begin();
	vector<Teacher>::iterator pEnd = v.end();
	// Traversal by iterator 
	while (pStart != pEnd){
		cout << pStart->age << " ";
		pStart++;
	}
	cout << endl;
}
// Storage  Teacher  Type a pointer 
void test03(){
	vector<Teacher*> v; // Storage  Teacher  Type a pointer 
	Teacher* t1 = new Teacher(10);
	Teacher* t2 = new Teacher(20);
	Teacher* t3 = new Teacher(30);
	v.push_back(t1);
	v.push_back(t2);
	v.push_back(t3);
	// Get the container iterator 
	vector<Teacher*>::iterator pStart = v.begin();
	vector<Teacher*>::iterator pEnd = v.end();
	// Traversal by iterator 
	while (pStart != pEnd){
		cout << (*pStart)->age << " ";
		pStart++;
	}
	cout << endl;
}
// Containers nested containers   difficulty 
void test04()
{
	vector< vector<int> > v;
	vector<int>v1;
	vector<int>v2;
	vector<int>v3;

	for (int i = 0; i < 5;i++)
	{
		v1.push_back(i);
		v2.push_back(i * 10);
		v3.push_back(i * 100);
	}
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);

	for (vector< vector<int> >::iterator it = v.begin(); it != v.end();it++)
	{
		for (vector<int>::iterator subIt = (*it).begin(); subIt != (*it).end(); subIt ++)
		{
			cout << *subIt << " ";
		}
		cout << endl;
	}
} 
int main(){
	//test01();
	//test02();
	//test03();
	test04();
	system("pause");
	return 0;
}

Part of it comes from :

[【C/C++】STL Detailed explanation ]:( https://blog.csdn.net/qq_42322103/article/details/99685797)

版权声明
本文为[Southeast Asian monsoon]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210123173950081q.html