• Both algorithms move all elements

• Both algorithms move all elements in the range [beg,end) to the front, for which the unary predicate op(elem) yields true. • Both algorithms return the first position for which op() yields false. • The difference between partition() and stable_partition() is that the algorithm stable_partition() preservestherelativeorderofelementsthatmatchthecriterionandthose that do not. • You could use this algorithmto split elementsintotwo parts accordingto a sortingcriterion. The nth_element() algorithm has a similar ability. See Section 11.2.2, page 514, for a discussion of the differences between these algorithms and nth_element(). • Note that op should not change its state during a function call. See Section 10.1.4, page 483, for details. • Before C++11, partition() required bidirectional iterators instead of forward iterators and guaranteed at most numElems/2 swaps. • Use partition_copy() (see Section 11.8.6, page 594) to copy elements into one destination range for fulfilling and one for not fulfilling a predicate (available since C++11). • Complexity: – Forpartition(): linear(atmostnumElems/2swapsandnumElemscallsofop()ifbidirec- tional iterators or random-access iterators are used; at most numElems swaps if the iterators are only forward iterators). – For stable_partition(): linear if there is enough extra memory (numElems swaps and calls of op()); otherwise, n-log-n (numElems calls of op() but numElems*log(numElems) swaps). The following program demonstrates the use of and the difference between partition() and stable_partition():

ผลลัพธ์ (ไทย) 1:

•อัลกอริทึมทั้งสองย้ายองค์ประกอบทั้งหมดในช่วง [beg,end) หน้า สำหรับที่ op(elem) เพรดิเคตเดี่ยวทำให้จริง •อัลกอริทึมทั้งสองกลับตำแหน่ง first สำหรับการคำนวณอัตราผลตอบแทนที่ op() •ความแตกต่างระหว่าง partition() และ stable_partition() ได้ที่ preservestherelativeorderofelementsthatmatchthecriterionandthose stable_partition() อัลกอริทึมที่ไม่ •คุณสามารถใช้ algorithmto นี้แบ่งส่วน elementsintotwo ตาม sortingcriterion อัลกอริทึม nth_element() มีความคล้ายคลึงกัน ดูหัวข้อ 11.2.2 หน้า 514 สำหรับคำอธิบายเกี่ยวกับความแตกต่างระหว่าง nth_element() และอัลกอริทึมเหล่านี้ หมายเหตุ• op ที่ควรเปลี่ยนสถานะในระหว่างการเรียกฟังก์ชัน ดูหัวข้อ 10.1.4 หน้า 483 รายละเอียด •ก่อน C 11 partition() ต้องใช้ iterators ทิศแทน iterators ไปข้างหน้า และรับประกัน swaps ที่สุด numElems/2 • Partition_copy() ใช้ (ดูส่วน 11.8.6 หน้า 594) เพื่อคัดลอกองค์ประกอบลงในช่วงปลายทางหนึ่งสำหรับ fulfilling และสำหรับ fulfilling ไม่เพรดิเคต (ใช้ได้ตั้งแต่ C 11) •ความซับซ้อน: -Forpartition(): เชิงเส้น (ใช้ iterators ifbidirec tional () atmostnumElems/2swapsandnumElemscallsofop หรือเข้าถึงโดยสุ่ม iterators มากที่สุด numElems swaps ถ้า iterators ที่มีเฉพาะ iterators ไปข้างหน้า) -สำหรับ stable_partition(): มีหน่วยความจำเสริมเพียงพอ (numElems swaps และเรียก op()) เชิง อื่น ๆ n-บันทึก-n (เรียก numElems ของ op() แต่ numElems*log(numElems) swaps) โปรแกรมต่อไปนี้สาธิตการใช้และความแตกต่างระหว่าง partition() และ stable_partition():

ผลลัพธ์ (ไทย) 2:

