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. quatratische Laufzeit und ist unbrauchbar fuer grosse Datenmengen.
Ich 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ören.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
void rearrange_vector(const vector<int> indices, vector<string> &v) {
for(int idx1=0; idx1 < v.size(); ++idx1) {
int idx2 = indices[idx1];
// nur dann tauschen, wenn nicht schonmal getauscht wurde,
// und wenn ein tausch ueberhaupt notwenig ist
if(idx2 > idx1) {
swap(v[idx1], v[idx2]);
}
}
}
int main() {
// 1. Problem space
vector<string> firstnames = {"Dennis", "Alexander", "Bjarne", "James", "James" };
vector<string> lastnames = {"Ritchie", "Stepanov", "Stroustrup", "Coplien", "Gosling" };
// 2. vector of indices - sorted according to the order of firstnames
vector<int> indices(firstnames.size());
// create sequenz 0,1,2,3,...
iota(begin(indices), end(indices), 0);
sort(begin(indices), end(indices), [&](int i1, int i2) {
return firstnames[i1] < firstnames[i2];
});
// debug
cout << "Sorted indices\n";
for(auto i : indices) {
cout << i << " ";
}
cout << "\n";
// 3. rearrangement according to the sorted indices
rearrange_vector(indices, firstnames);
rearrange_vector(indices, lastnames);
// 4. print results
for (size_t i=0; i < indices.size(); ++i) {
cout << firstnames[i] << " " << lastnames[i] << endl;
}
return 0;
}
[1] http://stackoverflow.com/questions/25085015/how-do-i-sort-two-vectors-containing-relative-entries-using-stl