从零开始学C++之STL（七）：剩下5种算法代码分析与使用示例（remove 、rotate 、sort、lower_bound、accumulate）

2022-03-07 17:24:52

一、移除性算法 （remove）

 C++ Code 
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
  
// TEMPLATE FUNCTION remove_copy

template < 
class _InIt,

         
class _OutIt,

         
class _Ty > 
inline

_OutIt _Remove_copy(_InIt _First, _InIt _Last,

                    _OutIt _Dest, 
const _Ty &_Val, _Range_checked_iterator_tag)

{

    
// copy omitting each matching _Val
    _DEBUG_RANGE(_First, _Last);

    _DEBUG_POINTER(_Dest);

    
for (; _First != _Last; ++_First)

        
if (!(*_First == _Val))

            *_Dest++ = *_First;

    
return (_Dest);

}

template < 
class _InIt,

         
class _OutIt,

         
class _Ty > 
inline

_OutIt unchecked_remove_copy(_InIt _First, _InIt _Last,

                             _OutIt _Dest, 
const _Ty &_Val)

{

    
// copy omitting each matching _Val
    
return _STD _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val,

                             _STD _Range_checked_iterator_tag());

}

// TEMPLATE FUNCTION remove

template < 
class _FwdIt,

         
class _Ty > 
inline

_FwdIt remove(_FwdIt _First, _FwdIt _Last, 
const _Ty &_Val)

{

    
// remove each matching _Val
    _First = find(_First, _Last, _Val);

    
if (_First == _Last)

        
return (_First);    
// empty sequence, all done
    
else

    {

        
// nonempty sequence, worth doing
        _FwdIt _First1 = _First;

        
return (_STDEXT unchecked_remove_copy(++_First1, _Last, _First, _Val));

    }

}

如下图所示：

从零开始学C++之STL（七）：剩下5种算法代码分析与使用示例（remove 、rotate 、sort、lower_bound、accumulate）

假设现在想要remove 的元素是3，则传入到 _Remove_copy 函数的3个参数如上图第一行所示，Val 即3。

接着遍历First ~ Last 区间的元素，将非移除元素拷贝到前面，覆盖前面的元素，最后的指向如图，函数返回的是Dest 位置，如下代

码所示：

for (; _First != _Last; ++_First)

if (!(*_First == _Val))

*_Dest++ = *_First;

由上图可看出移除性算法并没有改变元素的个数，如果要真正删除，可以将remove 的返回值传入erase 进行删除，如：

v.erase(remove(v.begin(), v.end(), 3), v.end()); 即会将后面两个元素4 和 5 删除掉。

示例代码1：

 C++ Code 

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

  
#include <iostream>


#include <vector>


#include <list>


#include <algorithm>


using 
namespace std;

void print_element(
int n)

{

    cout << n << 
' ';

}

int main(
void)

{

    
int a[] = { 
, 
, 
, 
, 
, 
 };

    vector<
int> v(a, a + 
);

for_each(v.begin(), v.end(), print_element);

    cout << endl;

/*remove(v.begin(), v.end(), 3);
    for_each(v.begin(), v.end(), print_element);
    cout<<endl;*/

v.erase(remove(v.begin(), v.end(), 
), v.end());

    for_each(v.begin(), v.end(), print_element);

    cout << endl;

return 
;

}

二、变序性算法（ rotate）

 C++ Code 

1

2

3

4

5

6

7

  
template<
class _FwdIt> 
inline


void rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last)

{

    
// rotate [_First, _Last)
    
if (_First != _Mid && _Mid != _Last)

        _Rotate(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last), _Iter_cat(_First));

}

rotate 调用了_Rotate，实际上_Rotate 继续调用了某个函数，内部实现代码比较长，而且不容易看懂，这边可以看一下简易的等价

版本实现，来自这里，如下：

 C++ Code 

1

2

3

4

5

6

7

8

9

10

11

12

  
template <
class ForwardIterator>


void rotate (ForwardIterator first, ForwardIterator middle,

             ForwardIterator last)

