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.