使用STL计数排序

Question

我正在努力学习如何使用C++标准库和一些现代的C++11特性。有人能在下面回顾我的计数排序算法并批评我的风格/算法/ STL的使用吗？谢谢!

#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

const int kSize = 100000000;      // Size of container to sort
const int kRangeFrom = -1000000;  // first of range for random number generator
const int kRangeTo = 1000000;     // last of range for random number generator

// Linear time sorting algorithm for integers
template<typename InputIterator>
void counting_sort(InputIterator first, InputIterator last) {
  auto minmax_el = std::minmax_element(first, last);
  auto min = *minmax_el.first;
  auto max = *minmax_el.second;
  std::vector<std::size_t> counts(max - min + 1, 0);

  std::for_each(first, last, [&](auto x) { 
    ++counts[x - min];  // Store value counts
  }); 

  for (auto it_c = counts.begin(); it_c != counts.end(); ++it_c) { 
    auto idx = std::distance(counts.begin(), it_c);
    std::fill_n(first, *it_c, idx + min); // Store in sorted order
    std::advance(first, *it_c);
  }
}

int main() {
  std::random_device rd;
  std::mt19937 mt(rd());
  std::uniform_int_distribution<int> dist(kRangeFrom,kRangeTo);

  std::vector<int> v1(kSize);
  std::generate(v1.begin(), v1.end(), [&](){ return dist(mt); });

  std::vector<int> v2(kSize);
  std::copy(v1.begin(), v1.end(), v2.begin());

  auto first1 = std::chrono::steady_clock::now();
  counting_sort(v1.begin(), v1.end());
  auto last1 = std::chrono::steady_clock::now();

  auto first2 = std::chrono::steady_clock::now();
  std::sort(v2.begin(), v2.end());
  auto last2 = std::chrono::steady_clock::now();

  std::cout << "counting sort time: " << std::chrono::duration<double, std::milli>(last1 - first1).count() << " ms" << '\n';
  std::cout << "std::sort time: " << std::chrono::duration<double, std::milli>(last2 - first2).count() << " ms" << '\n';
  std::cout << "v1 == v2: " << std::equal(v1.begin(), v1.end(), v2.begin()) << '\n';

  return 0;
}

Answer 1

关联容器

更新:由于std::map的O(n.log(n))性质，我们已经得出结论，这不是一个好主意(但值得进行测试)。

与使用向量存储计数不同，您可以使用关联容器。

std::vector<std::size_t> counts(max - min + 1, 0);

// replace with 

using ValueType = std::iterator_traits<InputIterator>::value_type;
std::map<ValueType, std::size_t>  counts;

1. 这将限制您使用的内存量，否则您使用的空间可能会超过内存。
2. 此外，在稀疏数组上迭代可能会花费很大的代价(因为会有大量的零计数)。通过使用关联容器，您只能对有效值进行迭代。

基于

范围的

使用新的范围。

for (auto it_c = counts.begin(); it_c != counts.end(); ++it_c) {

// replace with:

for(auto const& value: counts) {

基于

和关联容器

的组合范围

void counting_sort(InputIterator first, InputIterator last)
{
    using ValueType = std::iterator_traits<InputIterator>::value_type;
    std::map<ValueType, std::size_t> counts;

    for(auto value: boost::make_iterator_range(first, last)) { 
        ++counts[value];
    }

    for(auto count: counts) {
        ValueType&   value = count.first;
        std::size_t& size  = count.second;  
        std::fill_n(first, size, value);
        std::advance(first, size);
    }
}