Counting sort using STL

I'm trying to learn to use the C++ Standard Library and some of the modern C++11 features. Can someone review my counting sort algorithm below and critique my style/algorithm/use of the STL? Thank you!

#include 
#include 
#include 
#include 
#include 
#include 

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
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 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 dist(kRangeFrom,kRangeTo);

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

  std::vector 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 (last1 - first1).count() (last2 - first2).count() << " ms" << '\n';
  std::cout << "v1 == v2: " << std::equal(v1.begin(), v1.end(), v2.begin()) << '\n';

  return 0;
}

Associative container

Update: Because of the O(n.log(n)) nature of std::map we have concluded this is not a good idea (But it was worth the test).

Rather than using a vector to store the count you can use an associative container.

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

// replace with 

using ValueType = std::iterator_traits::value_type;
std::map  counts;

• This will limit the amount of memory you use otherwise the amount of space you use could potentially exceed memory.

• Also iterating over a sparse array would be expensive (As there will be lots of zero counts). By using an associative container you only iterate over valid values.

Range based for

Use the new range based for.

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

// replace with:

for(auto const& value: counts) {

Combine range based for and associative containers

void counting_sort(InputIterator first, InputIterator last)
{
    using ValueType = std::iterator_traits::value_type;
    std::map 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);
    }
}

StackExchange Code Review Q#126705, answer score: 7