std::copy_n ทำงานกับช่วงที่ทับซ้อนกันหรือไม่

ฉันกำลังดูมาตรฐาน C++ ที่ N3485 25.3.1 [alg.copy] ซึ่งกำหนดอัลกอริธึม 4 แบบ:

  • copy
  • copy_backward
  • copy_if
  • copy_n

ในคำอธิบายสำหรับ copy มีหมายเหตุ 25.3.1 [alg.copy]/3 นี้:

ต้องการ: ผลลัพธ์จะต้องไม่อยู่ในช่วง [แรก, สุดท้าย)

นั่นคือ copy ทำงานไม่ถูกต้องเสมอไปเมื่อช่วงทับซ้อนกัน (คล้ายกับ memcpy)

copy_backward และ copy_if มีภาษาที่คล้ายกันซึ่งห้ามไม่ให้มีช่วงที่ทับซ้อนกัน (25.3.1 [alg.copy]/14 และ 25.3.1 [alg.copy]/8 ตามลำดับ)

อย่างไรก็ตาม ไม่มีข้อห้ามดังกล่าวสำหรับ copy_n และไม่มี copy_n_backward นี่หมายความว่า copy_n ทำสิ่งที่ถูกต้องเมื่อช่วงคาบเกี่ยวกันใช่หรือไม่

(การใช้งาน copy_n ของ MSVC++ ดูเหมือนจะมอบสิทธิ์ให้กับ std::memmove ดังนั้นฉันรู้ว่ามันปลอดภัยที่นี่ใน MSVC++ 2013 แต่ฉันไม่ต้องการพึ่งพาสิ่งนี้หากมาตรฐานบอกเป็นอย่างอื่น)


c++ algorithm stl stl-algorithm
person Billy ONeal    schedule 23.12.2013    source แหล่งที่มา
comment
การใช้งาน copy_n ของ MSVC++ ดูเหมือนจะมอบสิทธิ์ให้กับ std::memmove โปรดทราบว่าเราทำสิ่งนี้เฉพาะเมื่อการเปลี่ยนแปลงนั้นถูกต้องเท่านั้น นั่นคือ โดยที่ตัววนซ้ำเป็นตัวชี้ไปยังอ็อบเจ็กต์ที่สามารถคัดลอกได้เล็กน้อย   -  person James McNellis    schedule 23.12.2013
comment
@เจมส์: แน่นอน :) ในกรณีนี้เกิดขึ้นว่านี่คือการเปลี่ยนแปลงที่ปลอดภัย   -  person Billy ONeal    schedule 23.12.2013
comment
@James: อ่า ฉันเข้าใจประเด็นของคุณแล้ว หากอินพุตเป็นเช่น std::list ตัววนซ้ำ มันจะไม่ปลอดภัยในการใช้งานของ MSVC++ ฟังดูเหมือนเป็นคำตอบสำหรับฉัน...   -  person Billy ONeal    schedule 23.12.2013
comment
ว้าว นั่นเป็นกรณีขอบแปลก ๆ ฉันอยากจะบอกว่ามันอาจเป็นข้อผิดพลาด (พวกเขาตั้งใจให้เป็น UB) แต่ดูเหมือนว่าเกือบจะจงใจละเลย...   -  person user541686    schedule 23.12.2013
comment
การใช้งาน SGI ดั้งเดิมมีข้อกำหนดดังกล่าวสำหรับ copy_n ฉันไม่รู้ว่าทำไมสิ่งนี้ถึงไม่อยู่ในมาตรฐาน คุณสามารถส่งปัญหาได้ BTW, copy ห้ามเฉพาะการทับซ้อนกันซึ่งเอาต์พุต เริ่มต้น ในช่วงอินพุต แต่จะทำงานได้ดีเมื่อช่วงเอาต์พุต สิ้นสุด อยู่ในช่วงอินพุต (เช่น การคัดลอกไปทางซ้าย)   -  person TemplateRex    schedule 04.01.2014

คำตอบ (2)


arrow_upward
3
arrow_downward

มันมีความปลอดภัย*. ทำไม เพราะมาตรฐานไม่ได้บอกว่า ไม่ ปลอดภัย พวกเขาคัดลอกฟังก์ชันจาก 25.3.1 มี Requires: สำหรับสิ่งที่พวกเขาต้องการ (นี่คือที่ซึ่งข้อห้ามที่ทับซ้อนกันระบุไว้ในแบบฟอร์มการคัดลอกอื่นๆ)

อย่างไรก็ตาม copy_n ไม่ บอกว่าต้องการให้ช่วงไม่ทับซ้อนกัน ซึ่งหมายความว่าไม่เป็นไร เนื่องจากไม่ได้ถูกห้ามอย่างชัดเจน หากจำเป็นก็จะระบุ

