Sıra kapsayıcı (C ++) - Sequence container (C++)

Bu makale olabilir gerek Temizlemek Wikipedia'yla tanışmak için kalite standartları. Spesifik sorun şudur: Konuşmaya bakın Lütfen yardım et bu makaleyi geliştir Eğer yapabilirsen. (Aralık 2011) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Hesaplamada, sıra kapsayıcıları bir gruba atıfta bulunmak konteyner sınıf şablonları içinde standart kitaplık of C ++ programlama dili veri öğelerinin depolanmasını uygulayan. Olmak şablonlar tamsayılar veya özel sınıflar gibi rastgele öğeleri depolamak için kullanılabilirler. Tüm sıralı kapların ortak bir özelliği, öğelere sıralı olarak erişilebilmesidir. Diğer tüm standart kitaplık bileşenleri gibi, bunlar da ad alanı std.

Aşağıdaki kapsayıcılar, C ++ standardının mevcut revizyonunda tanımlanmıştır: dizi, vektör, liste, forward_list, deque. Bu konteynerlerin her biri, veri depolama için farklı algoritmalar uygular; bu, farklı işlemler için farklı hız garantilerine sahip oldukları anlamına gelir:^[1]

• dizi derleme zamanı yeniden boyutlandırılamayan bir dizi uygular.
• vektör hızlı bir dizi uygular rasgele erişim ve öğeleri eklerken otomatik olarak yeniden boyutlandırma yeteneği.
• deque uygular çift ​​uçlu kuyruk nispeten hızlı rastgele erişim ile.
• liste uygular çift ​​bağlantılı liste.
• forward_list uygular tek bağlantılı liste.

Kapların her birinin düzgün çalışması için elemanlarını kopyalayabilmesi gerektiğinden, elemanların türü yerine getirmelidir. CopyConstructible ve Atanabilir Gereksinimler.^[2] Belirli bir kap için tüm öğeler aynı türe ait olmalıdır. Örneğin, veriler her iki şekilde de saklanamaz. kömür ve int aynı kapsayıcı örneği içinde.

Tarih

Bu bölüm genişlemeye ihtiyacı var. Yardımcı olabilirsiniz ona eklemek. (Aralık 2011)

Başlangıçta, sadece vektör, liste ve deque tanımlandı. 1998'de C ++ dilinin standardizasyonuna kadar, bunlar Standart Şablon Kitaplığı (STL) tarafından yayınlanan SGI.

dizi kap ilk başta çeşitli isimler altında birkaç kitapta yer aldı. Daha sonra bir Boost ve standart C ++ kitaplığına dahil edilmek üzere önerilmiştir. Dahil etme motivasyonu dizi C-tarzı dizinin iki problemini çözmesiydi: STL benzeri bir arayüzün olmaması ve başka herhangi bir nesne gibi kopyalanamama. İlk olarak C ++ TR1 ve daha sonra dahil edildi C ++ 11.

forward_list kapsayıcı, alanı verimli kullanan bir alternatif olarak C ++ 11'e eklendi liste ters yinelemeye gerek olmadığında.

Özellikleri

dizi, vektör ve deque tümü öğelere hızlı rastgele erişimi destekler. liste çift ​​yönlü yinelemeyi desteklerken forward_list yalnızca tek yönlü yinelemeyi destekler.

dizi öğenin takılmasını veya çıkarılmasını desteklemez. vektör Sonunda hızlı eleman yerleştirmeyi veya çıkarmayı destekler. Vektörün sonunda olmayan herhangi bir elemanın eklenmesi veya çıkarılması, yerleştirme konumu ile kopyalanacak vektörün sonu arasına elemanlar gerektirir. yineleyiciler etkilenen unsurlar bu nedenle geçersiz kılınır. Aslında, herhangi bir ekleme potansiyel olarak tüm yineleyicileri geçersiz kılabilir. Ayrıca, tahsis edilen depolama alanı vektör eleman eklemek için çok küçüktür, yeni bir dizi tahsis edilir, tüm elemanlar yeni diziye kopyalanır veya taşınır ve eski dizi serbest bırakılır. deque, liste ve forward_list tümü, kabın herhangi bir yerine elemanların hızlı bir şekilde takılmasını veya çıkarılmasını destekler. liste ve forward_list bu tür işlemlerde yineleyicilerin geçerliliğini korur, oysa deque hepsini geçersiz kılar.

