Wen hat es nicht schon einmal gest\u00f6rt, dass std::sort() so transparent arbeitet? Manchmal muss man wissen welche Elemente beim Sortieren wohin verschoben werden. Sozusagen eine Permutation.
\nManchmal ist es m\u00f6glich, den zu sortierenden Daten eine ID mitzugeben. Aber oft nicht. Zum Beispiel arbeite ich mit 2D Punkten. Diese liegen nat\u00fcrlich sch\u00f6n dicht gepackt im std::vector, und die ID ist implizit durch die Position im vector gegeben. Durch das Sortieren w\u00fcrde sich auch die ID \u00e4ndern, was aber nicht geht, da sie mit andern Daten noch verkn\u00fcpft 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 \u00e4ndert sich zu meinen Ungunsten.<\/p>\n
Zumindest in meinem Anwendungsfall brauche ich die sortierten Daten auch nur kurzzeitig, und die original Daten sollen unver\u00e4ndert bleiben. Es w\u00fcrde teilweise auch vollkommen langen, wenn die sort Funktion nur ein vector Mein erster Ansatz ist, eine sort() Funktion zu schreiben, welche als zus\u00e4tzliches 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 \u00e4ndert. 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.<\/p>\n Hier der Code der ersten Implementierung:<\/p>\n Swap idx 0 with idx 3 Wen hat es nicht schon einmal gest\u00f6rt, dass std::sort() so transparent arbeitet? Manchmal muss man wissen welche Elemente beim Sortieren wohin verschoben werden. Sozusagen eine Permutation. Manchmal ist es m\u00f6glich, den zu sortierenden Daten eine ID mitzugeben. Aber oft nicht. Zum Beispiel arbeite ich mit 2D Punkten. Diese liegen nat\u00fcrlich sch\u00f6n dicht gepackt im std::vector, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-3390","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3390","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3390"}],"version-history":[{"count":4,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3390\/revisions"}],"predecessor-version":[{"id":3394,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3390\/revisions\/3394"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3390"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3390"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3390"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nUm eine ID zu erhalten, werte ich die Adresse der Elemente im std::vector aus. Damit die original Daten (erst einmal) in ihrer urspr\u00fcnglichen 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.<\/p>\n\r\ntemplate<typename T, typename Allocator, typename Visitor>\r\ninline void sort(std::vector<T,Allocator>& data, Visitor&& vis) {\r\n std::vector<std::reference_wrapper<const T>> sorted;\r\n sorted.reserve(data.size());\r\n for(const auto& x : data) {\r\n sorted.push_back(std::cref(x));\r\n }\r\n\r\n std::sort(sorted.begin(), sorted.end());\r\n \/\/ ptrdiff_t is the signed equivalent to size_t\r\n for(size_t i=0; i < sorted.size(); ++i) {\r\n \/\/ get the address of an item in data, not sorted.\r\n const size_t idx1 = std::addressof(sorted[i].get()) - data.data();\r\n if(i < idx1) {\r\n std::swap(data[i], data[idx1]);\r\n vis(i, idx1);\r\n }\r\n }\r\n}\r\n\r\n\/\/\/\/\/\/\r\n\r\n struct Visitor {\r\n void operator()(size_t i, size_t j) {\r\n std::cout << "Swap idx " << i << " with idx " << j << "\\n";\r\n }\r\n };\r\n\r\n std::vector<int> v {3,2,1,0};\r\n cpl::sort(v, Visitor());\r\n QVERIFY(std::is_sorted(v.begin(), v.end()));\r\n<\/pre>\n
\nSwap idx 1 with idx 2<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"