Kontener sekwencji (C++)

W informatyce kontenery sekwencji odnoszą się do grupy szablonów klas kontenerów w standardowej bibliotece języka programowania C++ , które implementują przechowywanie elementów danych. Będąc szablonami , można ich używać do przechowywania dowolnych elementów, takich jak liczby całkowite lub niestandardowe klasy. Wspólną właściwością wszystkich kontenerów sekwencyjnych jest to, że dostęp do elementów można uzyskać sekwencyjnie. Podobnie jak wszystkie inne komponenty biblioteki standardowej, znajdują się one w przestrzeni nazw std .

Następujące kontenery są zdefiniowane w bieżącej wersji standardu C++: array , vector , list , forward_list , deque . Każdy z tych kontenerów implementuje inne algorytmy przechowywania danych, co oznacza, że mają różne gwarancje prędkości dla różnych operacji:

array implementuje tablicę o niezmiennym rozmiarze w czasie kompilacji.
vector implementuje tablicę z szybkim dostępem losowym i możliwością automatycznej zmiany rozmiaru podczas dołączania elementów.
deque implementuje dwustronną kolejkę ze stosunkowo szybkim dostępem losowym.
list implementuje podwójnie połączoną listę .
forward_list implementuje pojedynczo połączoną listę .

Ponieważ każdy z kontenerów musi mieć możliwość kopiowania swoich elementów, aby działał poprawnie, typ elementów musi spełniać wymagania CopyConstructible i Assignable . Dla danego kontenera wszystkie elementy muszą należeć do tego samego typu. Na przykład nie można przechowywać danych zarówno w postaci char , jak i int w tej samej instancji kontenera.

Historia

zdefiniowano tylko vector , list i deque . Do czasu standaryzacji języka C++ w 1998 roku były one częścią Standardowej Biblioteki Szablonów (STL), publikowanej przez SGI . Alexander Stepanov , główny projektant STL, ubolewa nad wyborem nazwy vector , mówiąc, że pochodzi ona ze starszych języków programowania Scheme i Lisp , ale jest niezgodna z matematycznym znaczeniem tego terminu.

Kontener tablicy pojawił się najpierw w kilku książkach pod różnymi nazwami. Później został włączony do Boost i zaproponowano włączenie do standardowej biblioteki C++. Motywacją do włączenia tablicy było to, że rozwiązuje ona dwa problemy tablicy w stylu C: brak interfejsu podobnego do STL i niemożność kopiowania jak każdy inny obiekt. Po raz pierwszy pojawił się w C++ TR1 , a później został włączony do C++11 .

Kontener forward_list został dodany do języka C++ 11 jako wydajna pod względem miejsca alternatywa dla listy , gdy iteracja odwrotna nie jest potrzebna.

Nieruchomości

array , vector i deque obsługują szybki losowy dostęp do elementów. list obsługuje iterację dwukierunkową, podczas gdy forward_list obsługuje tylko iterację jednokierunkową.

array nie obsługuje wstawiania ani usuwania elementów. vector obsługuje szybkie wstawianie lub usuwanie elementów na końcu. Każde wstawienie lub usunięcie elementu, który nie znajduje się na końcu wektora, wymaga skopiowania elementów między pozycją wstawienia a końcem wektora. Iteratory do elementów, których to dotyczy, są w ten sposób unieważnione . W rzeczywistości każde wstawienie może potencjalnie unieważnić wszystkie iteratory. Ponadto, jeśli przydzielona pamięć w wektorze jest zbyt mała, aby wstawić elementy, przydzielana jest nowa tablica, wszystkie elementy są kopiowane lub przenoszone do nowej tablicy, a stara tablica jest zwalniana. deque , list i forward_list obsługują szybkie wstawianie i usuwanie elementów w dowolnym miejscu kontenera. list i forward_list zachowują ważność iteratorów w takiej operacji, podczas gdy deque unieważnia je wszystkie.

Wektor

