Wen hat es nicht schon einmal gestört, dass std::sort() so transparent arbeitet? Manchmal muss man wissen welche Elemente beim Sortieren wohin verschoben werden. Sozusagen eine Permutation.
Manchmal ist es möglich, den zu sortierenden Daten eine ID mitzugeben. Aber oft nicht. Zum Beispiel arbeite ich mit 2D Punkten. Diese liegen natürlich schön dicht gepackt im std::vector, und die ID ist implizit durch die Position im vector gegeben. Durch das Sortieren würde sich auch die ID ändern, was aber nicht geht, da sie mit andern Daten noch verknüpft ist. Und die ID explicit abspeichern ist auch nicht gut, da dann die x/y Koordinaten vom Punkt im Speicher nicht mehr optimal ausgerichtet sind. Das Speicherlayout ändert sich zu meinen Ungunsten.
Zumindest in meinem Anwendungsfall brauche ich die sortierten Daten auch nur kurzzeitig, und die original Daten sollen unverändert bleiben. Es würde teilweise auch vollkommen langen, wenn die sort Funktion nur ein vector
Mein erster Ansatz ist, eine sort() Funktion zu schreiben, welche als zusätzliches Argument einen Visitor akzeptiert. Diese Funktion ruft die eigentlich std::sort() Funktion auf, so dass alles vom Standard noch eingehalten wird und sich auch nichts an der asymptotischen Laufzeit ändert.
Um eine ID zu erhalten, werte ich die Adresse der Elemente im std::vector aus. Damit die original Daten (erst einmal) in ihrer ursprünglichen Reihenfolge bleiben, wird ein zweiter std::vector mit Referenz Wrappern erstellt. Dies kostet pro Element den Speicherplatz einer Referenz, also 8byte. Dies ist, denke ich, nie ein Problem.
Nach der eigentlichen Sortierung mit std::sort ist so feststellbar, wie die Elemente im vector getauscht wurden. Damit wird das Visitor Objekt aufgerufen, so dass der Anweder den Permutationsvektor erstellen kann. Und die eigentlichen Daten werden durch swap sortiert.
Hier der Code der ersten Implementierung:
template<typename T, typename Allocator, typename Visitor>
inline void sort(std::vector<T,Allocator>& data, Visitor&& vis) {
std::vector<std::reference_wrapper<const T>> sorted;
sorted.reserve(data.size());
for(const auto& x : data) {
sorted.push_back(std::cref(x));
}
std::sort(sorted.begin(), sorted.end());
// ptrdiff_t is the signed equivalent to size_t
for(size_t i=0; i < sorted.size(); ++i) {
// get the address of an item in data, not sorted.
const size_t idx1 = std::addressof(sorted[i].get()) - data.data();
if(i < idx1) {
std::swap(data[i], data[idx1]);
vis(i, idx1);
}
}
}
//////
struct Visitor {
void operator()(size_t i, size_t j) {
std::cout << "Swap idx " << i << " with idx " << j << "\n";
}
};
std::vector<int> v {3,2,1,0};
cpl::sort(v, Visitor());
QVERIFY(std::is_sorted(v.begin(), v.end()));
Swap idx 0 with idx 3
Swap idx 1 with idx 2