Sekvenční kontejner (C ++) - Sequence container (C++)

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: Podívejte se na rozhovor Prosím pomozte vylepšit tento článek jestli můžeš. (Prosinec 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Ve výpočetní technice, sekvenční kontejnery odkazují na skupinu kontejner šablony tříd v standardní knihovna z Programovací jazyk C ++ které implementují ukládání datových prvků. Bytost šablony, lze je použít k ukládání libovolných prvků, jako jsou celá čísla nebo vlastní třídy. Jedna společná vlastnost všech sekvenčních kontejnerů je, že k prvkům lze přistupovat sekvenčně. Stejně jako všechny ostatní standardní součásti knihovny jsou umístěny jmenný prostor std.

V aktuální revizi standardu C ++ jsou definovány následující kontejnery: pole, vektor, seznam, forward_list, deque. Každý z těchto kontejnerů implementuje různé algoritmy pro ukládání dat, což znamená, že mají různé záruky rychlosti pro různé operace:^[1]

• pole implementuje nezměnitelné pole v době kompilace.
• vektor implementuje pole rychle náhodný přístup a schopnost automaticky měnit velikost při připojování prvků.
• deque implementuje a oboustranná fronta s poměrně rychlým náhodným přístupem.
• seznam implementuje a dvojnásobně propojený seznam.
• forward_list implementuje a jednotlivě propojený seznam.

Protože každý z kontejnerů musí být schopen kopírovat své prvky, aby správně fungoval, musí typ prvků splňovat CopyConstructible a Přiřaditelné požadavky.^[2] U daného kontejneru musí všechny prvky patřit stejnému typu. Například nelze ukládat data ve formě obou char a int ve stejné instanci kontejneru.

Dějiny

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Prosinec 2011)

Původně pouze vektor, seznam a deque byly definovány. Do standardizace jazyka C ++ v roce 1998 byly součástí Standardní knihovna šablon (STL), publikoval SGI.

The pole kontejner se nejprve objevil v několika knihách pod různými jmény. Později byl začleněn do Zvýšit knihovny a bylo navrženo pro zařazení do standardní knihovny C ++. Motivace pro začlenění pole bylo, že řeší dva problémy pole ve stylu C: nedostatek rozhraní podobného STL a neschopnost být kopírován jako jakýkoli jiný objekt. Nejprve se objevil v C ++ TR1 a později byla začleněna do C ++ 11.

The forward_list kontejner byl přidán do C ++ 11 jako prostorově efektivní alternativa k seznam když není potřeba reverzní iterace.

Vlastnosti

pole, vektor a deque všechny podporují rychlý náhodný přístup k prvkům. seznam podporuje obousměrnou iteraci, zatímco forward_list podporuje pouze jednosměrnou iteraci.

pole nepodporuje vložení nebo vyjmutí prvku. vektor podporuje rychlé vložení nebo vyjmutí prvku na konci. Jakékoli vložení nebo odebrání prvku, který není na konci vektoru, vyžaduje kopírování prvků mezi pozicí vložení a koncem vektoru. The iterátory k ovlivněným prvkům jsou tedy zneplatněny. Ve skutečnosti může jakékoli vložení potenciálně zneplatnit všechny iterátory. Také, pokud přidělené úložiště v vektor je příliš malý na vložení prvků, je přiděleno nové pole, všechny prvky jsou zkopírovány nebo přesunuty do nového pole a staré pole je uvolněno. deque, seznam a forward_list všechny podporují rychlé vkládání nebo vyjímání prvků kdekoli v kontejneru. seznam a forward_list zachovává platnost iterátorů pro tuto operaci, zatímco deque zruší platnost všech z nich.

Vektor

Prvky a vektor jsou uloženy souvisle.^[3] Jako všichni dynamické pole implementace, vektory mají nízké využití paměti a dobré referenční lokalita a datová mezipaměť využití. Na rozdíl od jiných kontejnerů STL, jako jsou deques a seznamy vektory umožňují uživateli označit počáteční kapacitu kontejneru.

Vektory umožňují náhodný přístup; to znamená, že na prvek vektoru lze odkazovat stejným způsobem jako na prvky polí (pomocí indexů pole). Propojené seznamy a sady, na druhou stranu nepodporují náhodný přístup ani aritmetiku ukazatele.

Struktura vektorových dat je schopna rychle a snadno alokovat potřebnou paměť potřebnou pro uložení konkrétních dat a je schopna tak učinit v amortizované konstantní době. To je zvláště užitečné pro ukládání dat v seznamech, jejichž délka nemusí být známa před vytvořením seznamu, ale kde je odstranění (jiné než, možná na konci) vzácné. Vymazání prvků z vektoru nebo dokonce úplné vymazání vektoru nemusí nutně uvolnit paměť spojenou s tímto prvkem.

