STL迭代器在std::map::begin()之前的问题

Question

在C++11的std::map中，是否存在某个有效的迭代器x，使得++x保证等于map::begin()？我想检测一个我刚调用的函数（我的函数）是否已经把一个迭代器从前面走出去了。该函数将恰好将迭代器向后移动一个位置。

这个答案对于库中的其余部分是否成立呢？

- George Hilliard

---

简短回答：不行。你真的需要找到其他方法来处理（或更好地预防）这种情况。 - Jerry Coffin

@JerryCoffin，这就是为什么我们有反向迭代器的原因，可以看看我的回答。 - TemplateRex

Answer 1

非常重要的一点是，标准库容器是半开区间 [begin, end)，也就是说可以迭代到结尾的下一个位置。对于双向（和随机）迭代器，您还可以执行 --end() 以返回上一个位置。通过 *end() 解引用结尾的下一个位置是未定义行为，同样地，通过 --begin() 或 begin() - 1 减少起始迭代器也是未定义行为。唯一的例外是 std::forward_list，它有一个不可解引用的迭代器 before_begin()，满足 ++before_begin() == begin()（但请注意，对于 forward_list，您也不能减少 begin()）。

双向迭代器的这种基本不对称性意味着反向迭代器只是常规迭代器的薄包装器。在大多数标准库实现中，它们只是包含底层迭代器的副本 base_。递增 std::reverse_iterator 会调用类似于 --base_; return *this; 的内容，而解引用操作则会执行 auto old = base_; return *--old;。在任何时候，底层迭代器都不会被减少到在 begin() 之前的位置，也不会以这种方式解引用 end()。

以下是四种遍历支持双向或随机迭代器容器的方法，以及各种迭代器之间的关系（.base() 将 std::reverse_iterator 转换回其底层迭代器）。

#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <string>

int main()
{    
    auto c = std::map<int, std::string>{ {1, "hello"}, {2, "world"} };
    
    {   // 1) forward iteratation
        auto it = begin(c);
        for (; it != end(c); ++it){}
        std::cout << std::boolalpha << (it == c.rbegin().base()) << "\n";
    }

    {   // 2) meh, backward iteration
        auto it = end(c) - 1; //end return iterator after the last element.
        for (; it != begin(c); --it){}
        std::cout << std::boolalpha << (it == c.rend().base()) << "\n";
    }

    {   // 2') better: reverse iteration
        auto it = c.rbegin();
        for (; it != c.rend(); ++it){}
        std::cout << std::boolalpha << (it.base() == begin(c)) << "\n";
    }

    {   // 1') backward reverse, better avoid this
        auto it = c.rend();
        for (; it != c.rbegin(); --it){}
        std::cout << std::boolalpha << (it.base() == end(c)) << "\n";
    }
}

如果你有一个数据结构需要支持双向迭代，但没有成员迭代器.rbegin()或rend()，你可以通过std::reverse_iterator(end())和std::reverse_iterator(begin())来轻松定义它们（这也是标准库通常实现它们的方式）。

实时示例

- TemplateRex

---

感谢您对我的回答进行了大量的负面评价，我想说的是，我在回答中已经说明了这是未定义行为，并且未定义行为并不是魔鬼。如果您只需要在一个地方编译代码并记录下它是未定义行为，那么问题在哪里呢？话虽如此，显然他应该能够使用反向迭代器，但我只是在回答他的问题。 - aaronman

@aaronman，很抱歉听到你因为被踩而感到不悦。公平地说，我是三个踩帖者中唯一解释原因的人。请不要太在意，我并没有说你的回答很糟，但是 Stack Overflow 的回答也应该对未来的读者有所帮助。由于 UB 可以悄悄地破坏你的代码，所以它确实是个麻烦。 - TemplateRex

我个人会避免在任何我编写的代码中出现未定义行为，但如果有人明确要求不按照正确方式（使用反向迭代器）进行操作，并且我给出的答案提到了答案是未定义行为，我不知道有什么大不了的。同时，感谢你对我的回答进行评论，这样我就可以责备你，而不像其他DV者一样没有留言。 - aaronman

有人能为我定义一下 UB 这个缩写吗？ - George Hilliard

@thirtythreeforty C++标准委员会已经成立了一个研究小组来研究这个问题，也可以参考这个问答。 - TemplateRex

Answer 2

不，std容器中开始之前的迭代器都是未定义行为（除了反向迭代器，但这可能无法解决您的问题）。

您可能需要修复相关函数。如果失败，请在调用函数之前包装它并捕获错误行为。如果还是不行，您可以将负无穷元素插入到map键类型排序中，并添加一个标记值。如果仍然无法解决问题，则可以编写迭代器适配器，将map迭代器包装成可以在开始之前走一步而不会出现未定义行为的迭代器。

这些按照我的建议顺序排列，每种方法都有可能失败，并且随着建议越来越遥远，错误率和风险也会增加。

- Yakk - Adam Nevraumont

---

迭代器包装器乍一看很干净，但是一想到我如何使用它们，就会变得非常肮脏，非常快。 - George Hilliard

@thirtythreeforty 是的，这就是为什么我包含它的原因，但只作为远程“哦，天哪，没有其他办法了”的选择。通过一个 boost 迭代器 fasade 帮助，它只会有些许的不好处理。或者手动编写。或者将两个 boost 类型抹除的迭代器范围进行惰性连接。(再次按建议顺序排列)。如果你采用最后一个的最后一个，你会得到你应得的：它在理论上起作用，但味道真糟糕。简而言之，修复这个函数，它不应该对它没有有效范围的迭代器进行减量操作。 - Yakk - Adam Nevraumont

啊，std::forward_list确实有一个before_begin()成员。 - TemplateRex

@TemplateRex：那就是标准库中唯一一个您无法“从前面遍历迭代器”的容器。我认为这不是巧合。 - MSalters

@MSalters 当然，但问题是最好通过检查 rend() 而不是通过 UB 减少 begin() 并像怀尔·E·科亚特一样走到前面，详见下面的答案来避免前向行走。 - TemplateRex

Answer 3

我想您指的是“将迭代器向前移动”，我假设您正在像这样减少前向迭代器：

// don't do this:
for(it = mymap.end(); --it >= mymap.begin(); ) { ... }

相反，像这样增加一个反向迭代器：

// this is better:
for(it = mymap.rbegin(); it != mymap.rend(); ++it) { ... }

-Jesse

- Jesse Chisholm

---

如果我使用反向迭代器，我会遇到另一个函数的相同问题，但是需要在map的末尾移动迭代器向前。 - George Hilliard

出于好奇，为什么你需要将迭代器移动到其自然方向的相反方向？使用 do { ... } while (it != mymap.begin(); 有什么不同吗？ - Jesse Chisholm

我怀疑你说的 begin()-1 是未定义的。如果你已经到达了 end()，那么在增加后但在执行之前检查；如果你刚刚处理了 begin()，则在执行后但在减少之前检查可能会卡住。 - Jesse Chisholm

@thirtythreeforty 在向前移动时，请使用常规迭代器，而在向后移动时，请使用反向迭代器。或者，如果您想要使用常规迭代器进行向后迭代，请确保永远不要将 begin() 减少，因为这会导致 UB。请参阅我的答案以了解四种迭代方式。 - TemplateRex

@JesseChisholm obj[-1] 是未定义行为。 - TemplateRex