C++基于数组实现的list拼接后元素顺序错误问题排查

需求说明 #

实现两个基于数组的列表拼接逻辑：

• 将第一个列表的所有元素按原有顺序追加到第二个列表尾部，追加完成后清空第一个列表
• 若插入过程中因达到数组最大容量导致插入失败，需将两个列表回滚到插入操作执行前的状态

异常表现 #

基础功能可正常运行，但拼接后列表元素顺序不符合预期：

• 测试用例：第一个列表元素为10 20 30 40 50，第二个列表元素为100 200 300
• 实际拼接输出：100 200 300 10 30 50 20 40
• 预期拼接输出：100 200 300 10 20 30 40 50

原始实现代码 #

using namespace std;
const int maxsize=100;
template<class T>
class list{
    T entry[maxsize];
    int count;
    public:
    list(){
        count=0;
    }
    bool empty(){
        return count==0;
    }
    bool insert(int pos, T item){
        if(pos<0 || pos>count) return 0;
        if(count>=maxsize) return 0;
        for(int i=count-1; i>=pos; i--)
            entry[i+1]=entry[i];    
        entry[pos]=item;
        count++;
        return 1;
    }
    bool remove(int pos){
        if(pos<0 || pos>=count) return 0;
        for(int i=pos; i<count-1; i++)
            entry[i]=entry[i+1];
        count--;
        return 1;
    }
    bool retrieve(int pos, int &item){
        if(pos<0 || pos>=count) return 0;
        item=entry[pos];
        return 1;
    }
    bool replace(int pos, int item){
        if(pos<0 || pos>=count) return 0;
        entry[pos]=item;
        return 1;
    }
    int size(){
        return count;
    }
};
void print(list<int>L){
    int item;
    for(int i=0;i<L.size();i++){
        L.retrieve(i,item);
        cout<<item<<" ";
    }
    cout<<endl;
}
void fill(list<int>&L, int n){
    for(int i=1; i<n; i++)
        L.insert(L.size(),rand()%100);
}
bool concat (list<int>&l1,list<int>&l2){
    int item;
    int c=l2.size();
    while(!l1.empty()) {
    for(int i=0; i<l1.size(); i++){
        l1.retrieve(i,item);
        if(l2.insert(l2.size(),item)==0){
            for(int j=c; j>l2.size()-1; j--){
                l2.retrieve(j,item);
                l1.insert(l1.size(),item);
                l2.remove(j);
            }
        return 0;
        }
    else {
    c++;
    l1.remove(i);
}
}
    }
    return 1;
}
main(){
    list<int>L1, L2;
    L1.insert(0,10);
    L1.insert(1,20);
    L1.insert(2,30);
    L1.insert(3,40);
    L1.insert(4,50);
    L2.insert(0,123);
    L2.insert(1,143);
    L2.insert(2,345);
    L2.insert(3,545);
    L2.insert(4,536);
    print(L1);
    print(L2);
    cout<<"<<1: succeeded, 0: failed>> "<<concat(L1,L2)<<endl;
    cout<<"First List: ";
    print(L1);
    cout<<"Second List: ";
    print(L2);
}

问题根因 #

拼接函数concat的遍历与删除逻辑存在本质错误：
在遍历l1的for循环里，每成功把一个元素插到l2，就立刻删除l1当前i位置的元素。删除操作会让l1里i位置后面的所有元素往前挪一位，但循环变量i还是会照常加1，直接跳过了刚挪到i位置的下一个元素，最后插进去的元素顺序自然是乱的。
对应错误输出的实际执行流程：

• 初始l1是[10,20,30,40,50]，i=0取到10，插入l2后删除i=0的元素，l1变成[20,30,40,50]
• i自增到1，此时取到的是索引1位置的30，插入l2后删除i=1的元素，l1变成[20,40,50]
• i自增到2，取到索引2位置的50，插入l2后删除i=2的元素，l1变成[20,40]
• 第一轮for循环结束，外层while判断l1不为空，再次进入for循环
• i=0取到20，插入l2后删除i=0元素，l1变成[40]
• i自增到1，超出l1当前长度，for循环结束，while判断l1仍不为空，第三次进入for循环
• i=0取到40，插入l2后删除i=0元素，l1为空
  最后l2追加的元素顺序就是10、30、50、20、40，和观测到的错误输出完全一致。
  另外这种边插入边修改l1的写法，也让失败回滚的逻辑变复杂，现有回滚代码无法保证元素按原顺序放回l1。

修复方案 #

核心思路是所有元素插入成功之前，完全不修改l1的内容，从根源上避免遍历跳元素的问题，同时简化回滚逻辑：

• 操作开始前先记录l2的初始长度，作为回滚的标记点
• 按索引从0到l1末尾的顺序，依次把元素取出来追加到l2尾部，全程不修改l1
• 如果中途插入失败，直接把l2里超过初始长度的新增元素全部删除即可——这时候l1从来没被改过，自然保持操作前的状态，不需要额外回滚
• 等所有元素都成功插入l2之后，再清空l1就完成操作
  修复后的concat函数代码如下：

bool concat (list<int>&l1,list<int>&l2){
    int item;
    // 记录l2操作前的初始长度，用于失败回滚
    const int original_l2_size = l2.size();
    const int l1_total = l1.size();
    // 先完成所有插入操作，过程中不修改l1
    for(int i = 0; i < l1_total; i++){
        l1.retrieve(i, item);
        // 插入失败则回滚l2到初始状态
        if(!l2.insert(l2.size(), item)){
            while(l2.size() > original_l2_size){
                l2.remove(l2.size() - 1);
            }
            return false;
        }
    }
    // 全部插入成功，再清空l1
    while(!l1.empty()){
        l1.remove(0);
    }
    return true;
}

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