Sekvensbehållare (C++)

Inom datoranvändning hänvisar sekvensbehållare till en grupp containerklassmallar i standardbiblioteket för programmeringsspråket C++ som implementerar lagring av dataelement . Eftersom de är mallar kan de användas för att lagra godtyckliga element, som heltal eller anpassade klasser. En gemensam egenskap för alla sekventiella behållare är att elementen kan nås sekventiellt. Liksom alla andra standardbibliotekskomponenter finns de i namnutrymmet std .

Följande behållare är definierade i den aktuella versionen av C++-standarden: array , vector , list , forward_list , deque . Var och en av dessa behållare implementerar olika algoritmer för datalagring, vilket innebär att de har olika hastighetsgarantier för olika operationer:

• array implementerar en kompileringstid som inte kan ändras storleksmässigt.
• vektor implementerar en array med snabb slumpmässig åtkomst och en förmåga att automatiskt ändra storlek när element läggs till.
• deque implementerar en dubbelkö med jämförelsevis snabb slumpmässig åtkomst.
• list implementerar en dubbellänkad lista .
• forward_list implementerar en enkellänkad lista .

Eftersom var och en av behållarna måste kunna kopiera sina element för att fungera korrekt, måste typen av element uppfylla kraven CopyConstructible och Assignable . För en given behållare måste alla element tillhöra samma typ. Till exempel kan man inte lagra data i form av både char och int inom samma containerinstans.

Historia

definierades endast vektor , lista och deque . Fram till standardiseringen av C++-språket 1998 var de en del av Standard Template Library (STL), utgiven av SGI . Alexander Stepanov , den primära designern av STL, beklagar valet av namnet vektor och säger att det kommer från de äldre programmeringsspråken Scheme och Lisp men är oförenligt med den matematiska betydelsen av termen.

Arraybehållaren dök först upp i flera böcker under olika namn . Senare införlivades det i ett Boost- bibliotek och föreslogs för inkludering i standard C++-biblioteket. Motivationen för att inkludera en array var att den löser två problem med C-style arrayen: avsaknaden av ett STL-liknande gränssnitt och en oförmåga att kopieras som vilket annat objekt som helst. Det dök först upp i C++ TR1 och inkorporerades senare i C++11 .

Forward_list - behållaren lades till i C++11 som ett utrymmeseffektivt alternativ till list när omvänd iteration inte behövs.

Egenskaper

array , vector och deque stöder alla snabb slumpmässig åtkomst till elementen. list stöder dubbelriktad iteration, medan forward_list endast stöder enkelriktad iteration.

array stöder inte insättning eller borttagning av element. vektor stöder snabb elementinsättning eller borttagning i slutet. Varje infogning eller borttagning av ett element som inte är i slutet av vektorn behöver element mellan infogningspositionen och slutet av vektorn som ska kopieras. Iteratorerna till de påverkade elementen ogiltigförklaras därmed . Faktum är att varje infogning potentiellt kan ogiltigförklara alla iteratorer. Dessutom, om den tilldelade lagringen i vektorn är för liten för att infoga element, allokeras en ny array, alla element kopieras eller flyttas till den nya arrayen och den gamla arrayen frigörs. deque , list och forward_list alla stöder snabb infogning eller borttagning av element var som helst i behållaren. list och forward_list bevarar giltigheten för iteratorer på sådan operation, medan deque ogiltigförklarar dem alla.

Vektor

Elementen i en vektor lagras kontinuerligt. Liksom alla dynamiska arrayimplementeringar har vektorer låg minnesanvändning och bra referenslokalitet och datacacheanvändning . Till skillnad från andra STL-behållare, såsom deques och lists , tillåter vektorer användaren att ange en initial kapacitet för behållaren.

Vektorer tillåter slumpmässig åtkomst ; det vill säga ett element i en vektor kan refereras på samma sätt som element i arrayer (med arrayindex). Länkade listor och uppsättningar stöder å andra sidan inte slumpmässig åtkomst eller pekarritmetik.

