Apakah kategori iterator C ++ melarang penulisan adaptor iterator UTF-8?

8

Saya telah mengerjakan adaptor iterator UTF-8. Yang saya maksud adalah adaptor yang mengubah iterator ke charatau unsigned charurutan menjadi iterator ke char32_turutan. Pekerjaan saya di sini terinspirasi oleh iterator yang saya temukan online ini .

Namun, ketika saya melihat melalui standar ketika saya memulai implementasi saya sendiri, saya menyadari: tampaknya tidak mungkin untuk mengimplementasikan adaptor seperti itu sambil tetap memenuhi persyaratan yang C ++ tempatkan pada iterator.

Misalnya, dapatkah Anda membuat iterator UTF-8 yang memenuhi persyaratan InputIterator? Ya, tetapi hanya selama iterator yang Anda berikan bukan merupakan InputIterator. Mengapa?

Karena InputIterator memerlukan kemampuan untuk melakukan iterator yang sama lebih dari satu kali. Anda juga dapat melakukan dereferensi banyak salinan dari iterator itu, asalkan semuanya sama.

Tentu saja, dereferencing adaptor iterator UTF-8 membutuhkan dereferencing dan berpotensi menambah iterator dasar. Dan jika iterator adalah InputIterator, maka Anda tidak bisa mendapatkan nilai asli kembali setelah Anda menambahkannya. Dan fakta bahwa salinan harus berfungsi berarti bahwa Anda tidak dapat menyimpan secara lokal char32_tyang mewakili nilai yang sebelumnya diterjemahkan. Anda bisa melakukan ini:

auto it = ...
auto it2 = it; //Copies an empty `char32_t`.
*it;           //Accesses base iterator, storing `it.ch`.
*it;           //Doesn't access the base iterator; simply returns `it.ch`.
*it2;          //Cannot access `it.ch`, so must access base iterator.

Oke, bagus, jadi Anda tidak bisa menggunakan InputIterators. Tetapi bagaimana dengan ForwardIterator? Apakah mungkin untuk membuat adaptor ForwardIterator yang dapat mengadaptasi ForwardIterators melalui urutan karakter UTF-8?

Yang bermasalah juga, karena operasi *ityang diperlukan untuk memproduksi value_type&atau const value_type&. InputIterators dapat memuntahkan apa pun yang dapat dikonversi menjadi value_type, tetapi ForwardIteratordiperlukan untuk memberikan referensi aktual [forward.iterators] /1.3:

jika Xiterator bisa berubah, referenceadalah referensi untuk T; jika Xiterator konstan, referenceadalah referensi keconst T

Satu-satunya jalan di sini adalah untuk setiap iterator untuk membawa sekitar char32_t, yang ada hanya untuk menyediakan penyimpanan untuk referensi itu. Dan bahkan kemudian, nilai itu harus diperbarui setiap kali instance iterator bertambah dan direferensikan. Ini secara efektif membatalkan referensi lama, dan standar tidak secara eksplisit mengizinkan itu (pembatalan hanya dapat terjadi ketika iterator dihancurkan, atau jika wadah mengatakan demikian).

Kode yang saya temukan online tidak berlaku karena ini, karena mengembalikan nilai uint32_t(ditulis pra-C ++ 11) dengan nilai daripada referensi yang tepat.

Apakah ada jalan lain di sini? Sudahkah saya mengabaikan sesuatu dalam standar, atau beberapa teknik implementasi yang dapat saya gunakan untuk mem-bypass masalah ini? Atau apakah ini tidak mungkin dengan kata-kata standar saat ini?

Catatan: yang aneh adalah bahwa tampaknya mungkin untuk menulis OutputIterator yang sesuai untuk konversi UTF-8. Yaitu, tipe yang mengambil char32_tdan menulis UTF-8 ke charatau unsigned charOutputIterator.

Nicol Bolas
sumber
3
Diketahui bahwa kata-kata ForwardIteratortidak cocok dengan jenis iterator proxy , seperti yang vector<bool>dimungkinkan. Ada artikel terkenal yang ditulis pada tahun 1999 oleh Herb Sutter yang menjelaskan mengapa tekad itu dibuat. Di zaman modern, ada kecenderungan memikirkan kembali masalah ini. Saya menemukan satu yang ditulis oleh Eric Niebler . Mungkin ada lebih banyak; bahkan mungkin ada beberapa yang ditulis oleh Herb Sutter sendiri, dalam beberapa proposal C ++.
rwong
Dengan InputIterator tidak bisakah Anda membaca cache sebelum melakukan dereferencing iterator?
user253751
@immibis: Um, baca cache apa? Membaca dari input iterator sebelum pengguna benar-benar berdereferensi itu dapat menyebabkan saya mengakses iterator yang tidak valid, karena iterator tidak selalu tahu di mana akhir kisaran. Jadi jika Anda menambahkan iterator, itu tidak berarti tidak masalah untuk mengubahnya. Juga, ingat poin yang saya buat tentang menyalin InputIterators: Jika Anda melakukan dereferensi dua salinan dari iterator input yang sama, Anda seharusnya mendapatkan nilai yang sama.
Nicol Bolas

Jawaban:

2

Saya pikir jawaban singkatnya adalah ya. Adaptor iterator yang menerjemahkan UTF-8 (dan lebih umum, yang berpotensi membutuhkan beberapa item input untuk menghasilkan item output tunggal) harus berlapis di atas iterator yang memodelkan (setidaknya) BidirectionalIterator.

Perhatikan bahwa ini dengan asumsi Anda hanya menginginkan iterator konstan (yaitu, Anda hanya membaca UTF-8 dari input, bukan menulis UTF-8 ke koleksi yang mendasarinya). Jika Anda ingin mendukung penulisan, segala sesuatunya menjadi lebih buruk dengan tergesa-gesa - mengubah dari satu nilai ke nilai lainnya di level UTF-32 dapat dengan mudah menghasilkan pengkodean UTF-8 yang memiliki ukuran berbeda, sehingga Anda harus siap untuk memasukkan / menghapus item di tengah koleksi yang mendasarinya jika Anda akan mendukung penulisan.

Jerry Coffin
sumber