如何使用反向迭代器调用erase函数

237

我正在尝试做这样的事情:

for ( std::list< Cursor::Enum >::reverse_iterator i = m_CursorStack.rbegin(); i != m_CursorStack.rend(); ++i )
{
    if ( *i == pCursor )
    {
        m_CursorStack.erase( i );
        break;
    }
}

然而,erase接受的是正向迭代器而不是反向迭代器。是否有一种方法可以将反向迭代器转换为正向迭代器或另一种方法来从列表中删除该元素?


19
顺便提一下,当编写这种循环时,不要像你在i != m_CursorStack.rend()中所做的那样反复计算结束迭代器。相反,应该写成i = m_CursorStack.rbegin(), end = m_CursorStack.rend(); i != end;。也就是说,初始化一个您可以保留用于重复比较的迭代器--假设结束位置不会因循环体的副作用而改变。 - seh
在我看来,这里显而易见的问题是你为什么要这样做。通过反向遍历列表,你能得到什么好处?自己编写代码而不使用std::remove,你又能得到什么好处? - Jerry Coffin
4
我只想移除一个元素,因此需要删掉 'break;',使用 'remove' 会删除所有匹配的元素并且需要更长时间,而且不能实现我想要的效果。在这种情况下,我想要移除的元素几乎总是列表的最后一个或非常靠近它,因此反向迭代也更快且更适合解决这个问题。 - 0xC0DEFACE
4
这段话表明设计者没有具体定义实现,因为作为用户,你不需要知道或关心它,但是@seh却期望我们奇迹般地知道rend()是如何计算的并且非常耗费资源。 - stu
@JerryCoffin,从std::vector::erase()的规范中可以看出:“使得被删除点之后(包括end()迭代器)的所有迭代器和引用失效。”因此,如果您想要在向量中删除多个元素,可以从末尾开始迭代,一边删除一边前进,这样就不必担心迭代器失效的问题。 - user140327
显示剩余5条评论
14个回答

231
经过更多的研究和测试,我找到了解决方案。显然根据标准[24.4.1/1],i.base()i之间的关系是:
&*(reverse_iterator(i)) == &*(i - 1)

(来自Dr. Dobbs文章):

所以当获取base()时,您需要应用一个偏移量。因此解决方案是:

m_CursorStack.erase( --(i.base()) );

编辑

针对C++11进行更新,增加了两种额外的解决方案:

  • reverse_iterator i 不变:

      m_CursorStack.erase( std::next(i).base() );
    
  • reverse_iterator i 前进:

      std::advance(i, 1);
      m_CursorStack.erase( i.base() );
    

我发现这些比我的以前的解决方案更清晰。使用任何你需要的。


28
你应该注意引用的文章中的一些细节 - 为了可移植,表达式应该是 m_CursorStack.erase((++i).base())(天啊,使用反向迭代器做这种事真令人头痛...)。还应注意,《DDJ》文章被整合到 Meyer 的《Effective STL》书中。 - Michael Burr
9
我发现那个图比有帮助更加令人困惑。因为rbegin、ri和rend实际上都指向它们所绘制的元素右边的元素。该图显示了如果您*它们,您将访问哪个元素,但是我们在谈论的是如果您base它们,您将指向哪个元素,这是右侧的一个元素。我不太喜欢--(i.base())(++i).base()解决方案,因为它们会改变迭代器。我更喜欢(i+1).base(),这也可以起作用。 - mgiuca
7
反向迭代器是“骗子”。。当解引用时,反向迭代器返回在它之前的元素。参见这里 - bobobobo
5
请明确一点,这种技术仍然不能在普通的for循环中使用(其中迭代器以正常方式递增)。请参见https://dev59.com/kVoU5IYBdhLWcg3w35rN - logidelic
1
m_CursorStack.erase((++i).base()) 看起来如果 ++i 把你带到了最后一个元素之后,这可能会成为一个问题。你能在 end() 上调用 erase 吗? - stu
显示剩余7条评论

24

有趣的是,这个页面上还没有正确的解决方案。因此,以下是正确的解决方案:

对于前向迭代器,解决方案很简单:

std::list< int >::iterator i = myList.begin();
while ( i != myList.end() ) {
  if ( *i == to_delete ) {
    i = myList.erase( i );
  } else {
    ++i;
  } 
}

如果您使用反向迭代器,您需要执行相同的操作:

std::list< int >::reverse_iterator i = myList.rbegin();
while ( i != myList.rend() ) {
  if ( *i == to_delete ) {
    i = decltype(i)(myList.erase( std::next(i).base() ));
  } else {
    ++i;
  } 
}

注意:

  • 您可以使用迭代器构造reverse_iterator
  • 您可以使用std::list::erase的返回值

