Apa itu deque di STL?

Saya sedang melihat wadah STL dan mencoba untuk mencari tahu apa itu sebenarnya (yaitu struktur data yang digunakan), dan deque menghentikan saya: Saya pikir pada awalnya bahwa itu adalah daftar ditautkan ganda, yang akan memungkinkan penyisipan dan penghapusan dari kedua ujungnya di waktu yang konstan, tetapi saya merasa terganggu oleh janji yang dibuat oleh operator [] untuk dilakukan dalam waktu yang konstan. Dalam daftar tertaut, akses sewenang-wenang seharusnya O (n), kan?

Dan jika itu array dinamis, bagaimana bisa menambahkan elemen dalam waktu yang konstan? Harus disebutkan bahwa realokasi dapat terjadi, dan bahwa O (1) adalah biaya diamortisasi, seperti untuk vektor .

Jadi saya bertanya-tanya apa struktur ini yang memungkinkan akses sewenang-wenang dalam waktu yang konstan, dan pada saat yang sama tidak perlu dipindahkan ke tempat baru yang lebih besar.

Deque didefinisikan secara rekursif: secara internal ia memelihara antrian ujung ganda dari ukuran tetap. Setiap chunk adalah vektor, dan antrian ("peta" dalam grafik di bawah) dari chunk itu sendiri juga merupakan vektor.

Ada analisis yang hebat tentang karakteristik kinerja dan bagaimana membandingkannya dengan vectorlebih di CodeProject .

Implementasi perpustakaan standar GCC secara internal menggunakan a T**untuk mewakili peta. Setiap blok data adalah T*yang dialokasikan dengan ukuran tetap __deque_buf_size(yang tergantung pada sizeof(T)).

Bayangkan itu sebagai vektor vektor. Hanya saja itu bukan standar std::vector.

Vektor luar berisi pointer ke vektor bagian dalam. Ketika kapasitasnya diubah melalui realokasi, alih-alih mengalokasikan semua ruang kosong ke akhir seperti std::vectorhalnya, itu membagi ruang kosong ke bagian yang sama di awal dan akhir vektor. Ini memungkinkan push_frontdan push_backpada vektor ini keduanya terjadi dalam waktu O (1) diamortisasi.

Perilaku vektor bagian dalam perlu diubah tergantung pada apakah itu di bagian depan atau belakang deque. Di belakangnya ia dapat berperilaku sebagai standar di std::vectormana ia tumbuh pada akhirnya, dan push_backterjadi dalam waktu O (1). Di depan itu perlu melakukan yang sebaliknya, tumbuh di awal dengan masing-masing push_front. Dalam praktiknya ini mudah dicapai dengan menambahkan pointer ke elemen depan dan arah pertumbuhan bersama dengan ukuran. Dengan modifikasi sederhana push_frontini juga bisa O (1) kali.

Akses ke elemen apa pun membutuhkan penyeimbangan dan pembagian ke indeks vektor luar yang tepat yang terjadi pada O (1), dan pengindeksan ke dalam vektor bagian dalam yang juga O (1). Ini mengasumsikan bahwa vektor bagian dalam semua ukuran tetap, kecuali yang di awal atau akhir deque.

deque = antrian berakhir ganda

Wadah yang bisa tumbuh di kedua arah.

Deque biasanya diimplementasikan sebagai a vectorof vectors(daftar vektor tidak dapat memberikan akses acak waktu konstan). Sementara ukuran vektor sekunder bergantung pada implementasi, algoritma yang umum adalah menggunakan ukuran konstan dalam byte.

(Ini adalah jawaban yang saya berikan di utas lain . Pada dasarnya saya berpendapat bahwa implementasi yang bahkan cukup naif, menggunakan satu vector, sesuai dengan persyaratan "push_ non-diamortisasi konstan {depan, belakang}". Anda mungkin akan terkejut , dan saya pikir ini tidak mungkin, tetapi saya telah menemukan kutipan lain yang relevan dalam standar yang mendefinisikan konteks dengan cara yang mengejutkan. Mohon bersabar, jika saya telah membuat kesalahan dalam jawaban ini, akan sangat membantu untuk mengidentifikasi hal-hal yang mana Saya telah mengatakan dengan benar dan di mana logika saya rusak.)

