std::set mit unterschiedlichen Compare Klassen



  • hallo zusammen

    Hier habe ich gelernt dass ich keine std::map benötige wenn sich mein key im Objekt des Values befindet. Hier reicht eine set. Wobei ich zum suchen eine compare methode bereit stellen muss. (danke @camper)

    class MyObject
    {
      string name;
      string alias;
      int value;
    }
    
    struct Compare
    {
       template <typename T>
       bool operator()(T&& x, const MyObject& y) const { return std::forward<T>(x) < y.name; }
    
       template <typename T>
       bool operator()(const MyObject& x, T&& y) const { return x.name < std::forward<T>(y); }
    }
    
    _set<MyObject, Compare> mySet;
    

    über find kann ich nun nach einem bestimmten Namen im Set suchen.

    _set.find("someName");
    

    möchte ich nun aber nach einem anderen Feld suchen z.B. alias. was muss ich dann tun?

    Eine zweites set zu erstellen mit einem anderen Comparer ist wahrscheinlich nicht nötig?



  • Benutze std::find_if() aus dem <algorithm>-Header und übergib der Funktion einen Funktionspointer, der ein MyObject als Parameter erwartet und ein boolescher Wert zurückgibt.


  • Mod

    Wenn eine Ordnungsrelation existiert, die auf alias basiert und zur gleichen Anordnung der Elemente im Set führt, wie die Compare, könnte Compare entsprechend erweitert werden (ggf. mit einer kleinen Wrapperklasse, um zwischen Sucher per name und Suche per alias zu unterscheiden).
    In der Regel wird das aber nicht der Fall sein. Dann kann immer linear gesucht werden find_if.

    Eine andere Möglichkeit besteht darin einen zweiten Container aus Zeigern auf MyObjekt zu benutzen, als set oder unorderd_set (oder auch multiset etc. - könnte ja sein, dass alias gar nicht eindeutig ist) oder auch einen sortierten vector. Letzteres ist besonders attraktiv, wenn - im Vergleich zu Suchoperationen - nur selten eingefügt werden muss. Zeiger in ein set (bzw. irgendeinen Node-basierenden Container) sind stabil. Nachteilig ist bei dieser Möglichkeit nat. dass dafür gesorgt werden muss, dass beide Container immer synchron verändert werden, es ist also zweckmäßig hierfür eine eigenständigen Klasse zu verwenden, die eine entsprechende Invariante hat.

    Eine fertige Lösung, die nebenbei auch effizienter ist, findet sich in boost.
    Beispiel:

    #include <iostream>
    #include <string>
    #include <string_view>
    #include <utility>
    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <boost/multi_index/member.hpp>
    
    namespace mi = boost::multi_index;
    // Ein paar simple Helper der Bequemlichkeit wegen weil wir C++17 haben
    template <typename T> struct identity { using type = T; };
    template <auto p> struct class_of_member;
    template <typename T, typename C, T C::* p> struct class_of_member<p> : identity<C> {};
    template <auto p> using class_of_member_t = typename class_of_member<p>::type;
    template <auto p> struct type_of_member;
    template <typename T, typename C, T C::* p> struct type_of_member<p> : identity<T> {};
    template <auto p> using type_of_member_t = typename type_of_member<p>::type;
    //
    template <auto p> using member_extractor = mi::member<class_of_member_t<p>, type_of_member_t<p>, p>;
    
    struct icompare {
        template <typename T, typename U>
        bool operator()(T&& lhs, U&& rhs) const noexcept {
            return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), [](auto&& l, auto&& r) { 
                return std::tolower(l) < std::tolower(r);
            });
        }
    };
    
    class MyObject
    {
    public:
        std::string name;
        std::string alias;
        int value;
        friend std::ostream& operator<<(std::ostream& s, const MyObject& x) {
            return s << "{name=" << x.name << ";alias=" << x.alias << ";value=" << x.value << '}';
        }
    };
    
    struct by_name {};
    struct by_alias {};
    
    template <typename Tag, typename C>
    void show(const C& c)
    {
        for ( auto&& v : mi::get<Tag>(c) )
            std::cout << v << ", ";
        std::cout << '\n';
    }
    
    int main() {
        using MyObjectsContainer = mi::multi_index_container<
            MyObject,
            mi::indexed_by<
                mi::ordered_unique<mi::tag<by_name>,  member_extractor<&MyObject::name>,  icompare>,
                mi::ordered_unique<mi::tag<by_alias>, member_extractor<&MyObject::alias>, icompare>
            >
        >;
        MyObjectsContainer c{ MyObject{ "abc", "666", 5 }, MyObject{ "DEF", "111", 0 }, MyObject{ "ggg", "333", 2 } };
        show<by_name>(c);
        show<by_alias>(c);
    }
    


  • Oh ich habe da was falsch erzählt. Sorry,

    class MyObject
    {
      string name;
      vector<string> aliasse;
      int value;
    }
    

    Der Alias ist zwar eindeutig aber ich habe mehrere Aliasse zu einem Objekt.
    Der Alias ist also ein vector von strings,

    Aktuell verwende ich ich maps. Hier habe ich wie du vorgeschlagen hast schon zwei Container. AlisaMap und NameMap

    Sollte ein Alias hinzukommen so habe ich einen weiteren Eintrag in meiner Aliasmap hinzugefügt mit einem Zeiger auf das Objekt.

    Gab es keinen Alias gab es keinen Eintrag in der Aliasmap. Gab es mehrere Aliase so auch mehrere Einträge in der Aliasmap.

    Die Container waren so auch nicht synchron. Ich denke ich setze jetzt ein set ein. Mit einem Compare auf Name. Und suche mit find_if nach dem alias.

    Wobei es dann wohl bessere wäre wenn ich aus dem vector<string> aliasse auch eine set machen würde. Dann könnte ich auch hier doppelte einträge vermeiden und schneller prüfen können ob es schon einen alias für ein anderes Objekt gibt.



  • Also so:

    std::set<shared_ptr<MyObject> NameCompare> _varDict;
    
    //... in Add Methode
    
    const auto iter = std::find_if(_varDict.begin(), _varDict.end(), [&alias](shared_ptr<MyObject> var) { return var->aliasse.find(alias) != var->aliasse.end(); });
    if(iter != _varDict.end())
    {
        throw std::runtime_error("Alias " + alias + " already exists")
    }
    
    (*iter)->AddAlias(alias);
    


  • (*iter)->AddAlias(alias);
    

    das war natürlich blödsinn.

    alias muss zur vorhandenen Variable hinzgefügt werden:

    auto var = _varDict.find(name);

    // find_if mit alias ...
    // und bei nicht finden dann:
    var->AddAlias(alias)



  • Aber noch eine andere Frage.

    Habe ich eine map:
    std::map<string, shared_ptr<MyObject>> ist hier der string also in meinem Fall der Name eindeutig.

    bei einem set
    std:set<shared_ptr<MyObject>> ist ja dann der Zeiger auf mein Objekt eindeutig. Nun muss ich beim hinzufügen aber immer überprüfen ob der Name nicht bereits in einem der Objekte drin ist. hier könnte ich also 2 verschiedene Objekte aber mit gleichem Namen einfügen. Da wäre ja eine map schon von Vorteil.


Log in to reply