减少结束迭代器 [英] Decrementing an off the end iterator

问题描述

我今天正在阅读关于如何支持双向迭代的容器，这段代码是有效的：

 集合c 10，10）; 
 auto last = --c.end（）; 
 * last; 
  

这让我想到是否需要提交一对双向迭代器[beg，end]到STL中的一个算法--end是定义的？如果是，结果是否应该解引用？

ie

  algo（T beg，T end）{
 // ... 
 auto iter = --end; 
 // ... 
 * iter; 
} 
  

解决方案

由双向迭代器首先和最后，然后 - 最后需要在 ++第一相同的条件下有效 - 即范围不为空。当且仅当 first == last 时，范围为空。

如果范围不为空， - last 评估到引用该范围中最后一个元素的迭代器，因此 * - last 需要有效。

也就是说，没有那么多标准算法需要专门的双向迭代器（并且不需要随机访问）。 上一页， copy_backward ， move_backward ， reverse ， reverse_copy ， stable_partition ， inplace_merge ， [prev | next] _permutation 。

如果你看看其中的一些，你应该看到典型的算法是递减结束范围的迭代器和解引用结果。

正如James所说，对于容器，函数 end（）按值返回一个迭代器 。没有一般要求对于 x 是一个右值， - x 应该是一个格式良好的表达式的迭代器的类型。例如，指针是双向迭代器，并且声明为 int * foo（）; 的函数通过值返回指针， - foo 不是一个格式正确的表达式。对于你在实现中看到的容器， end（）返回一个类类型，它具有 operator - 定义为成员函数，因此代码编译。

请注意，这方面有以下区别：

  auto last = -c.end（）; 
  

vs。

 code> auto last = c.end（）; 
 --last; 
  

前者递减右值，而后者递减左值。

I was reading today about how for containers that support bidirectional iteration, this piece of code is valid:

Collection c(10, 10);
auto last = --c.end();
*last;

That got me thinking, is it required that when submitting a pair of bidirectional iterators [beg, end) to an algorithm in the STL that --end is defined? If so, should the result be dereferenceable?

ie

void algo(T beg, T end){
    //...
    auto iter = --end;
    //...
    *iter;
} 

解决方案

If the algorithm requires a range defined by bidirectional iterators first and last, then --last needs to be valid under the same conditions that ++first does -- namely that the range isn't empty. The range is empty if and only if first == last.

If the range isn't empty, then --last evaluates to an iterator that refers to the last element in the range, so *--last indeed also needs to be valid.

That said, there aren't all that many standard algorithms that require specifically a bidirectional iterator (and don't require random-access). prev, copy_backward, move_backward, reverse, reverse_copy, stable_partition, inplace_merge, [prev|next]_permutation.

If you look at what some of those do, you should see that typically the algorithm does decrement the end-of-range iterator and dereference the result.

As James says, for containers the function end() returns an iterator by value. There is no general requirement that for iterators that --x should be a well-formed expression when x is an rvalue of the type. For example, pointers are bidirectional iterators, and a function declared as int *foo(); returns a pointer by value, and --foo() is not a well-formed expression. It just so happens that for the containers you've looked at in your implementation, end() returns a class type which has operator-- defined as a member function, and so the code compiles. It also works since the container isn't empty.

Be aware that there is a difference in this respect between:

auto last = --c.end();

vs.

auto last = c.end();
--last;

The former decrements an rvalue, whereas the latter decrements an lvalue.

这篇关于减少结束迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！