2016-10-14 106 views
0

我有以下的(簡化)代碼:升壓multi_index反向迭代擦除麻煩

#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失效,即使擦除不應該​​使任何其他迭代器失效。

任何想法我做錯了什麼?

回答

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

不幸的是,這並沒有幫助。剩餘堆使用(在'++ next'行中)。 – Bulletmagnet

+0

您是否直接複製了建議的代碼*逐字*?注意例如(if; rb!= fin)for(;;)'部分。 –

+0

對不起,提出的解決方案確實是錯誤的。編輯一個希望正確的選擇。 –

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 
    } 
} 
+0

謝謝。不幸的是,實際的代碼不夠簡單,無法使用'erase(iterator,iterator)'(想象一下,如果你願意,只有一些元素將被擦除)。 – Bulletmagnet

+0

你寫了「4. baz被刪除」。這是因爲'iter_base(victim)' - 一個迭代器 - 指向與「rb」相同的元素 - 一個反向迭代器 - ? – Bulletmagnet

+0

第一次回覆:一旦得到'direct_range'的結果,就可以用更復雜的代碼工作在非反向迭代器上來替換'erase(iterator,iterator)'。 –