c++ 处理迭代器时,由信号SIGSEGV(地址边界错误)终止

txu3uszq  于 2023-02-14  发布在  其他
关注(0)|答案(2)|浏览(146)

我尝试实现合并排序算法。首先我尝试创建合并方法。我使用向量和迭代器。但是merge函数中的while主体导致了这个错误:
"./a. out"由信号SIGSEGV终止(地址边界错误)
这是密码

#include <iostream>
#include <vector>

std::vector<int> merge(std::vector<int> &, std::vector<int> &);

int main()
{
  std::vector<int> vect {1,3,5,7};
  std::vector<int> vect2 {2,3,6,8};
  std::vector<int> temp_vect = merge(vect, vect2);
  for(int num: temp_vect) {
    std::cout << num  << std::endl;
  }

}

std::vector<int> merge(std::vector<int> & first_vect, std::vector<int> & second_vect)
{
  std::vector<int> sorted_vect;
  auto sorted_it = sorted_vect.begin();
  auto first_it = first_vect.begin(), second_it = second_vect.begin();

  while(first_it != first_vect.end() || second_it != second_vect.end()) {
      if(*first_it < *second_it) {
        sorted_vect.push_back(*first_it);
        first_it++;
      } else if(*first_it > *second_it) {
        sorted_vect.push_back(*second_it);
        second_it++;
      } else {
        sorted_vect.push_back(*first_it);
        sorted_vect.push_back(*second_it);
        first_it++; second_it++;
      }
  }

  if(first_it == first_vect.end()) {
    //end of first_vect reached
    //inserting the rest of second_vect
    sorted_vect.insert(sorted_vect.end() - 1, second_it, second_vect.end());
  } else if (second_it == second_vect.end()) {
    //end of second_vect reached
    //inserting the rest of first_vect
    sorted_vect.insert(sorted_vect.end() - 1, first_it, first_vect.end());
  }

  return sorted_vect;
}
pgvzfuti

pgvzfuti1#

通常SIGSEGV是在一个进程试图访问一个没有分配给该进程的内存时引发的。引发SIGSEGV的主要原因是解引用一个无效指针。在您的情况下,当您解引用first_it或second_it以检查其值时,当您到达列表的末尾时,会发生这种情况。
您至少需要三个更改:

1: line 23- while(first_it != first_vect.end() && second_it != second_vect.end())
2: line 40- sorted_vect.insert(sorted_vect.end(), second_it, second_vect.end());
3: line 44- sorted_vect.insert(sorted_vect.end(), first_it, first_vect.end());

1:您应该检查是否已到达任何列表的末尾:应使用和(&&)而不是或(||)。这将删除SIGSEGV错误。
2&3:您应该将剩余列表的其余部分添加到合并列表的末尾,而不是最后一个元素之前。
可选变更:
1.您不需要sorted_it变量(您没有使用它)
1.你不必检查是否相等,如果值相等,你可以插入其中的任何一个,循环的下一次迭代就会变魔术。
1.您不必检查哪个列表到达其末尾,您可以合并每个列表的其余部分。
以上所有内容都反映在这里:

std::vector<int> merge(std::vector<int> & first_vect, std::vector<int> & second_vect)
{
      std::vector<int> sorted_vect;
      auto first_it = first_vect.begin(), second_it = second_vect.begin();

      while(first_it != first_vect.end() && second_it != second_vect.end()) {
           if(*first_it < *second_it) {
               sorted_vect.push_back(*first_it);
               first_it++;
           } else {
               sorted_vect.push_back(*second_it);
               second_it++;
           }
      }
      sorted_vect.insert(sorted_vect.end(), first_it, first_vect.end());
      sorted_vect.insert(sorted_vect.end(), second_it, second_vect.end());
      return sorted_vect;
}
brccelvz

brccelvz2#

while(first_it != first_vect.end() || second_it != second_vect.end())

您正在迭代,直到:

  1. first_it等于first_vect.end()
  2. second_it等于second_vect.end()
    这两个条件都必须为真,例如,如果first_it已经到达first_vect.end(),则迭代将继续,直到second_it到达其向量的末尾。
if(*first_it < *second_it) {

正如我刚才解释的,first_it现在可以等于它的向量的end()迭代器,在这种情况下,解引用它会导致未定义的行为。
这同样适用于第二个向量的迭代器。
您的逻辑没有考虑到任何一个迭代器到达其向量的end()的可能性。
一种解决方法是将||转换为&&,然后在最后添加额外的代码,将任一向量中的任何剩余值附加到输出向量。
另一种解决这个问题的方法是调整if()条件,以考虑迭代器可能是end()值的可能性,并相应地进行。

if(second_it == second_vect.end() ||
      (first_it != first_vect.end() && *first_it < *second_it)) {

但是这个逻辑在这里变得有点复杂(两个if条件都必须以这种方式检查两个迭代器的边大小写)。

相关问题