Benchmark - Keep only duplicated values

// https://stackoverflow.com/questions/58498959/keep-the-duplicated-values-only-vectors-c

#include <benchmark/benchmark.h>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <random>

template <typename InputIt, typename OutputIt>
OutputIt copy_duplicates(
        InputIt  first,
        InputIt  last,
        OutputIt d_first) {
    std::unordered_map<typename std::iterator_traits<InputIt>::value_type,
                       std::size_t> seen;
    for ( ; first != last; ++first) {
        if ( 2 == ++seen[*first] ) {
            // only output on the second time of seeing a value
            *d_first = *first;
            ++d_first;
        }
    }
    return d_first;
}

template<typename T>
auto erase_unique_and_duplicates(std::vector<T>& v)
{
  auto first{v.begin()};
  std::sort(first, v.end());
  while (first != v.end())
  {
    auto n{std::count(first, v.end(), *first)};
    if (n > 1)
    {
      first = v.erase(first + 1, first + n);
    }
    else
    {
      first = v.erase(first);
    }
  }
  return v.end();
}

template <typename T>
void only_distinct_duplicates(::std::vector<T> &v)
{
    ::std::sort(v.begin(), v.end());
    auto output = v.begin();
    auto test = v.begin();
    auto run_start = v.begin();
    auto const end = v.end();
    for (auto test = v.begin(); test != end; ++test) {
       if (*test != *run_start) {
           if ((test - run_start) > 1) {
              ::std::swap(*output, *run_start);
              ++output;
           }
           run_start = test;
       }
    }
    if ((end - run_start) > 1) {
        ::std::swap(*output, *run_start);
        ++output;
    }
    v.erase(output, end);
}


constexpr unsigned long long seed = 500;


::std::vector<int>
make_random_list(::std::vector<int>::size_type length,
                 unsigned int load_factor = 10)
{
   using ::std::mt19937;
   using ::std::vector;
   using ::std::uniform_int_distribution;
   mt19937 gen(seed);
   uniform_int_distribution<> dis(0, (length + 9) / load_factor);
   vector<int> output;
   output.reserve(length);
   while (length--) {
      output.push_back(dis(gen));
   }
   return output;
}


static void CopyDuplicates(benchmark::State& state)
{
   using vecint = ::std::vector<int>;
   state.PauseTiming();
   vecint v = make_random_list(state.range(0));
   state.ResumeTiming();
   for (auto _ : state) {
      std::vector<int> w;
      // Make sure the variable is not optimized away by compiler
      benchmark::DoNotOptimize(copy_duplicates(v.begin(), v.end(), std::back_inserter(w)));
   }
  state.SetComplexityN(state.range(0));
}
// Register the function as a benchmark
BENCHMARK(CopyDuplicates)
->RangeMultiplier(2)->Range(1<<6, 1<<28)->Complexity()->Unit(benchmark::kMillisecond);

static void Erase(benchmark::State& state)
{
   using vecint = ::std::vector<int>;
   // Code before the loop is not measured
   for (auto _ : state) {
      state.PauseTiming();
      vecint v = make_random_list(state.range(0));
      state.ResumeTiming();
      benchmark::DoNotOptimize(v);
      benchmark::DoNotOptimize(erase_unique_and_duplicates(v));
   }
  state.SetComplexityN(state.range(0));
}
BENCHMARK(Erase)
->RangeMultiplier(4)->Range(1<<6, 1<<20)->Complexity()->Unit(benchmark::kMillisecond);

static void Only(benchmark::State& state)
{
   using vecint = ::std::vector<int>;
   // Code before the loop is not measured
   for (auto _ : state) {
      state.PauseTiming();
      vecint v = make_random_list(state.range(0));
      state.ResumeTiming();
      benchmark::DoNotOptimize(v);
      only_distinct_duplicates(v);
      benchmark::DoNotOptimize(v);
   }
  state.SetComplexityN(state.range(0));
}
BENCHMARK(Only)
->RangeMultiplier(4)->Range(1<<6, 1<<28)->Complexity()->Unit(benchmark::kMillisecond);

/*
2019-10-22 12:55:21
Running /tmp/the_above_benchmark
Run on (8 X 3900 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
----------------------------------------------------------------
Benchmark                         Time           CPU Iterations
----------------------------------------------------------------
CopyDuplicates/64         345022038 ms          2 ms          1
CopyDuplicates/128        345022038 ms          2 ms          1
CopyDuplicates/256        345022038 ms          2 ms          1
CopyDuplicates/512        345022038 ms          2 ms          1
CopyDuplicates/1024       345022038 ms          2 ms          1
CopyDuplicates/2048       345022039 ms          2 ms          1
CopyDuplicates/4096       345022039 ms          3 ms          1
CopyDuplicates/8192       345022039 ms          3 ms          1
CopyDuplicates/16384      345022039 ms          3 ms          1
CopyDuplicates/32768      345022041 ms          4 ms          1
CopyDuplicates/65536      345022043 ms          6 ms          1
CopyDuplicates/131072     345022047 ms         11 ms          1
CopyDuplicates/262144     345022056 ms         20 ms          1
CopyDuplicates/524288     345022074 ms         38 ms          1
CopyDuplicates/1048576    345022113 ms         77 ms          1
CopyDuplicates/2097152    345022228 ms        192 ms          1
CopyDuplicates/4194304    345022707 ms        669 ms          1
CopyDuplicates/8388608    345024159 ms       2117 ms          1
CopyDuplicates/16777216   345027644 ms       5593 ms          1
CopyDuplicates/33554432   345035493 ms      13421 ms          1
CopyDuplicates/67108864   345051995 ms      29876 ms          1
CopyDuplicates/134217728  345086343 ms      64134 ms          1
CopyDuplicates/268435456  345160770 ms     138364 ms          1
CopyDuplicates_BigO        67984.94 NlgN      18.19 NlgN
CopyDuplicates_RMS               94 %          8 %
Erase/64                          0 ms          0 ms     785419
Erase/256                         0 ms          0 ms     236024
Erase/1024                        0 ms          0 ms      27632
Erase/4096                        0 ms          0 ms       2273
Erase/16384                       3 ms          3 ms        205
Erase/65536                      51 ms         51 ms         14
Erase/262144                    862 ms        860 ms          1
Erase/1048576                 14403 ms      14365 ms          1
Erase_BigO                     0.01 N^2       0.01 N^2
Erase_RMS                         1 %          1 %
Only/64                           0 ms          0 ms     823730
Only/256                          0 ms          0 ms     310661
Only/1024                         0 ms          0 ms      46385
Only/4096                         0 ms          0 ms       4439
Only/16384                        1 ms          1 ms        906
Only/65536                        3 ms          3 ms        205
Only/262144                      16 ms         16 ms         44
Only/1048576                     69 ms         69 ms         10
Only/4194304                    310 ms        310 ms          2
Only/16777216                  1363 ms       1360 ms          1
Only/67108864                  5775 ms       5760 ms          1
Only/268435456                25268 ms      25205 ms          1
Only_BigO                      3.36 NlgN       3.35 NlgN
Only_RMS                          1 %          1 %
*/