自定义C++ Vector类insert函数触发Setup超时问题求助

问题描述 #

构建自定义Vector类并实现insert()函数时，出现执行超时错误：

[ 20%] Built target support
  [ 80%] Built target probLib1
  [ 90%] Building CXX object test/CMakeFiles/vector_insert.dir/vector_insert.cpp.o
  [100%] Linking CXX executable vector_insert
  [100%] Built target vector_insert
  
❌ vector_insert
::error::Setup timed out in 60000 milliseconds

Vector类私有成员定义：

private:
    T* ifmt; 
    int vsize;
    int vcap; 

insert()与push_back()函数实现：

void insert(int index, const T& item) // insert element
    {
        push_back(item); // ?
        for (int i = vsize - 1; i > index; --i)
        {
            ifmt[i] = ifmt[i - 1];
        }      
        ifmt[index] = item;     
        
    }

void push_back(const T& item) // append element // send element to the end
    {
      if (vsize == vcap) 
      {
        T* ttemp = new T[2 * vcap]; 
        for (int i = 0; i < vsize; ++i) 
        {
            ttemp[i] = ifmt[i];
        }
        delete [] ifmt; 
        vcap = vcap * 2; 
        ifmt = ttemp; 
      }
      ifmt[vsize] = item; 
      vsize = vsize + 1; 
    }

推测问题由push_back(item);语句导致，但不知如何解决。

问题分析与解决 #

你的insert()逻辑存在严重错误：直接调用push_back(item)会先把元素加到末尾，随后的循环又将元素从后往前挪，最后再给index位置赋值，这会导致元素重复添加；如果vcap初始值为0，push_back里的2*vcap会变成0，触发无效内存分配或无限扩容逻辑，最终导致超时。

正确的insert()实现应该先检查容量是否足够，再将index及之后的元素向后移动一位，最后插入新元素，而非先调用push_back：

void insert(int index, const T& item)
{
    // 检查索引合法性（可选但建议）
    if (index < 0 || index > vsize) {
        // 可抛出异常或做错误处理
        return;
    }

    // 容量不足则扩容，处理初始容量为0的情况
    if (vsize == vcap) {
        int new_cap = vcap == 0 ? 1 : 2 * vcap;
        T* ttemp = new T[new_cap];
        for (int i = 0; i < vsize; ++i) {
            ttemp[i] = ifmt[i];
        }
        delete[] ifmt;
        ifmt = ttemp;
        vcap = new_cap;
    }

    // 将index及之后的元素向后移动一位
    for (int i = vsize; i > index; --i) {
        ifmt[i] = ifmt[i - 1];
    }

    // 插入新元素并更新大小
    ifmt[index] = item;
    vsize++;
}

额外注意事项：

• 必须处理初始vcap为0的场景，否则第一次扩容会创建长度为0的数组，后续赋值操作会触发越界，引发未定义行为。
• 建议对insert的输入索引做合法性检查，避免传入index < 0或index > vsize的非法值。

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