C++的sort函数第二个参数为什么不是数组的最后一个元素的地址?

codinghuang
  • 142

clipboard.png

不是说第二个参数是要排序元素的结束地址吗?
按道理来说,我要把这10个元素排序,只需要到a + 9即可了。但是,如果是a + 9的话,最后一个元素就不会参与排序了。请问是什么原因?

回复
阅读 3.9k
3 个回答
✓ 已被采纳

The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

也就是说这个范围是 左闭右开 的

sort的算法实际上是很复杂的,不好看内部实现,在cppref倒是可以查到find算法的实现,方便理解问题. 算法在迭代器的使用原则上是一致的; 前闭后开是算法入参的要求,为什么有这个要求,看实现:

template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

last就是要求在容器尾部, 用来判断是否已经遍历到头了,和普通的for循环本质上一样

// 就把10想象成第二个入参吧. 
for(int i=0; i<10; ++i)

这是跟迭代器的设计思想有关系的。
sort函数传的是一个容器的开始迭代器和尾后迭代器。尾后迭代器,故名思意就是末尾元素的后面一个迭代器。

那,为什么要设计成尾后迭代器而不是尾元素迭代器呢?是因为:

for循环遍历一个容器v:

for (auto it = v.begin(); it != v.end(); it++) {
    //do sth
}

如果end()迭代器是尾元素,那么这个for循环遍历的时候就会遍历不到最后一个元素。

那有的人又会说,我可以把 for循环的判断条件修改维it <= v.end()呀,这样不就可以遍历整个容器了么?
但是有一点需要注意,并不是所有容器都有 <, <=, >,>=这些比较操作的,因为有点不是连续内存地址的话,大小是无法比较出来的,比如链表,你无法比较通过<来确定哪个元素在前面。
但是 !=和 ==是肯定能比较得出来的。

综上,我们需要遍历一个容器的时候,要用到的判断条件是it != end(),也就表明,end()不能是最后一个元素,而是最后一个元素的下一个元素。
进而,sort()的参数就是尾后迭代器,进而, 你需要传递a,和 a+10。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