Most efficient way to implement list compression

#1

What is the most efficient code to implement list compression.

E.g.,
{ 1, 5, 7, 3, 2 } → { 0, 3, 4, 2, 1 }

{ 43, 76, 76, 10 } → { 1, 2, 2, 0 }

(Order is preserved)

#2
#3

Here’s my implementation (different from the one on the guide).

This one also runs in \mathcal O(N\log N) but it’s generally more efficient because it uses sorting which is optimized (?)
My implementation directly modifies the values.

template<class T> struct Compress {
	T *cc[MAXN]; int ci = 0;

	void insert(T& x) {
		cc[ci++] = &x;
	}

	void compress() {
		sort(cc, cc + ci, [](T *i, T *j) { return *i < *j; });
		T pp = *cc[0]; *cc[0] = 1;
		for (int i = 1; i < ci; ++i)
			if (*cc[i] == pp) *cc[i] = *cc[i - 1];
			else pp = *cc[i], *cc[i] = *cc[i - 1] + 1;
	};
};
#4

Sorry, I should have specified more. I want it to receive a vector, and return a modified vector. Just a function.

#5 
#include <bits/stdc++.h>
using namespace std;

template<class T> struct Compress {
	vector<T*> cc;

	void insert(T& x) { cc.push_back(&x); }
	void compress() {
		sort(cc.begin(), cc.end(), [](T *i, T *j) { return *i < *j; });
		T pp = *cc[0]; *cc[0] = 0;
		for (int i = 1; i < (int) cc.size(); ++i)
			if (*cc[i] == pp) *cc[i] = *cc[i - 1];
			else pp = *cc[i], *cc[i] = *cc[i - 1] + 1;
	};
};

template<class T> vector<T> compressVector(const vector<T>& v) {
	Compress<T> cc;
	vector<T> ret(v.begin(), v.end());
	for (T& x : ret)
		cc.insert(x);
	cc.compress();
	return ret;
}

int main() {
	vector<int> a = {1, 5, 7, 3, 2 };
	vector<int> b = compressVector<int>(a);
	for (int& x : b) cout << x << ' ';
	cout << '\n';
}