C++中两个相似插入排序函数行为不一致问题排查

我在实现两个插入排序函数时遇到了奇怪的问题：两个函数都要对vector<pair<string, char>>按字符值升序排序，insertionSort1能输出正确结果，但仅调整了j--位置的insertionSort2却返回错误结果。更奇怪的是，当处理vector<int>时，两个函数都能正常工作。

问题复现代码（pair类型） #

#include <bits/stdc++.h>
using namespace std;

void insertionSort1(vector<pair<string,char>>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr.second<v[j].second) {v[j+1]=v[j]; v[j--];}
    v[j+1] = curr;
  }
}

void insertionSort2(vector<pair<string,char>>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr.second<v[j].second) {v[j+1]=v[j--];}
    v[j+1] = curr;
  }
}

int main() {
  vector<pair<string, char>> v1 {
    {"Alice"  , 'B'},
    {"Bob"    , 'A'},
    {"Charlie", 'B'},
    {"David"  , 'A'}
  };
  // 打印原向量
  for(auto i : v1) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Alice, B} {Bob, A} {Charlie, B} {David, A}
  // 排序
  insertionSort1(v1);
  // 打印排序后向量（结果正确）
  for(auto i : v1) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Bob, A} {David, A} {Alice, B} {Charlie, B}
  
  cout << "///////////////////////////////////////////\n";
  
  vector<pair<string, char>> v2 {
    {"Alice"  , 'B'},
    {"Bob"    , 'A'},
    {"Charlie", 'B'},
    {"David"  , 'A'}
  };
  // 打印原向量
  for(auto i : v2) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Alice, B} {Bob, A} {Charlie, B} {David, A}
  // 排序
  insertionSort2(v2);
  // 打印排序后向量（结果错误）
  for(auto i : v2) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Bob, A} {Bob, A} {David, A} {David, A}
  return 0;
}

问题复现代码（int类型） #

#include <bits/stdc++.h>
using namespace std;

void insertionSort1(vector<int>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr<v[j]) {v[j+1]=v[j]; v[j--];}
    v[j+1] = curr;
  }
}

void insertionSort2(vector<int>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr<v[j]) {v[j+1]=v[j--];}
    v[j+1] = curr;
  }
}

int main() {
  vector<int> v1 {7, 4, 1, 2, 3, 6, 9, 8, 5};
  for(auto i : v1) cout << i << " "; cout << endl; // 7 4 1 2 3 6 9 8 5
  insertionSort1(v1);
  for(auto i : v1) cout << i << " "; cout << endl; // 1 2 3 4 5 6 7 8 9
  
  cout << "//////////////////\n";
  
  vector<int> v2 {7, 4, 1, 2, 3, 6, 9, 8, 5};
  for(auto i : v2) cout << i << " "; cout << endl; // 7 4 1 2 3 6 9 8 5
  insertionSort2(v2);
  for(auto i : v2) cout << i << " "; cout << endl; // 1 2 3 4 5 6 7 8 9
  return 0;
}

问题根源：未定义行为 #

两个函数的唯一差异在while循环体：

• insertionSort1中是两步操作：v[j+1]=v[j]; v[j--];，分号是序列点，确保先完成v[j+1]的赋值，再执行j--，整个过程的行为是确定的。
• insertionSort2中合并为一步：v[j+1] = v[j--];，这里存在严重问题：赋值运算符左右两边的表达式都涉及变量j，右边的j--修改了j的值，左边的j+1读取了j的值，这两个操作之间没有序列点，属于C++中的未定义行为。

编译器可以自由选择求值顺序：

• 若先计算右边：取v[j]的值，j减1，再把值赋值给v[j+1]（此时j已减1，j+1等于原j值），逻辑和insertionSort1一致，结果正确。
• 若先计算左边：先得到j+1的目标位置，再执行j--修改j，最后把v[j]（已变为j-1位置的元素）赋值给目标位置，导致错误的元素复制，最终出现重复元素。

为什么int类型时表现正常？ #

未定义行为的结果不可预测，并非一定会出错。处理int向量时，编译器刚好选择了“先算右边”的求值顺序，让结果碰巧正确，但这只是巧合——换编译器、编译选项或输入数据，都可能触发错误。

修复方案 #

要避免未定义行为，必须确保修改和读取变量的操作间有明确序列点，比如把j--单独拆分（insertionSort1的写法），或者更清晰地写成：

while(j>=0 && curr.second<v[j].second) {
    v[j+1] = v[j];
    j--;
}

（注：insertionSort1中的v[j--];是多余的，仅读取v[j]值但未使用，正确写法应为直接j--;）

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