std::unordered_multiset::equal_range ohne Key-Konstruktion



  • Hallo,

    Ich möchte std::unordered_multiset::equal_range benutzen, ohne einen Key zu konstruieren, da dies teuer wäre. Minimales Beispiel:

    #include <string>
    #include <vector>
    #include <functional>
    #include <utility>
    #include <unordered_set>
    #include <iostream>
    
    void HashCombine( std::size_t& Seed ) {
        ( void )Seed;
    }
    template< typename HeadT, typename... TailT >
    void HashCombine( std::size_t& Seed, HeadT const& Head, TailT const&... Tail ) {
        using std::hash;
        hash< HeadT > Hasher;
        Seed ^= Hasher( Head ) + 0x9e3779b9 + ( Seed << 6 ) + ( Seed >> 2 );
        HashCombine( Seed, Tail... );
    }
    
    struct Data {
        std::string Name;
        std::vector< int > Values;
    
        template< typename ArgT >
        explicit Data( ArgT&& Arg, std::size_t Size )
            : Name( std::forward< ArgT >( Arg ) ), Values( Size ) {}
    };
    std::size_t DataHash( Data const& Object ) {
        std::size_t Result = 0;
        HashCombine( Result, Object.Name, Object.Values.size() );
        return Result;
    }
    bool DataEq( Data const& Lhs, Data const& Rhs ) {
        return Lhs.Name == Rhs.Name && Lhs.Values.size() == Rhs.Values.size();
    }
    
    int main() {
        std::unordered_multiset< Data, decltype( DataHash )*, decltype( DataEq )* > Dataset( 0, DataHash, DataEq );
        Dataset.emplace( "a", 1024 );
        Dataset.emplace( "a", 512 );
        Dataset.emplace( "a", 1024 );
        Dataset.emplace( "b", 1024 );
        const auto Range = Dataset.equal_range( Data{ "a", 1024 } ); // hier
        std::cout << std::distance( Range.first, Range.second ) << '\n';
    }
    

    Die betroffene Zeile ist 42. Ich möchte die Range aller Data s mit Name "a" und mit 1024 Werten herausfischen, ohne selbst jedes mal eine dynamische Allokation durchzuführen. Meine aktuelle Notlösung ist es linear über die unordered_multiset zu iterieren und jedes Objekt einzeln zu vergleichen, was natürlich der Idee einer Hashmap total widerspricht.
    Hat jemand eine Idee, wie ich die equal_range effizient herausbekommen kann?

    LG



  • Mit der Boost Variante geht das:
    http://www.boost.org/doc/libs/1_64_0/doc/html/boost/unordered_multiset.html#idp775619232-bb

    Mit den std Klassen fallen wir nur folgende zwei (naheliegenden) Ansätze ein

    1. Ne map statt nem set verwenden
    2. Data aufbohren so dass man Dummies erzeugen kann die den selben Hash-Wert haben und equal vergleichen, aber dennoch billig zu konstruieren sind

Log in to reply