Kapacita a přerozdělení

Typická vektorová implementace se interně skládá z ukazatele na a dynamicky přiděleno pole,^[1] a případně datové členy, které drží kapacitu a velikost vektoru. Velikost vektoru odpovídá skutečnému počtu prvků, zatímco kapacita odpovídá velikosti vnitřního pole.

Když se při vkládání nových prvků zvětší nová velikost vektoru nad jeho kapacitu, přerozdělení dojde.^[1][4] To obvykle způsobí, že vektor přidělí novou oblast úložiště, přesune dříve držené prvky do nové oblasti úložiště a uvolní starou oblast.

Protože adresy prvků se během tohoto procesu změní, jakékoli odkazy nebo iterátory prvky ve vektoru budou zneplatněny.^[5] Použití zneplatněných referenčních příčin nedefinované chování.

Operaci rezervy () lze použít k zabránění zbytečnému přerozdělování. Po volání rezervy (n) je kapacita vektoru zaručena minimálně n.^[6]

Vektor udržuje určité pořadí svých prvků, takže když se nový prvek vloží na začátek nebo do středu vektoru, následující prvky se posunou dozadu, pokud jde o jejich operátor přiřazení nebo kopírovací konstruktor. V důsledku toho se odkazy a iterátory na prvky za kurzorem zneplatní.^[7]

Vektory C ++ nepodporují záměrné přerozdělení paměti na místě; tj. při realokaci vektoru bude paměť, kterou drží, vždy zkopírována do nového bloku paměti pomocí konstruktoru kopírování jejích prvků a poté uvolněna. To je neúčinné pro případy, kdy vektor drží prostá stará data a pro přidělení je k dispozici další souvislý prostor za zadrženým blokem paměti.

Specializace na bool

Standardní knihovna definuje specializaci vektor šablona pro bool. Popis této specializace naznačuje, že implementace by měla zabalit prvky tak, aby každý bool používá pouze jeden bit paměti.^[8] To je obecně považováno za chybu.^[9][10] vector nesplňuje požadavky a Standardní knihovna C ++ kontejner. Například a kontejner :: reference musí být pravda lhodnota typu T. To není případ vector :: reference, což je třída proxy převoditelný na bool.^[11] Podobně vector :: iterátor nepřináší a bool & když odhlášeno. Mezi Výborem pro standardy C ++ a Pracovní skupinou pro knihovny existuje obecná shoda vector by měl být zastaralý a následně odstraněn ze standardní knihovny, zatímco funkce bude znovu zavedena pod jiným názvem.^[12]

Seznam

The seznam datová struktura implementuje a dvojnásobně propojený seznam. Data se nekontinuálně ukládají do paměti, což umožňuje struktuře dat seznamu zabránit přerozdělení paměti, které může být nezbytné u vektorů, když jsou do seznamu vloženy nové prvky.

Struktura dat seznamu přiděluje a uvolňuje paměť podle potřeby; proto nepřiděluje paměť, kterou aktuálně nepoužívá. Paměť se uvolní, když je prvek odstraněn ze seznamu.

Seznamy jsou účinné při vkládání nových prvků do seznamu; tohle je ${ displaystyle O (1)}$ úkon. Není nutné žádné řazení, jako u vektorů.

Seznamy nemají schopnost náhodného přístupu jako vektory (${ displaystyle O (1)}$ úkon). Přístup k uzlu v seznamu je ${ displaystyle O (n)}$ operace, která vyžaduje procházení seznamu k nalezení uzlu, ke kterému je třeba přistupovat.

U malých datových typů (například ints) je režie paměti mnohem významnější než u vektoru. Každý uzel zabírá velikost (typ) + 2 * velikost (typ*). Ukazatele jsou obvykle jedno slovo (obvykle čtyři bajty v 32bitových operačních systémech), což znamená, že seznam čtyř bajtových celých čísel zabírá přibližně třikrát více paměti než vektor celých čísel.

Přeposlat seznam

The forward_list datová struktura implementuje a jednotlivě propojený seznam.

Deque

deque je šablona třídy kontejneru, která implementuje a oboustranná fronta. Poskytuje podobné výpočetní složitost na vektor pro většinu operací, s výraznou výjimkou, kterou poskytuje amortizovaná konstantní doba vkládání a vyjímání z obou konců sekvence prvků. Na rozdíl od vektor, deque používá nesouvislé bloky paměti a neposkytuje žádné prostředky ke kontrole kapacity kontejneru a okamžiku přerozdělení paměti. Jako vektor, deque nabízí podporu pro iterátory náhodného přístupu a vložení a odebrání prvků zruší platnost všech iterátorů deque.

