STL summary

Catalog

One .STL The essence of

Two .STL Six components of

Containers

Algorithm  

iterator

Adapter

functor

---

One .STL The essence of

STL Is the standard template library , It's efficient C++ library , Increased code reuse rate , Make development more efficient .

Two .STL Six components of

Containers

STL The container of , It can be divided into sequential containers and associative containers .

Algorithm  

Algorithm ： Steps to solve the problem , In limited steps , Solve problems in mathematics or logic .STL There are a total of 70 Multiple , It mainly includes ： Sort , lookup , Permutation and combination , Data mobility , Copy , Delete , Compare combinations , Operations, etc .

①accumulate： Accumulate the elements in the interval

//  Yes [first, last) The elements in the interval are init Accumulate on the basis of 
template <class InputIterator, class T>
T accumulate ( InputIterator first, InputIterator last, T init );

//  Yes [fist, last) The elements in the interval are init On the basis of binary_op The specified operation is accumulated 
template <class InputIterator, class T, class BinaryOperation>
T accumulate ( InputIterator first, InputIterator last, T init,
BinaryOperation binary_op );

#include <numeric>
#include <vector>
struct Mul2
{
int operator()(int x, int y) { return x + 2 * y; }
};
int main()
{
//  Accumulate the elements in the interval 
vector<int> v{ 10, 20, 30 };
cout << accumulate(v.begin(), v.end(), 0)<<endl;
//  Multiply each element in the interval by 2, And then add up 
cout << accumulate(v.begin(), v.end(), 0, Mul2()) << endl;
return 0;
}

②count And count_if： The function of the algorithm is to count the number of occurrences of an element in the interval

//  Statistics value In the interval [first,last) Is the number of times 
template <class InputIterator, class T>
ptrdiff_t count ( InputIterator first, InputIterator last, const T& value )
{
ptrdiff_t ret=0;
while (first != last) if (*first++ == value) ++ret;
return ret;
}

//  Statistics satisfy pred The element of the condition is in [first, last) Number of in 
template <class InputIterator, class Predicate>
ptrdiff_t count_if ( InputIterator first, InputIterator last, Predicate pred )
{
ptrdiff_t ret=0;
while (first != last) if (pred(*first++)) ++ret;
return ret;
}

③find,find_if: The function of this algorithm is to find the position where the element first appears in the interval

//  stay [first, last) Search for value First occurrence , Find the location that returns the element , Otherwise return to last
//  Time complexity O(N)
template<class InputIterator, class T>
InputIterator find ( InputIterator first, InputIterator last, const T& value )
{
for ( ;first!=last; first++) if ( *first==value ) break;
return first;
}

//  stay [first, last) To find a solution that satisfies pred Where the element of the condition first appears , Find and return to that location , Otherwise return to last
//  Time complexity O(N)
template<class InputIterator, class Predicate>
InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred )
{
for ( ; first!=last ; first++ ) if ( pred(*first) ) break;
return first;
}

④max and min：max Returns the larger of the two elements ,min Returns the smaller of the two elements .

template <class T>
const T& max(const T& a, const T& b)
{
return (a<b)?b:a;
}
template <class T>
const T& min(const T& a, const T& b)
{
return !(b<a)?a:b;
}

⑤merge： This algorithm combines two ordered sequences into one , Must include header file when using .

int main()
{
vector<int> v{ 2, 6, 5, 8 };
list<int> L{ 9, 3, 0, 5, 7 };
sort(v.begin(), v.end());
L.sort();
vector<int> vRet(v.size() + L.size());
merge(v.begin(), v.end(), L.begin(), L.end(), vRet.begin());
for (auto e : vRet)
cout << e << " ";
cout << endl;
return 0;
}

⑥ partial_sort： The function of this algorithm is ： look for TOPK

//  In the interval [first, last) Before you find it middle-first The smallest element , And stored in [first, middle) in 
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last);

//  stay [first, last) Before you find it middle-first The largest or smallest element , And stored in [first, middle) in 
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);

⑦ partition： The function of the algorithm is to divide the elements in the interval according to the conditions , Must include header file when using .

template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred)
{
while (true)
{
while (first!=last && pred(*first)) ++first;
if (first==last--) break;
while (first!=last && !pred(*last)) --last;
if (first==last) break;
swap (*first++,*last);
}
return first;
}

⑧reverse： The function of the algorithm is to reverse the elements in the interval , Must include header file when using .

template <class BidirectionalIterator>
void reverse ( BidirectionalIterator first, BidirectionalIterator last)
{
while ((first!=last)&&(first!=--last))
swap (*first++,*last);
}

⑨sort： Multiple sorting algorithms are mixed .

⑩ unique： This function is used to delete adjacent repetitive elements in the interval , Ensure element uniqueness , Pay attention to ensure that the elements in the interval are orderly before use , To achieve real weight removal .

iterator

What is iterator ？ An iterator is a design pattern , Let the user access the container's data through a specific interface . An iterator is essentially a pointer .

Why iterators are needed ？ It can better realize the general algorithm .

Who should be responsible for providing iterators ？ The underlying structure of each container is different , The iterator acts as a conversion layer between the algorithm and the container . therefore ： Iterators for each container should be provided by the container designer , Then the container provides a unified interface according to the Convention .

Adapter

Adapter ： Then the adapter , It's a design pattern , To put it simply ： What you need is right in front of you , But it cannot be used because of the wrong interface , Its interface needs to be transformed for ease of use . namely ： Convert the interface of one class into the interface of another class desired by the user , Make classes with incompatible interfaces work together .

functor

functor ： An object with functional characteristics , The caller can use the object like a function , To be able to “ It behaves like a function ”, The class of this object must customize the function call operator operator(), After overloading the operator , You can add a pair of parentheses to the end of the functor object , To call the function defined by the function operator() operation , In terms of its behavior ,“ functor ” One more cut paste . General matching algorithm of imitative function , Role is ： Improve the flexibility of the algorithm .