[C++] Sorteren van objecten

[Verwijderd]

Ik heb een vector met pointers naar Word's (één of ander object), en daarbij hoort een vector met integers. Ik wil de vector met integers sorteren a.d.h.v. de woorden in de eerste vector. In andere woorden, hij moet de integers zo sorteren dat de daarbij behorende woorden op alfabetische volgorde staan. Ik heb nu dit:

C++:

template<class T> struct index_cmp {
    index_cmp(const T arr) : arr(arr) {}
    bool operator() (const size_t a, const size_t b) const {
        return arr[a] < arr[b]; 
    }
    const T arr;
};

// ...

sort(indices.begin(), indices.end(), index_cmp<vector<Word*>&>(words));

Hierin heeft indices dus type vector<int> en words type vector<Word*>. De operator < heb ik overgeload voor het Word object, zodat deze woorden vergelijkt (welke komt eerder in het alfabet).

Het bovenstaande zou volgens mij prima werken als words een vector<Word> was geweest, maar aangezien ik een vector<Word*> heb, worden nu de pointers met elkaar vergeleken in plaats van de woorden. De vergelijking veranderen in

C++:

return *(arr[a]) < *(arr[b]); 

mag niet, en de < operator overloaden voor Word-pointers mag ook niet.
Hoe los ik dit nu het handigst op

[.oisyn]

Verwijderd schreef op vrijdag 25 april 2008 @ 01:03:
De vergelijking veranderen in

C++:

return *(arr[a]) < *(arr[b]); 

mag niet

Waarom niet?

Of bedoel je dat je die niet wilt wijzigen? Eigenlijk mist index_cmp dan ook een extra template parameter. Want het is een comparator die werkt op indices ipv de objecten zelf, maar er staat niet bij wat de vergelijkingsfunctie is. En zoals gebruikelijk in de STL default die naar std::less, maar kun je 'm ook zelf meegeven (zoals jij al in je std::sort doet). Dus ik stel een kleine aanpassing voor:

C++:

template<class T, class P = std::less<T> > struct index_cmp { 
    index_cmp(const T arr, P p = P()) : arr(arr), pred(p) {} 
    bool operator() (const size_t a, const size_t b) const { 
        return pred(arr[a], arr[b]);  
    } 
    const T arr;
    P pred; 
}; 

En nu heb je de mogelijkheid om de vergelijkingsfunctie te overriden, door bijvoorbeeld een ptr_less mee te geven die weer de gedereferencte pointers vergelijkt.

[ Voor 67% gewijzigd door .oisyn op 25-04-2008 01:55 ]

[Verwijderd]

Ik weet niet zeker of ik het goed begrepen heb
Ik heb nu dit:

C++:

template<class T, class P = std::less<T> > struct index_cmp {
    index_cmp(const T arr, P p = P()) : arr(arr), pred(p) {}
    bool operator() (const size_t a, const size_t b) const {
        return pred(arr[a], arr[b]); 
    }
    const T arr;
    P pred;
};

bool smallerThan(Word* word1, Word* word2) {
    printf("Pointers are: %p and %p...\n", word1, word2);
    printf("Words are: %s and %s...\n", word1->getWord(), word2->getWord()); 
    return word1->isSmallerThan(*word2);
}

// ...

sort(indices.begin(), indices.end(), index_cmp<vector<Word*>&, bool (&)(Word*, Word*)>(words, smallerThan));

De code komt wel in de smallerThan(Word*, Word*) methode en print ook twee valide pointers uit, maar geeft vervolgens een segmentation fault in de tweede print-regel. De pointers lijken dus niet echt naar Word-objecten te refereren.
Aan de vector<Word*> words ligt het niet, want als ik die 'gewoon' sorteer werkt het prima:

C++:

sort(words.begin(), words.end(), smallerThan);

edit: Ook de indices vector is gevuld met de juiste waarden, en de indices en words vectoren zijn even groot.

Die bool isSmallerThan() en char* getWord() zijn methodes van m'n Word-class; die werken wel.

[ Voor 4% gewijzigd door Verwijderd op 25-04-2008 03:23 ]

[.oisyn]

Het ligt niet aan die code, die werkt prima. Ik heb het even geprobeerd:

C++:

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

class Word
{
    std::string m_str;
public:
    Word(const std::string & s) : m_str(s) { }
    const char * getWord() const { return m_str.c_str(); }
    bool isSmallerThan(const Word & other) const { return m_str < other.m_str; }
};

template<class T, class P = std::less<T> > struct index_cmp { 
    index_cmp(const T arr, P p = P()) : arr(arr), pred(p) {} 
    bool operator() (const size_t a, const size_t b) const { 
        return pred(arr[a], arr[b]);  
    } 
    const T arr; 
    P pred; 
}; 

