Verwenden des benutzerdefinierten std::set-Komparators

Lesezeit: 7 Minuten

Verwenden des benutzerdefinierten stdset Komparators
Omry Jadan

Ich versuche, die Standardreihenfolge der Elemente in einer Reihe von Ganzzahlen so zu ändern, dass sie lexikographisch statt numerisch sind, und ich kann Folgendes nicht mit g++ kompilieren:

Datei.cpp:

bool lex_compare(const int64_t &a, const int64_t &b) 
{
    stringstream s1,s2;
    s1 << a;
    s2 << b;
    return s1.str() < s2.str();
}

void foo()
{
    set<int64_t, lex_compare> s;
    s.insert(1);
    ...
}

Ich bekomme folgenden Fehler:

error: type/value mismatch at argument 2 in template parameter list for ‘template<class _Key, class _Compare, class _Alloc> class std::set’
error:   expected a type, got ‘lex_compare’

Was mache ich falsch?

Verwenden des benutzerdefinierten stdset Komparators
diralik

1. Moderne C++20-Lösung

auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s;

Wir verwenden die Lambda-Funktion als Komparator. Wie üblich sollte comparator einen booleschen Wert zurückgeben, der angibt, ob das als erstes Argument übergebene Element als vor dem zweiten in der Spezifizierung betrachtet wird strikte schwache Ordnung es definiert.

Online-Demo

2. Moderne C++11-Lösung

auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s(cmp);

Vor C++20 müssen wir Lambda als Argument an den Set-Konstruktor übergeben

Online-Demo

3. Ähnlich der ersten Lösung, aber mit Funktion statt Lambda

Komparator als übliche boolesche Funktion erstellen

bool cmp(int a, int b) {
    return ...;
}

Dann verwenden Sie es entweder auf diese Weise:

std::set<int, decltype(cmp)*> s(cmp);

Online-Demo

oder so:

std::set<int, decltype(&cmp)> s(&cmp);

Online-Demo

4. Alte Lösung mit struct with () Operator

struct cmp {
    bool operator() (int a, int b) const {
        return ...
    }
};

// ...
// later
std::set<int, cmp> s;

Online-Demo

5. Alternative Lösung: Struktur aus boolescher Funktion erstellen

Nehmen Sie die boolesche Funktion

bool cmp(int a, int b) {
    return ...;
}

Und struct daraus machen mit std::integral_constant

#include <type_traits>
using Cmp = std::integral_constant<decltype(&cmp), &cmp>;

Verwenden Sie schließlich die Struktur als Komparator

std::set<X, Cmp> set;

Online-Demo

  • Muss in Beispiel 1 cmp an den Konstruktor übergeben werden? Wird der Satz selbst einen erstellen, da der Lambda-Typ als Vorlagentyp angegeben ist?

    – PeteUK

    10. Januar 2020 um 16:18 Uhr

  • @PeteUK vor dem C++20-Komparator muss an den Konstruktor übergeben werden. In C++20 kann ein Konstruktor ohne Argumente verwendet werden. Danke für die Frage; Antwort wurde aktualisiert

    – diralik

    11. Januar 2020 um 19:39 Uhr


  • @diralik Vielen Dank für die Antwort und Aktualisierung Ihrer bereits großartigen Antwort.

    – PeteUK

    11. Januar 2020 um 23:40 Uhr

  • Das 5. ist verrückt. Jeden Tag findet man neue Ecken und Winkel der Sprache.

    – Jan Hošek

    15. Juli 2020 um 13:04 Uhr

  • Zur akzeptierten Antwort befördert (nur 10+ Jahre nachdem die ursprüngliche Frage gestellt wurde!).

    – Omry Yadan

    24. Dezember 2020 um 4:47 Uhr

1647083407 745 Verwenden des benutzerdefinierten stdset Komparators
Yacoby

Sie verwenden eine Funktion, wo Sie einen Funktor verwenden sollten (eine Klasse, die den ()-Operator überlädt, damit sie wie eine Funktion aufgerufen werden kann).

struct lex_compare {
    bool operator() (const int64_t& lhs, const int64_t& rhs) const {
        stringstream s1, s2;
        s1 << lhs;
        s2 << rhs;
        return s1.str() < s2.str();
    }
};

Sie verwenden dann den Klassennamen als Typparameter

set<int64_t, lex_compare> s;

Wenn Sie den Funktor-Boilerplate-Code vermeiden möchten, können Sie auch einen Funktionszeiger verwenden (vorausgesetzt lex_compare ist eine Funktion).

set<int64_t, bool(*)(const int64_t& lhs, const int64_t& rhs)> s(&lex_compare);

  • @Omry: Mich würde interessieren, welchen Compiler Sie verwenden: codepad.org/IprafuVf

    Matthias N.

    12. April 2010 um 9:21 Uhr

  • @Omry Welchen Compiler verwendest du?

    anon

    12. April 2010 um 9:22 Uhr

  • @Omry Der C++-Standard besagt, dass der zweite Vorlagenparameter der Name eines Typs sein muss – ein Funktionsname ist nicht der Name eines Typs.

    anon

    12. April 2010 um 9:24 Uhr

  • können wir decltype(lex_compare) verwenden, um den Funktionstyp zu bezeichnen?

    – Lewis Chan

    5. Juli 2018 um 4:13 Uhr

  • @LewisChan Der richtige Begriff wäre std::set<int64_t, decltype(&lex_compare)> s(&lex_compare)

    – Nishant Singh

    26. Oktober 2018 um 6:53 Uhr