*แก้ไข: เมื่อฉันหมายถึง "ปลอดภัย" ฉันหมายความว่ามันไม่ใช่พฤติกรรมที่ไม่ได้กำหนดไว้หรือเป็นโปรแกรมที่มีรูปแบบไม่ถูกต้อง อย่างไรก็ตาม ไม่รับประกันผลลัพธ์ว่าจะเป็นไปตามที่คุณต้องการหากช่วงหน่วยความจำทับซ้อนกัน สิ่งเดียวที่เรารับประกันคือ:

  1. สำหรับจำนวนเต็มที่ไม่ใช่ลบแต่ละตัว i < n จะดำเนินการ *(result + i) = *(first + i)
  2. ไม่อนุญาตให้เรียกใช้ฟังก์ชันที่มีช่วงทับซ้อนกัน และไม่ส่งผลให้เกิดการทำงานที่ไม่ได้กำหนดไว้

ดังนั้นเราจึงอนุมานได้ว่าหากช่วงทับซ้อนกัน ผลลัพธ์ที่จัดเก็บไว้ในปลายทางจะไม่รับประกันว่าจะเป็นสำเนาของแหล่งที่มา (ตามลำดับ) อีกต่อไป เรารับประกันว่าทุกค่าในปลายทางจะมาจากแหล่งที่มา แม้ว่าค่าเหล่านั้นจะขึ้นอยู่กับการทับซ้อนกันและลำดับที่แน่นอนในการคัดลอกองค์ประกอบก็ตาม

ดังนั้น หากโดย "ปลอดภัย" คุณหมายความว่าปลายทางมีสำเนาของแหล่งที่มาที่สมบูรณ์แบบเสมอ (เช่น memmove) ก็แสดงว่าไม่ มันไม่ "ปลอดภัย" แต่จะปลอดภัยในแง่ที่ว่าจะไม่ทำให้เกิดพฤติกรรมที่ไม่ได้กำหนด/ไม่ถูกต้องในตัวมันเอง

สรุป เรารับประกันได้ว่า *(result + i) = *(first + i) จะดำเนินการกับทุกองค์ประกอบในช่วงทั้งหมด เรารับรองว่าหากช่วงทับซ้อนกันโปรแกรมก็ยังไม่ถูกกำหนดไว้ เราไม่รับประกันลำดับการคัดลอกองค์ประกอบ เราไม่รับประกันว่าหากช่วงทับซ้อนกัน ค่าที่แน่นอนที่เก็บไว้ในผลลัพธ์จะเป็นเท่าใด (แต่เรารู้ว่าค่าทั้งหมดมาจากแหล่งที่มา)

person Cornstalks    schedule 23.12.2013
comment
copy_n จะตรวจสอบความปลอดภัยอย่างไรเมื่อตัววนซ้ำไม่รองรับการเข้าถึงแบบสุ่ม (ต้องการเพียงตัววนซ้ำอินพุตและตัววนซ้ำเอาต์พุต....) - person Billy ONeal; 23.12.2013
comment
@Billy cplusplus.com พูดว่า If the ranges overlap, some of the elements in the range pointed by result may have undefined but valid values. แต่ฉันไม่รู้ว่ามันน่าเชื่อถือแค่ไหน - person ; 23.12.2013
comment
@remyabel: cplusplus.com == ไม่น่าเชื่อถือเลย :) - person Billy ONeal; 23.12.2013
comment
@BillyONeal: อัปเดตแล้ว ขออภัย ตอนแรกฉันหมายถึงความปลอดภัยแตกต่างจากที่คุณเคยใช้ - person Cornstalks; 23.12.2013
comment
ดังนั้นจึงอนุญาตให้ส่งช่วงที่ทับซ้อนกันได้ แต่จริงๆ แล้วการทำเช่นนั้นให้ผลลัพธ์ที่คาดเดาไม่ได้ ดังนั้นจึงไร้ประโยชน์ในทุกกรณีที่เป็นไปได้ สเปกมันแปลกๆนะ ทำไมไม่ปฏิบัติต่อสิ่งนี้เหมือนกับฟังก์ชัน copy อื่นๆ พวกเขาคิดอะไรอยู่กันแน่? (ฉันยอมรับว่านั่นคือสิ่งที่สเป็คดูเหมือนจะพูด ดังนั้น +1 แต่ช่างแปลกประหลาดเหลือเกิน) - person Nemo; 23.12.2013
comment
@Nemo: ฉันยอมรับว่ามันแปลกประหลาด ฉันหวังว่าพวกเขาจะห้ามมัน หรืออย่างน้อยก็บอกอย่างชัดเจนว่าคุณทำได้ แต่คุณอาจได้ขยะกลับคืนมา - person Cornstalks; 23.12.2013

arrow_upward
1
arrow_downward

ฉันเห็นด้วยกับคำตอบของ Cornstalks และ +1 ให้ แต่ทฤษฎีต้องได้รับการสนับสนุนจากการปฏิบัติ

การดูการใช้งาน GCC (libstdc++-v3) และ Clang (libc++) อย่างรวดเร็วแสดงให้เห็นว่า copy_n ของพวกเขาเหมือนกับ (หรือมอบหมายให้) copy โดยไม่มีการสนับสนุนสำหรับการทับซ้อนกันเมื่อย้ายวัตถุไปยังที่อยู่ที่สูงขึ้น

ดังนั้น MSVC ชนะรอบนี้ อย่างน้อยก็ในกรณี POD ซึ่งมอบหมายให้ memmove

person Potatoswatter    schedule 23.12.2013