1.1 STL(Standard Template Library)

1.1.1 STL overview

STL is a powerful template based container library. The efficiency and reliability of algorithm design can be greatly improved by directly using these ready-made standardized components. It has been modified and perfected by many generations of Daniel programmers. In fact, simply put, it is something created by programmers for convenience and efficiency. For algorithm designers, the principle of "using STL as much as possible without realizing it by themselves".

STL is mainly composed of container, algorithm and iterator. Container is used to store data objects (elements), algorithm is used to operate data objects in container, and the intermediary between algorithm and container is iterator.

1.1. 2 what is an STL container

In short, STL container is a data structure, such as linked list, stack, queue, etc. These data structures already exist in STL. When we are programming, we can use them directly according to the corresponding rules.

Common data structures and corresponding header files of STL container:

1. Vector: (continuous space storage, you can use [] operator) quickly access random elements and quickly insert elements at the end. However, the insertion and deletion of elements in the middle of the sequence are slow. Moreover, if the space allocated at the beginning is insufficient, more space may be re allocated, and the performance cost of copying is high. Header file: < vector >
2. Deque (double ended queue): (small pieces are continuous. Small pieces are connected by linked lists. In fact, there is a pointer to map inside. Because the type is known, you can still use [] , but the speed is not as fast as vector) quickly access random elements, quickly insert elements at the beginning and end, but random insertion and deletion of elements are slower, and space redistribution is faster than vector. After space redistribution, the original elements do not need to be copied. For the sorting operation of deque, deque can be copied to vector first, and then copied back to deque after sorting. Header file < deque >
3. List (linked list): (each element is connected with a linked list) accessing random elements is not as fast as vector, and inserting random elements is faster than vector. Space is allocated to each element, so there is no reallocation due to insufficient space. Header file < list >
4. Set / multimap: the internal elements are unique and stored in a balanced tree structure, so they are sorted when traversing, and the search is faster. The elements in set are ordered and repeated, and all elements in multimap are ordered but not repeated. Header file < set >
5. map: the combination of one-to-one mapping. The key cannot be repeated. Header file < map >
6. Stack: stack, which must be used in combination with other containers. The default internal container in stl is deque. In first out, there is only one exit, and traversal is not allowed. Header file < stack >
7. Queue: it is a restricted deque. The internal container generally uses a list, which is relatively simple. First in first out, traversal is not allowed. Header file < queue >
8. unordered_set,unordered_map: Hash table, Hash table. Fast search, fast insertion, but not random access. In addition, it consumes a lot of space (here it depends on the Hash function). Header file < Map >
9. priority_queue: a priority queue, which is used to achieve the maximum heap (default) and the minimum heap. Finally, the largest element is always top in the queue. Header file < queue >
10. String: string processing container. Header file < string >

In the process of writing code, we name the function we want to write, but the function in STL also has a name. Will it be repeated? Let's talk about the namespace, Just like sort (), we may also define a sort (), but there is an algorithm of sort () in STL, so in order to avoid confusion, the sort () and identifier of STL are encapsulated in std of namespace. The sort () algorithm of STL is compiled as: std::sort(), so as to avoid name conflict. When we use STL, we need to add this sentence to the beginning of the file: using namespace std;

1.1. 3 what is STL algorithm

The algorithm part is mainly composed of header files < algorithm >, < numeric > and < functional >.
< algorithm > is the largest of all STL header files. The commonly used functions include comparison, exchange, search, traversal, copy, modify, reverse, sort, merge, etc.
< numeric > is small in size and only includes a few template functions that perform simple mathematical operations on the sequence, including some operations of addition and multiplication on the sequence.
< functional > defines some template classes to declare function objects.
STL provides a large number of template functions to realize the algorithm. As long as we are familiar with STL, many codes can be greatly simplified. We can complete the required functions by calling one or two algorithm templates, so as to greatly improve the efficiency.  
       #include <algorithm>
       #include <numeric>
       #include <functional>

In short, we now have a file library. When we need the files in this file library, we use the file library to solve the problem. We don't need to know how to do the process, and the result is correct.

1.1. 4 what is an iterator

To access the elements in the sequential container and associated container, you need to use the "iterator". The iterator is a variable, which is equivalent to the intermediary between the container and the algorithm operating the container. The iterator can point to an element in the container, and the iterator can read and write the element it points to. From this point of view, iterators and pointer types.

Iterators are defined in the following four ways:
Forward iterator, defined by:

1. Container class name:: iterator iterator name;

Constant forward iterator, defined by:

1. Container class name:: const_iterator iterator name;

Reverse iterator, defined by:

1. Container class name:: reverse_iterator iterator name;

Constant direction iterator, defined by:

1. Container class name:: const_reverse_iterator iterator name;

Examples of iterator usage:
The element it points to can be read through the iterator, and the * iterator name represents the element pointed to by the iterator. The non constant iterator can also modify the element it points to.

Iterators can perform + + operations. The difference between a direction iterator and a forward iterator is that:

• When you + + operate on a forward iterator, the iterator points to the latter element in the container
• When a reverse iterator performs a + + operation, the iterator points to the previous element in the container