Die Antwort von Yacoby inspiriert mich, einen Adapter zum Kapseln der Funktor-Boilerplate zu schreiben.

template< class T, bool (*comp)( T const &, T const & ) >
class set_funcomp {
    struct ftor {
        bool operator()( T const &l, T const &r )
            { return comp( l, r ); }
    };
public:
    typedef std::set< T, ftor > t;
};

// usage

bool my_comparison( foo const &l, foo const &r );
set_funcomp< foo, my_comparison >::t boo; // just the way you want it!

Wow, ich glaube, das war die Mühe wert!

  • Ansichtssache, denke ich.

    anon

    12. April 2010 um 11:15 Uhr

  • Wow, in der Tat! Aber es zeigt auch, wie grässlich die C++-Syntax ist. Ich hoffe, dass zukünftige Versionen und Standards die C++-Syntax vereinfachen werden.

    – Nav

    10. Dezember 2020 um 13:02 Uhr

  • @Nav Das ::t Teil kann in C++14 eliminiert werden. Ich denke, es sieht ungefähr so ​​​​gut aus wie das Java-Generika-Äquivalent und garantiert gleichzeitig keinen Laufzeitaufwand.

    – Kartoffelklatsche

    10. Dezember 2020 um 13:15 Uhr

Sie können einen Funktionskomparator verwenden, ohne ihn wie folgt zu umbrechen:

bool comparator(const MyType &lhs, const MyType &rhs)
{
    return [...];
}

std::set<MyType, bool(*)(const MyType&, const MyType&)> mySet(&comparator);

Dies ist irritierend, wenn Sie jedes Mal ein Set dieses Typs benötigen, und kann Probleme verursachen, wenn Sie nicht alle Sets mit demselben Komparator erstellen.

Verwenden des benutzerdefinierten stdset Komparators
Ciro Santilli Путлер Капут 六四事

std::less<> bei der Verwendung von benutzerdefinierten Klassen mit operator<

Wenn Sie es mit einem Satz Ihrer benutzerdefinierten Klasse zu tun haben operator< definiert, dann können Sie einfach verwenden std::less<>.

Wie unter erwähnt http://en.cppreference.com/w/cpp/container/set/find C++14 hat zwei neue hinzugefügt find APIs:

template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;

die es Ihnen ermöglichen:

main.cpp

#include <cassert>
#include <set>

class Point {
    public:
        // Note that there is _no_ conversion constructor,
        // everything is done at the template level without
        // intermediate object creation.
        //Point(int x) : x(x) {}
        Point(int x, int y) : x(x), y(y) {}
        int x;
        int y;
};
bool operator<(const Point& c, int x) { return c.x < x; }
bool operator<(int x, const Point& c) { return x < c.x; }
bool operator<(const Point& c, const Point& d) {
    return c.x < d;
}

int main() {
    std::set<Point, std::less<>> s;
    s.insert(Point(1, -1));
    s.insert(Point(2, -2));
    s.insert(Point(0,  0));
    s.insert(Point(3, -3));
    assert(s.find(0)->y ==  0);
    assert(s.find(1)->y == -1);
    assert(s.find(2)->y == -2);
    assert(s.find(3)->y == -3);
    // Ignore 1234, find 1.
    assert(s.find(Point(1, 1234))->y == -1);
}

Kompilieren und ausführen:

g++ -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out

Mehr Infos zu std::less<> finden Sie unter: Was sind transparente Komparatoren?

Getestet auf Ubuntu 16.10, g++ 6.2.0.

  • Ich denke, es ist an der Zeit, dass Sie Ihren Benutzernamen bearbeiten.)

    – A_P

    16. April 2021 um 13:48 Uhr

  • @A_P Hallo, warum meinst du?

    – Ciro Santilli Путлер Капут 六四事

    16. April 2021 um 14:14 Uhr

  • Ciro, es gibt kein Verbot mehr. Wer nicht genannt werden soll, hat das Büro verlassen und soll vergessen werden, wie man dumme Witze vergisst

    – A_P

    16. April 2021 um 17:30 Uhr


  • @A_P Solange Trump noch von Twitter gesperrt ist, ist es sinnvoll, dies zu hinterfragen.

    – Ciro Santilli Путлер Капут 六四事

    16. April 2021 um 18:17 Uhr

  • Ich denke, es ist an der Zeit, dass Sie Ihren Benutzernamen bearbeiten.)

    – A_P

    16. April 2021 um 13:48 Uhr

  • @A_P Hallo, warum meinst du?

    – Ciro Santilli Путлер Капут 六四事

    16. April 2021 um 14:14 Uhr

  • Ciro, es gibt kein Verbot mehr. Wer nicht genannt werden soll, hat das Büro verlassen und soll vergessen werden, wie man dumme Witze vergisst

    – A_P

    16. April 2021 um 17:30 Uhr


  • @A_P Solange Trump noch von Twitter gesperrt ist, ist es sinnvoll, dies zu hinterfragen.

    – Ciro Santilli Путлер Капут 六四事

    16. April 2021 um 18:17 Uhr

993460cookie-checkVerwenden des benutzerdefinierten std::set-Komparators

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy