Apakah std::copy_n berfungsi dengan rentang yang tumpang tindih?

Saya mencari standar C++ di N3485 25.3.1 [alg.copy], yang mendefinisikan 4 algoritma:

  • copy
  • copy_backward
  • copy_if
  • copy_n

Dalam deskripsi copy, ada catatan ini 25.3.1 [alg.copy]/3:

Membutuhkan: hasil tidak boleh berada dalam rentang [pertama, terakhir)

Artinya, copy tidak selalu berfungsi dengan benar ketika rentangnya tumpang tindih (mirip dengan memcpy).

copy_backward dan copy_if memiliki bahasa serupa yang melarang rentang yang tumpang tindih (masing-masing 25.3.1 [alg.copy]/14 dan 25.3.1 [alg.copy]/8).

Namun, tidak ada larangan untuk copy_n, dan tidak ada copy_n_backward. Apakah ini berarti copy_n melakukan hal yang benar ketika rentangnya tumpang tindih?

(Implementasi MSVC++ terhadap copy_n tampaknya didelegasikan ke std::memmove, jadi saya tahu ini aman di sini di MSVC++ 2013. Namun saya tidak ingin bergantung pada ini jika standar menyatakan sebaliknya)


c++ algorithm stl stl-algorithm
person Billy ONeal    schedule 23.12.2013    source sumber
comment
Implementasi MSVC++ terhadap copy_n tampaknya didelegasikan ke std::memmove Perhatikan bahwa kami hanya melakukan ini jika transformasi tersebut benar; yaitu, di mana iterator adalah penunjuk ke objek yang dapat disalin secara sepele.   -  person James McNellis    schedule 23.12.2013
comment
@James: Tentu saja. :) Dalam hal ini, ini adalah transformasi yang aman.   -  person Billy ONeal    schedule 23.12.2013
comment
@James: Ah, saya mengerti maksud Anda. Jika masukannya mis. std::list iterator, ini tidak aman pada implementasi MSVC++. Kedengarannya seperti jawaban bagiku...   -  person Billy ONeal    schedule 23.12.2013
comment
Wah itu kasus yang aneh, mau saya bilang mungkin salah (maksudnya UB) tapi sepertinya sengaja ditinggalkan...   -  person user541686    schedule 23.12.2013
comment
implementasi SGI yang asli memang memiliki persyaratan seperti itu untuk copy_n. Saya tidak tahu mengapa ini tidak ada dalam Standar. Anda bisa menyampaikan masalah. BTW, copy hanya melarang tumpang tindih yang keluarannya dimulai dalam rentang masukan, tetapi berfungsi dengan baik ketika rentang keluaran berakhir dan dalam rentang masukan (yaitu menyalin ke kiri).   -  person TemplateRex    schedule 04.01.2014

Jawaban (2)


arrow_upward
3
arrow_downward

Itu aman*. Mengapa? Karena standarnya tidak mengatakan tidak aman. Mereka menyalin fungsi dari 25.3.1 memiliki Memerlukan: untuk hal-hal yang diperlukan (di sinilah larangan yang tumpang tindih dinyatakan dalam formulir salinan lainnya).

Namun, copy_n tidak mengatakan bahwa rentang tersebut tidak boleh tumpang tindih, yang berarti tidak masalah, karena tidak dilarang secara eksplisit. Jika diperlukan, ia akan menyatakannya.

*Sunting: Yang saya maksud adalah "aman", yang saya maksud bukanlah perilaku tidak terdefinisi atau program yang salah untuk melakukan hal tersebut. Namun, hasilnya tidak dijamin sesuai dengan yang Anda inginkan jika rentang memori tumpang tindih. Satu-satunya hal yang kami jamin adalah:

  1. Untuk setiap bilangan bulat non-negatif i < n, *(result + i) = *(first + i) dilakukan
  2. Memanggil fungsi dengan rentang yang tumpang tindih tidak dilarang dan tidak mengakibatkan perilaku tidak terdefinisi.

Dengan demikian kita dapat menyimpulkan bahwa jika rentangnya tumpang tindih, maka hasil yang disimpan di tujuan tidak lagi dijamin merupakan salinan persis dari sumbernya. Kami menjamin bahwa setiap nilai di tujuan akan berasal dari sumbernya, meskipun nilai persisnya bergantung pada tumpang tindih dan urutan pasti elemen yang disalin.

Jadi jika yang Anda maksud dengan "aman" adalah bahwa tujuan selalu memiliki salinan sempurna dari sumbernya (seperti memmove), maka tidak, itu tidak "aman". Namun aman dalam arti tidak akan menyebabkan perilaku tidak terdefinisi/tidak valid.

Singkatnya, kami menjamin bahwa *(result + i) = *(first + i) akan dilakukan untuk setiap elemen di seluruh rentang. Kami menjamin bahwa jika rentangnya tumpang tindih, program masih belum terdefinisi. Kami tidak menjamin urutan penyalinan elemen. Kami tidak menjamin bahwa jika rentangnya tumpang tindih, berapa nilai pasti yang disimpan dalam hasilnya (tetapi kami tahu bahwa semuanya berasal dari sumbernya).

person Cornstalks    schedule 23.12.2013
comment
Bagaimana copy_n melakukan pemeriksaan keamanan ketika iterator tidak mendukung akses acak? (Ini hanya membutuhkan iterator masukan dan iterator keluaran....) - person Billy ONeal; 23.12.2013
comment
@Billy cplusplus.com mengatakan If the ranges overlap, some of the elements in the range pointed by result may have undefined but valid values. Tapi saya tidak tahu seberapa andalnya hal itu. - person ; 23.12.2013
comment
@remyabel: cplusplus.com == tidak bisa diandalkan sekali. :) - person Billy ONeal; 23.12.2013
comment
@BillyONeal: Diperbarui. Maaf, maksud saya awalnya aman berbeda dari yang mungkin Anda gunakan. - person Cornstalks; 23.12.2013
comment
Jadi melewati rentang yang tumpang tindih diperbolehkan, tetapi sebenarnya melakukan hal itu memiliki hasil yang tidak dapat diprediksi dan oleh karena itu tidak ada gunanya dalam setiap kasus yang mungkin terjadi? Spesifikasi yang aneh. Mengapa tidak memperlakukan ini sama dengan fungsi copy lainnya? Apa yang mungkin mereka pikirkan? (Saya setuju bahwa itulah yang dikatakan spesifikasinya, jadi +1. Tapi betapa anehnya.) - person Nemo; 23.12.2013
comment
@Nemo: Saya setuju itu aneh. Saya berharap mereka melarangnya, atau setidaknya secara eksplisit mengatakan Anda dapat melakukan ini, tetapi Anda mungkin mendapatkan sampah kembali. - person Cornstalks; 23.12.2013

arrow_upward
1
arrow_downward

Saya setuju dengan jawaban Cornstalks, dan memberi +1 padanya. Tapi, teori harus didukung dengan praktik.

Sekilas tentang implementasi GCC (libstdc++-v3) dan Clang (libc++) menunjukkan bahwa copy_n mereka sama dengan (atau didelegasikan ke) copy, tanpa dukungan untuk tumpang tindih saat memindahkan objek ke alamat yang lebih tinggi.

Jadi, MSVC memenangkan putaran ini, setidaknya dalam kasus POD yang didelegasikan ke memmove.

person Potatoswatter    schedule 23.12.2013