Vektordatastrukturen kan snabbt och enkelt allokera det nödvändiga minnet som behövs för specifik datalagring, och den kan göra det i avskriven konstant tid. Detta är särskilt användbart för att lagra data i listor vars längd kanske inte är känd innan listan ställs in men där borttagning (annat än kanske i slutet) är sällsynt. Att radera element från en vektor eller till och med rensa vektorn helt frigör inte nödvändigtvis något av minnet som är associerat med det elementet.

Kapacitet och omfördelning

En typisk vektorimplementering består, internt, av en pekare till en dynamiskt allokerad array, och möjligen datamedlemmar som håller vektorns kapacitet och storlek. Storleken på vektorn hänvisar till det faktiska antalet element, medan kapaciteten hänvisar till storleken på den interna arrayen.

När nya element infogas, om den nya storleken på vektorn blir större än dess kapacitet, sker omallokering . Detta får vanligtvis vektorn att allokera en ny lagringsregion, flytta de tidigare hållna elementen till den nya lagringsregionen och frigöra den gamla regionen.

Eftersom adresserna till elementen ändras under denna process, blir alla referenser eller iteratorer till element i vektorn ogiltiga. Att använda en ogiltig referens orsakar odefinierat beteende .

Operationen reserve() kan användas för att förhindra onödiga omfördelningar. Efter ett anrop till reserve(n) är vektorns kapacitet garanterat minst n.

Vektorn bibehåller en viss ordning av sina element, så att när ett nytt element infogas i början eller i mitten av vektorn, flyttas efterföljande element bakåt vad gäller deras tilldelningsoperator eller kopieringskonstruktor . Följaktligen blir referenser och iteratorer till element efter insättningspunkten ogiltiga.

C++-vektorer stöder inte in-place omallokering av minne, genom design; dvs, vid omallokering av en vektor, kommer minnet den höll alltid att kopieras till ett nytt minnesblock med hjälp av dess elements kopieringskonstruktor och sedan släppas. Detta är ineffektivt för fall där vektorn innehåller vanliga gamla data och ytterligare angränsande utrymme bortom det hållna minnesblocket är tillgängligt för allokering.

Specialisering för bool

Standardbiblioteket definierar en specialisering av vektormallen för bool . Beskrivningen av denna specialisering indikerar att implementeringen bör packa elementen så att varje bool bara använder en bit minne. Detta anses allmänt vara ett misstag. vector<bool> uppfyller inte kraven för en C++ Standard Library- behållare. Till exempel måste en container<T>::referens vara ett sant lvärde av typen T . Detta är inte fallet med vector<bool>::reference , som är en proxyklass som kan konverteras till bool . På liknande sätt vektorn<bool>::iteratorn ingen bool& när den avreferens . Det finns en allmän konsensus bland C++ Standard Committee och Library Working Group att vektor<bool> bör fasas ut och därefter tas bort från standardbiblioteket, medan funktionaliteten kommer att återinföras under ett annat namn.

Lista

Listdatastrukturen implementerar en dubbellänkad lista . Data lagras icke sammanhängande i minnet, vilket tillåter listdatastrukturen att undvika omfördelning av minne som kan vara nödvändig med vektorer när nya element infogas i listan.

Listdatastrukturen allokerar och avallokerar minne efter behov; därför allokerar den inte minne som den inte använder för närvarande. Minnet frigörs när ett element tas bort från listan.

Listor är effektiva när du infogar nya element i listan; detta är en $O(1)$ operation. Ingen växling krävs som med vektorer.

Listor har inte slumpmässig tillgång som vektorer ( $O(1)$ operation). Att komma åt en nod i en lista är en $O(n)$ operation som kräver en genomgång av listan för att hitta den nod som behöver nås.

Med små datatyper (som ints) är minnesoverheaden mycket mer betydande än för en vektor. Varje nod tar upp sizeof (typ) + 2 * sizeof (typ*) . Pekare är vanligtvis ett ord (vanligtvis fyra byte under 32-bitars operativsystem), vilket betyder att en lista med fyra byte heltal tar upp ungefär tre gånger så mycket minne som en vektor med heltal.

