[STL source code analysis] summary notes (12): functors and adapters

00 Write it at the front

functor （functors） And adapters （adapter） That's the whole STL The last part of . Although the content of these two parts is not much , You can put it together and say .

But as a STL Two of the six components , There are still many essence of design in both of them , It's worth learning .

This is also 【STL Source analysis 】 The last chapter of the summary notes .

01 functor （Functors）

The origin of imitative function

functor , seeing the name of a thing one thinks of its function , Is something like a function . Before we talk about functors , Let's see how it came about .

We have seen many algorithms before , Most algorithms provide a default version , But if the user wants to change the algorithm according to different application scenarios , It's OK, too . such as sort The sorting algorithm is ascending by default , We can also change it into descending order according to different operations .

And here it is ” operation “ Is the key to changing the algorithm .

The first method is to write this operation as a function , Then pass in the function pointer in the parameters of the algorithm . In this way, the algorithm can be changed completely , But there will be a problem , Just not flexible enough , Can't change at will .

for instance , Find greater than... In the array 10 The number of .

int RecallFunc(int *start, int *end, bool (*pf)(int)) { 
    int count=0; 
    for(int *i=start;i!=end+1;i++) { 
        count = pf(*i) ? count+1 : count; 
    } 
    return count; 
} 

bool IsGreaterThanTen(int num) { 
    return num>10 ? true : false; 
} 

int main() { 
    int a[5] = {10,100,11,5,19}; 
    int result = RecallFunc(a,a+4,IsGreaterThanTen);
    return 0;
}

We can put greater than 10 Write it as a function , And then pass it into the original algorithm .

But if we want to achieve more than any number , Give Way IsGreaterThanTen(int num) Turn into IsGreaterThan(int num1,int num2) Pass in two parameters , Then it can not be realized .（ Of course, a global variable can also be defined ）

At this time, the imitative function comes in handy .

Another example , For example, common size comparison less

template <class T>
struct less:public binary_function<T,T,bool>{
    bool operator()(const T&x,const T&y)const{turn x<y};
};

After this definition, a functor object can be generated .

Can generate a functor entity , Then call the entity ：

less<int> less_obj;
less_obj(3,5);

Or use temporary objects **（ Commonly used ）**

less<int>()(3,5);

Of course , Matching algorithm is the purpose of the imitative function , Only for algorithms .

sort(vi.begin(),vi.end(),less<int>());

### Imitative function and algorithm

You may have noticed , Functor requires overloaded parentheses .

Such overloading can make it well integrated into the algorithm .

Such as the algorithm accumulate, In the second version, notice the third parameter

template <class InputIterator,class T,class BinaryOperation>
T accumulate(InputIterator first,InputIterator last,T init,BinaryOperation binary_op){
    for(;first!=last;++first)
        init=binary_op(init,*first);
    return init;
}

The third parameter is binary_op, When passing in a functor here , This overloaded parenthesis operation can be directly applied to binary_op() The parameters in the . If the passed in functor is plus, So here can also be translated as plus()(init,*first)

Inheritance of functor

Can we also design imitative functions ？ Of course you can .

such as

struct myclass{
    bool operator()(int i,int j){
        return i<j;
    }
}myobj;

There seems to be no problem , It can also be called normally .

But carefully and above less The comparison , You can find the difference .

less Inherited one public binary_function<T,T,bool>

This inheritance is to let the functor be integrated into STL The key to the system .

Matchability of affine functions

In succession , There are two structures , Namely unary_function and binary_function.

The definition is also very simple , It is mainly used to represent the parameter types and return value types of functions .

unary_function Corresponding to unary operation , Such as negation .

template <class Arg,class Result>
struct unary_function{
    typedef Arg argument_type;
    typedef Result sult_type;
};

binary_function Corresponding to binary operation , For example, add and , Multiplication and so on .