Dalam jawaban ini, saya tidak mencoba mengidentifikasi implementasi yang baik , saya hanya mencoba untuk membantu kami menafsirkan persyaratan kompleksitas dalam standar C ++. Saya mengutip dari N3242 , yang menurut Wikipedia , dokumen standardisasi C ++ 11 terbaru yang tersedia secara gratis. (Tampaknya diatur secara berbeda dari standar akhir, dan karenanya saya tidak akan mengutip nomor halaman yang tepat. Tentu saja, aturan ini mungkin telah berubah dalam standar akhir, tetapi saya rasa itu tidak terjadi.)

A deque<T>dapat diimplementasikan dengan benar dengan menggunakan a vector<T*>. Semua elemen disalin ke tumpukan dan pointer disimpan dalam vektor. (Lebih lanjut tentang vektor nanti).

Kenapa T*bukannya T? Karena standar mengharuskan itu

"Penyisipan di kedua ujung deque membatalkan semua iterator ke deque, tetapi tidak memiliki efek pada validitas referensi ke elemen deque. "

(Penekanan saya). The T*membantu untuk memenuhi itu. Ini juga membantu kita untuk memuaskan ini:

"Memasukkan elemen tunggal baik di awal atau akhir deque selalu ..... menyebabkan panggilan tunggal ke konstruktor T. "

Sekarang untuk bit (kontroversial). Mengapa menggunakan a vectoruntuk menyimpan T*? Ini memberi kami akses acak, yang merupakan awal yang baik. Mari kita lupakan kerumitan vektor untuk sesaat dan membangunnya dengan hati-hati:

Standar berbicara tentang "jumlah operasi pada objek yang terkandung.". Untuk deque::push_frontini jelas 1 karena tepat satu Tobjek dibangun dan nol dari Tobjek yang ada dibaca atau dipindai dengan cara apa pun. Angka ini, 1, jelas merupakan konstanta dan tidak tergantung pada jumlah objek yang ada dalam deque. Ini memungkinkan kita untuk mengatakan bahwa:

'Untuk kami deque::push_front, jumlah operasi pada objek yang terkandung (Ts) adalah tetap dan tidak tergantung pada jumlah objek yang sudah ada dalam deque.'

Tentu saja, jumlah operasi pada T*tidak akan berperilaku baik. Ketika vector<T*>tumbuh terlalu besar, itu akan dialokasikan kembali dan banyak T*yang akan disalin. Jadi ya, jumlah operasi di T*akan sangat bervariasi, tetapi jumlah operasi di Ttidak akan terpengaruh.

Mengapa kita peduli tentang perbedaan antara penghitungan operasi Tdan penghitungan operasi T*? Itu karena standar mengatakan:

Semua persyaratan kompleksitas dalam klausa ini dinyatakan semata-mata dalam hal jumlah operasi pada objek yang terkandung.

Untuk deque, objek yang terkandung adalah T, bukan T*, artinya kita dapat mengabaikan operasi apa pun yang menyalin (atau meng-reallocs) a T*.

