好用的内置函数总结

__builtin_popcount()

• 返回输入数据中，二进制表示下 1 的个数。

__gcd()

• 字面意思，最大公约数

__lg()

• 以 $2$ 为底的对数向下取整，特别地有 __lg(0)=-1

partial_sum()

用于求前缀和或其他累积结果

• 函数原型：

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

• 使用例：

• std::vector<int> nums = {1, 2, 3, 4};
  std::vector<int> result(nums.size());
  
  // 使用 partial_sum 计算前缀和
  std::partial_sum(nums.begin(), nums.end(), result.begin());

• 自定义运算符的 partial_sum：

• std::vector<int> nums = {1, 2, 3, 4};
  std::vector<int> result(nums.size());
  
  // 使用乘法来计算部分积
  std::partial_sum(nums.begin(), nums.end(), result.begin(),
                   std::multiplies<int>());

lower_bound & upper_bound

• 函数调用方式：

• std::upper_bound(v.begin(), v.end(), standard, comp);
  std::lower_bound(v.begin(), v.end(), standard, comp);

  comp 是一个条件函数，默认为 < 小于运算符，传入一个数组成员和一个标准 standard ，返回一个 bool 值

• 作用方式：

  • 要求待查找的数列有序，并且对条件函数的返回值呈现 0，0，0，......，1，1，1 的局面
  • lower_bound 将返回第一个不满足条件的数的迭代器 / 指针
  • upper_bound 将返回第一个不满足条件且不与标准相等的数的迭代器 / 指针

CAUTION

• 在这里比较函数的判等与 std::set 中的判等是一致的，即双方均为 false

• 自定义比较函数的参数顺序必须是：目标值在前，容器元素在后 ，即：

• bool comp(const T &target, const U &element);