为什么标准迭代器范围[开始,结束]而不是[开始,结束]？

Question

为什么标准定义end()为一个结束而不是实际结束？

Answer 1

最好的论点是Dijkstra自己制作的:

• 你希望范围的大小是一个简单的差异结束  -  开始 ;

• 当序列退化为空的时,包括下限更"自然",并且因为替代(不包括下限)将需要存在"一个在开始之前"的前哨值.

你仍然需要证明为什么你开始计算零而不是一个,但这不是你问题的一部分.

当你有任何类型的算法来处理基于范围的构造的多个嵌套或迭代调用时,[开始,结束]约定背后的智慧会一次又一次地得到回报.相比之下,使用双闭合范围会产生一个接一个的,非常令人不愉快和嘈杂的代码.例如,考虑分区[ n ₀,n ₁)[ n ₁,n ₂ ] [ n ₂,n ₃).另一个例子是标准迭代循环for (it = begin; it != end; ++it),它运行end - begin时间.如果两端都是包容性的话,相应的代码将更不易读 - 并想象你如何处理空范围.

最后,我们还可以做一个很好的论证,为什么计数应该从零开始:对于我们刚刚建立的范围的半开公约,如果给出一系列N个元素(比如枚举数组的成员),那么0是自然的"开始",因此您可以将范围写为[0,N),而不会有任何尴尬的偏移或更正.

简而言之:我们1在基于范围的算法中看不到任何数字的事实是[开始,结束]约定的直接结果和动机.

Answer 2

其实,很多的迭代器相关的东西突然更有道理,如果你考虑不迭代器指向在该序列的元素,但在两者之间,与非关联访问的下一个元素的权利吧.那么"一个过去的结束"迭代器突然变得立竿见影:

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^               ^
   |               |
 begin            end

显然begin指向序列的开头,并end指向相同序列的结尾.解除引用begin访问元素A,并且解除引用end没有意义,因为没有元素权限.另外,i在中间添加一个迭代器

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
 begin     i      end

并且您可以立即看到,从要素的范围begin以i包含的元素A,并B同时从元素的范围i,以end包含的元素C和D.解除引用i赋予它正确的元素,这是第二个序列的第一个元素.

即使反向迭代器的"一个一个"突然变得明显:反转该序列给出:

   +---+---+---+---+
   | D | C | B | A |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
rbegin     ri     rend
 (end)    (i)   (begin)

我在下面的括号中写了相应的非反向(基础)迭代器.你看,属于反向迭代器i(我将其命名ri)还是元素之间分中B和C.但是由于顺序颠倒了,现在元素B就在它的右侧.

Answer 3

为什么标准定义end()为一个结束而不是实际结束？

因为:

1. 它避免了对空范围的特殊处理.对于空范围,begin()等于 end()&
2. 它使遍历元素的循环的结束标准变得简单:只要end()未到达,循环就会继续.

Answer 4

因为那时候

size() == end() - begin()   // For iterators for whom subtraction is valid

你不必做那些尴尬的事情

// Never mind that this is INVALID for input iterators...
bool empty() { return begin() == end() + 1; }

你会不小心写错误的代码一样

bool empty() { return begin() == end() - 1; }    // a typo from the first version
                                                 // of this post
                                                 // (see, it really is confusing)

bool empty() { return end() - begin() == -1; }   // Signed/unsigned mismatch
// Plus the fact that subtracting is also invalid for many iterators

另外:如果指向有效元素会find()返回什么end()？
你真的想要另一个被调用的成员invalid()返回一个无效的迭代器吗？!
两个迭代器已经足够痛苦了......

哦,看到这个相关的帖子.

也:

如果end是在最后一个元素之前,你将如何insert()在真正的结束？!

Answer 5

半闭范围的迭代器习惯用法[begin(), end())最初基于普通数组的指针算法.在该操作模式中,您将拥有传递数组和大小的函数.

void func(int* array, size_t size)

[begin, end)当您拥有该信息时,转换为半封闭范围非常简单:

int* begin;
int* end = array + size;

for (int* it = begin; it < end; ++it) { ... }

要使用全封闭范围,更难:

int* begin;
int* end = array + size - 1;

for (int* it = begin; it <= end; ++it) { ... }

由于指向数组的指针是C++中的迭代器(并且语法设计为允许这样做),因此调用std::find(array, array + size, some_value)它比调用它更容易std::find(array, array + size - 1, some_value).

另外,如果您使用半闭范围,您可以使用!=运算符检查结束条件,因为(如果您的运算符被正确定义)<暗示!=.

for (int* it = begin; it != end; ++ it) { ... }

然而,使用全闭范围并没有简单的方法.你被困住了<=.

在C++中支持<和>操作的唯一一种迭代器是随机访问迭代器.如果必须为<=C++中的每个迭代器类编写一个运算符,则必须使所有迭代器完全可比,并且创建功能较少的迭代器(例如双向迭代器std::list或输入迭代器)的选择较少iostreams如果C++使用完全封闭的范围,则运行).

Answer 6

通过end()指向一个结束,可以很容易地使用for循环迭代集合:

for (iterator it = collection.begin(); it != collection.end(); it++)
{
    DoStuff(*it);
}

随着end()指向最后一个元素,一个循环会更复杂:

iterator it = collection.begin();
while (!collection.empty())
{
    DoStuff(*it);

    if (it == collection.end())
        break;

    it++;
}