วิธีที่ดีที่สุดในการรวมคอนเทนเนอร์ STL หลายรายการโดยลบองค์ประกอบที่ซ้ำกันออก

ฉันมีคอนเทนเนอร์ STL สองคอนเทนเนอร์ที่ฉันต้องการรวม โดยลบองค์ประกอบใดๆ ที่ปรากฏมากกว่าหนึ่งครั้ง ตัวอย่างเช่น:

typedef std::list<int> container;
container c1;
container c2;

c1.push_back(1);
c1.push_back(2);
c1.push_back(3);

c2.push_back(2);
c2.push_back(3);
c2.push_back(4);

container c3 = unique_merge(c1, c2);
// c3 now contains the following 4 elements:
//   1, 2, 3, 4

std::unique ดูเหมือนจะมีไว้สำหรับองค์ประกอบที่อยู่ติดกันเท่านั้น และในกรณีของฉัน คอนเทนเนอร์อาจอยู่ในลำดับใดก็ได้ ฉันสามารถทำกลอุบาย std::set ได้บ้าง ฉันเดาว่า:

container unique_merge(const container& c1, const container& c2)
{
    std::set<container::value_type> s;
    BOOST_FOREACH(const container::value_type& val, c1)
        s.insert(val);
    BOOST_FOREACH(const container::value_type& val, c2)
        s.insert(val);
    return container(s.begin(), s.end());
}

มีวิธีที่ดีกว่าหรือฉันพลาดบางสิ่งบางอย่างที่ชัดเจนหรือไม่?


c++ stl
person Rob    schedule 11.11.2008    source แหล่งที่มา
comment
หากคุณขอให้มีบางสิ่งที่ชัดเจน การนำไปปฏิบัติของคุณก็ดีเพียงพอสำหรับกรณีส่วนใหญ่ แต่มีอัลกอริธึมที่ดีกว่าอยู่ โดยที่ O(N * log(M)) โดยที่ N คือจำนวนองค์ประกอบทั้งหมดในคอนเทนเนอร์ทั้งหมด และ M คือจำนวนคอนเทนเนอร์ รหัสไม่ใช่เรื่องเล็กน้อย ฉันจะเขียนทีหลังเมื่อฉันมีเวลา   -  person RnMss    schedule 01.04.2014
comment
@RnMss จริงเหรอ? คุณสามารถโพสต์คำตอบได้หรือไม่? ...   -  person user202729    schedule 04.04.2018
comment
@ user202729 โอ้พระเจ้า มันเป็นปี 2014...   -  person RnMss    schedule 07.04.2018
comment
@ user202729 ตอนนี้ฉันไม่แน่ใจเกี่ยวกับมัน ฉันคิดว่า ... ตัดสินจากสิ่งที่ฉันเขียนว่า ... บางที ... ในเวลานั้นฉันคิดว่าแต่ละคอนเทนเนอร์ได้รับการจัดเรียงแล้ว แต่จำนวนคอนเทนเนอร์อาจเป็นจำนวนที่มากกว่า (เช่น 1,000 หรือมากกว่า)   -  person RnMss    schedule 12.04.2018

คำตอบ (3)


arrow_upward
7
arrow_downward

สำหรับรายการที่ไม่เรียงลำดับ เคล็ดลับชุดของคุณน่าจะเป็นหนึ่งในสิ่งที่ดีที่สุด เม็ดมีดแต่ละอันควรเป็น O(log n) โดยต้องมีเม็ดมีด N และการเคลื่อนที่ข้ามจะเป็น O(n) ทำให้คุณได้รับ O(N*log n) ตัวเลือกอื่นคือการรัน std::sort ในแต่ละรายการแยกกัน จากนั้นดำเนินการผ่านรายการเหล่านั้นแบบขนานโดยใช้ std::set_union ซึ่งจะลบรายการที่ซ้ำกันออกให้คุณ นี่จะเป็น O(n*log n) ด้วย ดังนั้นหากคุณกังวลเกี่ยวกับประสิทธิภาพ คุณจะต้องโปรไฟล์ หากคุณไม่ทำสิ่งใดที่เหมาะสมกับคุณมากกว่า

แก้ไข: set_union จะใช้ได้ก็ต่อเมื่อไม่มีรายการซ้ำในรายการเดิม ไม่เช่นนั้นคุณจะต้องใช้ sort, merge, unique และ erase ประสิทธิภาพ O ขนาดใหญ่ยังคงเหมือนเดิม โดยมีข้อควรระวังเกี่ยวกับการทำโปรไฟล์เหมือนกัน

template <typename container>
container unique_merge(container c1, container c2)
{
    std::sort(c1.begin(), c1.end());
    std::sort(c2.begin(), c2.end());
    container mergeTarget;
    std::merge(c1.begin(), c1.end(), c2.begin(), c2.end(), 
        std::insert_iterator(mergeTarget, mergeTarget.end())
    );
    std::erase(
        std::unique(mergeTarget.begin(), mergeTarget.end()), 
        mergeTarget.end()
    );

    return mergeTarget;
}
person Eclipse    schedule 11.11.2008
comment
ตามข้อกำหนดสำหรับ std::set_union: หากมีองค์ประกอบที่ซ้ำกันในสองช่วง R1 และ R2 บอกว่า V เกิดขึ้น N ครั้งใน R1 และ M ครั้งใน R2 ผลลัพธ์ของ std::set_union จะมีค่า max(N, M) อินสแตนซ์ของ V ดังนั้นยกเว้นว่า N‹=1 และ M‹=1 มันก็ไม่ใช่วิธีแก้ปัญหาที่ถูกต้อง - person Andreas Magnusson; 12.11.2008
comment
นั่นคือสิ่งที่ฉันได้รับจากการไม่ทดสอบการคอมไพล์ - person Eclipse; 12.11.2008

arrow_upward
4
arrow_downward

คุณจะต้องเรียงลำดับอย่างใดอย่างหนึ่ง (ไม่ว่าจะชัดเจนหรือโดยปริยายผ่านคอนเทนเนอร์ที่เรียงลำดับเหมือนชุด)

มีสำนวนทั่วไปที่ใช้ std::sort/std::unique/std::erase เพื่อรับองค์ประกอบที่ไม่ซ้ำกันในคอนเทนเนอร์

ดังนั้นสร้างคอนเทนเนอร์ที่มีเนื้อหาของ c1 ต่อท้ายเนื้อหาของ c2 จากนั้นเรียงลำดับ ย้ายองค์ประกอบที่ไม่ซ้ำกันไปที่จุดสิ้นสุด แล้วลบออก บางสิ่งเช่นนี้:

container c(c1.begin(), c1.end());
c.insert(c.end(), c2.begin(), c2.end());
c.erase(std::unique(c.begin(), c.end()), c.end());
person Chris Morley    schedule 11.11.2008

arrow_upward
3
arrow_downward

ใช้ std::set_unionอัลกอริทึมจาก STL คุณจะต้องเรียงลำดับรายการอินพุตของคุณก่อน -- หรือสร้างสำเนาของรายการอินพุตของคุณ เรียงลำดับแล้วใช้ std::set_union

person Uhall    schedule 11.11.2008