Elementy wektora są przechowywane w sposób ciągły. Podobnie jak wszystkie tablic dynamicznych , wektory mają niskie zużycie pamięci i dobrą lokalizację odniesienia oraz wykorzystanie pamięci podręcznej danych . W przeciwieństwie do innych kontenerów STL, takich jak deques i lists , wektory pozwalają użytkownikowi określić początkową pojemność kontenera.

Wektory umożliwiają swobodny dostęp ; to znaczy, do elementu wektora można odwoływać się w taki sam sposób, jak do elementów tablic (przez indeksy tablic). połączone listy i zestawy nie obsługują dostępu swobodnego ani arytmetyki wskaźników.

Wektorowa struktura danych jest w stanie szybko i łatwo przydzielić niezbędną pamięć potrzebną do przechowywania określonych danych i jest w stanie to zrobić w zamortyzowanym stałym czasie. Jest to szczególnie przydatne do przechowywania danych na listach, których długość może nie być znana przed utworzeniem listy, ale gdzie usuwanie (inne niż być może na końcu) jest rzadkie. Wymazanie elementów z wektora lub nawet całkowite wyczyszczenie wektora niekoniecznie zwalnia jakąkolwiek pamięć związaną z tym elementem.

Pojemność i realokacja

Typowa implementacja wektora składa się wewnętrznie ze wskaźnika do dynamicznie przydzielanej tablicy i ewentualnie elementów danych przechowujących pojemność i rozmiar wektora. Rozmiar wektora odnosi się do rzeczywistej liczby elementów, podczas gdy pojemność odnosi się do rozmiaru wewnętrznej tablicy.

Po wstawieniu nowych elementów, jeśli nowy rozmiar wektora staje się większy niż jego pojemność, następuje ponowna alokacja . Zwykle powoduje to, że wektor przydziela nowy region pamięci, przenosi poprzednio przechowywane elementy do nowego regionu pamięci i zwalnia stary region.

Ponieważ adresy elementów zmieniają się podczas tego procesu, wszelkie odwołania lub iteratory do elementów w wektorze stają się nieważne. Użycie unieważnionego odwołania powoduje niezdefiniowane zachowanie .

Operacja Reserve() może być wykorzystana do zapobiegania niepotrzebnym ponownym alokacjom. Po wywołaniu funkcji Reserve(n) gwarantowana pojemność wektora wynosi co najmniej n.

Wektor zachowuje pewną kolejność swoich elementów, dzięki czemu po wstawieniu nowego elementu na początku lub w środku wektora kolejne elementy są cofane pod względem ich operatora przypisania lub konstruktora kopiującego . W konsekwencji odwołania i iteratory do elementów po punkcie wstawiania stają się nieważne.

Wektory języka C++ zgodnie z projektem nie obsługują realokacji pamięci w miejscu; tj. po ponownym przydzieleniu wektora, przechowywana w nim pamięć będzie zawsze kopiowana do nowego bloku pamięci przy użyciu konstruktora kopiującego jego elementów, a następnie zwalniana. Jest to nieefektywne w przypadkach, gdy wektor zawiera zwykłe stare dane , a dodatkowa ciągła przestrzeń poza przechowywanym blokiem pamięci jest dostępna do alokacji.

Specjalizacja dla bool

Biblioteka standardowa definiuje specjalizację szablonu wektora dla bool . Z opisu tej specjalizacji wynika, że implementacja powinna spakować elementy tak, aby każdy bool zajmował tylko jeden bit pamięci. Jest to powszechnie uważane za błąd. vector<bool> nie spełnia wymagań dotyczących kontenera standardowej biblioteki języka C++ . Na przykład container<T>::reference musi być prawdziwą wartością typu T . Inaczej jest w przypadku vector<bool>::reference , która jest klasą proxy konwertowalną na bool . Podobnie vector<bool>::iterator nie zwraca bool& po dereferencji . Wśród C++ Standard Committee i Library Working Group istnieje ogólna zgoda co do tego, że vector<bool> powinien zostać uznany za przestarzały, a następnie usunięty ze standardowej biblioteki, podczas gdy funkcjonalność zostanie ponownie wprowadzona pod inną nazwą.