Saya belum banyak bicara tentang bagaimana vektor akan berperilaku deque. Mungkin kita akan menafsirkannya sebagai penyangga bundar (dengan vektor selalu mengambil maksimumnya capacity(), dan kemudian realokasi semuanya menjadi penyangga yang lebih besar ketika vektor penuh. Detailnya tidak masalah.

Dalam beberapa paragraf terakhir, kami telah menganalisis deque::push_frontdan hubungan antara jumlah objek dalam deque sudah dan jumlah operasi yang dilakukan oleh push_front pada -objects yang terkandung T. Dan kami menemukan mereka tidak saling tergantung satu sama lain. Karena standar mengamanatkan kompleksitas dalam hal operasi-on T, maka kita dapat mengatakan ini memiliki kompleksitas konstan.

Ya, Operasional-On-T * -Kompleksitas diamortisasi (karena vector), tetapi kami hanya tertarik pada Kompleksitas Operasional-On-T dan ini konstan (tidak-diamortisasi).

Kompleksitas vektor :: push_back atau vektor :: push_front tidak relevan dalam implementasi ini; Pertimbangan tersebut melibatkan operasi T*dan karenanya tidak relevan. Jika standar mengacu pada gagasan teoritis 'konvensional' tentang kompleksitas, maka mereka tidak akan secara eksplisit membatasi diri pada "jumlah operasi pada objek yang terkandung". Apakah saya terlalu menafsirkan kalimat itu?

Dari gambaran umum, Anda dapat berpikir dequesebagai adouble-ended queue

Data dalam dequedisimpan oleh potongan-potongan vektor ukuran tetap, yang

ditunjukkan oleh map(yang juga merupakan potongan vektor, tetapi ukurannya dapat berubah)

Kode bagian utama deque iteratoradalah sebagai berikut:

/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
    typedef __deque_iterator<T, buff_size>              iterator;
    typedef T**                                         map_pointer;

    // pointer to the chunk
    T* cur;       
    T* first;     // the begin of the chunk
    T* last;      // the end of the chunk

    //because the pointer may skip to other chunk
    //so this pointer to the map
    map_pointer node;    // pointer to the map
}

Kode bagian utama dequeadalah sebagai berikut:

/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
    public:
        typedef T              value_type;
        typedef T&            reference;
        typedef T*            pointer;
        typedef __deque_iterator<T, buff_size> iterator;

        typedef size_t        size_type;
        typedef ptrdiff_t     difference_type;

    protected:
        typedef pointer*      map_pointer;

        // allocate memory for the chunk 
        typedef allocator<value_type> dataAllocator;

        // allocate memory for map 
        typedef allocator<pointer>    mapAllocator;

    private:
        //data members

        iterator start;
        iterator finish;

        map_pointer map;
        size_type   map_size;
}

Di bawah ini saya akan memberi Anda kode inti deque, terutama sekitar tiga bagian:

1. iterator

2. Cara membangun a deque

1. iterator ( __deque_iterator)

Masalah utama dari iterator adalah, ketika ++, - iterator, ia dapat melompat ke chunk lain (jika pointer ke edge of chunk). Sebagai contoh, ada tiga data yang potongan: chunk 1, chunk 2, chunk 3.

The pointer1pointer ke mulai dari chunk 2, ketika operator --pointerakan pointer ke akhir chunk 1, sehingga ke pointer2.

Di bawah ini saya akan memberikan fungsi utama __deque_iterator:

Pertama, lewati ke bagian mana pun:

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

Perhatikan bahwa, chunk_size()fungsi yang menghitung ukuran chunk, Anda dapat menganggapnya mengembalikan 8 untuk disederhanakan di sini.

operator* dapatkan data di chunk

reference operator*()const{
    return *cur;
}

operator++, --

// bentuk awalan peningkatan

self& operator++(){
    ++cur;
    if (cur == last){      //if it reach the end of the chunk
        set_node(node + 1);//skip to the next chunk
        cur = first;
    }
    return *this;
}

// postfix forms of increment
self operator++(int){
    self tmp = *this;
    ++*this;//invoke prefix ++
    return tmp;
}
self& operator--(){
    if(cur == first){      // if it pointer to the begin of the chunk
        set_node(node - 1);//skip to the prev chunk
        cur = last;
    }
    --cur;
    return *this;
}

self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
}

self& operator+=(difference_type n){ // n can be postive or negative
    difference_type offset = n + (cur - first);
    if(offset >=0 && offset < difference_type(buffer_size())){
        // in the same chunk
        cur += n;
    }else{//not in the same chunk
        difference_type node_offset;
        if (offset > 0){
            node_offset = offset / difference_type(chunk_size());
        }else{
            node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
        }
        // skip to the new chunk
        set_node(node + node_offset);
        // set new cur
        cur = first + (offset - node_offset * chunk_size());
    }

    return *this;
}

