Mengapa semua fungsi <algorithm> hanya mengambil rentang, bukan wadah?

49

Ada banyak fungsi yang berguna <algorithm>, tetapi semuanya beroperasi pada "urutan" - pasangan iterator. Misalnya, jika saya memiliki wadah dan suka menjalankannya std::accumulate, saya perlu menulis:

std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);

Yang ingin saya lakukan adalah:

int sum = std::accumulate(myContainer, 0);

Yang sedikit lebih mudah dibaca dan lebih jelas, di mata saya.

Sekarang saya bisa melihat bahwa mungkin ada kasus di mana Anda hanya ingin beroperasi pada bagian-bagian wadah, jadi itu pasti berguna untuk memiliki opsi melewati rentang. Tapi setidaknya dalam pengalaman saya, itu adalah kasus khusus yang langka. Saya biasanya ingin beroperasi di seluruh wadah.

Sangat mudah untuk menulis fungsi pembungkus yang mengambil wadah dan panggilan begin()dan end()di atasnya, tetapi fungsi kenyamanan tersebut tidak termasuk dalam perpustakaan standar.

Saya ingin tahu alasan di balik pilihan desain STL ini.

c++ language-design standard-library gitar mematikan
sumber
7
Apakah STL biasanya menyediakan pembungkus yang nyaman, atau apakah mengikuti kebijakan C ++ yang lebih lama ini-the-tools-now-go-shoot-yourself-in-the-foot?
Kilian Foth
2
Sebagai catatan: daripada menulis bungkus Anda sendiri, Anda harus menggunakan pembungkus algoritma di Boost.Range; dalam hal ini,boost::accumulate
ecatmur

Jawaban:

40

... pasti bermanfaat untuk memiliki opsi melewati rentang. Tapi setidaknya dalam pengalaman saya, itu adalah kasus khusus yang langka. Saya biasanya ingin beroperasi di seluruh wadah

Ini mungkin kasus khusus yang langka dalam pengalaman Anda , tetapi dalam kenyataannya seluruh wadah adalah kasus khusus, dan kisaran sewenang - wenang adalah kasus umum.

Anda telah memperhatikan bahwa Anda dapat mengimplementasikan seluruh wadah menggunakan antarmuka saat ini, tetapi Anda tidak dapat melakukan yang sebaliknya.

Jadi, penulis perpustakaan memiliki pilihan antara mengimplementasikan dua antarmuka di muka, atau hanya mengimplementasikan satu yang masih mencakup semua kasus.

Sangat mudah untuk menulis fungsi pembungkus yang mengambil wadah dan panggilan mulai () dan mengakhiri () di atasnya, tetapi fungsi kenyamanan tersebut tidak termasuk dalam perpustakaan standar

Benar, terutama karena fungsi gratis std::begindan std::endsekarang disertakan.

Jadi, katakanlah perpustakaan menyediakan kenyamanan berlebih:

template <typename Container>
void sort(Container &c) {
  sort(begin(c), end(c));
}

sekarang ini juga perlu menyediakan kelebihan yang setara dengan mengambil fungsi perbandingan, dan kami perlu menyediakan yang setara untuk setiap algoritma lainnya.

Tapi setidaknya kita membahas setiap kasus di mana kita ingin beroperasi pada wadah penuh, kan? Ya tidak cukup. Mempertimbangkan

std::for_each(c.rbegin(), c.rend(), foo);

Jika kita ingin menangani pengoperasian mundur pada wadah, kita memerlukan metode lain (atau pasangan metode) per algoritma yang ada.

Jadi, pendekatan berbasis rentang lebih umum dalam arti sederhana bahwa:

  • itu bisa melakukan semua yang versi seluruh-kontainer bisa
  • pendekatan seluruh-kontainer menggandakan atau tiga kali lipat jumlah kelebihan yang dibutuhkan, sementara masih kurang kuat
  • algoritme berbasis rentang juga dapat disusun (Anda dapat menumpuk atau menghubungkan adapter iterator, meskipun ini lebih umum dilakukan dalam bahasa fungsional dan Python)

Ada alasan sah lainnya, tentu saja, yaitu karena sudah banyak pekerjaan untuk mendapatkan standar STL, dan menggelembungkannya dengan pembungkus yang nyaman sebelum digunakan secara luas tidak akan banyak menggunakan waktu komite yang terbatas. Jika Anda tertarik, Anda dapat menemukan laporan teknis Stepanov & Lee di sini

Seperti disebutkan dalam komentar, Boost.Range memberikan pendekatan yang lebih baru tanpa memerlukan perubahan standar.

Tak berguna
sumber
9
Saya tidak berpikir siapa pun, termasuk OP, menyarankan menambahkan kelebihan untuk setiap kasus khusus. Bahkan jika "seluruh wadah" kurang umum daripada "rentang sewenang-wenang", itu jelas jauh lebih umum daripada "seluruh wadah, terbalik". Batasi f(c.begin(), c.end(), ...), dan mungkin hanya kelebihan beban yang paling umum digunakan (namun Anda menentukannya) untuk mencegah penggandaan jumlah kelebihan beban. Juga, adaptor iterator sepenuhnya ortogonal (seperti yang Anda perhatikan, mereka bekerja dengan baik di Python, yang iteratornya bekerja sangat berbeda dan tidak memiliki sebagian besar kekuatan yang Anda bicarakan).
3
Saya setuju seluruh wadah, ke depan kasus sangat umum, tetapi ingin menunjukkan bahwa itu adalah bagian yang jauh lebih kecil dari kemungkinan penggunaan daripada pertanyaan yang disarankan. Khususnya karena pilihannya bukan antara seluruh wadah dan sebagian wadah, tetapi antara seluruh wadah dan sebagian wadah, mungkin terbalik atau disesuaikan. Dan saya pikir itu adil untuk menyarankan bahwa kompleksitas yang dirasakan menggunakan adaptor lebih besar, jika Anda juga harus mengubah kelebihan algoritma Anda.
berguna
23
Perhatikan bahwa versi kontainer akan mencakup semua kasus jika STL menawarkan objek jangkauan; mis std::sort(std::range(start, stop)).
3
Sebaliknya: algoritma fungsional gabungan (seperti peta dan filter) mengambil objek tunggal yang mewakili koleksi dan mengembalikan objek tunggal, mereka tentu saja tidak menggunakan apa pun yang menyerupai sepasang iterator.
svick
3
makro bisa melakukan ini: #define MAKE_RANGE(container) (container).begin(), (container).end()</jk>
ratchet freak
21

