18. 常用函数

Note

以下函数基于 C++11 标准。

18.1. lower_bound，upper_bound

#include <algorithm>

lower_bound 从排好序的数组区间 [first, last) 中，采用二分查找，返回 大于或等于 val 的 第一个 元素位置。 如果所有元素都小于 val，则返回 last。

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

upper_bound 从排好序的数组区间 [first, last) 中，采用二分查找，返回 大于 val 的 第一个 元素位置。 如果所有元素都不大于 val，则返回 last。

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

统计有序数组中 val 的个数:

upper_bound(first, last, val) - lower_bound(first, last, val);

lower_bound 和 upper_bound 还支持指定一个二元谓词（Binary Predicate）来比较元素（缺省时为 operator< ），当 comp(a, b) 的第一个参数在数组中排在第二个参数前面时返回 true 。事实上这两个函数并不要求数组是严格排好序的（Sorted），只需要数组是关于 val 可分的（Partitioned）： comp(*iter, val) 为 true 的元素全部排在 comp(*iter, val) 为 false 的元素前面。

template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

\(\color{darkgreen}{Example}\)

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4using namespace std;
 5
 6int main(int argc, char ** argv)
 7{
 8  int a[11] = {1,2,3,4,5,5,5,5,6,7,8};
 9  cout << lower_bound(a, a + 11, 5) - a << endl; // 4
10  cout << upper_bound(a, a + 11, 5) - a << endl; // 8
11  vector<int> v(a, a + 11); // 用 a 对 v 初始化
12  cout << lower_bound(v.begin(), v.end(), 5) - v.begin() << endl; // 4
13  cout << upper_bound(v.begin(), v.end(), 5) - v.begin() << endl; // 8
14
15  *lower_bound(a, a + 11, 5) = 500;
16  for (auto ai : a) cout << ai << ends; // 1 2 3 4 500 5 5 5 6 7 8
17  cout << endl;
18
19  *lower_bound(v.begin(), v.end(), 5) = 500;
20  for (auto vi : v) cout << vi << ends; // 1 2 3 4 500 5 5 5 6 7 8
21  cout << endl;
22
23  return 0;
24}

Note

map、multimap、set、multiset 是基于红黑树实现的、有序的，其中 map、multimap 默认按照 key 排序。 这四种模板都自带 lower_bound 和 upper_bound 成员函数。

map<int,int> m;
int val = 5;
auto it = m.lower_bound(val);

相当于

auto it = lower_bound(
    m.begin(),
    m.end(),
    val,
    [](pair<int,int> p, const int v){return p.first < v;}
);

18.2. fill，fill_n，for_each

#include <algorithm>

fill 函数将一个区间 [first, last) 的每个元素都赋予 val 值。

template <class ForwardIterator, class T>
void fill (ForwardIterator first, ForwardIterator last, const T& val);

fill_n 函数从 first 开始依次赋予 n 个元素 val 值。

template <class OutputIterator, class Size, class T>
void fill_n (OutputIterator first, Size n, const T& val);

for_each 把函数 fn 应用于区间 [first, last) 的每个元素。

template <class InputIterator, class Function>
Function for_each (InputIterator first, InputIterator last, Function fn)
{
  while (first != last)
  {
    fn (*first);
    ++first;
  }
  return fn;      // or, since C++11: return move(fn);
}

fn 是一个一元谓词（Unary Predicate），接受一个参数，其返回值被忽略。fn 可以是一个函数指针或函数对象。

Note

函数对象

如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。 函数对象是一个对象，但是使用的形式看起来像函数调用，实际上也执行了函数调用。

\(\color{darkgreen}{Example}\)

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4using namespace std;
 5
 6template<class T>
 7void print(T elem){ cout << elem << " "; }
 8
 9struct myclass
10{
11  void operator() (int elem) { cout << elem << " "; }
12}myobject;
13// 注意：这里重载的是 () 运算符，接受一个参数；myobject 是一个结构体变量（类对象），调用 myobject(6) 会打印 6。
14
15int main(int argc, char ** argv)
16{
17
18  float a[4] = { 0.0 }; // {0.0, 0.0, 0.0, 0.0}
19  vector<int> v(4, 0); // {0, 0, 0, 0}
20
21  fill(a, a+4, 3.3); // {3.3, 3.3, 3.3, 3.3}
22  fill_n(a, 2, 6.6); // {6.6, 6.6, 3.3, 3.3}
23  fill_n(v.begin(), 4, 9); // {9, 9, 9, 9}
24
25  for_each(a, a + 4, print<float>); //  6.6 6.6 3.3 3.3
26  cout << endl;
27  for_each(v.begin(), v.end(), print<int>); //  9 9 9 9
28  cout << endl;
29  for_each(v.begin(), v.end(), myobject); //  9 9 9 9
30  cout << endl;
31
32  int b[10][20];
33  fill(b[0], b[0] + 200, 2); // b 所有元素为 2
34
35  return 0;
36}

