How to understand this result when using std::sort?

Question

I'm trying to implement a PP class. Please first help check the following imcomplete code:

template <typename E>
class PP{
public:
    struct Point2D {
        static int used_count;
        E _x;
        E _y;
        Point2D() : _x(0), _y(0) {
            used_count++;
            std::cout << "Point2D(), used_count = " << used_count << "\n";
        }
        virtual ~Point2D() {
            used_count--;
            std::cout << "~Point2D(), used_count = " << used_count << "\n";
        }
    };

    std::vector<Point2D> _points;
    int _size;

    PP(int size) : _size(size) {
        _points.resize(_size);
        std::cout << "PP(int size)\n";
    }
    PP(E points[][2], int size)
        : PP(size) {  // Nx2 points
        for (int i = 0; i < _size; i++) {
            _points[i]._x = points[i][0];
            _points[i]._y = points[i][1];
        }
        std::cout << "PP(E points[][2])\n";
    }

    virtual ~PP() {
        std::cout << "~PP()\n";
    }

    void Print(const std::string& title) {
        std::cout << title << "\n";
        for (auto iter = _points.begin(); iter != _points.end(); iter++) {
            const Point2D& p = *iter;
            std::cout << p._x << ", " << p._y << "\n";
        }
    }

    void DoSort() {
        std::sort(_points.begin(), _points.end(), [](const Point2D& l, const Point2D& r){ 
            return (l._y > r._y) || (l._y == r._y && l._x > r._x);
        });
    }
};


template<> int PP<int>::Point2D::used_count = 0;
int main() {
      int arr[][2] = {{1, 2},
                      {3, 4},
                      {5, 1},
                      {1, 5},
                      {2, 8},
                      {9, 1},
                      {6, 4},
                      {5, 6}};
      int size = sizeof(arr) / sizeof(arr[0]);

      if (1) {
          PP<int> *t = new PP<int>(arr, size);

          // test sort
          {
              t->Print("before sort");
              t->DoSort();
              t->Print("after sort");
          }

          delete t;
      }
}

The result is as follows:

  Point2D(), used_count = 1
  Point2D(), used_count = 2
  Point2D(), used_count = 3
  Point2D(), used_count = 4
  Point2D(), used_count = 5
  Point2D(), used_count = 6
  Point2D(), used_count = 7
  Point2D(), used_count = 8
  PP(int size)
  PP(E points[][2])
  before sort
  1, 2
  3, 4
  5, 1
  1, 5
  2, 8
  9, 1
  6, 4
  5, 6
  ~Point2D(), used_count = 7
  ~Point2D(), used_count = 6
  ~Point2D(), used_count = 5
  ~Point2D(), used_count = 4
  ~Point2D(), used_count = 3
  ~Point2D(), used_count = 2
  ~Point2D(), used_count = 1
  after sort
  2, 8
  5, 6
  1, 5
  6, 4
  3, 4
  1, 2
  9, 1
  5, 1
  ~PP()
  ~Point2D(), used_count = 0
  ~Point2D(), used_count = -1
  ~Point2D(), used_count = -2
  ~Point2D(), used_count = -3
  ~Point2D(), used_count = -4
  ~Point2D(), used_count = -5
  ~Point2D(), used_count = -6
  ~Point2D(), used_count = -7

My question is, in the DoSort function, I just use the reference of Point2D, what are the reasons that the destructors of Point2D are invoked in the std::sort routine? What is happened? Could you please help give some advice? Thanks in advance.

Answer 1

You are not measuring the copy constructors that are invoked. You can do that by adding:

Point2D(Point2D const & p) : _x(p._x), _y(p._y) {
     used_count++;
     std::cout << "Point2D(), used_count = " << used_count << "\n";
}

If you do that, you get the expected used_count.

Here's a demo.

The extra copies are made in the internals of std::sort where there are copies made of Point2D, when elements are swapped.

Normally std::sort would use the move functions in its internals, but the reason you see these unnecessary copies is because you have not defined move for your class. If you do that:

Point2D(Point2D&& p) : _x(p._x), _y(p._y) {
    std::cout << "Point2D(), used_count = " << used_count << "\n";
    used_count++;
}

Point2D& operator=(Point2D&&) = default;

you see that there are no copies made. However, the used_count will still osciallate between 8 and 9, in the call to std::sort. There are still the same number of temporaries that are created, but these are moved instead of copied, which is more efficient, in general. For this particular class instantiaion, there may not be much of an improvement, since it only contains 2 ints, but this is a good habit to get into. e.g. if you instantiate PP over std::string you can gain a considerable improvement in efficiency.

Here's a demo.