17 Temmuz 2019 Çarşamba

STL Veri Yapısı - dequeue

Giriş
Şu satırı dahil ederiz.
#include <deque>
vector, deque ve list sequence container olarak anılırlar.
Yapısı
Şeklen şöyledir

Bucket Size
Bu sınıfta reserve metodu yoktur çünkü büyümek için tüm elemanları tekrar taşımak zorunda değildir. Hemen hemen bütün dequeue sınıfları bucket mantığını kullanır. Sınıfın içi şuna benzer
template<typename T>
struct deque_stub {
 using Page = std::array<T, 32>; //Note: This is just an example
 std::vector<std::unique_ptr<Page>> pointers_to_pages;
 std::size_t end_insert{32};
 std::size_t start_elem{0};
 // read further
};
Açıklaması şöyle.
As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.
Açıklaması şöyle.
A deque is typically implemented as a two-layer structure, the top level is an array of pointers to fixed-sized chunks.
Bucket büyüklüğünü tanımlama imkanı yoktur. Açıklaması şöyle.
std::deque stores elements in "buckets" (arrays) of fixed size. Different compilers use different bucket sizes:

- MSVC: 16 bytes or element size if it's bigger
- GCC: 512 bytes or element size if it's bigger
- Clang: element_size < 256 ? 4096 : element_size * 16
Copy Constructor
Gerekirse container_cast kodu kullanılabilir.

back metodu
En sondaki elemana erişmemizi sağlar
std::dequeue<Person> deq;
deq.push_back(Person());
deq.back().setName("George");
erase metodu
Açıklaması şöyle
An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.
Örnek
Şöyle yaparız.
auto it = deq.begin();
deq.erase(i);
max_size metodu
Dequeue veri yapısına eklenebilecek azami eleman sayısını gösterir. Belirtilen sayı kadar elemana yetecek kadar bellek olmayabilir. Sadece kodlama anlamında üst sınırın ne olduğunu bulmak için kullanılır.
deq.max_size()
insert metodu
Iterator invalidation rules yazısındaki açıklama şöyle.
An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.
- Eğer eklenen veri ortalarda bir yerdeyse tüm iterator'ler ve  refence'lar geçersiz hale gelir. Çünkü 
1. dequeue içindeki vector reallocate edilir. Örneğin yeni bir bucket eklenir. Bu durumda iterator'ler geçersiz hale gelir.
2. Ayrıca bucket - yani array - içindeki elemanlar da kaydırılır. Dolayısıyla referans'lar da geçersiz hale gelir. 

- Eğer eklenen veri başta veya sondaysa, tüm iterator'le geçersiz hale gelir  ancak reference'lar etkilenmez. Çünkü 
1. dequeue içindeki vector reallocate edilir. Örneğin yeni bir bucket eklenir. Bu durumda iterator'ler geçersiz hale gelir.
2. Ancak bucket'a olan pointer'lar ve hatta bucket'ın içindeki nesneler de etkilenmez. Dolayısıyla referans'lar da geçersiz hale gelmez. Bucket içindeki nesnelerin etkilenmemesinin sebebi bucket'a yazılmaya sondan başlanması gibi düşünülebilir. Eğer bir array'e sondan yazmaya başlarsam, yeni eklenen eleman öm tarafa doğru geleceği için, arkadaki mevcut elemanları kaydırmak zorunda kalmam. Böylece referansları da bozulmaz. Kod kabaca şöyledir
template<typename X>
void push_front(X&& element) {
 if (start_elem == 0) {
  pointers_to_pages.insert(
    pointers_to_pages.begin(), std::make_unique<Page>());
  start_elem = 32;
 }
 --start_elem;
 (*(pointers_to_pages.front()))[start_elem] = std::forward<X>(element);
}
operator [] metodu
Bu metod tam olarak nerede kullanılıyor bilmiyorum. 
Örnek
Şöyle yaparız.
vector<int> v1;
deque<int> d1;
for( int i =0; i < 1000000;++i)
    v1.push_back(i);
for( int j =0; j < 1000000;++j)
    d1.push_back(j);
cout << *(&v1[0] +90000) << endl; // output 90000
cout<<  *(&d1[0] +90000)<<endl;   // Output is not the same as expected
push_back metodu
En sona eleman ekler. Eklenen eleman sonda olsa bile iterator invalid hale gelir. Açıklaması şöyle
push_back() and push_front() are defined in terms of insert(). Similarly, pop_back() and pop_front() are defined in terms of erase().
...
So push_front() and push_back() will invalidate iterators, but references to the elements themselves remain valid.
Örnek
Şöyle yaparız.
std::dequeue<Person> deq;
deq.push_back(Person());
push_front metodu
Açıklama yaz

size metodu
Diğer yüm veri yapılarında olduğu gibi size ile mevcut büyüklük alınabilir.

7 yorum:

  1. Merhaba,

    "Eğer eklenen veri ortalarda bir yerde ise tüm iterator'leri gerçersiz hale getirir, refence'lar etkilenmez." ifadesi hatali sanrim, dogrusu "Referanslar etkilenir etkilenir."

    iyi gunler

    YanıtlaSil
  2. Gördüm ve düzelttim. Ayrıca açıklamalar ekledim. Teşekkürler:)

    YanıtlaSil
  3. Eklenen açiklamalar için de ben teşekkur ederim, durumu aydınlatici olmuş

    YanıtlaSil
  4. Bir sorum olacakti, asagida ortadaki elemanin referansini aliyorum ve sonra oraya insert ediyorum. Ancak referans halen geçerli gözukuyor. Bu durum garanti edilmediginden mi referans degisir deniyor acaba ?

    #include
    #include
    int main ()
    {
    std::deque vec;
    for (int i=0; i<10; i++) vec.push_back(i);
    for (auto a : vec ) std::cout << ' ' << a ;

    int& rv = vec[4];
    std::cout << '\n' << "before insertion: " << rv << " , " << &rv ;

    vec.insert (vec.begin()+4, 26);

    std::cout << '\n' << '\n';
    for (auto a : vec ) std::cout << ' ' << a ;

    std::cout << '\n' << "after insertion: " << rv << " , " << &rv ;

    return 0;
    }

    YanıtlaSil
    Yanıtlar
    1. Bu örnekte dequeue'nun ilk bucket'ına işlem yapılıyor. Bu yüzden referans değişmiyor gibi görünüyor, çünkü ilk bucket'a eklemeler, bucket'ın sonundan başlayarak yapılır. Eğer bucket büyüklüğü örneğin 32 ise sorun çıkmıyor. Ancak verdiğiniz örnek sadece tesadüf, Eğer örnek kodu 35 tane ekleyip, 33. elemanı değiştirecek hale getirirseniz, referansın da geçersiz olduğu görülür. Yani açıklamadaki gibi ortaya insert() işlemi referansın değişmeyeceğini garanti etmez - bazen tesadüfen çalışsa da :)

      Sil
    2. Bucket'ın sonundan başlayarak eklemeler yapiliyorsa elemanlar bucket bazinda fiziksel olarak sirali durmuyor o zaman. Yani deque uzerinden sirali indeksle iterate ettigimizde fiziksel olarak memory'de sirali elemanlar uzerinde dolaşmiyoruz. Dogru mu anliyorum ?

      Sil
    3. Sadece ilk bucket için sondan başlayarak ekleme yapılıyor. Böylece push_fron() ile referanslar bozulmuyor. Diğer bucketlara normal şekilde baştan başlayarak ekleme yapılıyor. Ben böyle anladım :)

      Sil