Oordnade associativa behållare (C++)

I programmeringsspråket C++ är oordnade associativa behållare en grupp klassmallar i C++ Standard Library som implementerar varianter av hashtabeller . Eftersom de är mallar kan de användas för att lagra godtyckliga element, som heltal eller anpassade klasser. Följande behållare är definierade i den aktuella versionen av C++-standarden: unordered_set , unordered_map , unordered_multiset , unordered_multimap . Var och en av dessa behållare skiljer sig endast på begränsningar som ställs på deras element.

De oordnade associativa behållarna liknar de associativa behållarna i C++ Standard Library men har andra begränsningar. Som namnet antyder är inte elementen i de oordnade associativa behållarna ordnade . Detta beror på användningen av hashing för att lagra objekt. Behållarna kan fortfarande itereras igenom som en vanlig associativ behållare.

Historia

Den första allmänt använda implementeringen av hashtabeller i C++-språket var hash_map , hash_set , hash_multimap , hash_multiset klassmallar av Silicon Graphics (SGI) Standard Template Library (STL). På grund av deras användbarhet inkluderades de senare i flera andra implementeringar av C++ Standard Library (t.ex. GNU Compiler Collections (GCC) libstdc++ och Visual C++ (MSVC) standardbiblioteket).

Klassmallarna hash_* föreslogs i C++ Technical Report 1 (C++ TR1) och accepterades under namn unordered_* . Senare införlivades de i C++11 -revisionen av C++-standarden. En implementering är också tillgänglig i Boost C++-biblioteken som <boost/unordered_map.hpp> .

Översikt över funktioner

Behållarna definieras i rubriker med namn efter behållarnas namn, t.ex. är unordered_set definierad i rubriken <unordered_set> . Alla behållare uppfyller kraven för Container- konceptet , vilket innebär att de har metoderna begin() , end() , size() , max_size() , empty() och swap() .

	unordered_set ( C++11 )	unordered_map (C++11)	unordered_multiset (C++11)	unordered_multimap (C++11)	Beskrivning
	(konstruktör)	(konstruktör)	(konstruktör)	(konstruktör)	Konstruerar behållaren från olika källor
	(förstörare)	(förstörare)	(förstörare)	(förstörare)	Förstör uppsättningen och de ingående elementen
	operator=	operator=	operator=	operator=	Tilldelar värden till behållaren
	get_allocator	get_allocator	get_allocator	get_allocator	Returnerar allokatorn som används för att allokera minne för elementen
Elementåtkomst	—	på	—	—	Åtkomst till specificerat element med gränskontroll.
	—	operatör[]	—	—	Åtkomst till specificerat element utan gränskontroll.
Iteratorer	Börja	Börja	Börja	Börja	Returnerar en iterator till början av behållaren
	slutet	slutet	slutet	slutet	Returnerar en iterator till slutet av behållaren
Kapacitet	tömma	tömma	tömma	tömma	Kontrollerar om behållaren är tom
	storlek	storlek	storlek	storlek	Returnerar antalet element i behållaren.
	max_size	max_size	max_size	max_size	Returnerar det högsta möjliga antalet element i behållaren
Modifierare	klar	klar	klar	klar	Rensar innehållet.
	Föra in	Föra in	Föra in	Föra in	Infogar element.
	placera	placera	placera	placera	Konstruerar element på plats ( C++11 )
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	Konstruerar element på plats med hjälp av en ledtråd ( C++11 )
	radera	radera	radera	radera	Raderar element.
	byta	byta	byta	byta	Byter innehållet med en annan behållare.
Slå upp	räkna	räkna	räkna	räkna	Returnerar antalet element som matchar specifik nyckel.
	hitta	hitta	hitta	hitta	Hittar ett element med en specifik nyckel.
	lika_intervall	lika_intervall	lika_intervall	lika_intervall	Returnerar ett intervall av element som matchar specifik nyckel.
Gränssnitt för hink	...
Hash policy	...
Observatörer	hash_function	hash_function	hash_function	hash_function	Returnerar funktionen som används för att skapa hash för en nyckel
	key_eq	key_eq	key_eq	key_eq	Returnerar nyckeljämförelsefunktion.

Användningsexempel

 
 
 
 
 

      
      
      
      
      
      
      
      
      
      
      
      
      
          
          
          
          
     0
 #include  <iostream>  #include  <string>  #include  <unordered_map>  int  main  ()  {  std  ::  unordered_map  <  std  ::  string  ,  int  >  months  ;  månader  [  "januari"  ]  =  31  ;  månader  [  "februari"  ]  =  28  ;  månader  [  "mars"  ]  =  31  ;  månader  [  "april"  ]  =  30  ;  månader  [  "maj"  ]  =  31  ;  månader  [  "juni"  ]  =  30  ;  månader  [  "juli"  ]  =  31  ;  månader  [  "augusti"  ]  =  31  ;  månader  [  "september"  ]  =  30  ;  månader  [  "oktober"  ]  =  31  ;  månader  [  "november"  ]  =  30  ;  månader  [  "december"  ]  =  31  ;  std  ::  cout  <<  "september -> "  <<  månader  [  "september"  ]  <<  std  ::  endl  ;  std  ::  cout  <<  "april -> "  <<  månader  [  "april"  ]  <<  std  ::  endl  ;  std  ::  cout  <<  "december -> "  <<  månader  [  "december"  ]  <<  std  ::  endl  ;  std  ::  cout  <<  "february -> "  <<  månader  [  "februari"  ]  <<  std  ::  endl  ;  återvända  ;  } 

Anpassade hash-funktioner

För att använda anpassade objekt i std::unordered_map måste en anpassad hashfunktion definieras. Denna funktion tar en const-referens till den anpassade typen och returnerar en size_t

 
 
  

 
      
         
  
 #inkludera  <unordered_map>  struct  X  {  int  i  ,  j  ,  k  ;};  struct  hash_X  {  size_t  operator  ()(  const  X  &  x  )  const  {  return  std  ::  hash  <  int  >  ()(  x  .  i  )  ^  std  ::  hash  <  int  >  ()(  x  .  j  )  ^  std  ::  hash  <  int  >  ()(  x  .  k  );  }  }; 

Den användardefinierade funktionen kan användas som den är i std::unordered_map, genom att skicka den som en mallparameter

   std  ::  unordered_map  <  X  ,  int  ,  hash_X  >  my_map  ; 

Eller kan ställas in som standard hash-funktion genom att specialisera std::hash-funktionen

  
     
         
         
             
                 
        
    



   namnområde  std  {  mall  <>  klass  hash  <  X  >  {  public  :  size_t  operator  ()(  const  X  &  x  )  const  {  return  hash  <  int  >  ()(  x  .  i  )  ^  hash  <  int  >  ()(  x  .  j  )  ^  hash  <  int  >  ()(  x  .  k  );  }  };  }  //...  std  ::  unordered_map  <  X  ,  int  >  my_map  ;