เพิ่มปัญหาการลบตัววนซ้ำ multi_index แบบย้อนกลับ

ฉันมีรหัส (ตัวย่อ) ต่อไปนี้:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
namespace bmi = boost::multi_index;

#include <string>
#include <iostream>
#include <cassert>

using Container = boost::multi_index_container<
    std::string,
    bmi::indexed_by< bmi::ordered_non_unique< bmi::identity<std::string> > >
>;

/// Get the base of a non-reverse iterator. It's the iterator itself.
inline
Container::iterator const&
iter_base(Container::iterator const& it)
{
    return it;
}

/** Get a non-reverse iterator that points at the same element as the given reverse_iterator.
 *
 * @param rit reverse_iterator
 * @return a (non-reverse) iterator that points to the same element.
 * @pre @p rit is dereferenceable (not equal to @c rend() of whatever container @p rit came from)
 */
inline
Container::iterator
iter_base(Container::reverse_iterator const& rit)
{
    auto bit = rit.base();
    // if 'rit' is a reverse iterator: &*(rit.base() - 1) == &*rit
    return --bit;
}

template <typename IT>
void evict(Container& c, IT rb, IT fin)
{
    std::vector<std::string> result;
    for (; rb != fin; ) {
        if (rb->size() == 3) {
            auto victim = rb;
            ++rb;
            std::cout << "victim->" << *victim << ", next->" << (rb==fin ? std::string{"THE END"} : *rb) << "\n";
            auto next = c.erase(iter_base(victim));
            std::cout << "size=" << c.size() << "\n";
            for (auto const& s : c) {
                std::cout << "remain: " << s << "\n"; // bar - baz - foo
            }

            rb = IT(next);
            (void)next;
        }
        else {
            result.push_back(*rb);
        }
    }
}

int main(int argc, char**)
{
    bool forward = (argc == 1);

    Container c;
    c.insert("foo"); // will be last
    c.insert("bar");
    c.insert("baz");

    if (forward) {
        auto b = c.lower_bound("baz");

        std::cout << ">> " << *b << "\n"; // prints baz

        auto rb = (b);
        std::cout << "<< " << *rb            << "\n"; // prints baz
        std::cout << "<< " << *iter_base(rb) << "\n"; // prints baz

        evict(c, rb, c.end());
    }
    else {
        auto b = c.upper_bound("baz");

        std::cout << ">> " << *b << "\n"; // prints foo

        auto rb = Container::reverse_iterator(b);
        std::cout << "<< " << *rb            << "\n"; // prints baz
        std::cout << "<< " << *iter_base(rb) << "\n"; // prints baz

        evict(c, rb, c.rend());
    }
}

โค้ดจริงไม่เพียงแต่ลบข้อมูลเท่านั้น แต่ยังเพียงพอที่จะแสดงให้เห็นพฤติกรรมดังกล่าวอีกด้วย

แก้ไขเพื่อแสดงว่าไม่มีการลบเกิดขึ้นในลูป ควรเพิ่มรายการใน result ตามลำดับไปข้างหน้าหรือย้อนกลับ ขึ้นอยู่กับประเภทของตัววนซ้ำที่ใช้

เมื่อทำงานโดยไม่มีข้อโต้แย้ง forward==true และผลลัพธ์เป็นไปตามที่คาดไว้:

>> baz
<< baz
<< baz
victim->baz, next->foo
size=2
remain: bar
remain: foo
victim->foo, next->THE END
size=1
remain: bar

เมื่อรันด้วยอาร์กิวเมนต์ forward==false และผลลัพธ์คือ:

>> foo
<< baz
<< baz
victim->baz, next->bar
size=2
remain: bar
remain: foo
segmentation fault (core dumped)

(ไม่เป็นไปตามที่คาดไว้)

การคอมไพล์ด้วย address sanitizer จะแสดง heap-use-after-free ในบรรทัดที่ 42 (บรรทัด ++rb)

ดูเหมือนว่าการโทร erase(victim) ทำให้ rb ไม่ถูกต้อง แม้ว่าการลบจะไม่ทำให้ตัววนซ้ำอื่น ๆ เป็นโมฆะก็ตาม

มีความคิดอะไรบ้างที่ฉันทำอะไรผิด?


person Bulletmagnet    schedule 14.10.2016    source แหล่งที่มา


คำตอบ (2)


คำตอบที่สอง พร้อมคำขอเพิ่มเติมจาก OP ว่าการแวะผ่านสามารถทำได้ในลำดับโดยตรงหรือย้อนกลับตามลักษณะของตัววนซ้ำ ด้วยความระมัดระวังเล็กน้อย สิ่งนี้สามารถทำได้ดังนี้:

template <typename IT>
void evict(Container& c, IT rb, IT fin)
{
    std::vector<std::string> result;
    if(rb != fin) for(;;) {
        IT next = rb;
        ++next;
        bool finished  = (next == fin);
        if (rb->size() == 3) {
            c.erase(iter_base(rb));
            std::cout << "size=" << c.size() << "\n";
            for (auto const& s : c) {
                std::cout << "remain: " << s << "\n"; // bar - baz - foo
            }
        }
        else {
            result.push_back(*rb);
        }
        if(finished) break;
        rb = next;
    }
}

แย่จัง โค้ดที่โดนโจมตียังคงทำงานอยู่ใน UB โปรดลองสิ่งนี้:

