--list.begin() == list.end() 吗？

Question

标准是否保证

--list.begin() == list.end()

总是成立并且它实际上是一个有效的操作？（list 是 std::list 的实例）。

至少 MSVC 2019 似乎是这种情况。

这在以下情况下会很有用：

for ( auto i = list.begin(); i != list.end(); ++i )
{
  ...
  list.erase(i--);
  ...
}

，即在迭代时删除元素，因为 i 可能是列表的开头。这也需要 ++list.end() == list.begin() 来保持；那怎么样？

Answer 1

Does the standard guarantee that
--list.begin() == list.end()

不，标准不保证 std::list（给定双向迭代器也不能假设这样的保证）。事实上，--list.begin() 的行为是未定义的。

This would also require ++list.end() == list.begin() to hold; what about that?

也不能保证，并且 ++list.end() 有未定义的行为。

[language-lawyer]的标准报价：

[bidirectional.iterators]

Expression | Operational   | Assertion/note
           | semantics     | pre-/post-condition
---------------------------------------------------------
--r        |               | Preconditions:
           |               |  there exists s such that r == ++s.
---------------------------------------------------------
r--        | { X tmp = r;  |
           | --r;          |
           | return tmp; } |

[input.iterators]

Expression | Operational   | Assertion/note
           | semantics     | pre-/post-condition
---------------------------------------------------------
++r        |               | Preconditions:
           |               |  r is dereferenceable.

问题是pre-condition不满足。

我对编写具体示例的建议。这略有不同之处在于 my_function 将在元素实际从列表中删除之前调用：

list.remove_if([](int n) {
    if ( X + Y == W )
    {
        my_function( Y );
        return X || Y && Z;
    }
    return true;
});

如果需要确切的行为，那么您可以使用以下不太漂亮的方法：

for (auto it = list.begin(), last = list.end(); it != last;)
{
    auto next = it;
    ++next;
    
    if ( X + Y == W )
    {
        if ( X || Y && Z )
        {
            list.erase( it );
        }
        my_function( Y );
    }
    else
    {
        list.erase( it );
    }
    
    it = next;
}

Answer 2

当前的 MSVC C++ 标准库将 std::list 实现为循环双向链表，其中一个额外的节点充当第一个和最后一个元素之间的耦合器。

所以 --list.begin() == list.end() 确实成立。

但请注意 --list.begin() 的行为是未定义的，这就是为什么这个特定的实现是一个可能的选择。

--list.begin() == list.end() 吗？

Does --list.begin() == list.end()?

c++

iteration

iterator

stdlist

language-lawyer