Vektör

Bir vektör bitişik olarak saklanır.^[3] Hepsi gibi dinamik dizi uygulamalar, vektörler düşük bellek kullanımına sahiptir ve referans yeri ve veri önbelleği kullanım. Diğer STL kaplarından farklı olarak, örneğin Deques ve listeler vektörler, kullanıcının kap için bir başlangıç ​​kapasitesini belirtmesine izin verir.

Vektörler izin verir rasgele erişim; yani, bir vektörün bir elemanı, dizilerin elemanları ile aynı şekilde referans verilebilir (dizi indeksleri ile). Bağlantılı listeler ve setleri Öte yandan, rastgele erişim veya işaretçi aritmetiğini desteklemez.

Vektör veri yapısı, belirli veri depolaması için gerekli olan gerekli belleği hızlı ve kolay bir şekilde tahsis edebilir ve bunu amorti edilmiş sabit zamanda yapabilir. Bu, özellikle uzunluğu listeyi ayarlamadan önce bilinemeyen, ancak kaldırma işleminin (belki de sonunda dışında) nadir olduğu listelerde veri depolamak için özellikle yararlıdır. Bir vektörden öğeleri silmek veya hatta vektörü tamamen temizlemek, o öğeyle ilişkili hafızanın hiçbirini mutlaka serbest bırakmaz.

Kapasite ve yeniden tahsis

Tipik bir vektör uygulaması, dahili olarak bir göstericiden oluşur. dinamik olarak tahsis edilmiş dizi,^[1] ve muhtemelen vektörün kapasitesini ve boyutunu tutan veri üyeleri. Vektörün boyutu, gerçek öğe sayısını ifade ederken, kapasite dahili dizinin boyutunu ifade eder.

Yeni elemanlar eklendiğinde, vektörün yeni boyutu kapasitesinden daha büyük olursa, yeniden tahsis oluşur.^[1][4] Bu genellikle vektörün yeni bir depolama bölgesi tahsis etmesine, önceden tutulan öğeleri yeni depolama bölgesine taşımasına ve eski bölgeyi serbest bırakmasına neden olur.

Çünkü adresler bu işlem sırasında değişen öğelerden, herhangi bir referans veya yineleyiciler vektördeki elemanlar geçersiz hale gelir.^[5] Geçersiz bir referans nedenleri kullanma tanımlanmamış davranış.

Rezerve () işlemi, gereksiz yeniden tahsisleri önlemek için kullanılabilir. Bir rezerve etme çağrısından sonra (n), vektörün kapasitesinin en az n olması garanti edilir.^[6]

Vektör, elemanlarının belirli bir sırasını korur, böylece vektörün başlangıcına veya ortasına yeni bir eleman eklendiğinde, sonraki elemanlar değerleri bakımından geriye doğru hareket eder. atama operatörü veya yapıcı kopyala. Sonuç olarak, ekleme noktasından sonra öğelere yapılan referanslar ve yineleyiciler geçersiz hale gelir.^[7]

C ++ vektörleri, tasarım gereği belleğin yerinde yeniden tahsis edilmesini desteklemez; yani, bir vektörün yeniden tahsisi üzerine, tuttuğu bellek, elemanlarının kopya yapıcısını kullanarak her zaman yeni bir bellek bloğuna kopyalanacak ve sonra serbest bırakılacaktır. Bu, vektörün geçerli olduğu durumlar için verimsizdir. düz eski veriler ve tahsis için tutulan bellek bloğunun ötesinde ek bitişik alan mevcuttur.

Bool için uzmanlık

