부스트는 반복자 삭제 문제

Question

역 multi_index I 다음 (간체) 코드를 가지고 :

#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 행)에 heap-after-free가 표시됩니다.

지우기가 다른 이터레이터를 무효로하지 않아도 되겠지만, erase(victim)을 호출하면 어떤 식 으로든 rb이 무효화 된 것처럼 보입니다.

내가 뭘 잘못하고 있는지 아는 사람이 있습니까?

Answer 1

두 번째 대답을 통과 반복자의 성격에 따라 직접 또는 역순으로 수행 할 수 OP에서 추가 요청을 다음과 같이 그것을 할 수있는 하나의 잠재적 인 방법입니다. 약간의주의로 이것은 다음과 같이 수행 할 수 있습니다 코드를 통해 시달리는가 아직 UB로 실행중인

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

내 나쁜. 이것을 시도하십시오 :

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은 아직 존재하지 않습니다. "foo"에

   auto victim = rb;

2. rb 점, "foo"-victim 점. "baz"에

   ++rb;

3. rb 점, "foo"-victim 점.

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

4. "baz"는 에 rb 포인트 "foo"에"baz", victim 점을 삭제, 삭제됩니다. 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 
    } 
}