最长上升子序列：

 1/* https://leetcode.com/problems/longest-increasing-subsequence/ */
 2/* O(nlogn) in time.*/
 3
 4class Solution
 5{
 6public:
 7  int lengthOfLIS(vector<int>& nums)
 8  {
 9    if(nums.size()<=1) return nums.size();
10    int inf = INT_MAX;
11    int len = nums.size();
12    int* dp = new int[len];
13    fill(dp, dp+len, inf);
14    for(int k = 0; k < len; ++k) *lower_bound(dp, dp+len, nums[k]) = nums[k];
15    int length = lower_bound(dp, dp+len, inf) - dp;
16    delete[] dp;
17    return length;
18  }
19};

18.3. sort

#include <algorithm>

// default
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);

// custom
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

comp 是一个二元谓词（Binary Predicate），接受两个参数，返回 bool 型或一个可以转换为 bool 型的类型。comp 可以是一个函数指针或函数对象。

如果需要稳定排序，可以使用 stable_sort 直接代替 sort 。

\(\color{darkgreen}{Example}\)

 1#include <iostream>
 2#include <vector>
 3#include <functional>
 4#include <algorithm>
 5using namespace std;
 6
 7bool comparator(int i, int j)
 8{
 9  return (i < j);
10}
11
12struct myclass
13{
14  bool operator() (int i, int j)
15  {
16    return (i < j);
17  }
18} myobject;
19// 注意：这里重载的是 () 运算符，接受两个参数；myobject 是一个结构体变量（类对象）
20
21int main(int argc, char ** argv)
22{
23
24  int a[] = { 32, 71, 12, 45, 26, 80, 53, 33 };
25  vector<int> v(a, a + 8);               // 32 71 12 45 26 80 53 33
26
27  // using default comparison (operator <):
28  sort(v.begin(), v.begin() + 4);           //(12 32 45 71)26 80 53 33
29
30  // using comparator as comp，这里是相当于一个函数指针
31  sort(v.begin() + 4, v.end(), comparator); // 12 32 45 71(26 33 53 80)
32
33  // using object as comp，这里是一个函数对象
34  sort(v.begin(), v.end(), myobject);     //(12 26 32 33 45 53 71 80)
35
36  // using build-in comp: 类模板 greater 的类对象
37  sort(v.begin(), v.end(), greater<int>()); // (80 71 53 45 33 32 26 12)
38
39  // using build-in comp: 类模板 less 的类对象
40  sort(v.begin(), v.end(), less<int>());  //(12 26 32 33 45 53 71 80)
41
42  // using reverse_iterator
43  sort(v.rbegin(), v.rend());  // (80 71 53 45 33 32 26 12)
44
45  // sort array
46  sort(a, a + 8, greater<int>());  // (80 71 53 45 33 32 26 12)
47  sort(a, a + 8);                 // (12 26 32 33 45 53 71 80)，可使用 comparator、myobject、less<int>()
48
49  return 0;
50}

string 类也是可以排序的，如

string str;
sort(str.begin(), str.end());

Warning

如果把自定义的 comparator 函数封装为类的成员函数，应该定义为 静态成员函数（static） 。

18.4. reverse

#include <algorithm>

template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);

翻转区间 [first, last) 内的元素。适用于 vector、string 以及 静态数组、动态数组等。

\(\color{darkgreen}{Example}\)

 1#include <iostream>     // std::cout
 2#include <algorithm>    // std::reverse
 3#include <numeric>      // std::iota
 4#include <vector>       // std::vector
 5
 6int main ()
 7{
 8  std::vector<int> myvector;
 9
10  // set some values:
11  myvector.resize(9);
12  std::iota(myvector.begin(), myvector.end(), 1);   // 1 2 3 4 5 6 7 8 9
13
14  std::reverse(myvector.begin(),myvector.end());    // 9 8 7 6 5 4 3 2 1
15
16  // print out content:
17  std::cout << "myvector contains:";
18  for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
19    std::cout << ' ' << *it;
20  std::cout << '\n';
21
22  return 0;
23}