{

    ForwardIterator next = middle;

    
while (first != next)

    {

        swap (*first++, *next++);

        
if (next == last) next = middle;

        
else 
if (first == middle) middle = next;

    }

}

假设一个容器有 1 2 3 4 5 6 六个元素，现在想把 1 2 放到后面去，可以这样写 rotate(v.begin(), v.begin()+2, v.end());  如下图所示：

从零开始学C++之STL（七）：剩下5种算法代码分析与使用示例（remove 、rotate 、sort、lower_bound、accumulate）

即将first 与 next 对应的元素互换且不断向前推进，直到first == next 为止。

三、排序算法 （sort）

 C++ Code 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

  
template<
class _RanIt> 
inline


void sort(_RanIt _First, _RanIt _Last)

{

    
// order [_First, _Last), using operator<
    _DEBUG_RANGE(_First, _Last);

    std::_Sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Last - _First);

}

template < 
class _RanIt,

         
class _Pr > 
inline


void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)

{

    
// order [_First, _Last), using _Pred
    _DEBUG_RANGE(_First, _Last);

    _DEBUG_POINTER(_Pred);

    std::_Sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Last - _First, _Pred);

}

sort 重载了两个版本，第一个版本只有2个参数，默认按从小到大排序（using operator<)；第二个版本有三个参数，即可以自定义比较逻辑

（_Pred）。它们都调用了标准库的std::_Sort， 跟踪进去发现比较复杂，在_Sort 内会根据一些条件选择不同的排序方式，如标准库的堆排序，合并

排序，插入排序等等。站在使用的角度看，没必要去深究，但如果是想学习相关的排序，那是很好的资源。

示例代码2：

 C++ Code 

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

  
#include <iostream>


#include <vector>


#include <list>


#include <algorithm>


using 
namespace std;

void print_element(
int n)

{

    cout << n << 
' ';

}

bool my_greater(
int a, 
int b)

{

    
return a > b;

}

int main(
void)

{

    
int a[] = { 
, 
, 
, 
, 
, 
 };

    vector<
int> v(a, a + 
);

for_each(v.begin(), v.end(), print_element);

    cout << endl;

rotate(v.begin(), v.begin() + 
, v.end());

    for_each(v.begin(), v.end(), print_element);

    cout << endl;

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

    for_each(v.begin(), v.end(), print_element);

    cout << endl;

sort(v.begin(), v.end(), my_greater);

    for_each(v.begin(), v.end(), print_element);

    cout << endl;

return 
;

}

四、已序区间算法 （lower_bound 、upper_bound）

使用这些算法的前提是区间已经是有序的。

 C++ Code 

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

  
// TEMPLATE FUNCTION lower_bound

template < 
class _FwdIt,

         
class _Ty,

         
class _Diff > 
inline

_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, 
const _Ty &_Val, _Diff *)

{

    
// find first element not before _Val, using operator<
    _DEBUG_ORDER_SINGLE(_First, _Last, 
true);

    _Diff _Count = 
;

    _Distance(_First, _Last, _Count);

for (; 
 < _Count; )

    {

        
// divide and conquer, find half that contains answer
        _Diff _Count2 = _Count / 
;

        _FwdIt _Mid = _First;

        std::advance(_Mid, _Count2);

        _DEBUG_ORDER_SINGLE(_Mid, _Last, 
false);

if (_DEBUG_LT(*_Mid, _Val))

            _First = ++_Mid, _Count -= _Count2 + 
;

        
else

            _Count = _Count2;

    }

    
return (_First);

}

template < 
class _FwdIt,

         
class _Ty > 
inline

_FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, 
const _Ty &_Val)

{

    
// find first element not before _Val, using operator<
    _ASSIGN_FROM_BASE(_First,

                      _Lower_bound(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val, _Dist_type(_First)));

    
return _First;

}

lower_bound() 返回第一个“大于等于给定值" 的元素位置，其实还重载了另一个low_bound 版本，如下：

 C++ Code 

1

2

3

4

5

6

7

  
// TEMPLATE FUNCTION lower_bound WITH PRED

template < 
class _FwdIt,

         
class _Ty,

         
class _Diff,

         
class _Pr > 
inline

