binary_search ohne Value oder BindIterator



  • Gegeben ein sortierter vector<shared_ptr<BigObject>> v. BigObject enthält ein paar MB Daten sowie einen string path. Der vector ist nach BigObject::path sortiert. Ziel: Finde heraus, ob der vector v ein BigObject mit gegebenem string p enthält. Die Lösung ist irgendwie sowas:

    return binary_search(cbegin(v), cend(v), ???, [](shared_ptr<BigObject> &bo1, shared_ptr<BigObject> &bo2){return bo1.path < bo2.path;});
    

    Ich möchte es vermeiden ein shared_ptr<BigObject> zu erstellen und dort path setzen nur um damit binary_search aufrufen zu können. Einen Iterator bauen, der aus dem shared_ptr<BigObject> den pfad rausfummelt und auf dem vector-Iterator basiert erscheint mir unnötig kompliziert. Alternativ ginge std::find, aber das hat dasselbe Problem. Geht das irgendwie einfacher? Sowas wie BindIterator<VectorIterator, VectorIterator::path> oder so?



  • Mit find_if gehts.



  • Ich denke, die eifnachste Möglichkeit wäre, dass du den Path relativ easy zugänglich machst (z.B. ein einfacher Getter) und ein Dummy BigObject erzeugst, was nur eben den path gesetzt hat.

    Zur Not kapselst du das noch weiter ab nach folgendem Motto:

    // Anstelle von
    class BigObject
    {
        // xXx MB daten
        std::string path;
        // ...
    };
    std::vector<std::shared_ptr<BigObject>> vec;
    
    // eher sowas:
    class BigObject
    {
        class RealBigObject
        {
            // xXx MB Daten
        };
        std::string path;
        std::unique_ptr<RealBigObject> data;
    };
    std::vector<std::shared_ptr<BigObject>> vec;
    

    Du trennst halt die Daten vom path ab.


  • Mod

    nwp3 schrieb:

    Mit find_if gehts.

    Ist stark suboptimal, bei einem sortieren Container.

    Es gibt eine sehr einfache Lösung für dieses Problem

    binary_search( cbegin(v), cend(v), p, [] (string const& val, shared_ptr<BigObject> const& bo2) {return val < bo2.path;} ); 
    // Du nutzt ja scheinbar C++14? Warum kein generisches Lambda
    

    Der Trick ist, dass der Comparator als erstes Argument nur einen Typen haben muss, in den der Typ vom zusuchenden Argument konvertierbar sein muss.



  • Ich benutze das leicht kastrierte C++11 von VS2013, das kann keine generischen Lambdas. Ich will clang 😞

    #include <vector>
    #include <string>
    #include <memory>
    #include <algorithm>
    
    using namespace std;
    
    struct BigObject{
    	BigObject(int i) : bigdata(i), path(to_string(i)){}
    	string path;
    	int bigdata;
    	operator const string&() const{ //nur zum testen
    		return path;
    	}
    };
    
    int main(){
    	vector<shared_ptr<BigObject>> v;
    	for (int i = 0; i < 10; i++)
    		v.push_back(make_shared<BigObject>(i));
    	string p(to_string(5));
    	binary_search(cbegin(v), cend(v), p, [](string const& val, shared_ptr<BigObject> const& bo2) {return val < bo2->path; });
    }
    
    Error: cannot convert argument 1 from 'const std::shared_ptr<BigObject>' to 'const std::string &'
    

    Die Fehlermeldung hatte ich erwartet. Ich weiß auch nicht wie ich shared_ptr<BigObject> beibringen soll sich in einen string konvertieren zu lassen.



  • Geht sowas wie

    struct comparator {
      bool operator<(string const& val, shared_ptr<BigObject> const& bo2) { ... }
      bool operator<(shared_ptr<BigObject> const& bo1, string const& val) { ... }
    };
    
    binary_search(cbegin(v), cend(v), p, comparator{});
    

    ?


  • Mod

    Ups - ich habe den Referenz-Artikel nicht ganz zuende gelesen, mein Fehler:

    Update type requirements? The types Type1 and Type2 must be such that an object of type T can be implicitly converted to either type, and such that an object of type ForwardIt can be dereferenced and then implicitly converted to either type. [..]

    Dann wird das wohl nicht ganz so hübsch...

    Eigener Vergleichs-Funktor? Mein Vorposter hat es ja vorgemacht:

    struct Comp
        {
    		// (1) nicht nötig: bool operator()( shared_ptr<BigObject> const& a, shared_ptr<BigObject> const& b ) { return a->path < b->path; }
    		/* (2) */bool operator()( std::string const& val, shared_ptr<BigObject> const& b ) { return val < b->path; }
    		/* (3) */bool operator()( shared_ptr<BigObject> const& b, std::string const& val ) { return b->path < val; }
        };
    
        binary_search(begin(v), end(v), p, Comp{});
    


  • Arcoth schrieb:

    bool operator()( shared_ptr<BigObject> const& a, shared_ptr<BigObject> const& b ) { return a->path < b->path; }
    

    Sicher, dass es den braucht?


  • Mod

    lamb schrieb:

    Arcoth schrieb:

    bool operator()( shared_ptr<BigObject> const& a, shared_ptr<BigObject> const& b ) { return a->path < b->path; }
    

    Sicher, dass es den braucht?

    Edit: 🤡

    Nächstes mal gucke ich gleich in den Standard:

    The elements e of [first,last) are partitioned with respect to the expressions [...] comp(e, value) and !comp(value, e) .



  • Extrem coole Idee, das geht sogar 😃
    Vielleicht sind Lambdas doch kein Allheilmittel 🤡



  • Alternative:

    struct Delegate{
    	Delegate(const string &str) : s(str){}
    	Delegate(const shared_ptr<BigObject> &b) : s(b->path){}
    	const string &s;
    };
    
    int main(){
    	vector<shared_ptr<BigObject>> v;
    	for (int i = 0; i < 10; i++)
    		v.push_back(make_shared<BigObject>(i));
    	string p(to_string(5));
    	binary_search(cbegin(v), cend(v), p, [](const Delegate &d1, const Delegate &d2){ return d1.s < d2.s; });
    }
    

Log in to reply