18.5. min_element，max_element，minmax_element

#include <algorithm>

  • min_element ：会返回指向输入序列的最小元素的迭代器；

  • max_element ：会返回指向最大元素的迭代器；

  • minmax_element ：会以 pair 对象的形式返回这两个迭代器。first 指向最小元素；second 指向最大元素。

min_element:

// default
template <class ForwardIterator>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

// custom
template <class ForwardIterator, class Compare>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp); // [first, last)

\(\color{darkgreen}{Example}\)

 1#include <iostream>
 2#include <algorithm>
 3using namespace std;
 4
 5int main(int argc, char ** argv)
 6{
 7
 8  int a[10] = { 1, 2, 3, 4, 5, 6 };
 9  cout << a[9] << endl; // 0
10
11  cout << *min_element(a, a + 10) << endl; // 0
12
13  cout << *max_element(a, a + 10) << endl; // 6
14
15  auto p = minmax_element(a, a + 10);
16
17  cout << *p.first << ends << *p.second << endl; // 0 6
18
19  return 0;
20}

18.6. accumulate

#include <numeric>

// sum
template <class InputIterator, class T>
T accumulate (InputIterator first, InputIterator last, T init);

// custom
template <class InputIterator, class T, class BinaryOperation>
T accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

累加区间 [first, last) 的元素，并加上 init 。

\(\color{darkgreen}{Example}\)

 1#include <iostream>     // std::cout
 2#include <functional>   // std::minus
 3#include <numeric>      // std::accumulate
 4
 5int myfunction (int x, int y) {return x+2*y;}
 6
 7struct myclass
 8{
 9  int operator()(int x, int y) {return x+3*y;}
10} myobject;
11
12int main ()
13{
14  int init = 100;
15  int numbers[] = {10,20,30};
16
17  std::cout << "using default accumulate: ";
18  std::cout << std::accumulate(numbers,numbers+3,init); // 100 + (10 + 20 + 30)
19  std::cout << '\n';
20
21  std::cout << "using functional's minus: ";
22  std::cout << std::accumulate (numbers, numbers+3, init, std::minus<int>()); // 100 - (10 + 20 + 30)
23  std::cout << '\n';
24
25  std::cout << "using custom function: ";
26  std::cout << std::accumulate (numbers, numbers+3, init, myfunction); // 100 + 2 * (10 + 20 + 30)
27  std::cout << '\n';
28
29  std::cout << "using custom object: ";
30  std::cout << std::accumulate (numbers, numbers+3, init, myobject); // 100 + 3 * (10 + 20 + 30)
31  std::cout << '\n';
32
33  return 0;
34}

18.7. partial_sum

#include <numeric>

累加，并把结果存到序列（数组、向量） result 中。

// sum
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result);

// custom
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum (InputIterator first, InputIterator last,
                            OutputIterator result,
                            BinaryOperation binary_op);

// y0 = x0
// y1 = x0 + x1
// y2 = x0 + x1 + x2
// y3 = x0 + x1 + x2 + x3
// y4 = x0 + x1 + x2 + x3 + x4
// ... ... ...

\(\color{darkgreen}{Example}\)

 1#include <iostream>     // std::cout
 2#include <functional>   // std::multiplies
 3#include <numeric>      // std::partial_sum
 4#include <vector>
 5
 6int myop (int x, int y) {return x+y+1;}
 7
 8int main ()
 9{
10  int val[] = {1,2,3,4,5};
11  int result[5];
12
13  std::partial_sum (val, val+5, result);
14  std::cout << "using default partial_sum: ";
15  for (int i = 0; i < 5; i++) std::cout << result[i] << ' '; // 1 3 6 10 15
16  std::cout << '\n';
17
18  std::vector<int> result_vec(6, 0); // 0 0 0 0 0 0
19  std::partial_sum (val, val+5, result_vec.begin()); // 1 3 6 10 15 0
20
21  std::partial_sum (val, val+5, result, std::multiplies<int>()); // 1 2 6 24 120
22  std::cout << "using functional operation multiplies: ";
23  for (int i = 0; i < 5; i++) std::cout << result[i] << ' ';
24  std::cout << '\n';
25
26  std::partial_sum (val, val+5, result, myop); // 1 4 8 13 19
27  std::cout << "using custom function: ";
28  for (int i = 0; i < 5; i++) std::cout << result[i] << ' ';
29  std::cout << '\n';
30  return 0;
31}