bool smallerThan(Word* word1, Word* word2) { 
    printf("Pointers are: %p and %p...\n", word1, word2); 
    printf("Words are: %s and %s...\n", word1->getWord(), word2->getWord());  
    return word1->isSmallerThan(*word2); 
} 


int main()
{
    std::vector<Word*> words;
    std::vector<size_t> indices;

    for (size_t i = 0; i < 10; i++)
    {
        std::string s = "atest";
        s[0] += std::rand() % 26;
        words.push_back(new Word(s));
        indices.push_back(i);

        std::cout << "[" << i << "]: " << s << std::endl;
    }

    sort(indices.begin(), indices.end(), index_cmp<std::vector<Word*>&, bool (&)(Word*, Word*)>(words, smallerThan));
    
    for (size_t i = 0; i < 10; i++)
        std::cout << "[" << indices[i] << "]: " << words[indices[i]]->getWord() << std::endl;
}

output:

[0]: ptest
[1]: htest
[2]: qtest
[3]: gtest
[4]: htest
[5]: utest
[6]: mtest
[7]: etest
[8]: atest
[9]: ytest
Pointers are: 004341A0 and 004340D0...
Words are: htest and ptest...
Pointers are: 004341D8 and 004341A0...
Words are: qtest and htest...
Pointers are: 004341D8 and 004340D0...
Words are: qtest and ptest...
Pointers are: 00434230 and 004341A0...
Words are: gtest and htest...
Pointers are: 00434270 and 00434230...
Words are: htest and gtest...
Pointers are: 00434270 and 004341D8...
Words are: htest and qtest...
Pointers are: 00434270 and 004340D0...
Words are: htest and ptest...
Pointers are: 00434270 and 004341A0...
Words are: htest and htest...
Pointers are: 004342D8 and 00434230...
Words are: utest and gtest...
Pointers are: 004342D8 and 004341D8...
Words are: utest and qtest...
Pointers are: 00434300 and 00434230...
Words are: mtest and gtest...
Pointers are: 00434300 and 004342D8...
Words are: mtest and utest...
Pointers are: 00434300 and 004341D8...
Words are: mtest and qtest...
Pointers are: 00434300 and 004340D0...
Words are: mtest and ptest...
Pointers are: 00434300 and 00434270...
Words are: mtest and htest...
Pointers are: 00434388 and 00434230...
Words are: etest and gtest...
Pointers are: 004343B0 and 00434388...
Words are: atest and etest...
Pointers are: 004343D8 and 004343B0...
Words are: ytest and atest...
Pointers are: 004343D8 and 004342D8...
Words are: ytest and utest...
[8]: atest
[7]: etest
[3]: gtest
[1]: htest
[4]: htest
[6]: mtest
[0]: ptest
[2]: qtest
[5]: utest
[9]: ytest

Ik denk toch dat er iets niet klopt aan je indices.

[MSalters]

Een paar assert's in je predicate lijken me handig, om te checken dat a < arr.size() && b < arr.size()

Verder vindt ik die pointer cast wel erg vies. Kleine tip, gebruik template argument deduction:

C++:

template <typename C, typename P> make_index_cmp(C const& cont, P const& pred)
{
    return index_cmp<C,P>(cont, pred);
}
//...
std::sort(indices.begin(), indices.end(), make_index_cmp(words, smallerThen));

[.oisyn]

Je vergeet nog index_cmp<C,P> als return-type te specificeren . Overigens kopiëert ie nu de hele array, terwijl minne478 een reference gebruikte (index_cmp<C&,P>).

[Verwijderd]

Hmmm blijkbaar moeten je indices netjes van 0 tot words.size() - 1 lopen. Als ik in je voorbeeld dit verander:

C++:

indices.push_back(i + 1);

stopt jouw code er ook mee na een paar vergelijkingen. Toch vreemd... indices wordt toch gewoon gesorteerd aan de hand van words, dan zou het toch niet uit moeten maken wat er dan in die indices zelf zit

Anyway, ik krijg het nu wel aan de praat. Bedankt!

[.oisyn]

Natuurlijk niet. Je sorteert de indices array, en gebruikt die indices om lookups te doen in je word array (de sort functie roept index_cmp ten minste 1 keer aan voor iedere index in de array). Al die dingen moeten dan natuurlijk wel kloppen.

[ Voor 22% gewijzigd door .oisyn op 25-04-2008 18:30 ]

[Verwijderd]

Ah ok... dat stukje van std::sort had ik dus niet goed begrepen. Bedankt!