带有来自模板化容器的迭代器的 C++ 函数

Question

我正在尝试编写一个基本的桶排序。我有一个函数接受 vector 的开始和结束迭代器。我需要将 vector 的 value_type 模板化，以便我可以使用它来创建用于排序的存储桶 vector (使用 std::numeric_limits)。该函数适用于不大于短整型的 T。

这是我写的函数:

template<typename T>
typename std::vector<T>::iterator forwardIterator;
void bucketSort(forwardIterator begin, forwardIterator end) {
  std::vector<unsigned> bucketVec(std::numeric_limits<T>::max() + 1, 0);
  for (auto it = begin; it != end; it++)
    bucketVec[*it]++;
  auto it = begin;
  for (unsigned j = 0; j < bucketVec.size(); j++)
    for (unsigned k = 0; k < bucketVec[j]; k++)
      *it++ = j;
}

当我尝试使用 g++ 和 -std=c++11, -O3 标志编译它时，我收到以下错误消息:

bucketSort.cpp:14:17: error: variable or field 'bucketSort' declared void
bucketSort.cpp:14:17: error: 'forwardIterator' was not declared in this scope
bucketSort.cpp:14:40: error: 'forwardIterator' was not declared in this scope
bucketSort.cpp: in function 'int main()':
bucketSort.cpp:55:46: error: 'bucketSort' was not declared in this scope

我不明白我做错了什么以及如何解决这个问题以使其正常工作。

Answer 1

std::iterator_traits 可以帮助您确定给定迭代器类型的值类型。

template<typename forwardIterator>
void bucketSort(forwardIterator begin, forwardIterator end) {
  using T = typename std::iterator_traits<forwardIterator>::value_type;
  std::vector<unsigned> bucketVec(std::numeric_limits<T>::max() + 1, 0);
  for (auto it = begin; it != end; it++)
    bucketVec[*it]++;
  auto it = begin;
  for (unsigned j = 0; j < bucketVec.size(); j++)
    for (unsigned k = 0; k < bucketVec[j]; k++)
      *it++ = j;
}