Pole

pole implementuje nezměnitelnou dobu kompilace pole. Velikost je určena v době kompilace parametrem šablony. Konstrukčně kontejner nepodporuje alokátory. Na rozdíl od ostatních standardních kontejnerů pole neposkytuje konstantní čas vyměnit.

Přehled funkcí

Kontejnery jsou definovány v záhlavích pojmenovaných za názvy kontejnerů, např. vektor je definován v záhlaví <vector>. Všechny kontejnery splňují požadavky Kontejner pojem, což znamená, že mají začít(), konec(), velikost(), max_size (), prázdný(), a vyměnit () metody.

Členské funkce

Existují další operace, které jsou k dispozici jako součást třídy seznamu, a existují algoritmy, které jsou součástí C ++ STL (Algoritmus (C ++) ), které lze použít s seznam a forward_list třída:

Operace

• seznam :: sloučit a forward_list :: sloučit - Sloučí dva seřazené seznamy
• seznam :: spoj a forward_list :: splice_after - Přesune prvky z jiného seznamu
• seznam :: odebrat a forward_list :: remove - Odstraní prvky rovnající se dané hodnotě
• seznam :: remove_if a forward_list :: remove_if - Odstraní prvky splňující specifická kritéria
• seznam :: zpět a forward_list :: reverse - Obrátí pořadí prvků
• seznam :: jedinečný a forward_list :: unique - Odstraní po sobě jdoucí duplicitní prvky
• seznam :: seřadit a forward_list :: sort - Seřadí prvky

Nečlenské funkce

Příklad použití

Následující příklad ukazuje různé techniky zahrnující vektor a Standardní knihovna C ++ zejména algoritmy míchání, třídění, hledání největšího prvku a mazání z vektoru pomocí vymazat-odstranit idiom.

#zahrnout <iostream>#zahrnout <vector>#zahrnout <array>#zahrnout <algorithm> // řazení, max_element, random_shuffle, remove_if, lower_bound #zahrnout <functional> // větší#zahrnout <iterator> // začátek, konec, cbegin, cend, vzdálenost// zde se pro větší pohodlí používá uvážlivě v reálných programech. použitím jmenný prostor std;použitím jmenný prostor std::zástupné symboly;auto hlavní(int, char**)  -> int{  pole<int,4> přílet{ 1, 2, 3, 4 };  // inicializuje vektor z pole  vektor<int> čísla( cbegin(přílet), postoupit(přílet) );  // vloží více čísel do vektoru  čísla.zatlačit zpátky(5);  čísla.zatlačit zpátky(6);  čísla.zatlačit zpátky(7);  čísla.zatlačit zpátky(8);  // vektor aktuálně obsahuje {1, 2, 3, 4, 5, 6, 7, 8}  // náhodně zamíchá prvky  random_shuffle( začít(čísla), konec(čísla) );    // vyhledejte největší prvek, O (n)  auto největší = max_element( cbegin(čísla), postoupit(čísla) );    cout << „Největší počet je“ << *největší << " n";  cout << "Je umístěn na indexu" << vzdálenost(největší, cbegin(čísla)) << " n";    // seřadit prvky  třídit( začít(čísla), konec(čísla) );  // najdi pozici čísla 5 ve vektoru   auto Pět = lower_bound( cbegin(čísla), postoupit(čísla), 5 );      cout << „Číslo 5 se nachází v indexu“ << vzdálenost(Pět, cbegin(čísla)) << " n";    // smaže všechny prvky větší než 4   čísla.vymazat( remove_if(začít(čísla), konec(čísla),     svázat(větší<>{}, _1, 4) ), konec(čísla) );    // vytiskne všechna zbývající čísla  pro(konst auto& živel : čísla)    cout << živel << " ";    vrátit se 0;}

Výstup bude následující:

Největší počet je 8 Je umístěn na indexu 6 (podle implementace). Číslo 5 je umístěn na indexu 41 2 3 4

Reference

• William Ford, William Topp. Datové struktury s C ++ a STL, Druhé vydání. Prentice Hall, 2002. ISBN  0-13-085850-1. Kapitola 4: Vektorová třída, str. 195–203.
• Josuttis, Nicolai M. (1999). Standardní knihovna C ++. Addison-Wesley. ISBN  0-201-37926-0.

Poznámky