9

In C++11's std::map, is there some valid iterator x such that ++x is guaranteed to equal map::begin()? I would like to detect if a function I just called (mine) has walked an iterator off the front of a function. The function will move the iterator exactly one position backward.

Does the answer hold for the rest of the library?

4

3 回答 3

9

不，std容器中开始之前的迭代器都是 UB（反向迭代器除外，这可能无法解决您的问题）。

您可能需要修复有问题的功能。如果做不到这一点，请在调用它之前将其包装并捕获不良行为。如果做不到这一点，您可以在键类型排序中插入一个负无穷大元素map，并添加一个标记值。如果做不到这一点，您可以编写迭代器适配器，将您的map迭代器与可以在没有 UB 的情况下一开始就进行的迭代器一起包装。

这些大致按照我的推荐顺序排列。每个都有可能失败的方式，并且随着我的建议变得更加遥远，它们变得更容易出错和危险。

于 2013-10-17T02:32:14.167 回答
7

意识到标准库容器是半开放范围是非常重要的[begin, end)，即您可以迭代一个过去的结束。对于双向（和随机）迭代器，您也可以这样做--end()并从边缘回来。取消引用 one-past-the-end by*end()是未定义的行为，通过--begin()or递减 begin 迭代器也是如此begin() - 1。只有一个例外：它有一个满足std::forward_list的不可取消引用的迭代器（但请注意，对于 a你也不能递减）。before_begin()++before_begin() == begin()forward_listbegin()

双向迭代器的这种基本不对称意味着反向迭代器是常规迭代器的薄包装器。在大多数标准库实现中，它们只包含base_底层迭代器的副本。增加类似的std::reverse_iterator调用--base_; return *this;，并取消引用它auto old = base_; return *--old;。基础迭代器在任何时候都不会递减到 before ，并且不会以这种方式begin()取消对 of 的引用。end()

以下是对支持双向或随机迭代器的容器进行迭代的四种方法，以及各种迭代器之间的关系（.base()将 a 转换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())（这也是标准库通常实现它们的方式）。

于 2013-10-17T08:26:10.533 回答
1

通过“将迭代器从前面移开”，我假设您正在减少前向迭代器，如下所示：

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

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

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

-杰西

于 2013-10-17T02:22:52.810 回答