在空容器上调用时 std::partition 的行为？

发布于 2024-08-14 21:06:28 字数 315 浏览 3 评论 0原文

在空容器（std::list）上调用 std::partition 时遇到问题。

std::list<int>::iterator end_it = std::partition(l.begin(), l.end(), SomeFunctor(42));
std::list<int>::iterator it = l.begin();

while (it != end_it)
{
  // do stuff
}

如果列表为空，std::partition 返回一个迭代器，即不等于到 l.end()。这是默认行为吗？

原文

I ran into a problem when calling std::partition on an empty container (std::list).

std::list<int>::iterator end_it = std::partition(l.begin(), l.end(), SomeFunctor(42));
std::list<int>::iterator it = l.begin();

while (it != end_it)
{
  // do stuff
}

If the list is empty, std::partition returns an iterator, that is not equal
to l.end(). Is this the default behaviour?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

千寻… 2024-08-21 21:06:28

我是否遗漏了某些东西，或者不应该：

std::list<int>::iterator end_it = l.begin();

是：

std::list<int>::iterator end_it = l.end();

但实际上我认为partition()的返回值对于空值集是未定义的。返回值定义为：

迭代器 i 使得对于任何
[first, i) 范围内的迭代器 j，
pred(*j) != false，并且对于任何
[i,last) 范围内的迭代器 k，
pred(*j) == false。

恕我直言，谓词不能应用于结束迭代器，因为它不能取消引用。

Am I missing something, or shouldn't:

std::list<int>::iterator end_it = l.begin();

be:

std::list<int>::iterator end_it = l.end();

But actually I think the return value of partition() is undefined for an empty set of values. The return value is defined to be:

An iterator i such that for any
iterator j in the range [first, i),
pred(*j) != false, and for any
iterator k in the range [i, last),
pred(*j) == false.

IMHO, the predicate cannot be applied to an end iterator, as it would not be dereferrencable.

回复收藏 0 原文

故事还在继续 2024-08-21 21:06:28

目前确实没有好的答案。 C++ 委员会的库工作组发行号 1205 正好涵盖了这个问题。该问题包括主要决议和替代拟议决议，但尚未被接受或拒绝（我不喜欢其中任何一个）。

由于该标准没有给出将算法应用于空范围的结果的明确定义，因此我认为这样做的结果目前是未定义的。我认为有希望在下一版本的标准中定义它，但目前还没有。即使是这样，从实际的角度来看，至少在一段时间内避免它可能会更好，因为编译器可能需要一段时间才能在这方面达到一致（尽管它通常应该是相当轻松修复）。

编辑，主要是为了回应 Martin B 的评论：列出了 [alg.partitions] 的问题，其中包括 std::partition 和 std::stable_partition。不幸的是，拟议的措辞似乎没有直接解决其中任何一个问题。它引用的段落（至少在 N2960 中）在 std::is_paritioned 的描述中，这几乎是 Martin B 所描述的，尽管他使用了错误的名称。更糟糕的是，主要提议的决议是非规范性注释的形式。

不过，正如我所说，我不太喜欢这两个拟议的决议。主要尝试将要求放在非规范性注释中。如果这些注释澄清了其他地方确实已经存在但可能很难找到的要求，那么它们就很好。在这种情况下，我很确定这些要求确实不存在。替代解决方案更好，但无法解决空范围是否为有效范围的核心问题。

IMO，更好的解决方案将从 §24.1/7 开始。这已经告诉我们：“范围 [i, i) 是一个空范围；...”我认为它应该添加规范语言来明确声明空范围是或不是有效范围。如果它不是有效范围，则无需添加任何其他内容 - 已经明确将算法应用于无效范围会产生未定义的行为。

如果空范围有效，则需要添加规范性措辞来定义将每种算法应用于空范围的结果。这将回答基本问题，然后说明该答案对每个特定算法意味着什么。

Right now, there really is no good answer. The Library Working Group of the C++ committee issue number 1205 covers exactly this question. That issue includes both a primary and an alternative proposed resolution but neither has been accepted or rejected yet (and I don't like either one).

Since the standard doesn't give an unambiguous definition of the result of applying an algorithm to an empty range, I'd say the result of doing so is currently undefined. I think there's some hope that it'll be defined in the next version of the standard, but for now it's really not. Even when it is, from a practical viewpoint it'll probably be better to avoid it at least for a while, because it may be a while before compilers conform in this respect (though it should usually be a fairly easy fix).

Edit, mostly in response to Martin B's comment: the issue is listed for [alg.partitions], which includes both std::partition and std::stable_partition. Unfortunately, the proposed wording does not seem to directly address either one. The paragraph it cites is (at least in N2960) in the description of std::is_paritioned, which is pretty much what Martin B described, even though he used the wrong name for it. Worse, the primary proposed resolution is in the form of non-normative notes.

As I said, though, I don't really like either proposed resolution. The primary tries to place requirements in non-normative notes. Such notes are fine if they clarify requirements that are really already present elsewhere, but might be hard to find. In this case, I'm pretty sure the requirements really aren't present. The alternative resolution is better, but fails to address the core question of whether an empty range is a valid range.

IMO, a better resolution would start at §24.1/7. This already tells us that: "A range [i, i) is an empty range;..." I think it should add normative language to explicitly state that an empty range either is or is not a valid range. If it's not a valid range, nothing else needs to be added -- it's already explicit that applying an algorithm to an invalid range gives undefined behavior.

If an empty range is valid, then normative wording needs to be added to define the results for applying each algorithm to an empty range. This would answer the basic question, then state what that answer implies for each specific algorithm.

回复收藏 0 原文