3. sortieren einer datenstruktur mit mehreren sortier-kriterien

sortieren einer datenstruktur mit mehreren sortier-kriterien

  • ?

    hallo!
    Ich habe ein kleines Problem!
    Ich habe eine Tabelle (vector) von Daten-Objekten die ich anhand mehrerer Sortier-Kriterien mit der STL stable_sort-Methode sortieren möchte.

    Ich habe dazu mal folgendes gemacht:

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

// ausgabe der aktuellen vergleichsoperation
void printCompare(const DataObject& next, const DataObject& current, Sort* sort)
{
    cout << "compare '";
    next.print();
    cout << "' to '";
    current.print();
    cout << "'";
    if( sort != NULL && !sort->order_.empty() )
    {
        cout << " using ";
        for( vector<pair<string, bool> >::iterator it = sort->order_.begin(); it != sort->order_.end(); it++ )
            cout << (*it).first << " " << ((*it).second ? "(asc)" : "(desc)") << " ";
    }
    cout << endl;
}

void printIsLess(const DataObject& next, const DataObject& current)
{
    cout << "'";
    next.print();
    cout << "' is less or equal to '";
    current.print();
    cout << "'" << endl;
}

class DataObject
{
    public:
        DataObject(const string& m1, const string& m2, const string& m3) : m1_(m1), m2_(m2), m3_(m3) {}
        ~DataObject() {}

        const string& m1() const { return m1_; }
        void m1(const string& m1) { m1_ = m1; }

        const string& m2() const { return m2_; }
        void m2(const string& m2) { m2_ = m2; }

        const string& m3() const { return m3_; }
        void m3(const string& m3) { m3_ = m3; }

    public:
        void print() const { cout << m1_ << " " << m2_ << " " << m3_; }

    private:
        string m1_;
        string m2_;
        string m3_;
};

class DataCollection : public vector<DataObject>
{
    public:
        DataCollection() {}
        virtual ~DataCollection() {}

    public:
        void sort(Sort* sort)
        {
            if( sort != NULL && !sort->order_.empty() )
            {
                DataSort ds(sort);
                std::stable_sort(begin(), end(), ds);
            }
        }

    public:
        void print() const
        {
            for( const_iterator it=begin(); it!=end(); it++ )
            {
                (*it).print();
                cout << endl;
            }
        }
};

// hier sind die kriterien hinterlegt
class Sort
{
    public:
        Sort() {}
        virtual ~Sort() {}

    public:
        bool valid() const { return !order_.empty(); }

    public:
        vector<pair<string, bool> > order_;
};

// hier die sortier-methode
class DataSort
{
    public:
        DataSort(Sort* sort=NULL) { sort_ = sort; }
        virtual ~DataSort() {}

    public:
        bool operator()(const DataObject& d1, const DataObject& d2)
        {
            if( sort_ != NULL && !sort_->order_.empty() )
            {
                printCompare(next, current, sort_);

                for( vector<pair<string, bool> >::iterator it = sort_->order_.begin(); it != sort_->order_.end(); it++ )
                {
                    if( strcasecmp((*it).first.c_str(), "m1") == 0 )
                    {
                        if( (*it).second && next.m1() > current.m1() )
                            return false;
                        else if( !(*it).second && next.m1() < current.m1() )
                            return false;
                    }
                    else if( strcasecmp((*it).first.c_str(), "m2") == 0 )
                    {
                        if( (*it).second && next.m2() > current.m2() )
                            return false;
                        else if( !(*it).second && next.m2() < current.m2() )
                            return false;
                    }
                    else if( strcasecmp((*it).first.c_str(), "m3") == 0 )
                    {
                        if( (*it).second && next.m3() > current.m3() )
                            return false;
                        else if( !(*it).second && next.m3() < current.m3() )
                            return false;
                    }
                }

                printIsLess(next, current);
                return true;
            }

            return false;
        }

    private:
        Sort* sort_;
};

