So drehen Sie einen permutierten Index

Question

Ich studiere Accelerated C++: Practical Programming by Example gerade jetzt, und ich war von der folgenden Frage fest.

#include <iostream> 
#include <vector> 
#include <cctype> 
#include <algorithm> 
using namespace std; 


vector<string> split(const string&s){ 
    vector<string> ret; 
    typedef string::size_type string_size; 
    string_size i=0; 
    while (i!=s.size()){ 
     while (i!=s.size() && isspace(s[i])){ 
      i++; 
     } 
     string_size j=i; 
     while (j!=s.size() && !isspace(s[j])){ 
      j++; 
     } 
     if (i!=j){ 
      ret.push_back(s.substr(i,j-i)); 
      i=j; 
     } 
    } 
    return ret; 
} 

void Display(vector<string> s){ 
    for (vector<string>::size_type i=0;i!=s.size();i++){ 
     cout<<s[i]<<endl; 
    } 
} 

vector<string> Rotation(string&s){ 
    string ss=s+" "+s; 
    vector<string>s1=split(s); 
    vector<string>ret; 
    ret.push_back(s); 
    string::size_type slength=s.size(); 
    string::size_type count=0; 
    for (vector<string>::size_type i=0;i!=s1.size()-1;i++){ 
     string k=s1[i]; 
     string::size_type ksize=k.size(); 
     count+=ksize+1; 
     string pushed=ss.substr(count,slength); 
     ret.push_back(pushed); 
    } 
    return ret; 
} 

string lower(const string&s){ 
    string ret; 
    for(string::size_type i=0;i!=s.size();i++){ 
     ret.push_back(tolower(s[i])); 
    } 
    return ret; 
} 

bool compare(const string& s1, const string& s2){ 
    return lower(s1)<lower(s2); 
} 

int main() { 
    string s; 
    cout<<"Enter String"<<endl; 
    vector<string> vs; 
    while (getline(cin,s)){ 
     vector<string>Rotated=Rotation(s); 
     vs.insert(vs.end(),Rotated.begin(),Rotated.end()); 
    } 
    sort(vs.begin(),vs.end(),compare); 
    Display(vs); 
    return 0; 
} 

I Schritt 1 und 2 (Drehung und Sortierung) beendet haben, aber ich hatte keine Ahnung, wie un drehen zu. Ich habe diese Frage eine Zeit lang gegoogelt, und einige Lösungen sagen, dass ich die Struktur am Anfang initialisieren sollte. Ich frage mich, ob mein aktueller Code den letzten Schritt noch lösen kann, oder ich muss alles ändern, was ich codiert habe.

Answer 1

Ich löste dieses Problem von mir nach dem Nachdenken für eine Weile. Unten ist mein Code. Gibt es eine Möglichkeit, meinen Algorithmus zu verbessern, obwohl ich bereits das Gefühl habe, dass es gut ist?

#include <iostream> 
#include <vector> 
#include <cctype> 
#include <algorithm> 
using namespace std; 

struct Input{ 
    string word; 
    int interpoint; 
}; 

vector<string> split(const string&s){ 
    vector<string> ret; 
    typedef string::size_type string_size; 
    string_size i=0; 
    while (i!=s.size()){ 
     while (i!=s.size() && isspace(s[i])){ 
      i++; 
     } 
     string_size j=i; 
     while (j!=s.size() && !isspace(s[j])){ 
      j++; 
     } 
     if (i!=j){ 
      ret.push_back(s.substr(i,j-i)); 
      i=j; 
     } 
    } 
    return ret; 
} 

string joinstring(vector<string>&vs){ 
    string result; 
    for (vector<string>::size_type i=0;i!=vs.size();i++){ 
     if (i==vs.size()-1) 
      result+=vs[i]; 
     else 
      result+=vs[i]+" "; 
    } 
    return result; 
} 

vector<Input> Rotation(const string& s){ 
    vector<Input> Rotated; 
    vector<string> splited=split(s); 
    vector<string>::size_type splitsize=splited.size(); 
    for (vector<string>::size_type i=0;i!=splitsize;i++){ 
     Input OneRotated; 
     vector<string> splited=split(s); 
     rotate(splited.begin(),splited.begin()+i,splited.end()); 
     OneRotated.interpoint=splitsize-i; 
     OneRotated.word=joinstring(splited); 
     Rotated.push_back(OneRotated); 
    } 
    return Rotated; 
} 


void Display(vector<string> s){ 
    for (vector<string>::size_type i=0;i!=s.size();i++){ 
     cout<<s[i]<<endl; 
    } 
} 

string lower(const string&s){ 
    string ret; 
    for(string::size_type i=0;i!=s.size();i++){ 
     ret.push_back(tolower(s[i])); 
    } 
    return ret; 
} 

bool compare(Input& s1, Input& s2){ 
    return lower(s1.word)<lower(s2.word); 
} 

vector<string> Unrotate(vector<Input>& Total, vector<string>& Left){ 
    vector<string>Right; 
    for(vector<Input>::size_type i=0;i!=Total.size();i++){ 
     vector<string>splited=split(Total[i].word); 
     int spoint=Total[i].interpoint; 
     vector<string>TheLeft(splited.begin()+spoint,splited.end()); 
     vector<string>TheRight(splited.begin(),splited.begin()+spoint); 
     Left.push_back(joinstring(TheLeft)); 
     Right.push_back(joinstring(TheRight)); 
    } 
    return Right; 
} 

vector<string> reconstruct(vector<string>&s){ 
    string::size_type maxlen=0; 
    for (vector<string>::size_type i=0;i!=s.size();i++){ 
     maxlen=max(maxlen,s[i].size()); 
    } 
    vector<string>ret; 
    for (vector<string>::size_type j=0;j!=s.size();j++){ 
     ret.push_back(string(maxlen-s[j].size(),' ')+s[j]); 
    } 
    return ret; 
} 


vector<string>hcat(const vector<string>& left, const vector<string>& right) 
{ 
    vector<string> ret; 
    vector<string>::size_type i = 0, j = 0; 
    while (i != left.size() || j != right.size()) { 

     string s; 
     // copy a row from the left-hand side, if there is one 
     if (i != left.size()) 
      s = left[i++]; 


     if (j != right.size()) 
      s += " "+right[j++]; 

     ret.push_back(s); 
    } 
    return ret; 
} 

int main() { 
    string s; 
    cout << "Enter String" <<endl; 
    vector<Input> vs; 
    while (getline(cin, s)) { 
     vector<Input> Rotated=Rotation(s); 
     vs.insert(vs.end(),Rotated.begin(),Rotated.end()); 
    } 
    sort(vs.begin(),vs.end(),compare); 
    vector<string> LeftBlock; 
    vector<string> RightBlock = Unrotate(vs,LeftBlock); 
    Display(hcat(reconstruct(LeftBlock),RightBlock)); 

    return 0; 
}