•ขั้นตอนวิธีการทั้งสองย้ายองค์ประกอบทั้งหมดที่อยู่ในช่วง [ขอจบ) ไปด้านหน้าซึ่งสหกรณ์ภาคเอก (elem) อัตราผลตอบแทนที่แท้จริง •ขั้นตอนวิธีการทั้งสองกลับตำแหน่งครั้งแรกสำหรับสหกรณ์ซึ่ง () อัตราผลตอบแทนที่ผิดพลาด •ความแตกต่างระหว่างพาร์ทิชัน () และ stable_partition () เป็นที่ preservestherelativeorderofelementsthatmatchthecr​​iterionandthose stable_partition ขั้นตอนวิธี () ที่ทำไม่ได้ •คุณสามารถใช้ algorithmto นี้แยก elementsintotwo ส่วน accordingto sortingcriterion nth_element () ขั้นตอนวิธีการมีความสามารถที่คล้ายกัน ดูมาตรา 11.2.2, หน้า 514, สำหรับการอภิปรายของความแตกต่างระหว่างขั้นตอนวิธีการเหล่านี้และ nth_element () •หมายเหตุสหกรณ์ที่ไม่ควรเปลี่ยนสถานะของตนในระหว่างการเรียกใช้ฟังก์ชัน ดูมาตรา 10.1.4, หน้า 483 สำหรับรายละเอียด •ก่อน C + +11 พาร์ทิชัน () ที่จำเป็น iterators แบบสองทิศทางแทน iterators ไปข้างหน้าและการรับประกันที่มากที่สุด numElems / 2 สัญญาแลกเปลี่ยน •ใช้ partition_copy () (ดูมาตรา 11.8.6, หน้า 594) เพื่อคัดลอกองค์ประกอบลงในช่วงหนึ่งในปลายทางเพื่อตอบสนองและเป็นหนึ่งในไม่ตอบสนองคำกริยา (ใช้ได้ตั้งแต่ C + +11) •ซับซ้อน: - Forpartition () เชิงเส้น (atmostnumElems/2swapsandnumElemscallsofop () ifbidirec-tional iterators หรือ iterators random-access จะใช้ที่มากที่สุดแลกเปลี่ยน numElems ถ้า iterators เป็นเพียงไปข้างหน้า iterators) - สำหรับ stable_partition (): เชิงเส้นในกรณีที่มีหน่วยความจำเสริมพอ (แลกเปลี่ยน numElems การใช้โทรศัพท์ของสหกรณ์ ()) มิฉะนั้น-n log n (numElems สายของสหกรณ์ () แต่ numElems * log (numElems) สัญญาแลกเปลี่ยน) โปรแกรมต่อไปนี้แสดงให้เห็นถึงการใช้และความแตกต่างระหว่างพาร์ทิชัน () และ stable_partition ():

ผลลัพธ์ (ไทย) 3:

- ทั้งขั้นตอนวิธีการย้ายองค์ประกอบทั้งหมดในช่วง [ ขอร้อง จบ ) ไปด้านหน้า ซึ่ง OP ภาคแสดงนารี ( ใส้ ) อัตราผลตอบแทนที่แท้จริง - ทั้งขั้นตอนวิธีการคืนตำแหน่งแรกที่ op() ผลผลิตจึงเป็นเท็จ - ความแตกต่างระหว่างและ partition() stable_partition() คือขั้นตอนวิธี stable_partition() preservestherelativeorderofelementsthatmatchthecriterionandthose ที่ไม่- คุณสามารถใช้นี้ algorithmto แยก elementsintotwo ชิ้นส่วนตามแบบ sortingcriterion . การ nth_element() ขั้นตอนวิธีมีความสามารถที่คล้ายคลึงกัน ดูส่วน 11.2.2 หน้า 514 สำหรับการอภิปรายของความแตกต่างระหว่างอัลกอริทึมเหล่านี้และ nth_element() . - สังเกตว่า OP ไม่ควรเปลี่ยนสถานะของมันในระหว่างการเรียกใช้ฟังก์ชัน ดูส่วน 10.1.4 หน้า 483 , รายละเอียด - ก่อน C 11partition() บังคับใช้ลำดับชั้น iterators แทน iterators ไปข้างหน้าและการรับประกัน numelems ที่สุด / 2 swaps - ใช้ partition_copy() ( ดูมาตรา 11.8.6 หน้า 174 ) เพื่อคัดลอกองค์ประกอบเป็นหนึ่งปลายทางช่วงระหว่างประเทศ จึงครบและไม่ครบจึงบอกภาคแสดง ( ใช้ได้ตั้งแต่ ซี 11 ) บริการ forpartition() ความซับซ้อน : ) :เส้น ( atmostnumelems / 2swapsandnumelemscallsofop() ifbidirec - iterators tional หรือการเข้าถึงแบบสุ่ม iterators ใช้ ; มากที่สุด numelems แลกเปลี่ยนถ้า iterators เพียงไปข้างหน้า iterators ) 2552 stable_partition() : เชิงเส้น ถ้ามีพอเพิ่มหน่วยความจำ ( numelems แลกเปลี่ยนและสายของ op() ) ; อย่างอื่น , n-log-n ( numelems โทร op() แต่ numelems * บันทึก ( numelems ) Swaps )รายการต่อไปนี้แสดงให้เห็นถึงการใช้และความแตกต่างระหว่าง stable_partition() :
partition() และ