void PrintCollection(const string& msg, const DataCollection& dc)
{
    cout << msg << endl;
    dc.print();
    cout << endl;
}

void Test(DataCollection& dc)
{
    // sortiere nach m1 aufsteigend und m2 absteigend
    cout << "Test:" << endl << "_____" << endl;

    Sort sort;
    sort.order_.push_back(pair<string, bool>("m1", true));
    sort.order_.push_back(pair<string, bool>("m2", false));
    dc.sort(&sort);

    PrintCollection("Sorted data:", dc);
}

int main()
{
    DataCollection dc;

    dc.push_back(DataObject("A", "A", "A"));
    dc.push_back(DataObject("A", "A", "B"));
    dc.push_back(DataObject("A", "A", "C"));
    dc.push_back(DataObject("A", "B", "A"));
    dc.push_back(DataObject("A", "B", "B"));
    dc.push_back(DataObject("A", "B", "C"));
    dc.push_back(DataObject("A", "C", "A"));
    dc.push_back(DataObject("A", "C", "B"));
    dc.push_back(DataObject("A", "C", "C"));
    dc.push_back(DataObject("B", "A", "A"));
    dc.push_back(DataObject("B", "A", "B"));
    dc.push_back(DataObject("B", "A", "C"));
    dc.push_back(DataObject("B", "B", "A"));
    dc.push_back(DataObject("B", "B", "B"));
    dc.push_back(DataObject("B", "B", "C"));
    dc.push_back(DataObject("B", "C", "A"));
    dc.push_back(DataObject("B", "C", "B"));
    dc.push_back(DataObject("B", "C", "C"));
    dc.push_back(DataObject("C", "A", "A"));
    dc.push_back(DataObject("C", "A", "B"));
    dc.push_back(DataObject("C", "A", "C"));
    dc.push_back(DataObject("C", "B", "A"));
    dc.push_back(DataObject("C", "B", "B"));
    dc.push_back(DataObject("C", "B", "C"));
    dc.push_back(DataObject("C", "C", "A"));
    dc.push_back(DataObject("C", "C", "B"));
    dc.push_back(DataObject("C", "C", "C"));

    random_shuffle(dc.begin(), dc.end());
    PrintCollection("Initial data:", dc);
    Test(dc);

    return 0;
}

    Führe ich das Testprogramm nun aus erhalte ich folgende ausgabe:

    Initial data:
    A B B
    B A B
    B A C
    B C A
    C C A
    B C B
    B C C
    A A B
    C C C
    B A A
    A B A
    C B B
    C A B
    A A C
    A A A
    C B C
    C C B
    C A A
    B B B
    A C C
    A B C
    C B A
    A C B
    B B A
    B B C
    C A C
    A C A

    Test:
    ____
    compare 'B A B' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B A B' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B A C' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B A C' to 'B A B' using m1 (asc) m2 (desc)
    'B A C' is less or equal to 'B A B'
    compare 'B A C' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B C A' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B C A' to 'B A B' using m1 (asc) m2 (desc)
    'B C A' is less or equal to 'B A B'
    compare 'B C A' to 'B A C' using m1 (asc) m2 (desc)
    'B C A' is less or equal to 'B A C'
    compare 'B C A' to 'A B B' using m1 (asc) m2 (desc)
    compare 'C C A' to 'A B B' using m1 (asc) m2 (desc)
    compare 'C C A' to 'B A B' using m1 (asc) m2 (desc)
    compare 'B C B' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B C B' to 'C C A' using m1 (asc) m2 (desc)
    'B C B' is less or equal to 'C C A'
    compare 'B C B' to 'B A B' using m1 (asc) m2 (desc)
    'B C B' is less or equal to 'B A B'
    compare 'B C B' to 'B A C' using m1 (asc) m2 (desc)
    'B C B' is less or equal to 'B A C'
    compare 'B C B' to 'B C A' using m1 (asc) m2 (desc)
    'B C B' is less or equal to 'B C A'
    compare 'B C B' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B C C' to 'A B B' using m1 (asc) m2 (desc)
    compare 'B C C' to 'C C A' using m1 (asc) m2 (desc)
    'B C C' is less or equal to 'C C A'
    compare 'B C C' to 'B A B' using m1 (asc) m2 (desc)
    'B C C' is less or equal to 'B A B'
    compare 'B C C' to 'B A C' using m1 (asc) m2 (desc)
    'B C C' is less or equal to 'B A C'
    compare 'B C C' to 'B C A' using m1 (asc) m2 (desc)
    'B C C' is less or equal to 'B C A'
    compare 'B C C' to 'B C B' using m1 (asc) m2 (desc)
    'B C C' is less or equal to 'B C B'
    compare 'B C C' to 'A B B' using m1 (asc) m2 (desc)
    compare 'C C C' to 'A A B' using m1 (asc) m2 (desc)
    compare 'C C C' to 'A A B' using m1 (asc) m2 (desc)
    compare 'B A A' to 'A A B' using m1 (asc) m2 (desc)
    compare 'B A A' to 'C C C' using m1 (asc) m2 (desc)
    compare 'A B A' to 'A A B' using m1 (asc) m2 (desc)
    'A B A' is less or equal to 'A A B'
    compare 'C B B' to 'A B A' using m1 (asc) m2 (desc)
    compare 'C B B' to 'B A A' using m1 (asc) m2 (desc)
    compare 'C A B' to 'A B A' using m1 (asc) m2 (desc)
    compare 'C A B' to 'C B B' using m1 (asc) m2 (desc)
    compare 'A A C' to 'A B A' using m1 (asc) m2 (desc)
    compare 'A A C' to 'C A B' using m1 (asc) m2 (desc)
    'A A C' is less or equal to 'C A B'
    compare 'A A C' to 'C B B' using m1 (asc) m2 (desc)
    compare 'A B A' to 'A B B' using m1 (asc) m2 (desc)
    'A B A' is less or equal to 'A B B'
    compare 'A A B' to 'A B B' using m1 (asc) m2 (desc)
    compare 'A A B' to 'B C C' using m1 (asc) m2 (desc)
    compare 'A A B' to 'B C B' using m1 (asc) m2 (desc)
    compare 'A A B' to 'B C A' using m1 (asc) m2 (desc)
    compare 'A A B' to 'B A C' using m1 (asc) m2 (desc)
    'A A B' is less or equal to 'B A C'
    compare 'C C C' to 'B A C' using m1 (asc) m2 (desc)
    compare 'C C C' to 'B A B' using m1 (asc) m2 (desc)
    compare 'C C C' to 'C C A' using m1 (asc) m2 (desc)
    'C C C' is less or equal to 'C C A'
    compare 'B A A' to 'C C A' using m1 (asc) m2 (desc)
    compare 'C B C' to 'A A A' using m1 (asc) m2 (desc)
    compare 'C B C' to 'A A A' using m1 (asc) m2 (desc)
    compare 'C C B' to 'A A A' using m1 (asc) m2 (desc)
    compare 'C C B' to 'C B C' using m1 (asc) m2 (desc)
    'C C B' is less or equal to 'C B C'
    compare 'C C B' to 'A A A' using m1 (asc) m2 (desc)
    compare 'C A A' to 'A A A' using m1 (asc) m2 (desc)
    compare 'C A A' to 'C B C' using m1 (asc) m2 (desc)
    compare 'B B B' to 'A A A' using m1 (asc) m2 (desc)
    compare 'B B B' to 'C A A' using m1 (asc) m2 (desc)
    'B B B' is less or equal to 'C A A'
    compare 'B B B' to 'C B C' using m1 (asc) m2 (desc)
    'B B B' is less or equal to 'C B C'
    compare 'B B B' to 'C C B' using m1 (asc) m2 (desc)
    compare 'A C C' to 'A A A' using m1 (asc) m2 (desc)
    'A C C' is less or equal to 'A A A'
    compare 'A B C' to 'A C C' using m1 (asc) m2 (desc)
    compare 'A B C' to 'C A A' using m1 (asc) m2 (desc)
    'A B C' is less or equal to 'C A A'
    compare 'A B C' to 'C B C' using m1 (asc) m2 (desc)
    'A B C' is less or equal to 'C B C'
    compare 'A B C' to 'B B B' using m1 (asc) m2 (desc)
    'A B C' is less or equal to 'B B B'
    compare 'A B C' to 'C C B' using m1 (asc) m2 (desc)
    compare 'A C B' to 'C B A' using m1 (asc) m2 (desc)
    'A C B' is less or equal to 'C B A'
    compare 'B B A' to 'A C B' using m1 (asc) m2 (desc)
    compare 'B B A' to 'C B A' using m1 (asc) m2 (desc)
    'B B A' is less or equal to 'C B A'
    compare 'B B A' to 'A C B' using m1 (asc) m2 (desc)
    compare 'B B C' to 'A C B' using m1 (asc) m2 (desc)
    compare 'B B C' to 'C B A' using m1 (asc) m2 (desc)
    'B B C' is less or equal to 'C B A'
    compare 'B B C' to 'B B A' using m1 (asc) m2 (desc)
    'B B C' is less or equal to 'B B A'
    compare 'B B C' to 'A C B' using m1 (asc) m2 (desc)
    compare 'C A C' to 'A C B' using m1 (asc) m2 (desc)
    compare 'C A C' to 'C B A' using m1 (asc) m2 (desc)
    compare 'A C A' to 'A C B' using m1 (asc) m2 (desc)
    'A C A' is less or equal to 'A C B'
    compare 'A C A' to 'A C C' using m1 (asc) m2 (desc)
    'A C A' is less or equal to 'A C C'
    compare 'A C B' to 'A C C' using m1 (asc) m2 (desc)
    'A C B' is less or equal to 'A C C'
    compare 'B B C' to 'A C C' using m1 (asc) m2 (desc)
    compare 'B B C' to 'A A A' using m1 (asc) m2 (desc)
    compare 'B B C' to 'C C B' using m1 (asc) m2 (desc)
    compare 'B B C' to 'A B C' using m1 (asc) m2 (desc)
    compare 'B B C' to 'B B B' using m1 (asc) m2 (desc)
    'B B C' is less or equal to 'B B B'
    compare 'B B A' to 'B B B' using m1 (asc) m2 (desc)
    'B B A' is less or equal to 'B B B'
    compare 'C B A' to 'B B B' using m1 (asc) m2 (desc)
    compare 'C B A' to 'C B C' using m1 (asc) m2 (desc)
    'C B A' is less or equal to 'C B C'
    compare 'C A C' to 'C B C' using m1 (asc) m2 (desc)
    compare 'C A C' to 'C A A' using m1 (asc) m2 (desc)
    'C A C' is less or equal to 'C A A'
    compare 'C A A' to 'C A B' using m1 (asc) m2 (desc)
    'C A A' is less or equal to 'C A B'
    compare 'C A A' to 'A A C' using m1 (asc) m2 (desc)
    compare 'C A C' to 'A A C' using m1 (asc) m2 (desc)
    compare 'C B C' to 'A A C' using m1 (asc) m2 (desc)
    compare 'C B A' to 'A A C' using m1 (asc) m2 (desc)
    compare 'B B B' to 'A A C' using m1 (asc) m2 (desc)
    compare 'B B A' to 'A A C' using m1 (asc) m2 (desc)
    compare 'B B C' to 'A A C' using m1 (asc) m2 (desc)
    compare 'A B C' to 'A A C' using m1 (asc) m2 (desc)
    'A B C' is less or equal to 'A A C'
    compare 'A B C' to 'C B B' using m1 (asc) m2 (desc)
    'A B C' is less or equal to 'C B B'
    compare 'A B C' to 'B A A' using m1 (asc) m2 (desc)
    'A B C' is less or equal to 'B A A'
    compare 'A B C' to 'C C A' using m1 (asc) m2 (desc)
    compare 'C C B' to 'C C A' using m1 (asc) m2 (desc)
    'C C B' is less or equal to 'C C A'
    compare 'C C B' to 'C C C' using m1 (asc) m2 (desc)
    'C C B' is less or equal to 'C C C'
    compare 'C C B' to 'B A B' using m1 (asc) m2 (desc)
    compare 'A A A' to 'B A B' using m1 (asc) m2 (desc)
    'A A A' is less or equal to 'B A B'
    compare 'A A A' to 'B A C' using m1 (asc) m2 (desc)
    'A A A' is less or equal to 'B A C'
    compare 'A A A' to 'A A B' using m1 (asc) m2 (desc)
    'A A A' is less or equal to 'A A B'
    compare 'A A A' to 'B C A' using m1 (asc) m2 (desc)
    compare 'A C C' to 'B C A' using m1 (asc) m2 (desc)
    'A C C' is less or equal to 'B C A'
    compare 'A C C' to 'B C B' using m1 (asc) m2 (desc)
    'A C C' is less or equal to 'B C B'
    compare 'A C C' to 'B C C' using m1 (asc) m2 (desc)
    'A C C' is less or equal to 'B C C'
    compare 'A C C' to 'A B B' using m1 (asc) m2 (desc)
    'A C C' is less or equal to 'A B B'
    compare 'A C C' to 'A B A' using m1 (asc) m2 (desc)
    'A C C' is less or equal to 'A B A'

    Sorted data:
    A C A
    A C B
    A C C
    A B A
    A B B
    B C C
    B C B
    B C A
    A A A
    A A B
    B A C
    B A B
    C C B
    C C C
    C C A
    A B C
    B A A
    C B B
    A A C
    B B C
    B B A
    B B B
    C B A
    C B C
    C A C
    C A A
    C A B

    ==> die Sortierung funktioniert so überhaupt nicht!
    Hat irgend jemand eine Idee warum es so nicht funktioniert und wie es funktionieren könnte?
    Habe schon mehrere Varianten ausprobiert, habe aber immer eine unsortierte Tabelle erhalten!

    Bin für jede Anregung dankbar!

    Lg
    orsox

    0
  • C

    sort() erwartet keine <= Beziehung, sondern eine < Beziehung.

    0
  • ?

    stable_sort aber schon, oder?

    0
  • C

    Nein - so weit ist die STL schon konsistent, daß alles, was mit Sortieren (sort(), stable_sort(), lower_bound() und Familie, set<>/map<>,...) zu tun hat, die selben Randbedingungen setzt - sie erwarten eine < Beziehung als Vergleichskriterium.

    0
  • ?

    dh. wenn ich die operatoren in der sort-methode dementsprechend anpasse (statt > dann >= und statt < dann <=) sollte es dann funktinieren!?

    0
  • F

    http://www.sgi.com/tech/stl/StrictWeakOrdering.html
    http://en.wikipedia.org/wiki/Strict_weak_ordering

    0
  • ?

    Danke erstmal für die Anregungen.

    Damit ich das jetzt richtig verstehe...

    - sort bzw. stable_sort ruft cmp( *(it+1), *it ) auf
    - wenn *(it+1) < *it ist, muss ich true, ansonsten false zurückliefern

    das hieße dann aber wiederum daß die in meinem Beispiel verwendete Logik funktionieren müsste, oder steh ich jetzt komplett auf'm schlauch? 😕

    wenn ich mehrere sortier-kriterien betrachten muss, dann kann ich doch erst true zurückliefern, wenn keine bedingung ( *(it+1) > *it (für das jeweilige kriterium und somit member) ) erfüllt ist!? 😕

    0
Anmelden zum Antworten