18.8. iota

#include <numeric>

template <class ForwardIterator, class T>
void iota (ForwardIterator first, ForwardIterator last, T val);

采用递增的形式，将 val 开始的等差数列赋值给区间 [first, last) 的元素。

\(\color{darkgreen}{Example}\)

 1#include <iostream>     // std::cout
 2#include <numeric>      // std::iota
 3
 4int main () {
 5  float numbers[10];
 6
 7  std::iota (numbers,numbers+10,3.5);
 8
 9  std::cout << "numbers:";
10  for (float& i:numbers) std::cout << ' ' << i; // 3.5 4.5 5.5 6.5 7.5 8.5 9.5 10.5 11.5 12.5
11  std::cout << '\n';
12
13  return 0;
14}

18.9. inner_product

#include <numeric>

// sum/multiply
template <class InputIterator1, class InputIterator2, class T>
T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);

// custom
template <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2>
T inner_product (InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2,
                 T init,
                 BinaryOperation1 binary_op1,
                 BinaryOperation2 binary_op2);

内积运算，再与 init 做运算:

while (first1 != last1)
{
  init = init + (*first1)*(*first2);
  // or: init = binary_op1 (init, binary_op2(*first1,*first2));
  ++first1; ++first2;
}
return init;

\(\color{darkgreen}{Example}\)

 1#include <iostream>     // std::cout
 2#include <functional>   // std::minus, std::divides
 3#include <numeric>      // std::inner_product
 4
 5int myaccumulator (int x, int y) {return x-y;}
 6int myproduct (int x, int y) {return x+y;}
 7
 8int main ()
 9{
10  int init = 100;
11  int series1[] = {10,20,30};
12  int series2[] = {1,2,3};
13
14  std::cout << "using default inner_product: ";
15  std::cout << std::inner_product(series1,series1+3,series2,init); // 100 + (10*1 + 20*2 + 30*3)
16  std::cout << '\n';
17
18  std::cout << "using functional operations: ";
19  std::cout << std::inner_product(series1,series1+3,series2,init,
20                                  std::minus<int>(),std::divides<int>()); // 100 - (10/1 + 20/2 + 30/3)
21  std::cout << '\n';
22
23  std::cout << "using custom functions: ";
24  std::cout << std::inner_product(series1,series1+3,series2,init,
25                                  myaccumulator,myproduct); // 100 - (10+1 + 20+2 + 30+3)
26  std::cout << '\n';
27
28  return 0;
29}

18.10. memset

#include <cstring>

void *memset ( void * ptr, int value, size_t num );

memset 按 字节 赋值， fill 按 元素 赋值。

如果用 memset 给 int 型变量赋值，只能是 0 或 -1。

\(\color{darkgreen}{Example}\)

 1#include <iostream>
 2#include <cstring>
 3
 4int main()
 5{
 6  char str[] = "almost every programmer should know memset!";
 7  memset (str,'-',6);
 8  cout << str << endl; // ------ every programmer should know memset!
 9
10  int a[10][10];
11  memset(a, -1, sizeof(a)); // 或者 10*10*sizeof(int)，全部赋值为-1
12  for(int e:a) cout << bitset<sizeof(int)*8>(e) << endl; // 11111111  11111111  11111111  11111111 （补码）
13
14  int b[5];
15  memset(b, 1, sizeof(b));// 或者 5*sizeof(int)，全部赋值为 16843009
16  for(int e:b) cout << bitset<sizeof(int)*8>(e) << endl; // 00000001 00000001 00000001 00000001 （int型占4字节，每个字节都赋值为1）
17
18  return 0;
19}

18.11. 附：几个头文件

  • <cmath>

    • pow

    • sqrt

    • floor

    • ceil

    • round

    • log

    • log10

    • exp

  • <cstdlib>

    • abs

    • fabs

    • rand

  • <limits>

    • INT_MIN: (signed int)0x80000000

    • INT_MAX: 0x7fffffff

  • <algorithm>

    • min

    • max

  • <utility>

    • pair

    • move

  • <functional>

    • less< TYPE >

    • greater< TYPE >

  • <cassert>

    • assert

18.12. 参考资料

  1. Cppreference headers

  1. C++ reference

  1. C/C++-STL中lower_bound与upper_bound的用法

  1. c++sort函数的使用总结

  1. C++ sort排序函数用法