c++ - 将元素附加到 vector 会导致后续排序失败

Question

我有 2 个 vector :一个元素 vector 和一个计数 vector 。在对Element vector 进行排序时，我需要对Element vector 值对应的计数 vector 进行排序。我需要将元素 vector 附加到全局 vector (Proc) 及其对应的 Proc_count vector ，该 vector 的大小逐渐增加，并重复上述排序过程。

但是，在将元素附加到 Proc 和 Proc_count vector 的末尾后，第二个排序步骤失败了。我知道重新调整 vector 的大小会使迭代器无效，但是即使在使用 std::reserve 之后，我也会注意到相同的结果。

typedef uint64_t data_t;

struct MyComparator
{
   const std::vector<data_t> & value_vector;
   MyComparator(const std::vector<data_t> & val_vec):
          value_vector(val_vec) {}

   bool operator()(int i1, int i2)
  {
    return value_vector[i1] < value_vector[i2];
  }
};

void SortAndAggregate(std::vector<data_t>& arr, std::vector<int>& count, std::vector<int>& add)
{

 sort(count.begin(), count.end(), MyComparator(arr));
 sort(arr.begin(), arr.end());

    printf("Sorted arr: \n");
    for (std::vector<data_t>::iterator it = arr.begin() ; it != arr.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';

    printf("Sorted count: \n");
    for (std::vector<int>::iterator it = count.begin() ; it != count.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';

 int aggr=0;
 for(int i = 0; i < (int)(arr.size()); i++)
    {
      aggr = count[i];
      if (arr[i] == arr[i+1]) {
          do {
                aggr += count[i+1];
                i++;
             } while(i<(int)arr.size() && (arr[i] == arr[i+1]));
       }
       add.push_back(aggr);
    }

 arr.erase( unique( arr.begin(), arr.end() ), arr.end() );
 assert(arr.size() == add.size());

    printf("Sorted add: \n");
    for (std::vector<int>::iterator it = add.begin() ; it != add.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';
    std::cout << '\n';

}

int main(int argc, char *argv[])
{
    int N=20;
    srand(time(0));

    data_t mydata[] = {14,32,71,12,45,26,80,53,33, 9};
    int mycnt[]     = {1,  2, 3, 4, 5, 6, 7, 8, 9,10};
    std::vector<data_t> dummy_data (mydata, mydata+10);
    std::vector<int> dummy_cnt (mycnt, mycnt+10);

    std::vector<data_t> arr1;
    std::vector<int> cnt;
    std::vector<int> arr3;
    std::vector<data_t> proc_buf;
    std::vector<int> proc_buf_cnt;

    proc_buf.reserve(20);
    proc_buf_cnt.reserve(20);

    proc_buf.insert(proc_buf.end(), dummy_data.begin(), dummy_data.end());
    proc_buf_cnt.insert(proc_buf_cnt.end(), dummy_cnt.begin(), dummy_cnt.end());

    SortAndAggregate (proc_buf, proc_buf_cnt, arr3);
    proc_buf_cnt = arr3;
    arr3.clear();

    printf("Proc buffer before: \n");
    for (std::vector<data_t>::iterator it = proc_buf.begin() ; it != proc_buf.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';

    printf("Proc Count buffer before: \n");
    for (std::vector<int>::iterator it = proc_buf_cnt.begin() ; it != proc_buf_cnt.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';
    std::cout << '\n';

    for (int i = 0; i < N; ++i)
    {
         arr1.push_back(rand() % 10);
         cnt.push_back(i);
    }

    printf("Original array: \n");
    for (int it = 0 ; it < (int)arr1.size(); ++it)
         std::cout << ' ' << arr1[it];
    std::cout << '\n';

    printf("Original counts: \n");
    for (int it = 0; it < (int)cnt.size(); ++it)
         std::cout << ' ' << cnt[it];
    std::cout << '\n';
    std::cout << '\n';

    SortAndAggregate (arr1, cnt, arr3);

    proc_buf.insert(proc_buf.end(), arr1.begin(), arr1.end());
    proc_buf_cnt.insert(proc_buf_cnt.end(), arr3.begin(), arr3.end());
    arr3.clear();

    printf("Proc buffer before: size: %d \n", (int)proc_buf.size());
    for (std::vector<data_t>::iterator it = proc_buf.begin() ; it != proc_buf.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';

    printf("Proc Count buffer before: size: %d \n", (int)proc_buf_cnt.size());
    for (std::vector<int>::iterator it = proc_buf_cnt.begin() ; it != proc_buf_cnt.end(); ++it)
         std::cout << ' ' << *it;
    std::cout << '\n';
    std::cout << '\n';

    SortAndAggregate (proc_buf, proc_buf_cnt, arr3);
    proc_buf_cnt = arr3;

    assert(proc_buf.size() == proc_buf_cnt.size());

    arr1.clear();
    cnt.clear();
    arr3.clear();
    proc_buf.clear();
    proc_buf_cnt.clear();

    return 0;
 }

输出:

   Proc buffer before: 
   9 12 14 26 32 33 45 53 71 80
   Proc Count buffer before: 
   10 9 3 5 1 8 4 7 2 6

   Original Element array: 
   4 6 6 1 7 1 0 7 3 7 8 7 5 0 9 5 6 5 1 3
   original Element counts: 
   0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   Sorted arr: 
   0 0 1 1 1 3 3 4 5 5 5 6 6 6 7 7 7 7 8 9
   Sorted count: 
   6 13 3 18 5 19 8 0 17 15 12 1 16 2 11 9 7 4 10 14 // CORRECT sorted order
   Sorted aggregate: 
   19 26 27 0 44 19 31 10 14

   Appended Proc buffer (size: 19) 
   9 12 14 26 32 33 45 53 71 80 0 1 3 4 5 6 7 8 9
   Appended Proc Count buffer (size: 19) 
   10 9 3 5 1 8 4 7 2 6 19 26 27 0 44 19 31 10 14

   Sorted arr: 
   0 1 3 4 5 6 7 8 9 9 12 14 26 32 33 45 53 71 80
   Sorted count:  
   10 10 19 19 14 31 0 1 2 3 4 5 6 7 8 9 26 27 44 // INCORRECT sorted order ...!!!!
   Sorted aggregate: 
   10 10 19 19 14 31 0 1 5 4 5 6 7 8 9 26 27 44

关于为什么第二类失败的任何线索？我错过了什么吗？

Answer 1

正如另一个答案所暗示的，您遇到了越界访问错误。

此外，您很幸运，您的程序甚至达到了它的极限，因为您在第一次调用 SortAndAggreate 时就进行了越界访问，因此您的输出是在你的问题中显示基本上是无用的，因为正在调用未定义的行为。

在您的 MyComparator 仿函数中，您这样做:

bool operator()(int i1, int i2)
{
    return value_vector[i1] < value_vector[i2];
}

value_vector 是一个大小为==10 的 vector 。但是，i1 和 i2 的值最终变为 9 和 10，因此您将访问一个元素那是越界的。

问题的根源在于main:

int mycnt[] = {1,  2, 3, 4, 5, 6, 7, 8, 9,10};

当您填充 prof_buf_cnt 时，您使用这些值作为索引，并且您使用 prof_buf_cnt 作为 std::sort 中的索引仿函数 MyComparator。

至少在这里，解决方案是使用基于 0 的索引。

int mycnt[] = { 0, 1,  2, 3, 4, 5, 6, 7, 8, 9 };

---

注意:如果您将 MyComparator 仿函数中的那一行替换为以下内容:

    return value_vector.at(i1) < value_vector.at(i2);

您会立即看到问题，因为会抛出 std::out_of_range 异常。这将保证您的程序会因错误而停止，而不是继续运行并给人以它正在正常工作的印象(唯一的问题是输出错误)。

---

有关未定义行为的不可预测性的示例，请参见下面的两个链接:

See this example of your code using at()

See this example of your code using [ ]

请注意，上面的第二个链接显示您的代码“有效”，即使它不应该达到它所做的程度，而第一个链接通过抛出异常正确诊断问题。