Interval: Evolusi C ++ yang Mendatang

Standar C ++ 20 akan segera muncul, yang kemungkinan akan menambah konsep rentang , tetapi sedikit orang yang tahu apa yang mereka dan apa yang mereka makan. Saya tidak dapat menemukan sumber berbahasa Rusia yang dapat diakses tentang binatang buas ini, oleh karena itu dalam artikel ini saya ingin memberi tahu Anda lebih banyak tentangnya, berdasarkan ceramah oleh Arno Schödl "Dari Iterators ke Ranges: Evolusi STL yang Akan Datang" dari Konferensi Rapat C ++ 2015- tahun ini. Saya akan mencoba membuat artikel ini sejelas mungkin bagi mereka yang pertama kali menemukan konsep ini, dan pada saat yang sama saya akan berbicara tentang semua jenis chip seperti adapter interval untuk mereka yang sudah akrab dengan konsep ini dan ingin tahu lebih banyak.

Perpustakaan dengan rentang

Pada saat penulisan ini, ada tiga perpustakaan utama yang mengimplementasikan interval:

• Tingkatkan
• Rentang v3
• perpustakaan umum think-cell

Perpustakaan pertama, pada kenyataannya, adalah nenek moyang dari konsep ini (yang tidak mengejutkan, karena tidak ada dalam koleksi perpustakaan Boost :)). Yang kedua adalah perpustakaan Eric Niebler, yang akan dijelaskan nanti. Dan akhirnya, perpustakaan terakhir, seperti yang Anda duga, ditulis oleh think-cell, yang, bisa dikatakan, dikembangkan dan ditingkatkan Boost.Range.

Mengapa interval adalah masa depan kita?

Bagi mereka yang tidak terbiasa dengan konsep interval, kami mendefinisikan konsep non-sepele ini sebagai sesuatu yang memiliki awal dan akhir ( sepasang iterator ).

Sekarang mari kita pertimbangkan tugas berikut: ada vektor, perlu untuk menghapus semua elemen berulang dari itu. Di bawah standar saat ini, kami akan menyelesaikannya seperti ini:

std::vector<T> vec=...; std::sort( vec.begin(), vec.end() ); vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() ); 

Dalam hal ini, kami menunjukkan nama vektor sebanyak 6 kali! Namun, dengan menggunakan konsep interval (menggabungkan iterator di awal dan akhir vektor ke dalam satu objek), kita dapat menulis berkali-kali lebih mudah dengan menetapkan vektor yang diinginkan hanya sekali :

 tc::unique_inplace( tc::sort(vec) ); 

Manakah dari interval saat ini dalam standar saat ini?

Dalam standar C ++ 11, rentang berbasis untuk loop dan akses universal ke awal / akhir wadah ditambahkan, dan dalam standar C ++ 17 terakhir, tidak ada yang baru terkait dengan interval yang ditambahkan.

 for ( int& i : <range_expression> ) { ... } 

 std::begin/end(<range_expression>) 

Interval masa depan

Sekarang mari kita memikirkan perpustakaan Range V3 yang disebutkan sebelumnya. Eric Nibler, penciptanya, ketika proyek rumahnya menciptakan Spesifikasi Teknis Range , memodifikasi perpustakaan algoritma untuk mendukung interval. Itu terlihat seperti ini:

 namespace ranges { template< typename Rng, typename What > decltype(auto) find( Rng && rng, What const& what ) { return std::find( ranges::begin(rng), ranges::end(rng), what ); } } 

Di situsnya ada beberapa pratinjau dari apa yang ingin dia standarisasi, ini adalah Range V3 .

Rentang apa yang bisa dipertimbangkan?

Pertama-tama, wadah (vektor, string, daftar dll), karena mereka memiliki awal dan akhir. Jelas bahwa wadah memiliki elemennya sendiri, yaitu, ketika kita merujuk ke wadah, maka kita merujuk ke semua elemennya. Demikian pula ketika menyalin dan mendeklarasikan konstan (penyalinan dalam dan konsistensi). Kedua, tampilan juga dapat dianggap sebagai interval. Tampilan hanyalah sepasang iterator yang menunjuk ke awal dan akhir. Berikut ini adalah implementasi mereka yang paling sederhana:

 template<typename It> struct iterator_range { It m_itBegin; It m_itEnd; It begin() const { return m_itBegin; } It end() const { return m_itEnd; } }; 

Tampilan, pada gilirannya, hanya merujuk ke elemen, sehingga penyalinan dan konsistensi malas (ini tidak mempengaruhi elemen).

Adapter Interval

Para penemu interval tidak berhenti pada ini, karena kalau tidak konsep ini akan menjadi agak tidak berguna. Oleh karena itu, mereka memperkenalkan konsep seperti itu sebagai range adapter.

Ubah adaptor

Pertimbangkan tugas berikut: biarkan vektor int diberikan, di mana kita perlu menemukan elemen pertama sama dengan 4:

 std::vector<int> v; auto it = ranges::find(v, 4); 