Example 1:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<int> v;//v is a variable length array that holds variables of type int. there are no elements at the beginning 
	for(int n=0;n<5;n++)
	{
		v.push_back(n);//push_ The back member function adds an element at the end of the vector container 
	}
	vector<int>::iterator i;//Define forward iterators 
	for(i=v.begin();i!=v.end();++i)//Traversing containers using iterators 
	{
		cout<<*i<<" ";//*i is the element pointed to by iterator i 
		*i *=2;
	}
	cout<<endl;
	//Reverse iterator output container 
	for(vector<int>::reverse_iterator j=v.rbegin();j!=v.rend();++j)
	{
		cout<<*j<<" ";
	}
	return 0;
 } 

 

Example 2:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<int>myv;//Define vector container 
	myv.push_back(1);//push_back() inserts an element at the end 
	myv.push_back(2);
	myv.push_back(3);
	vector<int>::iterator it;//Define forward iterators 
	for (it=myv.begin();it!=myv.end();++it)// Forward output 
		printf("%d ", *it);
	printf("\n");
	vector<int>::reverse_iterator iit;	//Define reverse iterators 
	for(iit=myv.rbegin();iit!=myv.rend();++iit)//Reverse output 
	{
		cout<<*iit<<" ";
	 } 
	return 0;
 } 

1.2 common STL containers (directly understand the code)

1.2.1 vector

There are several ways to define a vector container:

vector<int> v1;//Defines a vector v1 whose element is int
vector<int> v2(10);//The initial size of the pointing vector v2 is 10 int elements
vector<int> v3(10.1.23);//The initial value of the ten initial elements of v3 is 1.23
vector<int> v4(a,a+5);//Initialize v4 with five elements of array a[0..4]

1.2. Some member functions provided by 2vector

1. Construct and copy constructors

 2. Destructor ~ vector()

The container object is destroyed and all allocated memory is reclaimed

3. Overloaded = symbol

vector<int> E;

E = B; // Use = symbol

B = vector<int>(); // Set B as an empty container

4. vector::begin() returns the iterator of the first element

Function prototype:

  iterator begin (); / / returns a variable iterator

const_iterator begin () const; // Returns an iterator of a constant, immutable

5.vector::end() returns the first position after crossing the boundary, that is, the next position of the last element

  iterator end ();

const_iterator end () const;

6.vector::rbegin() is the first element in reverse order, that is, the last element in positive order

  reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

7. The next position of the last element in reverse order of vector:: rend() is also equivalent to the previous position of the first element in positive order

  reverse_iterator rend();

const_reverse_iterator rend() const;

The same principle as vector::end()

8.vector::size() returns the number of elements in the container

  size_type size() const;

Note the difference from vector::capacity()

9.vector::max_size()

  size_type max_size () const;

Returns the maximum number of elements that can be stored in the container. This is a limit. When the container expands to this maximum value, it can no longer be automatically increased

10. vector::resize()

  void resize ( size_type sz, T c = T() );

Redistribute the number of elements in the container, which can also change the capacity of the container. If the number of redistributed elements is smaller than the original number, the sequence will be truncated and the subsequent part will be discarded. If it is larger than the original number, the subsequent value is the value of c, which is 0 by default

11. vector::capacity()

   size_type capacity () const;

Returns the size of the actual storage space of the vector, which is generally greater than or equal to the number of vector elements. Note the difference from the size() function

12. vector::empty()

   bool empty () const;

When the number of elements is 0, it returns true, otherwise it is false. It is based on the number of elements rather than the storage space of the container

13. vector::reserve()

   void reserve ( size_type n );

The size of the reallocated space. However, the n value must be larger than the value returned by the original capacity(). Otherwise, the storage space will remain unchanged. The n value must be larger than the original actual storage space to reallocate space, but the maximum value cannot be greater than max_size, otherwise an exception will be thrown

14. vector::operator [] / / overloaded [] symbol

   reference  operator[] ( size_type n );

const_reference  operator[] ( size_type n ) const;

Implements subscript access elements

15. vector::at()

   const_reference at ( size_type n ) const;

   reference at ( size_type n );

The operation of the function is the same as that of the subscript access element, except that an out exception will be thrown when the function exceeds the boundary_ of_ range

16. vector::front()

   reference front ( );

const_reference front ( ) const;

Returns the value of the first element, which is different from the begin() function. The begin() function returns the iterator of the first element

17. vector::back()

   reference back ( );

const_reference back ( ) const;

Similarly, return the value of the last element. Note the difference from the end() function

18. vector::assign()

   template <class InputIterator> void assign ( InputIterator first, InputIterator last );

void assign ( size_type n, const T& u );

The original element is discarded and then the element is reassigned. The first function uses the iterator, and the second function uses n elements, each with a value of u.

19. vector::push_back()

   void push_back ( const T& x );

Insert the element x in the last position of the container, and if the size value is greater than the capacity value, the space will be reallocated

20. vector::pop_back()

   void pop_back ( );

Delete last element

