Counting swaps using std::sort

Question

Is there a portable, minimal-overhead way to count the number of swap operations performed during a std::sort in C++? I would like to do this because I need to compute the sign of the permutation used to sort the list, and I was wondering if there was a way to reuse std::sort for this rather than writing my own sorting function.

Does this answer your question? [std::sort does not always call std::swap](https://stackoverflow.com/questions/14212701/stdsort-does-not-always-call-stdswap) — Eugene, Oct 21 '20 at 00:50
@Eugene I didn't think that it did, but I am fairly new to C++ and don't know if there is some other way to achieve this swap-counting. — Joppy, Oct 21 '20 at 01:00
The "portable" is the kicker. Unfortunately `std::swap` requires the type to be move constructible. Otherwise you could write a wrapper that simply denies any move trickery. — bitmask, Oct 21 '20 at 01:08
You could count the number of copy/move contructions occur for a custom type. — NathanOliver, Oct 21 '20 at 01:24

score 2 · Answer 1 · answered Oct 21 '20 at 01:30

I tried to answer real quick by making a wrapper/ custom type to overload std::swap...and then ran into the fact that for super small vectors swap isn't called...following the link in the comments so attempt 2 added a counter for the move_constructor.

I can't say this is a minimal overhead solution and you're probably better off writing your own sorting function if you need the exact number of swap operations.

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

struct A{
  static int swap_count;
  static int move_constructor_count;
  int a;
  A(int _a): a(_a) {}
  bool operator<(const A& other) const{
    return this->a < other.a;
  }
  A(const A&other): a(other.a) {move_constructor_count++;}
};
int A::swap_count = 0;
int A::move_constructor_count = 0;

namespace std{
    template<>
    void swap(A& lhs, A& rhs) {
       A::swap_count++;
       std::swap(lhs.a, rhs.a);
    }
}


int main() {
  std::default_random_engine gen;
  std::uniform_int_distribution<int> dis(1,100);

  std::vector<A> test;
  for(int _=0;_<10;_++) test.emplace_back(dis(gen)); //fill a vector randomly

  A::move_constructor_count = 0; // emplace calls move constructor
  std::sort(test.begin(), test.end());
  std::cout << "after sort1: swap count:" << A::swap_count << " move count: " << A::move_constructor_count << std::endl;


  // arbitrary way to fill a large test vector
  std::vector<A> test2;
  for(int _=0;_<1000;_++) test2.emplace_back(dis(gen)); //fill a vector randomly
    
  A::move_constructor_count = 0;
  A::swap_count = 0;
  std::sort(test2.begin(), test2.end());
  std::cout << "after sort2: swap count:" << A::swap_count << " move count: " << A::move_constructor_count << std::endl;

}

gave me

after sort1: swap count:0 move count: 9
after sort2: swap count:1806 move count: 999

Thanks for having a crack at it, I ended up writing my own heap-sort and just counting swaps in the end. The other thing I thought about was converting the array to an array of pairs `(a[i], i)` and then sorting, which leaves the permutation used in the second factor. But then you need even more code for cycle finding and counting... — Joppy, Oct 21 '20 at 09:28

Counting swaps using std::sort

1 Answers1