// skip n steps
self operator+(difference_type n)const{
    self tmp = *this;
    return tmp+= n; //reuse  operator +=
}

self& operator-=(difference_type n){
    return *this += -n; //reuse operator +=
}

self operator-(difference_type n)const{
    self tmp = *this;
    return tmp -= n; //reuse operator +=
}

// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
    return *(*this + n);
}

2. Cara membangun a deque

fungsi umum dari deque

iterator begin(){return start;}
iterator end(){return finish;}

reference front(){
    //invoke __deque_iterator operator*
    // return start's member *cur
    return *start;
}

reference back(){
    // cna't use *finish
    iterator tmp = finish;
    --tmp; 
    return *tmp; //return finish's  *cur
}

reference operator[](size_type n){
    //random access, use __deque_iterator operator[]
    return start[n];
}


template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
    fill_initialize(n, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
    // allocate memory for map and chunk
    // initialize pointer
    create_map_and_nodes(n);

    // initialize value for the chunks
    for (map_pointer cur = start.node; cur < finish.node; ++cur) {
        initialized_fill_n(*cur, chunk_size(), value);
    }

    // the end chunk may have space node, which don't need have initialize value
    initialized_fill_n(finish.first, finish.cur - finish.first, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
    // the needed map node = (elements nums / chunk length) + 1
    size_type num_nodes = num_elements / chunk_size() + 1;

    // map node num。min num is  8 ，max num is "needed size + 2"
    map_size = std::max(8, num_nodes + 2);
    // allocate map array
    map = mapAllocator::allocate(map_size);

    // tmp_start，tmp_finish poniters to the center range of map
    map_pointer tmp_start  = map + (map_size - num_nodes) / 2;
    map_pointer tmp_finish = tmp_start + num_nodes - 1;

    // allocate memory for the chunk pointered by map node
    for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
        *cur = dataAllocator::allocate(chunk_size());
    }

    // set start and end iterator
    start.set_node(tmp_start);
    start.cur = start.first;

    finish.set_node(tmp_finish);
    finish.cur = finish.first + num_elements % chunk_size();
}

Mari kita asumsikan i_dequememiliki 20 elemen int 0~19yang ukuran chunk-nya adalah 8, dan sekarang push_back 3 elemen (0, 1, 2) ke i_deque:

i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);

Ini struktur internal seperti di bawah ini:

Kemudian push_back lagi, itu akan memanggil mengalokasikan potongan baru:

push_back(3)

Jika kita push_front, itu akan mengalokasikan potongan baru sebelum prevstart

Perhatikan ketika push_backelemen menjadi deque, jika semua peta dan potongan diisi, itu akan menyebabkan mengalokasikan peta baru, dan menyesuaikan potongan. Tapi kode di atas mungkin cukup bagi Anda untuk mengerti deque.

Saya sedang membaca "Struktur data dan algoritma dalam C ++" oleh Adam Drozdek, dan menemukan ini berguna. HTH.

Aspek STL deque yang sangat menarik adalah implementasinya. Deque STL tidak diimplementasikan sebagai daftar tertaut tetapi sebagai array pointer ke blok atau array data. Jumlah blok berubah secara dinamis tergantung pada kebutuhan penyimpanan, dan ukuran array pointer berubah sesuai.

Anda dapat melihat di tengah adalah array pointer ke data (potongan di sebelah kanan), dan Anda juga dapat melihat bahwa array di tengah berubah secara dinamis.

Sebuah gambar bernilai ribuan kata.

Sementara standar tidak mengamanatkan implementasi tertentu (hanya akses acak waktu konstan), sebuah deque biasanya diimplementasikan sebagai kumpulan "halaman" memori yang berdekatan. Halaman baru dialokasikan sesuai kebutuhan, tetapi Anda masih memiliki akses acak. Tidak seperti std::vector, Anda tidak dijanjikan bahwa data disimpan secara bersebelahan, tetapi seperti vektor, penyisipan di tengah membutuhkan banyak pemindahan.