Sekarang mari kita bayangkan bahwa jenis vektornya bukan int, tetapi semacam struktur tulisan-sendiri yang kompleks, tetapi di dalamnya ada int, dan tugasnya masih sama:

 struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find_if( v, [](A const& a) { return a.id == 4; } ); 

Jelas bahwa kedua kode ini mirip dalam semantik, namun, mereka berbeda secara signifikan dalam sintaks, karena dalam kasus terakhir, kami harus secara manual menulis fungsi yang berjalan melalui bidang int . Tetapi jika Anda menggunakan transform adapter ( transform adapter ), maka semuanya terlihat jauh lebih ringkas:

 struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4); 

Faktanya, adaptor yang mentransformasikan “mengubah” struktur kita dengan membuat kelas pembungkus di sekitar bidang int. Jelas bahwa pointer menunjuk ke bidang id , tetapi jika kita ingin menunjuk ke seluruh struktur, kita perlu menambahkan di akhir .base () . Perintah ini merangkum bidang, karena penunjuk dapat berjalan melalui seluruh struktur:

 auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4).base(); 

Berikut ini adalah contoh implementasi transform adaptor (terdiri dari iterator, yang masing-masing memiliki functor sendiri):

 template<typename Base, typename Func> struct transform_range { struct iterator { private: Func m_func; //    decltype( tc::begin(std::declval<Base&>()) ) m_it; public: decltype(auto) operator*() const { return m_func(*m_it); } decltype(auto) base() const { return (m_it); } ... }; }; 

Adaptor filter

Dan jika dalam tugas terakhir kita tidak perlu menemukan elemen pertama, tetapi "menyaring" seluruh bidang int untuk keberadaan elemen tersebut? Dalam hal ini, kami akan menggunakan adaptor filter:

 tc::filter( v, [](A const& a) { return 4 == a.id; } ); 

Perhatikan bahwa filter dijalankan dengan malas selama iterasi.

Dan inilah implementasi naifnya (sesuatu seperti ini diterapkan di Boost.Range):

 template<typename Base, typename Func> struct filter_range { struct iterator { private: Func m_func; //     decltype( ranges::begin(std::declval<Base&>()) ) m_it; decltype( ranges::begin(std::declval<Base&>()) ) m_itEnd; public: iterator& operator++() { ++m_it; while( m_it != m_itEnd && !static_cast<bool>(m_func(*m_it)) ) ++m_it; return *this; } ... }; }; 

Seperti yang bisa kita lihat, dua iterator diperlukan di sini, bukan satu, seperti yang ada di adaptor transform. Iterator kedua diperlukan agar tidak sengaja melampaui batas wadah selama iterasi.

Beberapa optimasi

Oke, tapi seperti apa iteratornya dari tc :: filter (tc :: filter (tc :: filter (...))) ?

Tingkatkan

Sebagai bagian dari implementasi di atas, terlihat seperti ini:


Jelas, ini sangat tidak efisien.

Rentang v3

Mari kita pikirkan cara mengoptimalkan adaptor ini. Ide Eric Nibler adalah untuk meletakkan informasi umum (sebuah fungsi dan pointer ke ujung) di objek adaptor, dan kemudian kita dapat menyimpan tautan ke objek adaptor ini dan iterator yang diinginkan
*m_rng
m_it

Kemudian, dalam kerangka implementasi seperti itu, filter tiga akan terlihat seperti ini:


Ini masih belum sempurna, walaupun kadang-kadang lebih cepat dari implementasi sebelumnya.

think-cell, konsep indeks

Sekarang pertimbangkan solusi sel berpikir. Mereka memperkenalkan konsep indeks yang disebut untuk memecahkan masalah ini. Indeks adalah iterator yang melakukan semua operasi yang sama dengan iterator biasa, tetapi melakukan ini dengan mengacu pada interval.

 template<typename Base, typename Func> struct index_range { ... using Index = ...; Index begin_index() const; Index end_index() const; void increment_index( Index& idx ) const; void decrement_index( Index& idx ) const; reference dereference( Index& idx ) const; ... }; 

Kami menunjukkan cara menggabungkan indeks dengan iterator biasa.

Jelas bahwa iterator reguler juga dapat dianggap sebagai indeks. Di arah yang berlawanan, kompatibilitas dapat diterapkan, misalnya, sebagai berikut:

 template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; iterator& operator++() { m_rng.increment_index(m_idx); return *this; } ... }; 

Kemudian filter tiga kali lipat akan diterapkan secara sangat efisien:

 template<typename Base, typename Func> struct filter_range { Func m_func; Base& m_base; using Index = typename Base::Index; void increment_index( Index& idx ) const { do { m_base.increment_index(idx); } while ( idx != m_base.end_index() && !m_func(m_base.dereference_index(idx)) ); } }; 

 template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; ... }; 

Dalam kerangka implementasi seperti itu, algoritme akan bekerja dengan cepat terlepas dari kedalaman filter.

Interval dengan wadah nilai dan nilai

Sekarang mari kita lihat bagaimana interval bekerja dengan wadah nilai dan nilai:

lvalue

Rentang V3 dan think-cell berperilaku sama dengan lvalue. Misalkan kita memiliki kode seperti ini:

 auto rng = view::filter(vec, pred1); bool b = ranges::any_of(rng, pred2); 

Di sini kita memiliki vektor yang dinyatakan sebelumnya yang terletak di memori (lvalue), dan kita perlu membuat interval dan kemudian bekerja dengannya. Kami membuat tampilan menggunakan view :: filter atau tc :: filter dan menjadi senang, tidak ada kesalahan, dan kami kemudian dapat menggunakan tampilan ini, misalnya, di any_of.

Rentang V3 dan rvalue

Namun, jika vektor kami belum ada di memori (misalnya, jika kami baru saja membuatnya), dan kami akan menghadapi tugas yang sama, maka kami akan mencoba menulis dan kami menemukan kesalahan:

 auto rng = view::filter(create_vector(), pred1); //   bool b = ranges::any_of(rng, pred2); 

Mengapa itu muncul? Lihat akan menjadi tautan menggantung ke nilai karena fakta bahwa kita membuat vektor dan langsung meletakkannya di filter, yaitu, akan ada tautan nilai di filter, yang kemudian akan menunjuk ke sesuatu yang tidak diketahui ketika kompiler pergi ke baris berikutnya dan kesalahan terjadi. Untuk mengatasi masalah ini, Range V3 datang dengan aksi :

 auto rng = action::filter(create_vector(), pred1); //   bool b = ranges::any_of(rng, pred2); 

Tindakan melakukan semuanya sekaligus, yaitu hanya membutuhkan vektor, menyaring berdasarkan predikat, dan menempatkannya dalam interval. Namun, minusnya adalah bahwa ia tidak lagi malas, dan sel berpikir mencoba untuk memperbaiki minus ini.

sel berpikir dan menilai

Think-cell membuatnya sehingga alih-alih melihat wadah dibuat:

 auto rng = tc::filter(creates_vector(), pred1); bool b = ranges::any_of(rng, pred2); 

Akibatnya, kami tidak menemukan kesalahan yang sama, karena dalam implementasinya, filter mengumpulkan wadah nilai alih-alih tautan, jadi ini terjadi dengan malas. Dalam Range V3 mereka tidak ingin melakukan ini, karena mereka takut akan ada kesalahan karena filter berperilaku baik sebagai tampilan atau sebagai wadah, namun sel berpikir yakin bahwa programmer memahami bagaimana filter berperilaku, dan sebagian besar kesalahan muncul justru karena "kemalasan" ini.

Interval Generator

Kami menggeneralisasi konsep interval. Bahkan, ada interval tanpa iterator. Mereka disebut rentang generator . Misalkan kita memiliki widget GUI (elemen antarmuka) dan kami menyebutnya widget bergerak. Kami memiliki jendela yang meminta untuk memindahkan widgetnya, kami juga memiliki tombol di kotak daftar , dan jendela lain juga harus menggulir widgetnya, yaitu, kami memanggil traverse_widgets , yang menghubungkan elemen ke functor ( Anda dapat mengatakan ada fungsi enumerasi di mana Anda sambungkan functor, dan fungsinya daftar semua elemen yang ada di functor ini ).

 template<typename Func> void traverse_widgets( Func func ) { if (window1) { window1->traverse_widgets(std::ref(func)); } func(button1); func(listbox1); if (window2) { window2->traverse_widgets(std::ref(func)); } } 

Ini agak mengingatkan pada jarak widget, tetapi tidak ada iterator di sini. Menulisnya secara langsung akan menjadi tidak efisien dan, di atas segalanya, sangat sulit. Dalam hal ini, kita dapat mengatakan bahwa struktur seperti itu juga dianggap sebagai interval. Kemudian untuk kasus seperti itu ada penggunaan metode interval yang berguna, seperti any_of :

 mouse_hit_any_widget=tc::any_of( [] (auto func) { traverse_widgets(func); }, [] (auto const& widget) { return widget.mouse_hit(); } ); 

think-cell mencoba mengimplementasikan metode sehingga mereka memiliki antarmuka yang sama untuk semua jenis interval:

 namespace tc { template< typename Rng > bool any_of( Rng const& rng ) { bool bResult = false; tc::enumerate( rng, [&](bool_context b) { bResult = bResult || b; } ); return bResult; } } 

Menggunakan tc :: enumerate , perbedaan antara interval disembunyikan, karena implementasi seperti itu menganut konsep iterasi internal (apa konsep iterasi eksternal dan internal dijelaskan secara lebih rinci dalam kuliah), namun, implementasi ini memiliki kelemahan, yaitu, std :: any_of berhenti segera setelah true ditemukan. Mereka mencoba menyelesaikan masalah ini, misalnya, dengan menambahkan pengecualian ( interval generator yang disebut terputus ).

Kesimpulan

Saya benci rentang berbasis untuk loop karena memotivasi orang untuk menulisnya di mana saja diperlukan dan di mana tidak diperlukan, karena keringkasan kode yang sering memburuk, misalnya, orang menulis ini:

 bool b = false; for (int n : rng) { if ( is_prime(n) ) { b = true; break; } } 

sebagai gantinya:

 bool b = tc::any_of( rng, is_prime );