template <class Arg1,class Arg2,class Result>
struct binary_function{
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

If the functor inherits unary_function or binary_function, Then the subsequent adapters （adapter） You can get various types of functors .

This also makes STL The imitative functions in have the same splicing ability as building blocks .

02 Adapter （Adapter）

What is the adapter

Adapter （Adapter）, Also called adapter , In fact, it is to the existing class Change the interface . An application on a container is called a container adapter （container adapter）, It is called a function adapter when it is used in a functor （function adapter）, Used on iterators is called an iterator adapter （iterator adapter）

If A Want to achieve B Included functions , Then there are two ways ：A Inherit B perhaps A It contains B.

This is the second implementation for the adapter .

Container adapter

Container adapter we are deque I have already seen some of them , Namely queue and stack The implementation of the .

They all depend on deque Realized , So it is also called container adapter .

link

template <class T,class Sequence = deque<T>>
class stack{
    protected:
    	Sequence c;
    public:
    	bool empty() const{return c.empty()};
    	...
}

function adaptor

The function adapter is the play in the adapter . As we said earlier, the inheritance of the functor is also to better cooperate with the adapter .

Use the example in the first article to illustrate the function adapter

cout<<count_if(vi.begin(),vi.end(),bind2nd(less<int>(),40));

there bind2nd Is a typical function adapter .

Look at the code first

template <class Operation>
class binder2nd:public unary_function<typename Operation::first_agument_type,typename Operation::result_type>{

protected:
 Operation op;
 typename Operation::second_argument_type value;
public:
 binder2nd(const Operation&x,const typename Operation::second_argument_type&y)
     :op(x),value(y){}
 typename Operation::result_type
 operator(const typename Operation::first_agument_type &x )const{
     return op(x,value);
 }
};

This code contains a lot of information , Let's say it bit by bit .

1. First of all, understand typename Usage of ,typename You can directly tell the compiler that the following is the type, not the variable , Prevent compilation failures .
2. bind2nd Is used to bind a value to the second parameter of the functor .
3. Notice that it says binder2nd, yes bind2nd Inner function of .
4. binder2nd There was no call at first less(), It's about using op Write it down .
5. Operation::second_argument_type It is the link for the adapter to ask questions about the functor , Then the functor tells the adapter the type of the second parameter （ about less() That is to say int）
6. Finally, the parentheses are overloaded , Only then really called less()
7. Adapters are used to decorate functors , If the functor overloads the parentheses , Then the adapter should have the same effect after decoration , So you also need to overload the parentheses .

about binder2nd Come on , Users need to know Operation What type can I use . In the above example Operation In fact, that is less, But it's very troublesome to use , therefore STL Provides a wrapper for the outer interface .

template <class Operation,class T>
inline binder2nd<Operation>bind2nd(const Operation&op,const T&x){
    typedef typename Operation::second_argument_type arg2_type;
    return binder2nd<Operation>(op,arg2_type(x));
}

First ask the type of the second parameter , Then automatically deduce op The type of .

Function adapters are like functors , If it is possible to continue to modify , Will inherit unary_function or binary_function.

Iterator adapter

reverse iterator

The most interesting of the iterator adapters is the reverse iterator , That is to say reverse iterator, Handle elements from end to end .

Our common iterators are ：

sort(vi.begin(),vi.end());

The reverse iterator is written as

sort(vi.rbegin(),vi.rend());

Let's see rbegin() and rend() The definition of

rbegin(){
    return reverse_iterator(end());
}

rend(){
    return reverse_iterator(begin());
}

It can be seen that the implementation is also reverse , The head takes the tail , Tail tapping . However, there is still a difference in the actual overload implementation process .

Let's take a look at a picture ：

Because the front is closed and the back is open , Our common begin() It's the starting position , Corresponding to the first element , and end() Is the next position of the last element .

So after the reverse ,rbegin() refer to end() The previous element of ,rend() refer to begin() The previous element of .

So when overloading, you need to know what the previous element is （ But the position of the pointer does not change ）

reference operator*()const{
    Iterator tmp=current;
    return *--tmp;
}

#### inserter

inserter It is also an iterator adapter , Will be able to iterator The assignment operation of becomes an insert operation .

inserter The implementation of mainly depends on the cleverness of overloading .

Let's say I have two list

If you execute ：

list <int>::iterator it=foo.begin();
copy(bar.begin(),bar.end(),inserter(foo,it));

Will change from overwrite to insert

about copy Come on , The implementation is as follows ：

template <class ImputIterator,class OutputIterator>
OutputIterator copy(InputIterator first,InputIterator last,OutputIterator result){
    while(first!=last){
        *result=*first;
        ++result;
        ++first;
    }
    return result;
}

The process is through first Move to copy the original value to get result.

So let's use inserter How to implement other operations ？

Actually inserter The implementation of is overloaded “=”

template <class Container>
class insert_iterator{
    ...
insert<Container>&operator=(const typename Container::value_type& value){
        iter=container->insert(iter,value);
        ++iter;
        return *this;
    }
}

Isn't it very clever , stay copy in , When *result=*first when , This = Would call insert Insert values into , Then move the pointer to keep following .

And that's how it works inserter The function of .

X Adapter

So-called X Adapter , In addition to the classic adapters , There are also some special adapters that will be used . such as ostream_iterator and istream_iterator

ostream_iterator

First of all to see ostream, What is commonly used is cout

Structurally by out_stream And separator .

class ostream_iterator:public iterator<output_iterator_tag,void,void,void,void>{
    basic_ostream<charT,traits>*out_stream;
    const chatT*delim;
    ...
}

Take a look at an example to realize its implementation ：

std::vector<int>myvector;
for(int i=1;i<10;i++)
    myvector.push_back(i*10);

std::ostream_iterator<int>out_it(std::cout,",");
std:copy(myvector.begin(),myvector.end(),out_it);

Here we are creating ostream When it came to cout And separator “,”, It is equivalent to outputting a number first and then a comma .

The point is copy Call of the third parameter in .

copy We are ahead of the implementation of inserter I've seen it in

template <class ImputIterator,class OutputIterator>
OutputIterator copy(InputIterator first,InputIterator last,OutputIterator result){
    while(first!=last){
        *result=*first;
        ++result;
        ++first;
    }
    return result;
}

And for ostream Come on , How to integrate yourself into something like copy Such an algorithm is the key .

ostream_iterator Very skillfully overloaded “=”, Make everything reasonable .

ostream_iterator<T,charT,traits>&operator=(const T& value){
    *out_stream<<value;
    if(delim!=0)out_stream<<delim;
    return *this;
}

encounter =, The first output value, If the delimiter exists , Then output a separator .

istream_iterator

And ostream The opposite is istream, That is to say cin Something like that .

Structurally by instream and value form .

class istream_iterator:public iterator<input_iterator_tag,T,Distance,const T*,const T&>{
    basic_istream<charT,traits>*in_stream;
    T value;
    ...
}

for instance

double value1,value2;
std::istream_iterator<double>eos;
std::istream_iterator<double>iit(std::cin);
if(iit!=eos)value1=*iit;
++iit;
if(iit!=eos)value2=*iit;

You can see that the iit after , You can get value The value of the . Move iit Then you can get the next value.

And the realization here is istream_iterator Essence .

Actually istream_iterator The value has been stored in... At the time of creation value 了 .

istream_iterator(istream_type& s):in_stream(&s){
    ++*this;
}

...
istream_iterator<T,charT,traits,Distance>& operator++(){
    if(in_stream&&!(in_stream>>value)) in_stream=0;
    return *this;
}

const T& operator*() const {
    return value;
}

At creation time ++, And later overloaded ++ operation , send value Get the input value . Last * To obtain by dereference value value .

The operation of reading the value immediately upon creation is istream_iterator Points worth noting in .

03 summary

That's all 【STL Source analysis 】 Summarize all the notes .

It involves STL All aspects of , It is not very detailed, but it is also a reference , The little partner who needs to prepare for the work can be used as a review material to go over it all over again , To deepen the memory .

Thank you for reading .