Associativa behållare

Inom datorer hänvisar associativa behållare till en grupp klassmallar i standardbiblioteket för programmeringsspråket C++ som implementerar ordnade associativa arrayer . 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: set , map , multiset , multimap . Var och en av dessa behållare skiljer sig endast på begränsningar som ställs på deras element.

De associativa behållarna liknar de oordnade associativa behållarna i C++ standardbibliotek , den enda skillnaden är att de oordnade associativa behållarna, som deras namn antyder, inte ordnar sina element.

Design

Egenskaper

Nyckelunik : i karta och uppsättning måste varje nyckel vara unik. multimap och multiset har inte denna begränsning.
Elementsammansättning : i karta och multimap är varje element sammansatt av en nyckel och ett mappat värde. I set och multiset är varje element nyckeln; det finns inga mappade värden.
Elementordning : element följer en strikt svag ordning

Associativa behållare är utformade för att vara särskilt effektiva när det gäller att komma åt dess element genom sin nyckel, i motsats till sekvensbehållare som är mer effektiva när det gäller att komma åt element genom sin position. Associativa behållare är garanterade att utföra operationer för infogning, radering och testning av om ett element finns i den, i logaritmisk tid – O(log n ) . Som sådana implementeras de vanligtvis med hjälp av självbalanserande binära sökträd och stöder dubbelriktad iteration. Iteratorer och referenser ogiltigförklaras inte genom infogning och radering, förutom iteratorer och referenser till raderade element. Det definierande kännetecknet för associativa behållare är att element infogas i en fördefinierad ordning, såsom sorterade stigande.

De associativa behållarna kan grupperas i två underuppsättningar: kartor och uppsättningar. En karta, ibland kallad en ordbok, består av ett nyckel/värdepar. Nyckeln används för att beställa sekvensen, och värdet är på något sätt associerat med den nyckeln. Till exempel kan en karta innehålla nycklar som representerar varje unikt ord i en text och värden som representerar antalet gånger det ordet förekommer i texten. En uppsättning är helt enkelt en stigande behållare med unika element.

Som nämnts tidigare tillåter map and set endast en instans av en nyckel eller ett element att infogas i behållaren. Om flera instanser av element krävs, använd multimap eller multiset .

Både kartor och uppsättningar stöder dubbelriktade iteratorer. Mer information om iteratorer finns i Iteratorer .

Även om de inte officiellt ingår i STL- standarden, används hash_map och hash_set ofta för att förbättra söktiderna. Dessa behållare lagrar sina element som en hashtabell , där varje tabellpost innehåller en dubbelriktad länkad lista med element. För att säkerställa de snabbaste söktiderna ( O(1) ) , se till att hashalgoritmen för dina element returnerar jämnt fördelade hashvärden.

Prestanda

Den asymptotiska komplexiteten hos operationerna som kan tillämpas på associativa behållare är följande:

Drift	Komplexitet
Söker efter ett element	O(log n)
Infoga ett nytt element	O(log n)
Öka/minska en iterator	O(log n) (amorteras O(1) om endast ökningar eller endast minskningar görs)
Ta bort ett enda element	O(log n)

Översikt över funktioner

Behållarna definieras i rubriker med namn efter behållarnas namn, t.ex. set definieras i rubriken <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() .

	`uppsättning`	`Karta`	`multiset`	`multimap`	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.