4
这段代码可以运行,但请解释一下为什么要使用next以及将正向迭代器强制转换为反向迭代器是如何保证安全,而不会导致灾难性后果。 - Lefteris E
2
@LefterisE 这不是一个强制类型转换。它创建了一个新的逆向迭代器,该迭代器是由一个迭代器构造而来。这是逆向迭代器的常规构造函数。 - Šimon Tóth
1
除了“最令人烦恼的解析”示例之外,这可能是我遇到的最好的例子,其中使用大括号初始化将使代码对读者更加清晰。 - Chuu

17
请注意,如果在 for 循环中使用 m_CursorStack.erase((++i).base()),可能会出现问题,因为它会更改 i 的值。正确的表达式是 m_CursorStack.erase((i+1).base())

4
你需要创建迭代器的副本并执行iterator j = i; ++j,因为在迭代器上不支持i+1的操作,但这是正确的思路。 - bobobobo
4
@bobobobo,您可以使用Boost中的m_CursorStack.erase(boost::next(i).base()),或者在C++11中使用m_CursorStack.erase(std::next(i).base())。这将从m_CursorStack中删除指针i所指向的元素。 - alfC

13

...或者另一种从列表中删除该元素的方法?

这需要-std=c++11标志(对于auto):

auto it=vt.end();
while (it>vt.begin())
{
    it--;
    if (*it == pCursor) //{ delete *it;
        it = vt.erase(it); //}
}

5
谁保证列表中的迭代器是有序的? - Gaetano Mendola
@GaetanoMendola 请参阅标准22.2.4... 定义了list为“序列容器”... 必须拥有Cpp17RandomAccessIterator... 必须实现有序的><运算符。 或者,从概念上讲,如果容器没有某种排序,那么“反向”迭代器实际上是没有意义的。例如,unordered_map就没有这种排序。 - undefined

4
使用reverse_iteratorbase()方法并将结果递减可行,但值得注意的是,reverse_iterator与常规iterator不同。通常情况下,您应该优先选择常规iterator(以及const_iteratorconst_reverse_iterator),原因正如此例所示。请参阅Doctor Dobbs' Journal以深入讨论原因。

3
typedef std::map<size_t, some_class*> TMap;
TMap Map;
.......

for( TMap::const_reverse_iterator It = Map.rbegin(), end = Map.rend(); It != end; It++ )
{
    TMap::const_iterator Obsolete = It.base();   // conversion into const_iterator
    It++;
    Map.erase( Obsolete );
    It--;
}

3

这里是将erase的结果转换为反向迭代器的代码片段,以便在反向迭代时删除容器中的元素。有点奇怪,但即使删除第一个或最后一个元素也可以正常工作:

std::set<int> set{1,2,3,4,5};

for (auto itr = set.rbegin(); itr != set.rend(); )
{    
    if (*itr == 3)
    {
        auto it = set.erase(--itr.base());
        itr = std::reverse_iterator(it);            
    }
    else
        ++itr;
}

2
如果您不需要在途中擦除所有内容,那么为了解决这个问题,您可以使用“erase-remove”惯用语:
m_CursorStack.erase(std::remove(m_CursorStack.begin(), m_CursorStack.end(), pCursor), m_CursorStack.end());

std::remove函数将匹配到的所有元素交换到容器的末尾,并返回第一个匹配元素的迭代器。然后,使用范围内的erase函数从第一个匹配元素开始擦除至末尾。非匹配元素的顺序被保留。

如果你使用的是std::vector容器,在其中间进行擦除操作可能会涉及很多复制或移动操作,因此这种方法可能更快。

当然,上面解释了reverse_iterator::base()的用法也很有趣并值得了解,但是针对所述问题,我认为std::remove更适合。


1

我想澄清一些事情:在上面的评论和答案中,可擦除版本被提及为(++i).base()。然而,除非我漏掉了什么,正确的语句应该是(++ri).base(),这意味着你要“增加”反向迭代器(而不是迭代器)。

昨天我遇到了类似的需求,这篇文章很有帮助。谢谢大家。


0
为了补充其他人的答案,因为我在搜索std::string时偶然发现了这个问题,但没有找到太多有用的信息,所以在这里提供一个使用std::string、std::string::erase和std::reverse_iterator的解决方案。
我的问题是从完整的文件名字符串中删除图像文件名。最初使用std::string::find_last_of解决了这个问题,但我还研究了一种使用std::reverse_iterator的替代方法。
std::string haystack("\\\\UNC\\complete\\file\\path.exe");
auto&& it = std::find_if( std::rbegin(haystack), std::rend(haystack), []( char ch){ return ch == '\\'; } );
auto&& it2 = std::string::iterator( std::begin( haystack ) + std::distance(it, std::rend(haystack)) );
haystack.erase(it2, std::end(haystack));
std::cout << haystack;  ////// prints: '\\UNC\complete\file\'

这个程序使用了算法、迭代器和字符串头文件。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接