2014-06-18 61 views
-6

是否std::sort假设它能够正确地工作,如果它得到一个空的范围?std ::排序在空向量

我得到一个分段错误(GCC 4.8.3),此代码:

std::vector<float> f; 
std::sort(f.begin() + 1, f.end()); 

标准说,对于空载体begin()end()返回相同的值。所以我预计sort在上述情况下什么也不做,因为它应该得到一个空的范围:begin()+1应该大于end()

有这个空范围排序没有问题:

std::sort(f.begin(), f.end()); 
+4

那么'f.begin()+ 1'呢?那不是越界吗? – juanchopanza

+0

@juanchopanza它有一些价值,重要的是'begin()+ 1'是'end()'。 – user2052436

+4

这是一个值是无效的迭代器。它不是'>'或'<''而不是'end()'。这是无效的。 – juanchopanza

回答

1

f.begin()+1是出界,这是一个用于分割故障的原因。

使用f.begin()作为数组的开始,并且这将是安全使用的。

+0

好吧,为了排除第一个元素,我需要在调用'sort'前检查'size()> 0'。 – user2052436

+0

是的,这是正确的。 – pippin1289

+0

谢谢,pippin1289 – user2052436

3

std::sort预计[begin, end)是一个有效的范围,如果您继续增加begin您最终将达到end。在你的情况下,begin()+1已经过去了end(),所以std::sort无法知道它正在经过该范围的末尾。

std::sort需要迭代器,而不是指针。正因为如此,它无法运行begin < end检查:如果您通过两个迭代器的rbegin()rend(),则会失败。

如果您想对排除最初元素的std::vector部分进行排序,您需要确保容器不是空的。否则,begin()+1将产生无效的迭代器。

注意:虽然从技术角度而言,当您在空容器上执行begin()+1时发生未定义的行为,但您的案例中的崩溃几乎肯定来自std::sort中的取消引用。另请注意,如果您有C++ 11兼容的编译器,则使用std::next(v.begin(), 1)优于v.begin() + 1。上输入迭代

+1

你不会去std :: sort,它早就结束了。 – Deduplicator

+0

好吧,现在你也说出了实际的错误,我改变了我的投票。 – Deduplicator

2

递增具有前提迭代器必须提领。对于空向量,v.begin()不可解引用,因此试图执行v.begin() + 1(反过来以增量的方式定义)是未定义的行为。

此外,std::sort(begin, end)要求[begin, end)是一个有效的范围内,并且所述标准说(§24.2.1[iterator.requirements.general]/P7)

范围[i,j)是有效的,当且仅当ji可到达。将库中的函数应用于无效范围的结果未定义。

对于大多数随机访问迭代(<>为其定义的迭代器的唯一类型),如果a > b然后a不是来自b可达,所以[a, b)确实表示空范围 - 它不根本不表示有效范围。

+0

@Deduplicator ...这是第一段? –

+0

@Dupuplicator UB并不总是直接显示。在这里,segfault可能来自'it!= end',所以解除引导'begin + 1'(指向无效内存,是的)会发生,所以繁荣。是的,从技术上讲,该节目在'v.begin()+ 1'展出UB,但其他方面也很重要。 – stefan

+0

@Deduplicator'v.begin()+ 1'是未定义行为的原因正是因为'v.begin()'不可解引用,并且您有违反前提条件。 –