template <typename IT>
void evict(Container& c, IT rb, IT fin)
{
    std::vector<std::string> result;
    if(rb != fin) for(;;) {
        bool finished  = (std::next(rb) == fin);
        if (rb->size() == 3) {
            rb = IT{c.erase(iter_base(rb))};
            std::cout << "size=" << c.size() << "\n";
            for (auto const& s : c) {
                std::cout << "remain: " << s << "\n"; // bar - baz - foo
            }

        }
        else {
            result.push_back(*rb);
        }
        if(finished) break;
    }
}
person Joaquín M López Muñoz    schedule 15.10.2016
comment
น่าเสียดายที่นี่ไม่ได้ช่วยอะไร ฮีป-ใช้-หลัง-ฟรียังคงอยู่ (ในบรรทัด ++next) - person Bulletmagnet; 15.10.2016
comment
คุณได้คัดลอกโค้ด คำต่อคำ ที่เสนอโดยตรงหรือไม่ หมายเหตุเช่นส่วน if(rb != fin) for(;;) - person Joaquín M López Muñoz; 15.10.2016
comment
ขออภัย วิธีแก้ปัญหาที่เสนอมีข้อผิดพลาดจริงๆ แก้ไขโดยหวังว่าจะเป็นทางเลือกที่ถูกต้อง - person Joaquín M López Muñoz; 15.10.2016

โอเค การจัดการกับ Reverse Iterators เป็นเรื่องที่น่าปวดหัว มาวิเคราะห์ธุรกิจตัวชี้ระหว่างการดำเนินการของโค้ดส่วนนี้ของ evict:

auto victim = rb;
++rb;
auto next = c.erase(iter_base(victim));

เมื่ออยู่ในสายไปที่ evict(c, Container::reverse_iterator(c.upper_bound("baz")), c.rend()) โดย "ชี้ไปที่" ฉันหมายถึง "ตัววนซ้ำภายในชี้ไปที่" เรามีทีละขั้นตอน:

  1. ก่อนที่จะป้อนรหัส: rb ชี้ไปที่ "foo", victim ยังไม่มีอยู่

    auto victim = rb;

  2. rb ชี้ไปที่ "foo", victim ชี้ไปที่ "foo"

    ++rb;

  3. rb ชี้ไปที่ "baz", victim ชี้ไปที่ "foo"

    auto next = c.erase(iter_base(victim));

  4. "baz" ถูกลบแล้ว, rb ชี้ไปที่ ลบแล้ว "baz", victim ชี้ไปที่ "foo" การดำเนินการอ้างอิง การเปรียบเทียบ หรือ (de/in) การเพิ่มค่าเพิ่มเติมใดๆ ด้วย rb ถือเป็นลักษณะการทำงานที่ไม่ได้กำหนดไว้

ฉันเข้าใจว่าคุณกำลังพยายามเขียนฟังก์ชัน evict ที่ใช้ได้กับทั้งตัววนซ้ำและตัววนซ้ำ วิธีหนึ่งที่เป็นไปได้ในการทำมีดังนี้:

template<typename Container>
std::pair<typename Container::iterator,typename Container::iterator>
direct_range(
  typename Container::iterator first,
  typename Container::iterator last)
{
  return {first,last};
}

template<typename Container>
std::pair<typename Container::iterator,typename Container::iterator>
direct_range(
  typename Container::reverse_iterator first,
  typename Container::reverse_iterator last)
{
  return {last.base(),first.base()};
}

template <typename IT>
void evict(Container& c, IT rb, IT fin)
{
  auto p=direct_range<Container>(rb,fin);
  c.erase(p.first,p.second);

  for(auto const& s:c){
    std::cout<<"remain: "<<s<<"\n"; // bar - baz - foo
  }
}
person Joaquín M López Muñoz    schedule 14.10.2016
comment
ขอบคุณ. น่าเสียดายที่โค้ดจริงไม่ง่ายพอที่จะใช้ erase(iterator, iterator) (ลองนึกภาพว่าจะต้องลบองค์ประกอบบางส่วนเท่านั้น) - person Bulletmagnet; 14.10.2016
comment
คุณเขียนว่า 4. baz ถูกลบไปแล้ว นี่เป็นเพราะ iter_base(victim) - ตัววนซ้ำ - ชี้ไปที่องค์ประกอบเดียวกันกับ rb - ตัววนซ้ำ - ? - person Bulletmagnet; 14.10.2016
comment
ในการตอบกลับครั้งแรกของคุณ: เมื่อคุณได้ผลลัพธ์เป็น direct_range แล้ว คุณสามารถแทนที่ erase(iterator,iterator) ด้วยโค้ดที่ซับซ้อนมากขึ้นซึ่งทำงานกับตัววนซ้ำที่ไม่ย้อนกลับได้ - person Joaquín M López Muñoz; 15.10.2016
comment
คำตอบที่สองของคุณ: ใช่ - person Joaquín M López Muñoz; 15.10.2016
comment
ฉันแก้ไขลูปใน evict เพื่อแสดงว่าไม่ใช่แค่การลบเกิดขึ้นในลูป สำหรับฉันดูเหมือนว่าฉันไม่สามารถใช้ direct_range ในกรณีนี้ได้ (การวนซ้ำมากกว่า direct_range จะประมวลผลองค์ประกอบตามลำดับไปข้างหน้าเสมอ - มันจะเติมเวกเตอร์ในลำดับที่ไม่ถูกต้องเมื่อเรียกด้วย Reverse_iterators) - person Bulletmagnet; 15.10.2016