为什么标准迭代器范围是 [begin, end) 而不是 [begin, end]？

Question

为什么标准将end()定义为超过实际结尾的位置，而不是在实际结尾处？

- Puppy

---

我猜测，“因为标准这样规定”并不能令人满意，对吗？ :) - Luchian Grigore

当然不行。那样会削弱我们对标准背后人员的尊重。我们应该期望标准制定时所做出选择有其原因。 - Kerrek SB

我猜这个解释也值得你的关注：One Past the End。 - SChepurin

简而言之，计算机不像人一样数数。但是如果您想知道为什么人们不像计算机一样数数，我建议阅读《虚无：零的自然历史》（The Nothing that Is: A Natural History of Zero），深入了解人类在发现存在一个比一小一的数字时遇到的困难。 - John McFarlane

因为只有一种方法可以生成“最后一个”，所以通常不便宜，因为它必须是真实的。而生成“你从悬崖边掉下去了”则总是很便宜，有许多可能的表现方式可供选择。使用 (void*)"ahhhhhhh" 就可以了。 - Hans Passant

Answer 1

最有说服力的观点来自Dijkstra本人提出的：

• 你希望范围的大小是一个简单的差值end − begin；

• 包括下界更“自然”，当序列退化为空时，也因为另一种选择（排除下界）需要存在“开始之前”的哨兵值。

你仍然需要证明为什么从零开始计数而不是从一开始计数，但这不是你的问题的一部分。

在处理多个嵌套或迭代调用范围构造的算法时，半开范围约定背后的智慧一次又一次地得到回报，这些算法能够自然地链接。相比之下，使用双重封闭范围会导致偏移量错误和极其不愉快且难以理解的代码。例如，考虑一个分区[n₀, n₁)[n₁, n₂)[n₂,n₃)。另一个例子是标准迭代循环for (it = begin; it != end; ++it)，它运行了end - begin次。如果两端都是包含的，相应的代码将变得不太可读-想象一下如何处理空范围。

最后，我们还可以提出一个很好的观点，为什么计数应该从零开始：对于我们刚刚确定的半开区间约定，如果你给出一个N元素的范围（比如枚举数组成员），那么0就是自然的“开始”，这样你就可以将范围写成[0，N),而不需要任何尴尬的偏移或纠正。

简而言之：在基于范围的算法中我们不会看到数字 1，这直接是 [begin, end) 约定的结果和动机。

- Kerrek SB

---

典型的C语言循环遍历大小为N的数组是“for(i=0;i<N;i++) a[i]=0;”。现在，你不能直接使用迭代器来表达它 - 许多人浪费时间试图使<有意义。但是，使用“for(i=0;i!=N;i++)…”几乎同样明显。因此，将0映射到开始，将N映射到结束是方便的。 - Krazy Glew

@KrazyGlew：我故意没有在我的循环示例中加入类型。如果您将“begin”和“end”视为值分别为“0”和“N”的“int”，那么它就完美契合。可以说，“!=”条件比传统的“<”更自然，但直到我们开始思考更一般的集合时，我们才发现这一点。 - Kerrek SB

@KerrekSB：我同意“在我们开始思考更一般的集合之前，我们从未发现[！=更好]”。在我看来，这是Stepanov应该得到赞誉的事情之一——作为一个在STL之前尝试编写此类模板库的人。然而，我会争论“!=”更自然的观点，或者更确切地说，我会认为“!=”可能会引入错误，而“<”则可以检测到。想想 for(i=0;i!=100;i+=3)... - Krazy Glew

@KrazyGlew：你最后提到的点有些跑题，因为序列 {0, 3, 6, ..., 99} 不是 OP 所问的形式。如果你想它是这样的形式，你应该编写一个可 ++ 自增的迭代器模板 step_by<3>，然后就具有最初宣传的语义。 - Kerrek SB

@KrazyGlew 即使 < 有时会隐藏错误，它仍然是一个错误。如果有人在应该使用 < 的地方使用 !=，那么这就是一个错误。顺便说一下，这种类型的错误很容易通过单元测试或断言找到。 - Phil1970

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位于其右边。

- celtschk

---

这是我个人认为最好的答案，尽管我认为如果迭代器指向数字，并且元素位于数字之间，可能会更好地说明（语法foo[i]是紧接在位置i之后的项的简写）。思考一下，我想知道一个语言是否有单独的运算符用于“在位置i之后立即的项”和“在位置i之前立即的项”，因为许多算法使用相邻项对，说“在位置i两侧的项”可能比“在位置i和i + 1处的项”更清晰。 - supercat

@supercat：这些数字不应该表示迭代器的位置/索引，而是表示元素本身。我将用字母替换数字以使其更清晰。实际上，根据给定的数字，begin[0]（假设是随机访问迭代器）将访问元素1，因为在我的示例序列中没有元素0。 - celtschk

为什么使用“begin”而不是“start”这个词呢？毕竟，“begin”是一个动词。 - user1741137

@user1741137 我认为 "begin" 的意思是 "beginning" 的缩写（现在有意义了）。"beginning" 太长了，"begin" 听起来很合适。如果使用 "start" 就会与动词 "start" 冲突（例如当你必须在类中定义一个函数 start() 来启动特定的进程或其他操作时，如果与已经存在的函数冲突，那将会很烦人）。 - Fareanor

Answer 3

为什么标准将end()定义为超出实际结尾而不是在实际结尾处？

因为：

1. 这样可以避免对空范围进行特殊处理。 对于空范围，begin()等于end()。

2. 这使得循环的结束条件简单：只需在未达到end()之前继续循环即可。

- Alok Save

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

还有： 如果end()指向有效元素，find()会返回什么？
你真的想再加一个名为invalid()的成员函数来返回无效迭代器吗？！
两个迭代器已经够痛苦了...

哦，还有，看一下这篇相关文章.

---

此外：

如果end在最后一个元素之前，你怎么在真正的结尾处进行insert()操作呢？！

- user541686

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++迭代器类编写<=运算符，那么你必须使所有迭代器都可以进行完全比较，并且如果C++使用完全封闭的范围，则创建不太灵活的迭代器（例如在std::list上操作的双向迭代器或在iostreams上操作的输入迭代器）的选择将更少。

- Ken Bloom

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++;
}

- Anders Abel

Answer 7

1. 如果容器为空，则 begin() == end()。
2. C++ 程序员倾向于在循环条件中使用 != 而不是 <（小于），因此将 end() 指向末尾位置的下一个位置是方便的。

- Andreas DM