Ternyata ada artikel oleh Herb Sutter tentang hal ini. Pada dasarnya, masalahnya adalah ambiguitas yang berlebihan. Diberikan sebagai berikut:

template<typename Iter>
void sort( Iter, Iter ); // 1

template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2

Dan menambahkan yang berikut ini:

template<typename Container>
void sort( Container& ); // 3

template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4

Akan membuat sulit untuk dibedakan 4dan 1benar.

Konsep, seperti yang diusulkan tetapi pada akhirnya tidak termasuk dalam C ++ 0x, akan memecahkan itu, dan juga mungkin untuk mengelak menggunakan itu enable_if. Untuk beberapa algoritma, tidak ada masalah sama sekali. Tetapi mereka memutuskan untuk tidak melakukannya.

Sekarang setelah membaca semua komentar dan jawaban di sini, saya pikir rangeobjek akan menjadi solusi terbaik. Saya pikir saya akan melihat Boost.Range.

gitar mematikan
sumber
1
Nah, menggunakan hanya typename Itersepertinya terlalu diketik bebek untuk bahasa yang ketat. Saya lebih suka eg template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1dan template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4lain - lain (yang mungkin akan memecahkan masalah ambiguitas)
Vlad
@Vlad: Sayangnya, ini tidak akan berfungsi untuk array lama biasa, karena tidak T[]::iteratortersedia. Selain itu, iterator yang tepat tidak wajib menjadi tipe bersarang dari koleksi apa pun, itu cukup untuk didefinisikan std::iterator_traits.
firegurafiku
@firegurafiku: Yah, array mudah dikasus dengan beberapa trik TMP dasar.
Vlad
11

Pada dasarnya keputusan warisan. Konsep iterator dimodelkan pada pointer, tetapi kontainer tidak dimodelkan pada array. Selain itu, karena array sulit untuk dilewati (perlu parameter template non-type untuk panjang, secara umum), cukup sering fungsi hanya memiliki pointer yang tersedia.

Tapi ya, kalau dipikir-pikir keputusannya salah. Kita akan lebih baik dengan objek jangkauan yang dapat dibangun dari salah satu begin/endatau begin/length; sekarang kami memiliki beberapa _nalgoritma suffixed sebagai gantinya.

MSalters
sumber
5

Menambahkannya tidak akan memberi Anda kekuatan (Anda sudah dapat melakukan seluruh wadah dengan menelepon .begin()dan .end()diri sendiri), dan itu akan menambah satu hal lagi ke perpustakaan yang harus ditentukan dengan benar, ditambahkan ke perpustakaan oleh vendor, diuji, dipelihara, dll, dll.

Singkatnya, itu mungkin tidak ada karena tidak ada masalah dengan mempertahankan satu set templat tambahan hanya untuk menyelamatkan pengguna dari seluruh wadah dari mengetik satu parameter fungsi panggilan ekstra.

Michael Kohne
sumber
9
Itu tidak akan memberi saya kekuatan, itu benar - tetapi pada akhirnya, tidak juga std::getline, dan masih, itu ada di perpustakaan. Orang bisa mengatakan bahwa struktur kontrol yang diperluas tidak mendapatkan daya untuk saya, karena saya bisa melakukan semuanya hanya dengan menggunakan ifdan goto. Ya, perbandingan tidak adil, saya tahu;) Saya pikir saya bisa memahami spesifikasi / implementasi / beban pemeliharaan entah bagaimana, tapi itu hanya bungkus kecil yang sedang kita bicarakan di sini, jadi ...
lethal-guitar
Sebuah pembungkus kecil tidak ada biaya untuk kode dan mungkin tidak masuk akal untuk berada di perpustakaan.
ebasconp
-1

Sekarang, http://en.wikipedia.org/wiki/C++11#Range-based_for_loop adalah alternatif yang bagus std::for_each. Amati, tidak ada iterator eksplisit:

int a[5] = {1, 2, 3, 4, 5};
for (auto &i: a) { i *= 2; }

(Terinspirasi oleh https://stackoverflow.com/a/694534/2097284 .)

Camille Goudeseune
sumber
1
Ini hanya memecahkan bagian tunggal itu <algorithm>, tidak semua algos aktual yang dibutuhkan begindan enditerator - tetapi manfaatnya tidak dapat dilebih-lebihkan! Ketika saya pertama kali mencoba C ++ 03 di 2009ish, saya menghindar dari iterator karena lapisan perulangan, dan untungnya atau tidak, proyek saya pada saat itu mengizinkan ini. Mulai ulang pada C ++ 11 pada tahun 2014, itu adalah peningkatan yang luar biasa, bahasa C ++ selalu seharusnya, dan sekarang saya tidak bisa hidup tanpa auto &it: them:)
underscore_d