合并有序vector时外层循环次数异常的问题排查求助

我尝试实现Merge_Indexed函数，用于合并两个已排序的vector以优化归并排序，但用测试用例vector a={5,7,8,10}、vector b={2,4,9,11}运行时，外层遍历b的循环执行次数远超b的大小（本应4次），还出现元素重复插入的情况，异常输出如下，请求帮忙排查原因。

原代码 #

template<typename T>
std::vector<T> Merge_Indexed(std::vector<T>& a, std::vector<T>& b)
{
    for(auto it=b.begin(); it<b.end(); it++)
    {
        for(auto it2=a.end()-1; it2>=a.begin(); it2--)
        {
            if(*it>*it2)
            {
                a.insert(it2+1, T(*it));
                std::cout<<"Case 1\n";
                break;  
            }
            else if(*it<*it2&& it2==a.begin())
            {
                 a.insert(it2,T( *it));
                 std::cout<<"Case 2\n";
                 break;
            }
            else
            {
                std::cout<<"Case 3\n";
            }
            
        }
        for(int x: a)
        {
            std::cout<< x<<" ";
        }
        std::cout<<"\n******\n";
    }
    return a;
}

测试用例 #

std::vector<int> a= { 5,7,8,10 };
std::vector<int> b= { 2,4,9,11 };

异常输出 #

Case 3
Case 3
Case 3
Case 2
2 5 7 8 10 
******
Case 3
Case 3
Case 3
Case 3
Case 1
2 4 5 7 8 10 
******
Case 3
Case 1
2 4 5 7 8 9 10 
******
Case 1
2 4 5 7 8 9 10 11 
******
Case 3
Case 3
Case 3
Case 3
Case 3
Case 3
Case 3
Case 3
2 4 5 7 8 9 10 11 
******
Case 3
Case 3
Case 3
Case 3
Case 3
Case 3
Case 3
Case 1
2 4 4 5 7 8 9 10 11 
******
Case 3
Case 3
Case 3
Case 1
2 4 4 5 7 8 9 9 10 11 
******
Case 3
Case 1
2 4 4 5 7 8 9 9 10 11 11 
******
2 4 4 5 7 8 9 9 10 11 11

问题原因分析 #

1. 重复调用函数：异常输出中的8次循环是两次函数调用的结果（每次调用执行4次循环）。原函数直接修改传入的a，第二次调用时会基于已经合并过的a再次插入b的元素，导致重复插入。
2. 未处理元素相等的场景：原代码仅处理*it > *it2和*it < *it2且it2是begin的情况，当*it等于a中某个元素时，会继续向前遍历，最终找到比*it小的元素并插入，导致重复元素出现。
3. 内层循环逻辑漏洞：当*it等于a.begin()的元素时，原代码不会执行插入操作，导致元素遗漏（虽本次测试用例未触发，但属于潜在bug）。

修复方案 #

修改代码，使用临时vector存储结果，优化遍历逻辑，覆盖所有场景：

template<typename T>
std::vector<T> Merge_Indexed(const std::vector<T>& a, const std::vector<T>& b)
{
    std::vector<T> result = a;
    // 用范围for遍历b，避免迭代器风险
    for(const auto& val : b)
    {
        auto it = result.end();
        // 从后往前找到第一个<=val的元素
        while(it != result.begin())
        {
            --it;
            if(*it <= val)
            {
                result.insert(it + 1, val);
                std::cout << "Case 1\n";
                break;
            }
        }
        // 若所有元素都大于val，插入到开头
        if(it == result.begin() && *it > val)
        {
            result.insert(it, val);
            std::cout << "Case 2\n";
        }
        // 输出当前结果
        for(int x : result)
        {
            std::cout << x << " ";
        }
        std::cout << "\n******\n";
    }
    return result;
}

修复要点 #

• 使用临时vectorresult存储合并结果，避免修改原a，同时防止多次调用时重复插入。
• 用范围for遍历b，代码更简洁安全，避免迭代器相关问题。
• 处理元素相等的场景：找到第一个小于等于val的元素后插入到其后方，保证归并排序的稳定性。
• 参数使用const引用，明确不修改原输入容器，提升代码安全性。

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