Standart Kitaplık, bir uzmanlık alanını tanımlar. vektör için şablon bool. Bu uzmanlığın açıklaması, uygulamanın öğeleri paketlemesi gerektiğini, böylece her bool yalnızca bir bit bellek kullanır.^[8] Bu genellikle bir hata olarak kabul edilir.^[9][10] vektör için gereksinimleri karşılamıyor C ++ Standart Kitaplığı konteyner. Örneğin, bir kapsayıcı :: başvuru doğru olmalı lvalue tip T. Bu durum böyle değil vektör :: başvuru, hangisi bir proxy sınıfı dönüştürülebilir bool.^[11] Benzer şekilde, vektör :: yineleyici vermez bool & ne zaman başvurulan. C ++ Standart Komitesi ve Kütüphane Çalışma Grubu arasında genel bir fikir birliği vardır. vektör Kullanımdan kaldırılmalı ve daha sonra standart kitaplıktan kaldırılmalıdır, bu arada işlevsellik farklı bir ad altında yeniden tanıtılacaktır.^[12]

Liste

liste veri yapısı bir çift ​​bağlantılı liste. Veriler bitişik olmayan bir şekilde bellekte depolanır, bu da liste veri yapısının listeye yeni elemanlar eklendiğinde vektörlerle gerekli olabilecek belleğin yeniden tahsis edilmesini önlemesine izin verir.

Liste veri yapısı, belleği gerektiği gibi ayırır ve serbest bırakır; bu nedenle, şu anda kullanmadığı belleği ayırmaz. Listeden bir öğe kaldırıldığında bellek boşaltılır.

Listeye yeni öğeler eklerken listeler etkilidir; bu bir ${ displaystyle O (1)}$ operasyon. Vektörlerde olduğu gibi kaydırmaya gerek yoktur.

Listelerin vektörler gibi rasgele erişim yeteneği yoktur (${ displaystyle O (1)}$ operasyon). Listedeki bir düğüme erişmek, ${ displaystyle O (n)}$ erişilmesi gereken düğümü bulmak için bir liste geçişi gerektiren işlem.

Küçük veri türlerinde (örneğin, ints) bellek ek yükü, bir vektörinkinden çok daha önemlidir. Her düğüm yer alır boyutu (tür) + 2 * boyutu (tür *). İşaretçiler genellikle biridir kelime (32 bit işletim sistemlerinde genellikle dört bayttır), bu, dört baytlık bir tamsayı listesinin bir tamsayı vektörünün yaklaşık üç katı kadar bellek kapladığı anlamına gelir.

Yönlendirme listesi

forward_list veri yapısı bir tek bağlantılı liste.

Deque

deque bir kapsayıcı sınıfı şablonudur. çift ​​uçlu kuyruk. Benzer sağlar hesaplama karmaşıklığı -e vektör sağladığı önemli istisna dışında çoğu işlem için amortize edilmiş sabit zaman eleman dizisinin her iki ucundan ekleme ve çıkarma. Aksine vektör, deque bitişik olmayan bellek bloklarını kullanır ve kabın kapasitesini ve belleğin yeniden tahsis edilme anını kontrol etmek için hiçbir yol sağlamaz. Sevmek vektör, deque için destek sunuyor rastgele erişim yineleyiciler ve öğelerin eklenmesi ve kaldırılması tüm yineleyicileri deque'e geçersiz kılar.

Dizi

dizi yeniden boyutlandırılamayan bir derleme zamanı uygular dizi. Boyut, derleme zamanında bir şablon parametresi ile belirlenir. Tasarım gereği konteyner desteklemiyor ayırıcılar. Diğer standart konteynerlerden farklı olarak, dizi sabit zaman sağlamaz takas.

Fonksiyonlara genel bakış

Kaplar, kapların adlarından sonra adlandırılan başlıklarda tanımlanır, örn. vektör başlıkta tanımlanmıştır <vector>. Tüm kaplar, aşağıdaki koşullara uygundur: Konteyner konsept yani sahip oldukları başla(), son(), boyut(), max_size (), boş(), ve takas () yöntemler.

