How do I sort two vectors containing relative entries, using STL? [1]<\/p>\n
Da ich mir kein Account auf stackoverflow machen konnte, (ka. warum es passierte einfach nichts), gibt es jetzt hier die richtige Antwort.
\nDer Ansatz von Nikos Athanasiou war schon richtig, leider total krank programmiert und mit zu vielen Schleifen. So hat der Algo. quatratische Laufzeit und ist unbrauchbar fuer grosse Datenmengen.
\nIch uebernehme seinen Ansatz und tausche nur die Funktion rearrange_vector() aus. So ergibt sich eine linear-logaritmische Laufzeit dominiert durch die Sortierung. Und einen linearen Speicherverbrauch. Da aber nur integer indices gespeichert werden, ist der Zusatzverbraucht sehr gering. Gerade einmal 4byte pro Namen. Also ca. 4MB pro eine Millionen Namen. Das sollte nun wirklich niemand st\u00f6ren.<\/p>\n
\r\n#include <iostream>\r\n#include <vector>\r\n#include <string>\r\n#include <algorithm>\r\n#include <numeric>\r\n\r\nusing namespace std;\r\n\r\nvoid rearrange_vector(const vector<int> indices, vector<string> &v) {\r\n for(int idx1=0; idx1 < v.size(); ++idx1) {\r\n int idx2 = indices[idx1];\r\n \/\/ nur dann tauschen, wenn nicht schonmal getauscht wurde,\r\n \/\/ und wenn ein tausch ueberhaupt notwenig ist\r\n if(idx2 > idx1) {\r\n swap(v[idx1], v[idx2]);\r\n }\r\n }\r\n}\r\n\r\nint main() {\r\n \/\/ 1. Problem space\r\n vector<string> firstnames = {\"Dennis\", \"Alexander\", \"Bjarne\", \"James\", \"James\" };\r\n vector<string> lastnames = {\"Ritchie\", \"Stepanov\", \"Stroustrup\", \"Coplien\", \"Gosling\" };\r\n\r\n \/\/ 2. vector of indices - sorted according to the order of firstnames\r\n vector<int> indices(firstnames.size());\r\n \/\/ create sequenz 0,1,2,3,...\r\n iota(begin(indices), end(indices), 0);\r\n\r\n sort(begin(indices), end(indices), [&](int i1, int i2) {\r\n return firstnames[i1] < firstnames[i2];\r\n });\r\n\r\n \/\/ debug\r\n cout << \"Sorted indices\\n\";\r\n for(auto i : indices) {\r\n cout << i << \" \";\r\n }\r\n cout << \"\\n\";\r\n\r\n \/\/ 3. rearrangement according to the sorted indices\r\n rearrange_vector(indices, firstnames);\r\n rearrange_vector(indices, lastnames);\r\n\r\n \/\/ 4. print results\r\n for (size_t i=0; i < indices.size(); ++i) {\r\n cout << firstnames[i] << \" \" << lastnames[i] << endl;\r\n }\r\n\r\n return 0;\r\n}\r\n<\/code><\/pre>\n[1] http:\/\/stackoverflow.com\/questions\/25085015\/how-do-i-sort-two-vectors-containing-relative-entries-using-stl<\/p>\n","protected":false},"excerpt":{"rendered":"
How do I sort two vectors containing relative entries, using STL? [1] Da ich mir kein Account auf stackoverflow machen konnte, (ka. warum es passierte einfach nichts), gibt es jetzt hier die richtige Antwort. Der Ansatz von Nikos Athanasiou war schon richtig, leider total krank programmiert und mit zu vielen Schleifen. So hat der Algo. […]<\/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-2656","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\/2656","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=2656"}],"version-history":[{"count":8,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2656\/revisions"}],"predecessor-version":[{"id":2667,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2656\/revisions\/2667"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2656"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2656"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2656"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}