Bulletmagnet Bulletmagnet - 1 month ago 32
C++ Question

boost multi_index reverse iterator erase trouble

I have the following (simplified) code:

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


The real code does more than just erase, but this is enough to illustrate the behavior.

EDITED to show that no just removal happens in the loop.
Items are supposed to be added to
result
in forward or reverse order depending on which kind of iterator was used.

When run without arguments,
forward==true
and the output is as expected:

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


When run with an argument,
forward==false
and the output is:

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


(not as expected)

Compiling with address sanitizer shows a heap-use-after-free in line 42 (the ++rb line).

It seems that calling
erase(victim)
has invalidated
rb
somehow, even though erase is not supposed to invalidate any other iterator.

Any idea what I'm doing wrong?

Answer

Second answer, with the additional request from OP that traversal be done in direct or reverse order according to the nature of the iterator. With a little care this can be done like this:

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

My bad, the stricken through code was still running into UB. Please try this:

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