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

真正的代码并不仅仅是抹去更多，但这足以说明行为。

EDITED显示循环中不会发生任何删除。 根据使用哪种迭代器，项目应按正向或反向顺序添加到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

第二个答案，从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; 
    } 
} 

Answer 2

好的，处理逆向迭代器是一个痛苦的脖子。让我们的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"。对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 
    } 
}