cpp学习-第十章-泛型算法

发表于 | 分类于

核心简记

  1. 泛型算法作用于各种容器，大多数定义在algorithm中
  2. 指针可以当做迭代器传入泛型算法中。
  3. 泛型算法本身不执行容器的操作，只运行于迭代器上，因此不会改变底层容器的大小。除非改变是迭代器的效果
  4. copy版本的算法将结果放入新序列
  5. using namespace name; 将name下的名字都引入

算法查表可以参考:
https://blog.csdn.net/strint/article/details/45308001

定制操作

算法有额外的参数可以指定操作代替元素<=等操作
可调用对象>谓词(可调用的表达式、返回为条件值) 函数的指针可以做谓词。

传函数指针谓词时参数被限定了，不能加控制参数。使用lambda可以传入其它参数。
lambda:适用于一俩个地方使用的简单操作

1
2
3
4
5
6
7
8
9
10
11
[捕捉列表](参数列表)->返回类型{函数体}
捕获列表:
[] 空，不使用所在函数变量
[names] ,分割局部变量，默认为拷贝，加&为引用
[&]隐式引用，根据函数体代码自动推断使用的变量，但都是引用
[=]隐式拷贝，同上，都是拷贝值
[&,names] 指定的采用值捕获，其它引用捕获，方式必须不同
[=,names] 与上相反

忽略参数列表与()为空参数
忽略返回类型根据函数体推断，但体仅一个return。 返回类型必须尾置

lambda只能使用明确指明的外层函数局部变量。指明通过捕捉列表。可以直接使用所在函数外的名字与局部静态变量

lambda实际上是定义了一个新类型与其对象。该对象含捕获变量的数据成员，创建对象时初始化。
捕获的变量为lambda创建时拷贝，若要引用则[&a]即可。因为函数可以返回lambda对象因此作用域与生存期当心。

默认下不会改变捕获的值，想要在lambda中改变捕获的值要在参数列表后加mutable

函数也可以使用包装来达到多传参数的效果

1
2
3
4
5
6
7
<functional>
auto newcall=bind(oldcall,args)
如：
auto g=bind(f,a,b,_2,c,_1);
调用 g(_1,_2)
等价为 f(a,b,_2,c,_1)

生成一个新的函数适应参数列表。默认为拷贝，因为是传参而不是定义，因此引用也会化为拷贝，非占位符的参想引用传入要用库函数ref()返回可拷贝的引用对象。

迭代器

头文件iterator定义了额外的集中迭代器。

插入迭代器:

1
2
it=t 在it当前位置插入t
* ++ 都是返回本身

是对容器的包装，使用插入迭代器可以对容器插入元素，有三种插入迭代器:尾、头、指定位置。

流迭代器:
输入与输出流的迭代器。可以使流使用泛型算法。
输入流的操作多些:使用*返回读取的值，使用++读取下一个。
输出使用=输出

反向迭代器:
反向操作，容器必须同时支持++与–
调用反向迭代器的.base()方法可以返回正常迭代器，不过位置不同，因为[)要向后挪一个

移动迭代器:移动迭代器的解引用返回右值引用:

1
make_move_iterator(begin());

对其的解引用将使用右值引用。普通的是返回左值引用

泛型算法结构

算法的基本特性是要求迭代器提供哪些操作，可分为5个迭代器类别:其功能逐层增加
输入迭代器：只读，不写，单遍递增。如流输入迭代器
输出迭代器：只写，不读，单遍递增。如流输出迭代器
前向迭代器：读写，多遍递增。如forward_list的迭代器
双向迭代器：读写，多遍，可增可减。除了fl的库迭代器
随机访问迭代器：读写，多遍，随机读写。array、deque、string、vector都是

算法的参数模式:

1
2
3
4
be,ed,args  一个输入
be,ed,dest,args   一个输入，一个输出
be,ed,be2,args  俩个输入
be,ed,be2,ed2,args  俩个输入

  1. 一些有接受谓词的重载实现，如unique
  2. 后缀_if的版本可以接受谓词代替原元素值，如find
  3. 写回另一个指定输出目的的拷贝版本，后缀_copy

list与fl不用通用版本，其以成员函数形式实现了自己的版本，因为不拷贝效率更高。如:merge、remove、reverse、sort、unique。splice用于俩个之间移动元素。链表特有的会改变容器。

反汇编

1
2
3
4
5
6
7
8
9
int main(int argc, char const *argv[])
{
    int a=2;
    auto f=[a](int i,int j)->int{int d=a+i+j;return j;};
    int d=f(2,3);
    return 0;
}

x86-64

