如何修改C++函数实现元素按有序顺序插入vector？

Hey there! I see you're working on a vector exercise and stuck on the numsInsert function. No worries—let's break this down step by step so your program outputs 4 19 55 250 exactly as expected.

需求回顾 #

First, let's make sure we're on the same page:

• We need to modify the numsInsert function to take a reference to a vector<int> and a new integer newNum
• The goal is to insert newNum into the vector such that the entire vector stays sorted in ascending order at all times
• When all insertions are done, the vector should hold [4, 19, 55, 250], which will be printed as space-separated values

实现方法1：手动遍历找位置（适合理解原理） #

If you're still getting comfortable with STL algorithms, let's start with a manual approach that makes the logic crystal clear:

#include <iostream>
#include <vector>
using namespace std;

void numsInsert(vector<int>& numsList, int newNum) {
    // 找到newNum应该插入的位置
    int insertPos = 0;
    // 只要当前元素小于等于newNum，就继续往后找
    while (insertPos < numsList.size() && numsList[insertPos] <= newNum) {
        insertPos++;
    }
    // 在计算好的位置插入newNum
    numsList.insert(numsList.begin() + insertPos, newNum);
}

int main() {
    vector<int> nums;
    // 测试：随便按什么顺序插入数字，函数都会保持列表有序
    numsInsert(nums, 250);
    numsInsert(nums, 55);
    numsInsert(nums, 19);
    numsInsert(nums, 4);
    
    // 打印最终的有序列表
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

代码解释：

• 我们从insertPos = 0开始，也就是vector的起始位置
• 循环会一直执行，直到找到第一个比newNum大的元素（或者遍历到vector末尾）
• 找到位置后，用vector::insert()把newNum插入到这个元素的前面（如果所有元素都更小，就插在末尾）
• 这样每次插入后，vector都能保持有序状态

实现方法2：用STL的lower_bound（简洁高效） #

If you're ready to leverage STL tools, this approach is more concise and efficient—perfect for writing clean code:

#include <iostream>
#include <vector>
#include <algorithm> // 使用lower_bound需要包含这个头文件
using namespace std;

void numsInsert(vector<int>& numsList, int newNum) {
    // lower_bound返回指向第一个不小于newNum的元素的迭代器
    auto insertIt = lower_bound(numsList.begin(), numsList.end(), newNum);
    // 在该迭代器位置插入newNum
    numsList.insert(insertIt, newNum);
}

int main() {
    vector<int> nums;
    numsInsert(nums, 250);
    numsInsert(nums, 55);
    numsInsert(nums, 19);
    numsInsert(nums, 4);
    
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

代码解释：

• lower_bound是STL内置算法，专门用于在有序区间中查找第一个不小于目标值的元素，正好匹配我们的需求
• 我们直接把这个迭代器传给vector::insert()，它会自动把新元素放在正确的位置
• 对于大vector来说，这个方法比手动遍历更高效，因为lower_bound底层用的是二分查找

验证结果 #

不管你按什么顺序插入4, 19, 55, 250这几个数字，两种实现都会得到有序的vector [4, 19, 55, 250]，程序最终也会输出要求的序列。

内容的提问来源于stack exchange，提问作者user8402302