Lista

Struktura danych listy implementuje listę podwójnie połączoną . Dane są przechowywane w pamięci w sposób nieciągły, co pozwala strukturze danych listy uniknąć ponownego przydziału pamięci, który może być konieczny w przypadku wektorów, gdy nowe elementy są wstawiane do listy.

Struktura danych listy przydziela i zwalnia pamięć zgodnie z potrzebami; w związku z tym nie przydziela pamięci, której aktualnie nie używa. Pamięć jest zwalniana, gdy element jest usuwany z listy.

Listy są wydajne podczas wstawiania nowych elementów do listy; jest to ${\ Displaystyle O (1)}$ . Nie jest wymagane przesuwanie, jak w przypadku wektorów.

Listy nie mają możliwości dostępu swobodnego, jak wektory ( operacja ${\ Displaystyle O (1)} ).$ Dostęp do węzła na liście jest $przeglądania$ listy w celu znalezienia węzła, do którego należy

W przypadku małych typów danych (takich jak int) narzut pamięci jest znacznie większy niż w przypadku wektora. Każdy węzeł zajmuje sizeof (type) + 2 * sizeof (type*) . Wskaźniki to zwykle jedno słowo (zwykle cztery bajty w 32-bitowych systemach operacyjnych), co oznacza, że lista czterobajtowych liczb całkowitych zajmuje około trzy razy więcej pamięci niż wektor liczb całkowitych.

Lista do przodu

Struktura danych forward_list implementuje pojedynczo połączoną listę .

Deque

deque to szablon klasy kontenera, który implementuje dwustronną kolejkę . Zapewnia podobną złożoność obliczeniową do wektora dla większości operacji, z godnym uwagi wyjątkiem, że zapewnia amortyzowane wstawianie i usuwanie w stałym czasie z obu końców sekwencji elementów. W przeciwieństwie do vector , deque używa nieciągłych bloków pamięci i nie zapewnia środków do kontrolowania pojemności kontenera i momentu ponownego przydziału pamięci. Podobnie jak vector , deque oferuje wsparcie dla iteratory o swobodnym dostępie , a wstawianie i usuwanie elementów unieważnia wszystkie iteratory do deque.

Szyk

array implementuje tablicę o niezmiennym rozmiarze . Rozmiar jest określany w czasie kompilacji przez parametr szablonu. Z założenia kontener nie obsługuje alokatorów , ponieważ jest to w zasadzie opakowanie tablicy w stylu C.

Przegląd funkcji

Kontenery są zdefiniowane w nagłówkach nazwanych po nazwach kontenerów, np. wektor jest zdefiniowany w nagłówku <wektor> . Wszystkie kontenery spełniają wymagania koncepcji Container , co oznacza, że mają metody begin() , end() , size() , max_size() , empty() i swap() .

Funkcje członkowskie

Funkcje	`tablica` ( C++ 11 )	`wektor`	`deque`	`lista`	`forward_list` ( C++ 11 )	Opis
Podstawy	(domniemany)	(konstruktor)	(konstruktor)	(konstruktor)	(konstruktor)	Konstruuje pojemnik z różnych źródeł
		(burzyciel)	(burzyciel)	(burzyciel)	(burzyciel)	Niszczy kontener i zawarte w nim elementy
		`operator=`	`operator=`	`operator=`	`operator=`	Przypisuje wartości do kontenera
	—	`przydzielać`	`przydzielać`	`przydzielać`	`przydzielać`	Przypisuje wartości do kontenera
