Mengapa rentang iterator standar [awal, akhir) bukan [mulai, akhir]?

Mengapa Standar didefinisikan end()sebagai yang melewati akhir, bukan pada akhir yang sebenarnya?

Argumen terbaik dengan mudah adalah yang dibuat oleh Dijkstra sendiri :

• Anda ingin ukuran rentang menjadi perbedaan sederhana end  -  mulai ;

• termasuk batas bawah lebih "alami" ketika sekuens berubah menjadi kosong, dan juga karena alternatif ( tidak termasuk batas bawah) akan membutuhkan keberadaan nilai sentinel "satu-sebelum-awal".

Anda masih perlu menjustifikasi mengapa Anda mulai menghitung dengan nol daripada satu, tetapi itu bukan bagian dari pertanyaan Anda.

Kebijaksanaan di belakang konvensi [mulai, akhir] terbayar berkali-kali ketika Anda memiliki jenis algoritma apa pun yang berhubungan dengan beberapa panggilan bersarang atau berulang untuk konstruksi berbasis rentang, yang berantai secara alami. Sebaliknya, menggunakan rentang yang ditutup dua kali lipat akan menimbulkan kode off-by-one dan sangat tidak menyenangkan dan berisik. Sebagai contoh, perhatikan partisi [ n ₀ , n ₁ ) [ n ₁ , n ₂ ) [ n ₂ , n ₃ ). Contoh lain adalah loop iterasi standar for (it = begin; it != end; ++it), yang berjalan end - beginkali. Kode yang sesuai akan jauh lebih mudah dibaca jika kedua ujungnya inklusif - dan bayangkan bagaimana Anda akan menangani rentang kosong.

Akhirnya, kita juga dapat membuat argumen yang bagus mengapa penghitungan harus dimulai dari nol: Dengan konvensi setengah terbuka untuk rentang yang baru saja kita buat, jika Anda diberi rentang elemen N (katakanlah untuk menyebutkan anggota array), lalu 0 adalah "awal" alami sehingga Anda dapat menulis kisaran sebagai [0, N ), tanpa offset atau koreksi yang canggung.

Singkatnya: fakta bahwa kita tidak melihat angka 1di mana-mana dalam algoritma berbasis rentang adalah konsekuensi langsung dari, dan motivasi untuk, [awal, akhir) konvensi.

Sebenarnya, banyak hal yang berhubungan dengan iterator tiba-tiba lebih masuk akal jika Anda mempertimbangkan iterator tidak menunjuk pada elemen-elemen dari sekuens tetapi di antaranya , dengan dereferencing mengakses elemen berikutnya tepat untuk itu. Kemudian iterator "one past end" tiba-tiba langsung masuk akal:

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^               ^
   |               |
 begin            end

Jelas sekali begin menunjuk ke awal urutan, dan endmenunjuk ke akhir urutan yang sama. Dereferencing beginmengakses elemen A, dan dereferencing endtidak masuk akal karena tidak ada elemen yang tepat untuk itu. Juga, menambahkan iterator idi tengah memberi

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
 begin     i      end

dan Anda langsung melihat bahwa berbagai elemen dari begin hingga imengandung elemen Adan Bsementara rentang elemen dari ihingga endmengandung elemen Cdan D. Dereferencing imemberikan elemen tepat padanya, yaitu elemen pertama dari urutan kedua.

Bahkan "off-by-one" untuk iterator terbalik tiba-tiba menjadi jelas seperti itu: Membalik urutan itu memberi:

   +---+---+---+---+
   | D | C | B | A |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
rbegin     ri     rend
 (end)    (i)   (begin)

Saya telah menulis iterator non-reverse (base) yang sesuai dalam tanda kurung di bawah ini. Anda lihat, iterator terbalik milik i(yang saya beri nama ri) masih menunjuk di antara elemen Bdan C. Namun karena membalik urutan, sekarang elemen Bada di sebelah kanan.