_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last,

                    
const _Ty &_Val, _Pr _Pred, _Diff *)

也就是可以自定义比较逻辑，需要注意的是如果使用这个版本，那么区间应该本来就是按comp 方法排序的，如下面这句话：

The elements are compared using operator< for the first version, and comp for the second. The elements in the range shall already

be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.

由于是已序区间，所以函数内用的是二分查找，而两个版本主要的代码不同在于：

_DEBUG_LT(*_Mid, _Val)

_DEBUG_LT_PRED(_Pred, *_Mid, _Val)

upper_bound 与 lower_bound 类似，不过返回的是第一个”大于给定值“ 的元素位置。

示例代码3：

 C++ Code 

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

  
#include <iostream>


#include <vector>


#include <list>


#include <algorithm>


using 
namespace std;

void print_element(
int n)

{

    cout << n << 
' ';

}

int main(
void)

{

    
int a[] = { 
, 
, 
, 
, 
, 
 };

    vector<
int> v(a, a + 
);

for_each(v.begin(), v.end(), print_element);

    cout << endl;

vector<
int>::iterator it;

    it = lower_bound(v.begin(), v.end(), 
);

    
if (it != v.end())

    {

        cout << it - v.begin() << endl;

    }

it = upper_bound(v.begin(), v.end(), 
);

    
if (it != v.end())

    {

        cout << it - v.begin() << endl;

    }

return 
;

}

五、数值算法（accumulate）

 C++ Code 

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

  
// TEMPLATE FUNCTION accumulate

template < 
class _InIt,

         
class _Ty > 
inline

_Ty _Accumulate(_InIt _First, _InIt _Last, _Ty _Val)

{

    
// return sum of _Val and all in [_First, _Last)
    _DEBUG_RANGE(_First, _Last);

    
for (; _First != _Last; ++_First)

        _Val = _Val + *_First;

    
return (_Val);

}

template < 
class _InIt,

         
class _Ty > 
inline

_Ty accumulate(_InIt _First, _InIt _Last, _Ty _Val)

{

    
// return sum of _Val and all in [_First, _Last)
    
return _Accumulate(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val);

}

// TEMPLATE FUNCTION accumulate WITH BINOP

template < 
class _InIt,

         
class _Ty,

         
class _Fn2 > 
inline

_Ty _Accumulate(_InIt _First, _InIt _Last, _Ty _Val, _Fn2 _Func)

{

    
// return sum of _Val and all in [_First, _Last), using _Func
    _DEBUG_RANGE(_First, _Last);

    _DEBUG_POINTER(_Func);

    
for (; _First != _Last; ++_First)

        _Val = _Func(_Val, *_First);

    
return (_Val);

}

template < 
class _InIt,

         
class _Ty,

         
class _Fn2 > 
inline

_Ty accumulate(_InIt _First, _InIt _Last, _Ty _Val, _Fn2 _Func)

{

    
// return sum of _Val and all in [_First, _Last), using _Func
    
return _Accumulate(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val, _Func);

}

accumulate 重载了两个版本，第一个版本实现的是累加，第二个版本带_Func 参数，可以自定义计算，比如累乘等。代码都比较好理解，就不赘述

了。看下面的示例代码4：

 C++ Code 

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

  
#include <iostream>


#include <vector>


#include <list>


#include <algorithm>


#include <numeric>


using 
namespace std;

void print_element(
int n)

{

    cout << n << 
' ';

}

int mult(
int a, 
int b)

{

    
return a * b;

}

int main(
void)

{

    
int a[] = { 
, 
, 
, 
, 
 };

    vector<
int> v(a, a + 
);

for_each(v.begin(), v.end(), print_element);

    cout << endl;

// 累加
    cout << accumulate(v.begin(), v.end(), 
) << endl;

// 累乘
    cout << accumulate(v.begin(), v.end(), 
, mult) << endl;

return 
;

}

参考：

C++ primer 第四版
Effective C++ 3rd
C++编程规范

上一篇：PKI及SSL协议分析


下一篇：4组-Alpha冲刺-6/6