Alokatory	—	`get_allocator`	`get_allocator`	`get_allocator`	`get_allocator`	Zwraca alokator używany do przydzielania pamięci dla elementów
Dostęp do elementu	`Na`	`Na`	`Na`	—	—	Uzyskuje dostęp do określonego elementu ze sprawdzaniem granic.
	`operator[ ]`	`operator[ ]`	`operator[ ]`	—	—	Uzyskuje dostęp do określonego elementu bez sprawdzania granic.
	`przód`	`przód`	`przód`	`przód`	`przód`	Uzyskuje dostęp do pierwszego elementu
	`z powrotem`	`z powrotem`	`z powrotem`	`z powrotem`	—	Dostęp do ostatniego elementu
	`dane`	`dane`	—	—	—	Uzyskuje dostęp do podstawowej tablicy
Iteratory	`zacząć czacząć`	`zacząć czacząć`	`zacząć czacząć`	`zacząć czacząć`	`zacząć czacząć`	Zwraca iterator na początek kontenera
	`koniec cend`	`koniec cend`	`koniec cend`	`koniec cend`	`koniec cend`	Zwraca iterator na koniec kontenera
	`rozpocznij rozpocznij`	`rozpocznij rozpocznij`	`rozpocznij rozpocznij`	`rozpocznij rozpocznij`	—	Zwraca odwrotny iterator do odwrotnego początku kontenera
	`rend crend`	`rend crend`	`rend crend`	`rend crend`	—	Zwraca odwrotny iterator do odwrotnego końca kontenera
Pojemność	`pusty`	`pusty`	`pusty`	`pusty`	`pusty`	Sprawdza, czy pojemnik jest pusty
	`rozmiar`	`rozmiar`	`rozmiar`	`rozmiar`	—	Zwraca liczbę elementów w kontenerze.
	`największy rozmiar`	`największy rozmiar`	`największy rozmiar`	`największy rozmiar`	`największy rozmiar`	Zwraca maksymalną możliwą liczbę elementów w kontenerze.
	—	`rezerwa`	—	—	—	Rezerwuje miejsce w kontenerze
		`pojemność`	—			Zwraca liczbę elementów, które mogą być przechowywane w aktualnie przydzielonym magazynie
		`skurcz_do_dopasowania`	`skurcz_do_dopasowania`			Zmniejsza zużycie pamięci, zwalniając nieużywaną pamięć ( C++ 11 )
Modyfikatory		`jasne`	`jasne`	`jasne`	`jasne`	Czyści zawartość
		`wstawić`	`wstawić`	`wstawić`	—	Wstawia elementy
		`miejsce`	`miejsce`	`miejsce`		Konstruuje elementy w miejscu ( C++ 11 )
		`usuwać`	`usuwać`	`usuwać`		Wymazuje elementy
		—	`push_front`	`push_front`	`push_front`	Wstawia elementy na początek
			`miejsce_frontowe`	`miejsce_frontowe`	`miejsce_frontowe`	Konstruuje elementy na miejscu na początku ( C++ 11 )
			`pop_front`	`pop_front`	`pop_front`	Usuwa pierwszy element
		`push_back`	`push_back`	`push_back`	—	Wstawia elementy do końca
		`miejsce_z powrotem`	`miejsce_z powrotem`	`miejsce_z powrotem`		Konstruuje elementy na miejscu na końcu ( C++ 11 )
		`pop_back`	`pop_back`	`pop_back`		Usuwa ostatni element
		—	—	—	`wstaw_po`	Wstawia elementy po określonej pozycji ( C++ 11 )
					`miejsce_po`	Konstruuje elementy w miejscu po określonej pozycji ( C++ 11 )
					`wymaż_po`	Usuwa elementy w miejscu po określonej pozycji ( C++ 11 )
		`Zmień rozmiar`	`Zmień rozmiar`	`Zmień rozmiar`	`Zmień rozmiar`	Zmienia liczbę przechowywanych elementów
	`zamieniać`	`zamieniać`	`zamieniać`	`zamieniać`	`zamieniać`	Zamienia zawartość na inny kontener tego samego typu
	`wypełnić`	—	—	—	—	Wypełnia tablicę podaną wartością

Istnieją inne operacje, które są dostępne jako część klasy list i istnieją algorytmy, które są częścią C++ STL ( Algorithm (C++) ), których można używać z klasą list i forward_list :