Mengapa Standar didefinisikan end()sebagai yang melewati akhir, bukan pada akhir yang sebenarnya?

Karena:

1. Ini menghindari penanganan khusus untuk rentang kosong. Untuk rentang kosong, begin()sama dengan end()&
2. Itu membuat kriteria akhir menjadi sederhana untuk loop yang beralih pada elemen: Loop hanya berlanjut selama end()tidak tercapai.

Karena itu

size() == end() - begin()   // For iterators for whom subtraction is valid

dan Anda tidak perlu melakukan hal-hal aneh seperti

// Never mind that this is INVALID for input iterators...
bool empty() { return begin() == end() + 1; }

dan Anda tidak akan secara tidak sengaja menulis kode yang salah seperti

bool empty() { return begin() == end() - 1; }    // a typo from the first version
                                                 // of this post
                                                 // (see, it really is confusing)

bool empty() { return end() - begin() == -1; }   // Signed/unsigned mismatch
// Plus the fact that subtracting is also invalid for many iterators

Juga: Apa yang akan find()kembali jika end()diarahkan ke elemen yang valid?
Apakah Anda benar - benar ingin anggota lain dipanggil invalid()yang mengembalikan iterator yang tidak valid ?!
Dua iterator sudah cukup menyakitkan ...

Oh, dan lihat posting terkait ini .

Juga:

Jika endsebelum elemen terakhir, bagaimana Anda insert()pada akhirnya?

Ungkapan iterator dari rentang setengah tertutup pada [begin(), end())awalnya didasarkan pada aritmatika pointer untuk array polos. Dalam mode operasi itu, Anda akan memiliki fungsi yang melewati array dan ukuran.

void func(int* array, size_t size)

Konversi ke rentang setengah tertutup [begin, end)sangat sederhana ketika Anda memiliki informasi itu:

int* begin;
int* end = array + size;

for (int* it = begin; it < end; ++it) { ... }

Untuk bekerja dengan rentang yang tertutup sepenuhnya, lebih sulit:

int* begin;
int* end = array + size - 1;

for (int* it = begin; it <= end; ++it) { ... }

Karena pointer ke array adalah iterator di C ++ (dan sintaks dirancang untuk memungkinkan ini), itu jauh lebih mudah untuk dipanggil std::find(array, array + size, some_value)daripada memanggil std::find(array, array + size - 1, some_value).

Plus, jika Anda bekerja dengan rentang setengah tertutup, Anda dapat menggunakan !=operator untuk memeriksa kondisi akhir, karena (jika operator Anda didefinisikan dengan benar) <menyiratkan !=.

for (int* it = begin; it != end; ++ it) { ... }

Namun tidak ada cara mudah untuk melakukan ini dengan rentang tertutup sepenuhnya. Anda terjebak dengan<= .

Satu-satunya jenis iterator yang mendukung <dan >beroperasi di C ++ adalah iterator akses-acak. Jika Anda harus menulis <=operator untuk setiap kelas iterator di C ++, Anda harus membuat semua iterator Anda sepenuhnya dapat dibandingkan, dan Anda akan lebih sedikit pilihan untuk membuat iterator yang kurang mampu (seperti iterator dua arah aktif std::list, atau iterator input yang beroperasi pada iostreams) jika C ++ menggunakan rentang tertutup sepenuhnya.

Dengan end()penunjuk yang melewati akhir, mudah untuk mengulang koleksi dengan for for:

for (iterator it = collection.begin(); it != collection.end(); it++)
{
    DoStuff(*it);
}

Dengan end()menunjuk ke elemen terakhir, sebuah loop akan menjadi lebih kompleks:

iterator it = collection.begin();
while (!collection.empty())
{
    DoStuff(*it);

    if (it == collection.end())
        break;

    it++;
}

1. Jika wadah kosong begin() == end(),.
2. C ++ Programmer cenderung menggunakan !=alih-alih <(kurang dari) dalam kondisi loop, oleh karena itu end()menunjuk ke posisi yang tidak nyaman adalah mudah.