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 dieunordered_multiset
zu iterieren und jedes Objekt einzeln zu vergleichen, was natürlich der Idee einer Hashmap total widerspricht.
Hat jemand eine Idee, wie ich dieequal_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-bbMit den std Klassen fallen wir nur folgende zwei (naheliegenden) Ansätze ein
- Ne map statt nem set verwenden
- Data aufbohren so dass man Dummies erzeugen kann die den selben Hash-Wert haben und equal vergleichen, aber dennoch billig zu konstruieren sind