Üye fonksiyonları

Liste sınıfının bir parçası olarak kullanılabilen başka işlemler vardır ve C ++ STL'nin parçası olan algoritmalar vardır (Algoritma (C ++) ) ile kullanılabilen liste ve forward_list sınıf:

Operasyonlar

• list :: birleştirme ve forward_list :: birleştirme - Sıralanmış iki listeyi birleştirir
• list :: splice ve forward_list :: splice_after - Öğeleri başka bir listeden taşır
• liste :: kaldır ve forward_list :: remove - Verilen değere eşit öğeleri kaldırır
• list :: remove_if ve forward_list :: remove_if - Belirli kriterleri karşılayan öğeleri kaldırır
• liste :: ters ve forward_list :: ters - Elemanların sırasını tersine çevirir
• liste :: benzersiz ve forward_list :: unique - Ardışık yinelenen öğeleri kaldırır
• list :: sort ve forward_list :: sort - Elemanları sıralar

Üye olmayan işlevler

Kullanım örneği

Aşağıdaki örnek, bir vektör içeren çeşitli teknikleri gösterir ve C ++ Standart Kitaplığı algoritmalar, özellikle karıştırma, sıralama, en büyük elemanı bulmak ve bir vektörden silmek için deyimi sil-kaldır.

#Dahil etmek <iostream>#Dahil etmek <vector>#Dahil etmek <array>#Dahil etmek <algorithm> // sırala, max_element, random_shuffle, remove_if, lower_bound #Dahil etmek <functional> // daha büyük#Dahil etmek <iterator> // başlangıç, bitiş, cbegin, cend, mesafe// burada kolaylık sağlamak için kullanılır, gerçek programlarda mantıklı kullanın. kullanma ad alanı std;kullanma ad alanı std::yer tutucular;Oto ana(int, kömür**)  -> int{  dizi<int,4> arr{ 1, 2, 3, 4 };  // bir diziden bir vektör başlat  vektör<int> sayılar( cbegin(arr), cend(arr) );  // vektöre daha fazla sayı ekle  sayılar.Geri itmek(5);  sayılar.Geri itmek(6);  sayılar.Geri itmek(7);  sayılar.Geri itmek(8);  // vektör şu anda {1, 2, 3, 4, 5, 6, 7, 8} tutar  // öğeleri rastgele karıştır  random_shuffle( başla(sayılar), son(sayılar) );    // en büyük elemanı bul, O (n)  Oto en büyük = max_element( cbegin(sayılar), cend(sayılar) );    cout << "En büyük sayı" << *en büyük << " n";  cout << "Dizinde bulunur" << mesafe(en büyük, cbegin(sayılar)) << " n";    // öğeleri sırala  çeşit( başla(sayılar), son(sayılar) );  // 5 sayısının vektördeki konumunu bul   Oto beş = alt sınır( cbegin(sayılar), cend(sayılar), 5 );      cout << "5 sayısı dizinde yer almaktadır" << mesafe(beş, cbegin(sayılar)) << " n";    // 4'ten büyük tüm öğeleri sil   sayılar.silmek( remove_if(başla(sayılar), son(sayılar),     bağlamak(daha büyük<>{}, _1, 4) ), son(sayılar) );    // kalan tüm sayıları yazdır  için(sabit Oto& element : sayılar)    cout << element << " ";    dönüş 0;}

Çıktı aşağıdaki gibi olacaktır:

En büyük sayı 8'dir, indeks 6'da bulunur (uygulamaya bağlı) 5 numara 41 2 3 4 indeksinde bulunur

Referanslar

• William Ford, William Topp. C ++ ve STL ile Veri Yapıları, İkinci baskı. Prentice Hall, 2002. ISBN  0-13-085850-1. Bölüm 4: Vektör Sınıfı, s. 195–203.
• Josuttis, Nicolai M. (1999). C ++ Standart Kitaplığı. Addison-Wesley. ISBN  0-201-37926-0.

Notlar