21. vector::insert()

   iterator insert ( iterator position, const T& x );

   void insert ( iterator position, size_type n, const T& x );

template <class InputIterator>

void insert ( iterator position, InputIterator first, InputIterator last );

Insert a new element,

The first function inserts an element with a value of x before the position specified by the iterator

The second function inserts n elements with the value of x before the position specified by the iterator

The third function inserts a sequence of another container before the position specified by the iterator, iterators first to last

If the total number of elements after inserting new elements is greater than capacity, the space will be reallocated

22. vector::erase()

   iterator erase ( iterator position );

iterator erase ( iterator first, iterator last );

Delete an element or a sequence

23. vector::swap()

   void swap ( vector<T,Allocator>& vec );

Exchange the contents of the two containers, which involves the reallocation of storage space

24. vector::clear()

   void clear ( );

Empty the contents of the container. The size value is 0, but the storage space has not changed

example:

#include<bits/stdc++.h>
using namespace std;
int main()
{
 
        //Constructor, copy constructor (element types should be consistent),
	vector<int> A;  //Create an empty container
	vector<int> B(10,100); //Create a 10 element with a value of 100 for each element
	vector<int> C(B.begin(),B.end()); //Using iterators, you can take some elements and create a new container
	vector<int> D(C); //Copy the constructor and create an identical container
    
          //Heavy load=
	vector<int> E;
	E = B;
 
	//vector::begin() returns an iterator
   
	vector<int> F(10); //Create a container with 10 elements
           for (int i = 0; i < 10; i++)
          {
		F[i] = i;
          }
 
	/*
	vector<int> F; //Create an empty container
	for (int i = 0; i < 10; i++)
	{
		F.push_back(i);
	} 
        */
 
	vector<int>::iterator BeginIter = F.begin();
	cout << *BeginIter << endl; //Output 0
 
	//vector::end() returns the iterator
	vector<int>::iterator EndIter = F.end();
	EndIter--; //Move back one position
	cout << *EndIter << endl; //Output 9
 
	//vector::rbegin() returns the first element in reverse order, which is equivalent to the last element
	vector<int>::reverse_iterator ReverBeIter = F.rbegin();
	cout << *ReverBeIter << endl; //Output 9
 
	//The next position of the last element in reverse order of vector::rend() is also equivalent to the previous position of the first element in positive order
	vector<int>::reverse_iterator ReverEnIter = F.rend();
	ReverEnIter--;
	cout << *ReverEnIter << endl; //Output 0
 
	//vector::size() returns the number of elements
	cout << F.size() << endl; //Output 10
 
	//vector::max_size()
	cout << F.max_size() << endl; //Output 1073741823, which is the number of limit elements
 
	//vector::resize()
	cout << F.size() << endl; //Output 10
	F.resize(5);
	for(int k = 0; k < F.size(); k++)
		cout << F[k] << "  "; //Output 0 1 2 3 4
         cout << endl;
	
	//vector::capacity()
	cout << F.size() << endl; //5
	cout << F.capacity() << endl; //10
 
	//vector::empty()
         B.resize(0);
	cout << B.size() << endl; //0
	cout << B.capacity() << endl; //10
	cout << B.empty() << endl; //true
 
	//vector::reserve() / / reallocate storage space
           cout << C.capacity() << endl; //10
	C.reserve(4);
	cout << C.capacity() << endl; //10
	C.reserve(14);
	cout << C.capacity() << endl; //14
 
	//vector::operator []
	cout << F[0] << endl; //The first element is 0
 
	//vector::at()
	try
	{
	  cout << "F.size = " << F.size() << endl; //5
           cout << F.at(6) << endl; //Throw exception
	}
	catch(out_of_range)
	{	
	   cout << "at()Cross border visit" << endl;
	}
 
	//vector::front() returns the value of the first element
           cout << F.front() << endl; //0
 
	//vector::back()
	cout << F.back() << endl; //4
 
	//vector::assign()
	cout << A.size() << endl; //0
	vector<int>::iterator First = C.begin();
	vector<int>::iterator End = C.end()-2;
	A.assign(First,End);
	cout << A.size() << endl; //8
	cout << A.capacity() << endl; //8
 
	A.assign(5,3); //All the original elements will be discarded and re assigned
	cout << A.size() << endl; //5
	cout << A.capacity() << endl; //8
 
	//vector::push_back()
	cout << *(F.end()-1) << endl; //4
	F.push_back(100);
	cout << *(F.end()-1) << endl; //100
 
	//vector::pop_back()
	cout << *(F.end()-1) << endl; //100
	F.pop_back();
	cout << *(F.end()-1) << endl; //4
 
	//vector::swap()
	F.swap(D); //Swap the contents of the two containers
	for(int f = 0; f < F.size(); f++)
		cout << F[f] << " ";
	cout << endl;
	for (int d = 0; d < D.size(); d++)
	    cout << D[d] << " ";
         cout << endl;
	//vector::clear()
	F.clear();
	cout << F.size() << endl;     //0
	cout << F.capacity() << endl; //10
 
	return 0;
}