meningkatkan multi_index membalikkan iterator menghapus masalah

Saya memiliki kode berikut (yang disederhanakan):

#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());
    }
}

Kode sebenarnya tidak hanya menghapus, tetapi ini cukup untuk menggambarkan perilaku tersebut.

DIEDIT untuk menunjukkan bahwa tidak ada penghapusan yang terjadi dalam loop. Item seharusnya ditambahkan ke result dalam urutan maju atau mundur tergantung pada jenis iterator yang digunakan.

Ketika dijalankan tanpa argumen, forward==true dan hasilnya seperti yang diharapkan:

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

Ketika dijalankan dengan argumen, forward==false dan outputnya adalah:

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

(tidak seperti yang diharapkan)

Kompilasi dengan pembersih alamat menunjukkan heap-use-after-free di baris 42 (baris ++rb).

Tampaknya pemanggilan erase(victim) telah membatalkan rb, meskipun penghapusan tidak seharusnya membatalkan iterator lainnya.

Tahu apa yang saya lakukan salah?


c++ boost c++11 boost-multi-index
person Bulletmagnet    schedule 14.10.2016    source sumber

Jawaban (2)


arrow_upward
2
arrow_downward

Jawaban kedua, dengan tambahan permintaan dari OP agar traversal dilakukan dalam urutan langsung atau terbalik sesuai dengan sifat iteratornya. Dengan sedikit hati-hati hal ini dapat dilakukan seperti ini: 

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;
    }
}

Sayang sekali, kode yang tercoreng masih berjalan ke UB. Silakan coba ini:

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
Sayangnya, hal ini tidak membantu. Heap-use-after-free tetap ada (di baris ++next). - person Bulletmagnet; 15.10.2016
comment
Sudahkah Anda langsung menyalin kode yang diusulkan verbatim? Perhatikan misalnya bagian if(rb != fin) for(;;). - person Joaquín M López Muñoz; 15.10.2016
comment
Maaf, solusi yang diajukan memang salah. Diedit dengan alternatif yang semoga benar. - person Joaquín M López Muñoz; 15.10.2016

arrow_upward
2
arrow_downward

Oke, berurusan dengan iterator terbalik sangat merepotkan. Mari kita menganalisis bisnis pointer selama eksekusi bagian kode evict ini:

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

ketika di dalam panggilan ke evict(c, Container::reverse_iterator(c.upper_bound("baz")), c.rend()). Yang saya maksud dengan "menunjuk ke" adalah "iterator internal menunjuk ke". Langkah demi langkah yang kami miliki:

  1. Sebelum memasukkan kode: rb tunjuk ke "foo", victim belum ada.

    auto victim = rb;

  2. rb menunjuk ke "foo", victim menunjuk ke "foo".

    ++rb;

  3. rb menunjuk ke "baz", victim menunjuk ke "foo".

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

  4. "baz" terhapus, rb menunjuk ke dihapus "baz", victim menunjuk ke "foo". Operasi dereferensi, perbandingan, atau penambahan (de/in) lebih lanjut dengan rb adalah perilaku yang tidak terdefinisi.

Saya memahami Anda mencoba menulis fungsi evict yang berfungsi dengan iterator dan iterator terbalik. Salah satu cara potensial untuk melakukannya adalah sebagai berikut:

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
Terima kasih. Sayangnya, kode sebenarnya tidak cukup sederhana untuk menggunakan erase(iterator, iterator) (bayangkan jika Anda mau, hanya beberapa elemen yang harus dihapus). - person Bulletmagnet; 14.10.2016
comment
Anda menulis 4. baz terhapus. Apakah ini karena iter_base(victim) - sebuah iterator - menunjuk ke elemen yang sama dengan rb - sebuah iterator terbalik - ? - person Bulletmagnet; 14.10.2016
comment
Untuk balasan pertama Anda: setelah Anda mendapatkan hasil direct_range, Anda dapat mengganti erase(iterator,iterator) dengan kode yang lebih rumit yang bekerja pada iterator non-balik. - person Joaquín M López Muñoz; 15.10.2016
comment
Untuk balasan kedua Anda: ya. - person Joaquín M López Muñoz; 15.10.2016
comment
Saya mengedit loop di evict untuk menunjukkan bahwa tidak hanya penghapusan yang terjadi di loop. Sepertinya saya tidak dapat menggunakan direct_range dalam kasus ini (iterasi pada direct_range akan selalu memproses elemen dalam urutan maju - itu akan mengisi vektor dalam urutan yang salah ketika dipanggil dengan reverse_iterators). - person Bulletmagnet; 15.10.2016