提示

如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数：

template <class T>
T getXorSum(T *begin, T *end) {
  T ret = 0;
  for (T *it = begin; it != end; ++it) ret ^= *it;
  return ret;
}

……如果 $a$ 是 std::vector，则将上述调用代码里的 a 均改为 a.begin() 即可。

直觉上就感觉肯定是过不去编译的，实际也确实如此。将如下代码扔到洛谷在线 IDE（C++14，不开 O2）：

#include <bits/stdc++.h>

template <class T>
T getXorSum(T *begin, T *end) {
  T ret = 0;
  for (T *it = begin; it != end; ++it) ret ^= *it;
  return ret;
}

int main() {
  std::vector<int> n(5);
  std::cout << getXorSum(n.begin(), n.end());
  return 0;
}

编译报错信息为：

/tmp/compiler_vowheoxs/src: In function ‘int main()’:
/tmp/compiler_vowheoxs/src:12:25: 错误：对‘getXorSum(std::vector<int>::iterator, std::vector<int>::iterator)’的调用没有匹配的函数
   12 |   std::cout << getXorSum(n.begin(), n.end());
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
/tmp/compiler_vowheoxs/src:4:3: 附注：candidate: ‘template<class T> T getXorSum(T*, T*)’
    4 | T getXorSum(T *begin, T *end) {
      |   ^~~~~~~~~
/tmp/compiler_vowheoxs/src:4:3: 附注：  template argument deduction/substitution failed:
/tmp/compiler_vowheoxs/src:12:25: 附注：  mismatched types ‘T*’ and ‘__gnu_cxx::__normal_iterator<int*, std::vector<int> >’
   12 |   std::cout << getXorSum(n.begin(), n.end());
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

原因很简单，a.begin() 是迭代器，不是指针；尽管与指针相似，但是是完全不同的两个类型。

解决方法也很简单：把 T* 改为 It。使用 T* 的写法认为 T 是值类型，使用 It 的写法认为 It 是迭代器。此处建议参考 C++98 中 std::accumulate 的封装方式。参考代码如下：

template <class T, class It>
T getXorSum(It begin, It end, const T& init) {
  T ret = init;
  for (It it = begin; it != end; ++it) ret ^= *it;
  return ret;
}

使用方法则为：

1. getXorSum(a + 1, a + 1 + n, 0ull)
2. getXorSum(a, a + n, 0ull)
3. getXorSum(a.begin(), a.end(), 0ull)

或者直接使用 std::accumulate 函数：

1. std::accumulate(a + 1, a + 1 + n, 0ull, std::bit_xor<unsigned long long>{})
2. std::accumulate(a + 1, a + 1 + n, 0ull, std::bit_xor<>{})（需要 C++14，其它同理）
3. std::accumulate(a, a + n, 0ull, std::bit_xor<>{})
4. getXorSum(a.begin(), a.end(), 0ull, std::bit_xor<>{})