boost multi_index 反向迭代器擦除麻烦

Question

我有以下（简化的）代码：

#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)

（不符合预期）

使用地址清理器编译在第 42 行（++rb 行）显示释放后堆使用。

似乎调用 erase(victim) 以某种方式使 rb 无效，即使擦除不应该使任何其他迭代器无效。

知道我做错了什么吗？

Answer 1

好的，处理反向迭代器是一件令人头疼的事情。下面分析一下evict:

这部分代码执行过程中的指针业务

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

在调用 evict(c, Container::reverse_iterator(c.upper_bound("baz")), c.rend()) 时。 "points to" 我的意思是 "the internal iterator points to"。一步一步我们有：

输入代码前：rb指向"foo"，victim还不存在

auto victim = rb;
rb指向"foo"，victim指向"foo".

++rb;
rb指向"baz"，victim指向"foo".

auto next = c.erase(iter_base(victim));
"baz"被删除，rb指向删除"baz"，victim指向"foo"。 rb 的任何进一步取消引用、比较或 (de/in) 递增操作都是未定义的行为。

我了解到您正在尝试编写一个同时适用于迭代器和反向迭代器的 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
  }
}

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

boost multi_index 反向迭代器擦除麻烦

boost multi_index reverse iterator erase trouble

c++

boost

boost-multi-index

c++11