Elementåtkomst	—	`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
	`börja`	`börja`	`börja`	`börja`	Returnerar en omvänd iterator till den omvända början av behållaren
	`rämna`	`rämna`	`rämna`	`rämna`	Returnerar en omvänd iterator till den omvända änden 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.
	`nedre_gräns`	`nedre_gräns`	`nedre_gräns`	`nedre_gräns`	Returnerar en iterator till det första elementet med en nyckel som inte är mindre än det angivna värdet.
	`övre gräns`	`övre gräns`	`övre gräns`	`övre gräns`	Returnerar en iterator till det första elementet med en nyckel som är större än ett visst värde.
Observatörer	`key_comp`	`key_comp`	`key_comp`	`key_comp`	Returnerar nyckeljämförelsefunktionen.
Observatörer	`värde_komp`	`värde_komp`	`värde_komp`	`värde_komp`	Returnerar värdejämförelsefunktionen. I `set` och `multiset` är denna funktion likvärdig med `key_comp` , eftersom elementen endast består av en nyckel.

Användande

Följande kod visar hur man använder kartan<string, int> för att räkna förekomster av ord. Den använder ordet som nyckel och räkningen som värde .

 
 

 

      
     

           
    
        
    
    
           
    
                
    
    
     0
 #include  <iostream>  #include  <map>  int  main  ()  {  std  ::  map  <  std  ::  string  ,  int  >  wordcounts  ;  std  ::  sträng  s  ;  while  (  std  ::  cin  >>  s  &&  s  !=  "slut"  )  {  ++  ordantal  [  s  ];  }  while  (  std  ::  cin  >>  s  &&  s  !=  "end"  )  {  std  ::  cout  <<  s  <<  ' '  <<  ordräkningar  [  s  ]  <<  '\n'  ;  }  returnera  ;  }

När det körs låter programmet användaren skriva en serie ord separerade med mellanslag och ett ord "slut" för att beteckna slutet på inmatningen. Sedan kan användaren mata in ett ord för att fråga hur många gånger det har förekommit i den tidigare inmatade serien.

Ovanstående exempel visar också att operatören [] infogar nya objekt (med standardkonstruktorn) i kartan om det inte finns ett som är associerat med nyckeln. Så integraltyper nollinitieras, strängar initieras till tomma strängar, etc.

Följande exempel illustrerar infogning av element i en karta med infogningsfunktionen och sökning efter en nyckel med hjälp av en kartiterator och sökfunktionen:

 
 
 

 

       
     

    
      
      
      
    
    
    
     
    
     
    
                         
    
    
    
       

    
    

    
          

      
     
      

    
    
      
        
    
              
    
     
    
            
    

    
    
    
     0
 #include  <iostream>  #include  <map>  #include  <utility>  // Att använda make_pair-funktionen  int  main  ()  {  typedef  std  ::  map  <  char  ,  int  >  MapType  ;  MapType  my_map  ;  // Infoga element med hjälp av infogningsfunktionen  my_map  .  infoga  (  std  ::  par  <  char  ,  int  >  (  'a'  ,  1  ));  min_karta  .  infoga  (  std  ::  par  <  char  ,  int  >  (  'b'  ,  2  ));  min_karta  .  infoga  (  std  ::  par  <  char  ,  int  >  (  'c'  ,  3  ));  // Du kan också infoga element på ett annat sätt som visas nedan  // Använda funktionen value_type som tillhandahålls av alla standardcontainrar  my_map  .  insert  (  MapType  ::  value_type  (  'd'  ,  4  ));  // Använda verktygsfunktionen make_pair  my_map  .  infoga  (  std  ::  make_pair  (  'e'  ,  5  ));  // Använda C++11 initializer list  my_map  .  infoga  ({  'f'  ,  6  });  //map-nycklar sorteras automatiskt från lägre till högre.  //Så, my_map.begin() pekar på det lägsta nyckelvärdet inte nyckeln som infogades först.  MapType  ::  iterator  iter  =  min_karta  .  börja  ();  // Radera det första elementet med raderingsfunktionen  my_map  .  radera  (  iter  );  // Mata ut storleken på kartan med storleksfunktionen  std  ::  cout  <<  "  Size of my_map: " <<  my_map  .  storlek  ()  <<  '\n'  ;  std  ::  cout  <<  "Ange en nyckel för att söka efter: "  ;  röding  c  ;  std  ::  cin  >>  c  ;  // find kommer att returnera en iterator till det matchande elementet om det hittas  // eller till slutet av kartan om nyckeln inte hittas  iter  =  my_map  .  hitta  (  c  );  if  (  iter  !=  my_map  .  end  ())  {  std  ::  cout  <<  "Värdet är: "  <<  iter  ->  sekund  <<  '\n'  ;  }  else  {  std  ::  cout  <<  "Nyckeln finns inte i min_karta"  <<  '\n'  ;  }  // Du kan rensa posterna i kartan med hjälp av clear-funktionen  my_map  .  rensa  ();  återvända  ;  }

Exemplet som visas ovan visar användningen av några av funktionerna som tillhandahålls av map , såsom insert() (placera element i kartan), erase() (ta bort element från kartan), find() (kontrollera närvaron av elementet i kartan). behållare) etc.

När programmet körs infogas sex element med hjälp av insert() -funktionen, sedan raderas det första elementet med funktionen erase() och storleken på kartan matas ut. Därefter uppmanas användaren att ange en nyckel att söka efter på kartan. Med hjälp av iteratorn som skapats tidigare find() efter ett element med den givna nyckeln. Om det hittar nyckeln, skriver programmet ut elementets värde. Om den inte hittar den returneras en iterator till slutet av kartan och den visar att nyckeln inte kunde hittas. Slutligen raderas alla element i trädet med clear() .

Iteratorer

Kartor kan använda iteratorer för att peka på specifika element i behållaren. En iterator kan komma åt både nyckeln och det mappade värdet för ett element:


  








 // Deklarerar en map iterator  std  ::  map  <  Key  ,  Value  >::  iterator  it  ;  // Åtkomst till nyckelvärdet  it  ->  first  ;  // Åtkomst till det mappade värdet  it  ->  second  ;  // Iteratorns "värde", som är av typen std::pair<const Key, Value> (  *  it  )  ;

Nedan är ett exempel på att gå igenom en karta för att visa alla nycklar och värden med iteratorer:

 
 

 

       
    
           
         
        
         
     
          
         
    
    
    
         
    
            
              
    
    
    
    
              
    
            
              
    

     0
 #include  <iostream>  #include  <map>  int  main  ()  {  std  ::  map  <  std  ::  string  ,  int  >  data  {  {  "Bobs score"  ,  10  },  {  "Martys score"  ,  15  },  {  "Mehmets score"  ,  34  },  {  "Rockys score"  ,  22  },  // Nästa värden ignoreras eftersom element med samma nycklar redan finns i kartan {  "  Rockys score"  ,  23  },  {  "Mehmets score"  ,  33  }  };  // Iterera över kartan och skriv ut alla nyckel-/värdepar.  for  (  const  auto  &  element  :  data  )  {  std  ::  cout  <<  "Who(key = first): "  <<  element  .  först  ;  std  ::  cout  <<  " Score(värde = sekund): "  <<  element  .  andra  <<  '\n'  ;  } //  Om det behövs kan du iterera över kartan med hjälp av iterator,  //  Observera att iteratorns långa typnamn i detta fall kan ersättas med auto nyckelord  för  (  std  ::  map  <  std  ::  string ,   int  > ::  iterator  iter  =  data  .  begin  ();  iter  !=  data  .  end  ();  ++  iter  )  {  std  ::  cout  <<  "Who(key = first): "  <<  iter  ->  first  ;  std  ::  cout  <<  " Score(value = second): "  <<  iter  ->  second  <<  '\n'  ;  }  returnera  ;  }

För att kompilera ovanstående exempel på GCC-kompilator, måste du använda specifik standardvalflagga.

     g  ++  -  std  =  c  ++  11  källa  .  cpp  -  o  src

Detta kommer att mata ut nycklar och värden för hela kartan, sorterade efter nycklar.

Se även