c++ - 如何在不使用标准算法的情况下在排序 vector 中添加 c 元素？

Question

我的代码在某些情况下不起作用:当 c1 为 4 时，它不会输出任何内容，但它适用于大于 9 的数字。这是为什么？

#include<iostream>
#include<vector>
using namespace std;
void insertfast(vector<int>&v, int c)
{
if (c >= v[v.size()-1])v.push_back(c);
if (c <= v[0])v.insert(v.begin(), c);
int min = 1;
int max = v.size();
while (v.size() != 9) {
    int i = (min + max) / 2;
    if (v[i - 1] <= c && c <= v[i])v.insert(v.begin() + i, c);
    if (v[i] <= c && c <= v[i + 1])v.insert(v.begin() + (i + 1), c);
    if (c < v[i])
        max = i;
    else
        min = i;
}
}
int main()
{
vector<int>v1 = { 2,5,9,22,44,55,88,777 };
int c1 = 4;

insertfast(v1, c1);

for (int i = 0; i < 9; i++)
    cout << v1[i] << endl;
}

Answer 1

让我们花点时间从逻辑上逐步浏览这里的代码，因为我认为这是一道作业题，所以了解如何做很重要。有调试器之类的工具用于更大的项目和更困难的问题，但像这样的小逻辑错误一直在发生。

好的，所以 insertfast()是插入 int 的函数进入 vector<int>以有序的方式。您要做的第一件事是与 vector 的第一个和最后一个元素进行比较。

if (c >= v[v.size() - 1]) 
    v.push_back(c); 
if (c <= v[0]) 
    v.insert(v.begin(), c);

我们只能成为其中之一，如果其中任何一个为真，我们就完蛋了。所以这里最好的选择就是return从功能上讲，我们不关心做任何其他事情。我们知道这一点，但程序不知道。它会继续比较我们不想比较的东西并排除故障。

if (c >= v[v.size() - 1]) {
    v.push_back(c);
    return;
}
if (c <= v[0]) {
    v.insert(v.begin(), c);
    return;
}

如果这两个语句都是假的，而我们仍在函数中怎么办？我们仍然需要弄清楚在哪里插入这个值，所以我们遍历元素。

while (v.size() != 9)

这是一个非常糟糕的条件循环，因为它只有在我们将大小为 8 的 vector 传递给函数时才起作用。对于您的特定算法，您本质上想要循环，直到将某个值添加到 vector 。我建议使用无条件循环(毕竟我们正在尝试“快速”)，也就是无限循环，并且明确地在循环内返回或中断。

int min = 1;
int max = v.size();
while (1) {
    int i = (min + max) / 2;
    if (v[i - 1] <= c && c <= v[i]) {
        v.insert(v.begin() + i, c);
        return;
    }
    if (v[i] <= c && c <= v[i + 1]) {
        v.insert(v.begin() + (i + 1), c);
        return;
    }
    if (c < v[i])
        max = i;
    else
        min = i;
}

break而不是 return在这里也可以很好地工作，因为如果你跳出这个循环，函数的结尾就会被命中，你无论如何都会返回。因此，我们仅通过重新思考设计和单步执行代码就解决了这个问题。