Framåtlista

Forward_list- datastrukturen implementerar en enkellänkad lista .

Deque

deque är en containerklassmall som implementerar en dubbeländad kö . Det ger liknande beräkningskomplexitet som vektor för de flesta operationer, med det anmärkningsvärda undantaget att det tillhandahåller amorterad konstanttidsinsättning och borttagning från båda ändarna av elementsekvensen. Till skillnad från vektor använder deque diskontinuerliga minnesblock och ger inget sätt att kontrollera kapaciteten hos behållaren och ögonblicket för omfördelning av minne . Precis som vektor erbjuder deque stöd för iteratorer med slumpmässig åtkomst , och insättning och borttagning av element ogiltigförklarar alla iteratorer till dequen.

Array

array implementerar en array som inte kan ändras storlek . Storleken bestäms vid kompilering av en mallparameter. Genom designen stöder behållaren inte allokatorer eftersom det i grund och botten är en array-omslag i C-stil.

Översikt över funktioner

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

Medlemsfunktioner

Funktioner	array ( C++11 )	vektor	deque	lista	forward_list ( C++11 )	Beskrivning
Grunderna	(implicit)	(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 behållaren och de inneslutna elementen
		operator=	operator=	operator=	operator=	Tilldelar värden till behållaren
	—	tilldela	tilldela	tilldela	tilldela	Tilldelar värden till behållaren
Tilldelare		get_allocator	get_allocator	get_allocator	get_allocator	Returnerar allokatorn som används för att allokera minne för elementen
Elementåtkomst _	på	på	på	—	—	Åtkomst till specificerat element med gränskontroll.
	operatör[ ]	operatör[ ]	operatör[ ]			Åtkomst till specificerat element utan gränskontroll.
	främre	främre	främre	främre	främre	Åtkomst till det första elementet
	tillbaka	tillbaka	tillbaka	tillbaka	—	Åtkomst till det sista elementet
	data	data	—	—		Åtkomst till den underliggande arrayen
Iteratorer	börja cbörja	börja cbörja	börja cbörja	börja cbörja	börja cbörja	Returnerar en iterator till början av behållaren
	slut cend	slut cend	slut cend	slut cend	slut cend	Returnerar en iterator till slutet av behållaren
	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin	—	Returnerar en omvänd iterator till den omvända början av behållaren
	bryta upp	bryta upp	bryta upp	bryta upp		Returnerar en omvänd iterator till den omvända änden av behållaren
Kapacitet	tömma	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	max_size	Returnerar det högsta möjliga antalet element i behållaren.
	—	boka	—	—	—	Reserverar förvaring i behållaren
		kapacitet				Returnerar antalet element som kan hållas i för närvarande allokerad lagring
		krymp för att passa	krymp för att passa			Minskar minnesanvändning genom att frigöra oanvänt minne ( C++11 )
Modifierare		klar	klar	klar	klar	Rensar innehållet
		Föra in	Föra in	Föra in	—	Infogar element
		placera	placera	placera		Konstruerar element på plats ( C++11 )
		radera	radera	radera		Raderar element
		—	push_front	push_front	push_front	Infogar element i början
			emplace_front	emplace_front	emplace_front	Konstruerar element på plats i början ( C++11 )
			pop_front	pop_front	pop_front	Tar bort det första elementet
		trycka tillbaka	trycka tillbaka	trycka tillbaka	—	Infogar element till slutet
		emplace_back	emplace_back	emplace_back		Konstruerar element på plats i slutet ( C++11 )
		pop_back	pop_back	pop_back		Tar bort det sista elementet
		—	—	—	infoga_efter	Infogar element efter angiven position ( C++11 )
					emplace_after	Konstruerar element på plats efter angiven position ( C++11 )
					radera_efter	Raderar element på plats efter angiven position ( C++11 )
		ändra storlek	ändra storlek	ändra storlek	ändra storlek	Ändrar antalet lagrade element
	byta	byta	byta	byta	byta	Byter innehållet med en annan behållare av samma typ
	fylla	—	—	—	—	Fyller arrayen med det angivna värdet

Det finns andra operationer som är tillgängliga som en del av listklassen och det finns algoritmer som är en del av C++ STL ( Algorithm (C++) ) som kan användas med klassen list och forward_list :

Operationer

• list::merge och forward_list::merge - Sammanfogar två sorterade listor
• list::splice och forward_list::splice_after - Flyttar element från en annan lista
• list::remove och forward_list::remove - Tar bort element lika med det givna värdet
• list::remove_if och forward_list::remove_if - Tar bort element som uppfyller specifika kriterier
• list::reverse och forward_list::reverse - Vänder om ordningen på elementen
• list::unique och forward_list::unique - Tar bort på varandra följande dubbletter av element
• list::sort och forward_list::sort - Sorterar elementen

Användningsexempel

Följande exempel visar olika tekniker som involverar en vektor och C++ Standard Library- algoritmer, framför allt att blanda , sortera , hitta det största elementet och radera från en vektor med radera-ta bort idiom .

 
 
 
 
 
 


  

 

        

  
    

  
  
  
  
  
  

  
   
  
  
      
  
        
         
  
  
   

  
         
  
         
  
  
  
    
              
                      
  
  
       
        
 #inkludera  <iostream>  #inkludera  <vektor>  #inkludera  <array>  #inkludera  <algoritm>  // sortera, max_element, random_shuffle, remove_if, nedre_gräns  #inkludera  <funktionell>  // större  #inkludera  <iterator>  // start, end, cbegin, cend, distans  // används här för bekvämlighet, använd klokt i riktiga program.  använder  namnutrymme  std  ;  int  main  ()  {  array  arr  {  1  ,  2  ,  3  ,  4  };  // initiera en vektor från en arrayvektor  <  int  >  numbers  (  cbegin  (  arr  )  ,  cend  (  arr  ));  // infoga fler siffror i  vektornumren  .  push_back  (  5  );  siffror  .  push_back  (  6  );  siffror  .  push_back  (  7  );  siffror  .  push_back  (  8  );  // vektorn håller för närvarande { 1, 2, 3, 4, 5, 6, 7, 8 }  // blanda slumpmässigt elementen  shuffle  (  börja  (  siffror  ),  slut  (  siffror  ));  // lokalisera det största elementet, O(n)  auto  största  =  max_element  (  cbegin  (  siffror  ),  cend  (  siffror  ));  cout  <<  "Det största antalet är "  <<  *  största  <<  "  \n  "  ;  cout  <<  "Det ligger vid index"  <<  avstånd  (  störst  ,  cbegin  (  siffror  ))  <<  "  \n  "  ;  // sortera elementen  sortera  (  börja  (  siffror  ),  slut  (  siffror  ));  // hitta positionen för talet 5 i vektorn  auto  fem  =  nedre_gräns  (  cbegin  (  siffror  ),  cend  (  siffror  ) ,   5  );  cout  <<  "Siffran 5 finns vid index"  <<  avstånd  (  fem  ,  cbegin  (  siffror  ))  <<  '\  n  '  ;  // radera alla element som är större än 4  siffror  .  radera  (  remove_if  (  börja  (  siffror  ),  slut  (  siffror  ),  [](  auto  n  )  constexpr  {  return  n  >  4  ;  });  // skriv ut alla återstående siffror  för  (  const  auto  &  element  :  numbers  )  cout  <<  element  <<  ""  ;  } 

Utgången blir följande:

Det största antalet är 8 Det är placerat på index 6 (implementationsberoende) Antalet 5 är placerat vid index 4 1 2 3 4

•   William Ford, William Topp. Datastrukturer med C++ och STL, andra upplagan. Prentice Hall, 2002. ISBN 0-13-085850-1 . Kapitel 4: Vektorklassen, s. 195–203.
•   Josuttis, Nicolai M. (1999). C++ standardbiblioteket . Addison-Wesley. ISBN 0-201-37926-0 .