Sortierung eines std::vector<T>'s, ohne diesen zu ändern

Hallo an alle,

ich möchte einen std::vector<T> (am liebsten als Template) sortieren, ohne diesen zu verändern. Dazu habe ich mir überlegt, dass ich einfach einen zweiten Vektor mit Indizes anlege, damit auf den 1. zugreife und somit nur die Reihenfolge des 2. "Indexvektors" anpassen muss, also in etwa: v_const[v_idx[i]] .
Gibt es eine schnelle Möglichkeit, dass mit der STL zu erledigen? std::sort kann ich dafür nicht verwenden, oder?

(Anm.: Da der Inhalt des zu sortierenden Vektors beliebig sein soll, möchte ich bei der Sortierung auch eine Vergleichsfunktion angeben können, so wie auch bei std::sort .)

Danke für euche Hilfe!

Grüße
Sorter

volkard

Als Anregung, kann jetzt nicht ordentlich pr0ggern, muss Stargate gucken.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

template<typename T,typename LESS=std::less<T>>
struct IndexedComparator{
    std::vector<T>& vec;
    LESS less;
    IndexedComparator(std::vector<T>& vec,LESS less=LESS())
    :vec(vec),less(less){
    }
    bool operator()(size_t a,size_t b){
        return less(vec[a],vec[b]);
    }
};

int main() {
    using namespace std;
    vector<string> vec;
    vec.push_back("for");
    vec.push_back("if");
    vec.push_back("do");
    vec.push_back("while");

    vector<size_t> ivec;
    for(size_t i=0;i<vec.size();++i)
        ivec.push_back(i);

    sort(ivec.begin(),ivec.end(),IndexedComparator<string>(vec));

    for(vector<size_t>::iterator i=ivec.begin();i!=ivec.end();++i)
        cout<<vec[*i]<<'\n';
    cout<<'\n';

    sort(ivec.begin(),ivec.end(),IndexedComparator<string,std::greater<string>>(vec));

    for(vector<size_t>::iterator i=ivec.begin();i!=ivec.end();++i)
        cout<<vec[*i]<<'\n';
    cout<<'\n';
}

ipsec

Wenn der sortierte Vector anschießend unabhängig vom Originalvektor sein soll, kannst du letzteren auch einfach kopieren und die Kopie sortieren.

krümelkacker

volkard schrieb:

...

Schön!
Ich hätte sonst noch statt der Vektor-Referenz einen RandomAccess-Iterator genommen.

also

template<
  class RandAccIter,
  class Less = std::less<
                 typename std::iterator_traits<RandAccIter>::value_type
               >
>
struct index_less {
  typedef typename std::iterator_traits<RandAccIter>::difference_type idx_type;
  RandAccIter beg_;
  Less less_;
  ...
  bool operator()(idx_type a, idx_type b) const {
    return less_(beg_[a],beg_[b]);
  }
};

(oder so ähnlich)

Drehleiter

Vieleicht willst Du ja auch statt eiens Vectors eientlic sowas wie ein boost::multi_index?

Gruß

Sortierung eines std::vector&lt;T&gt;'s, ohne diesen zu ändern

Sortierung eines std::vector<T>'s, ohne diesen zu ändern