Operacje

list::merge i forward_list::merge — Scala dwie posortowane listy
list::splice i forward_list::splice_after - Przenosi elementy z innej listy
list::remove i forward_list::remove - Usuwa elementy równe podanej wartości
list::remove_if i forward_list::remove_if - Usuwa elementy spełniające określone kryteria
list::reverse and forward_list::reverse - Odwraca kolejność elementów
list::unique i forward_list::unique — Usuwa kolejne zduplikowane elementy
list::sort i forward_list::sort — Sortuje elementy

Funkcje niebędące członkami

Przykład użycia

Poniższy przykład ilustruje różne techniki obejmujące algorytmy wektora i standardowej biblioteki C++ , w szczególności shuffling , sorting , znajdowanie największego elementu i wymazywanie z wektora przy użyciu idiomu wymazywania-usuwania .

 
 
 
 
 
 


  

 

     #include  <iostream>  #include  <wektor>  #include  <tablica>  #include  <algorithm>  // sort, max_element, random_shuffle, remove_if, low_bound  #include  <funkcjonalne>  // większe  #include  <iterator>  // początek, koniec, cbegin, cend, distance  // użyte tutaj dla wygody, używaj rozsądnie w rzeczywistych programach.  używając  przestrzeni nazw  std  ;  int  main  ()  {  tablica  tablica  {  1     

  
    

  
  
  
   ,  2  ,  3  ,  4  };  // inicjalizacja wektora z tablicy  vector  <  int  >  numbers  (  cbegin  (  arr  ),  cend  (  arr  )); // wstaw więcej liczb do   numerów  wektorów  .  push_back  (  5  );  liczby  .  push_back  (  6  );  liczby  .  push_back  (  7  ); 
  
  

  
   
  
  
      
  
    liczby  .  push_back  (  8  );  // obecnie wektor zawiera { 1, 2, 3, 4, 5, 6, 7, 8 }  // losowo przetasuj elementy  shuffle  (  begin  (  numery  ),  koniec  (  liczby  ));  // znajdź największy element, O(n)  auto  największy  =  max_element  (  cbegin  (  liczby  ),  cend  (  liczby  ));  cos  <<      
         
  
  
    "Największa liczba to "  <<  *  największa  <<  "  \n  "  ;  cout  <<  "Znajduje sie pod indeksem "  <<  odleglosc  (  najwieksza  ,  cbegin  (  liczby  ))  <<  "  \n  "  ;  // sortowanie elementów  sort  (  begin  (  liczby  ),  koniec  (  liczby  )); 

  
         
  
         
  
  
   // znajdź pozycję liczby 5 w wektorze  auto  five  =  lower_bound  (  cbegin  (  liczby  ),  cend  (  liczby  ),  5  );  cout  <<  "Liczba 5 znajduje sie w indeksie "  <<  odleglosc  (  piec  ,  cbegin  (  liczby  ))  <<  '\  n  '  ;  // usuń wszystkie elementy większe niż 4  liczby  . 
    
              
                      
  
  
       
        
 kasuj  (  usuń_jeśli  (  początek  (  liczby  ),  koniec  (  liczby  ),  [] (  auto  n  )  constexpr  {  return  n  >  4  ;  });  // wypisz wszystkie pozostałe liczby  dla  (  const  auto  &  element  :  liczby  )  cout  <<  element  <<  " "  ;  }

Dane wyjściowe będą następujące:

Największa liczba to 8 Znajduje się pod indeksem 6 (w zależności od implementacji) Liczba 5 znajduje się pod indeksem 4 1 2 3 4

Williama Forda, Williama Toppa. Struktury danych w C++ i STL , wydanie drugie. Prentice Hall, 2002. ISBN 0-13-085850-1 . Rozdział 4: Klasa Vector, s. 195–203.
Josuttis, Nicolai M. (1999). Standardowa biblioteka C++ . Addison-Wesley. ISBN 0-201-37926-0 .

Notatki