FS——附加段寄存器(Extra Segment Register)，其值为附加数据段的段值；
GS——附加段寄存器(Extra Segment Register)，其值为附加数据段的段值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
.text:0000000000007A70 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:0000000000007A70 main            proc near               ; DATA XREF: start+2E↑o
.text:0000000000007A70
.text:0000000000007A70 var_28          = dword ptr -28h
.text:0000000000007A70 var_24          = dword ptr -24h
.text:0000000000007A70 var_20          = qword ptr -20h
.text:0000000000007A70 var_18          = dword ptr -18h
.text:0000000000007A70 var_14          = dword ptr -14h
.text:0000000000007A70 var_10          = dword ptr -10h
.text:0000000000007A70 var_8           = qword ptr -8
.text:0000000000007A70
.text:0000000000007A70 ; __unwind {
.text:0000000000007A70                 push    rbp
.text:0000000000007A71                 mov     rbp, rsp
.text:0000000000007A74                 sub     rsp, 30h
.text:0000000000007A78                 mov     rax, fs:28h
.text:0000000000007A81                 mov     [rbp+var_8], rax
.text:0000000000007A85                 mov     [rbp+var_14], 0
.text:0000000000007A8C                 mov     [rbp+var_18], edi
.text:0000000000007A8F                 mov     [rbp+var_20], rsi
//var_24为a
.text:0000000000007A93                 mov     [rbp+var_24], 2
//拷贝a构建对象在当前栈中
.text:0000000000007A9A                 mov     edi, [rbp+var_24]
.text:0000000000007A9D                 mov     [rbp+var_10], edi
//获取对象的this  传this、其它参数
.text:0000000000007AA0                 lea     rdi, [rbp+var_10]
.text:0000000000007AA4                 mov     esi, 2
.text:0000000000007AA9                 mov     edx, 3
.text:0000000000007AAE                 call    sub_7AE0
.text:0000000000007AB3                 mov     [rbp+var_28], eax
.text:0000000000007AB6                 mov     rdi, fs:28h
.text:0000000000007ABF                 mov     rcx, [rbp+var_8]
.text:0000000000007AC3                 cmp     rdi, rcx
.text:0000000000007AC6                 jnz     loc_7AD4
.text:0000000000007ACC                 xor     eax, eax
.text:0000000000007ACE                 add     rsp, 30h
.text:0000000000007AD2                 pop     rbp
.text:0000000000007AD3                 retn
.text:0000000000007AD4 ; ---------------------------------------------------------------------------
.text:0000000000007AD4
.text:0000000000007AD4 loc_7AD4:                               ; CODE XREF: main+56↑j
.text:0000000000007AD4                 call    ___stack_chk_fail
.text:0000000000007AD4 ; } // starts at 7A70
.text:0000000000007AD4 main            endp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
.text:0000000000007AE0 sub_7AE0        proc near               ; CODE XREF: main+3E↑p
.text:0000000000007AE0
.text:0000000000007AE0 var_14          = dword ptr -14h
.text:0000000000007AE0 var_10          = dword ptr -10h
.text:0000000000007AE0 var_C           = dword ptr -0Ch
.text:0000000000007AE0 var_8           = qword ptr -8
.text:0000000000007AE0
.text:0000000000007AE0 ; __unwind {
.text:0000000000007AE0                 push    rbp
.text:0000000000007AE1                 mov     rbp, rsp
//函数体
.text:0000000000007AE4                 mov     [rbp+var_8], rdi
.text:0000000000007AE8                 mov     [rbp+var_C], esi
.text:0000000000007AEB                 mov     [rbp+var_10], edx
.text:0000000000007AEE                 mov     rdi, [rbp+var_8]
.text:0000000000007AF2                 mov     edx, [rdi]
.text:0000000000007AF4                 add     edx, [rbp+var_C]
.text:0000000000007AF7                 add     edx, [rbp+var_10]
.text:0000000000007AFA                 mov     [rbp+var_14], edx
.text:0000000000007AFD                 mov     eax, [rbp+var_10]
.text:0000000000007B00                 pop     rbp
.text:0000000000007B01                 retn
.text:0000000000007B01 ; } // starts at 7AE0
.text:0000000000007B01 sub_7AE0        endp

ARM-64

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
.text:0000000000008BD0 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:0000000000008BD0                 EXPORT main
.text:0000000000008BD0 main                                    ; DATA XREF: LOAD:0000000000000DB8↑o
.text:0000000000008BD0                                         ; .got:main_ptr↓o
.text:0000000000008BD0
.text:0000000000008BD0 var_28          = -0x28
.text:0000000000008BD0 var_24          = -0x24
.text:0000000000008BD0 var_20          = -0x20
.text:0000000000008BD0 var_18          = -0x18
.text:0000000000008BD0 var_14          = -0x14
.text:0000000000008BD0 var_10          = -0x10
.text:0000000000008BD0 var_8           = -8
.text:0000000000008BD0 var_s0          =  0
.text:0000000000008BD0
.text:0000000000008BD0 ; __unwind {
.text:0000000000008BD0                 SUB             SP, SP, #0x40
.text:0000000000008BD4                 STP             X29, X30, [SP,#0x30+var_s0]
.text:0000000000008BD8                 ADD             X29, SP, #0x30
.text:0000000000008BDC                 SUB             X8, X29, #-var_10
.text:0000000000008BE0                 MOV             W9, #2
.text:0000000000008BE4                 MOV             W2, #3
.text:0000000000008BE8                 MRS             X10, #3, c13, c0, #2
.text:0000000000008BEC                 LDR             X10, [X10,#0x28]
.text:0000000000008BF0                 STUR            X10, [X29,#var_8]
.text:0000000000008BF4                 STUR            WZR, [X29,#var_14]
.text:0000000000008BF8                 STR             W0, [SP,#0x30+var_18]
.text:0000000000008BFC                 STR             X1, [SP,#0x30+var_20]
//a
.text:0000000000008C00                 STR             W9, [SP,#0x30+var_24]
//构造对象
.text:0000000000008C04                 LDR             W0, [SP,#0x30+var_24]
.text:0000000000008C08                 STUR            W0, [X29,#var_10]
// x8为var_10的地址，
.text:0000000000008C0C                 MOV             X0, X8
.text:0000000000008C10                 MOV             W1, W9
.text:0000000000008C14                 BL              sub_8C48
.text:0000000000008C18                 STR             W0, [SP,#0x30+var_28]
.text:0000000000008C1C                 MRS             X8, #3, c13, c0, #2
.text:0000000000008C20                 LDR             X8, [X8,#0x28]
.text:0000000000008C24                 LDUR            X10, [X29,#var_8]
.text:0000000000008C28                 CMP             X8, X10
.text:0000000000008C2C                 B.NE            loc_8C44
.text:0000000000008C30                 MOV             W8, WZR
.text:0000000000008C34                 MOV             W0, W8
.text:0000000000008C38                 LDP             X29, X30, [SP,#0x30+var_s0]
.text:0000000000008C3C                 ADD             SP, SP, #0x40
.text:0000000000008C40                 RET
.text:0000000000008C44 ; ---------------------------------------------------------------------------
.text:0000000000008C44
.text:0000000000008C44 loc_8C44                                ; CODE XREF: main+5C↑j
.text:0000000000008C44                 BL              .__stack_chk_fail
.text:0000000000008C44 ; } // starts at 8BD0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
.text:0000000000008C48 sub_8C48                                ; CODE XREF: main+44↑p
.text:0000000000008C48
.text:0000000000008C48 var_14          = -0x14
.text:0000000000008C48 var_10          = -0x10
.text:0000000000008C48 var_C           = -0xC
.text:0000000000008C48 var_8           = -8
.text:0000000000008C48
.text:0000000000008C48 ; __unwind {
.text:0000000000008C48                 SUB             SP, SP, #0x20
.text:0000000000008C4C                 STR             X0, [SP,#0x20+var_8]
.text:0000000000008C50                 STR             W1, [SP,#0x20+var_C]
.text:0000000000008C54                 STR             W2, [SP,#0x20+var_10]
.text:0000000000008C58                 LDR             X0, [SP,#0x20+var_8]
.text:0000000000008C5C                 LDR             W1, [X0]
.text:0000000000008C60                 LDR             W2, [SP,#0x20+var_C]
.text:0000000000008C64                 ADD             W1, W1, W2
.text:0000000000008C68                 LDR             W2, [SP,#0x20+var_10]
.text:0000000000008C6C                 ADD             W1, W1, W2
.text:0000000000008C70                 STR             W1, [SP,#0x20+var_14]
.text:0000000000008C74                 LDR             W0, [SP,#0x20+var_10]
.text:0000000000008C78                 ADD             SP, SP, #0x20
.text:0000000000008C7C                 RET
.text:0000000000008C7C ; } // starts at 8C48
.text:0000000000008C7C ; End of function sub_8C48

可见lambda在c++中实现的本质就是一个类与对象，自定义的类代码位于code，捕获的数据作为对象成员，创建lambda时创建对象，并用指定的局部变量初始化对象成员，之后使用该对象重载的调用运算符使用该部分数据。会传入this