C ++ - 第二次二进制搜索的分段错误

Question

我有一个 class ledger，其实例应该将成员 class company 的实例存储在两个向量 combyID 和 combyname，按两个不同的标准排序 - ID 和名称（均为字符串）。向量一开始是空的，因此不是在每次新添加成员实例 class 之后对它们进行排序，而是使用自定义的二进制搜索方法 binsID 和 binsName 搜索向量以查找元素添加，如果未找到该元素，则将其插入向量中。 insert()位置由idx值定义，通过二分查找法修改。

问题出在方法 NewCo 中，该方法调用了两种二进制搜索方法并最终将元素插入到向量中。当程序运行在 main 函数中调用不止一个 NewCo 时，会给出 Segmentation fault (core dumped) 错误。如果未调用 binsID 方法或未在 combyID 上调用 insert()（省略对该向量的插入），则不会出现错误。我发布了代码和 valgrind 分析。

代码：

#include <cstdlib>
#include <cstdio>
#include <iostream>  
#include <string>
#include <vector>
using namespace std;

class ledger
{
  public:
    bool NewCo (string name, string ID)
    {
        unsigned int idx_id = 0, idx_name = 0;
        bool found1 = binsID(combyID, idx_id, ID);  //line 14
        bool found2 = binsName(combyname, idx_name, name);
        if (found1 == false && found2 == false)
        {
            company co;
            co.co_name = name;
            co.co_id = ID;
            combyID.insert(combyID.begin() + idx_id, co);
            combyname.insert(combyname.begin() + idx_name, co);
            return 1;
        }
        return 0;
    }
  private:
      class company
      {
      public:
          string co_name;
          string co_id;
      };
      vector <company> combyID;
      vector <company> combyname;
      bool binsName(vector <company> vek, unsigned int & idx, string val)
      {
          if (vek.size() == 0) return false; 
          unsigned int begin = 0, end = vek.size() - 1, mid;
          while(begin <= end)
          {
              mid = (begin + end) / 2;
              idx = mid;
              if (vek[mid].co_name == val) 
              {
                  idx = mid;
                  return true;
              }
              else if (val < vek[mid].co_name)
                  end = mid - 1;
              else
                  begin = mid + 1;
          }
        if (vek[idx].co_name < val) idx++;
        return false;
      }
    bool binsID(vector <company> vek, unsigned int & idx, string val)
      {
        if (vek.size() == 0) return false; 
          unsigned int begin = 0, end = vek.size() - 1, mid;
          while(begin <= end)
          {
              mid = (begin + end) / 2;
              idx = mid;
              if (vek[mid].co_id == val)  //line 66
              {
                  idx = mid;
                  return true;
              }
              else if (val < vek[mid].co_id)
                  end = mid - 1;
              else
                  begin = mid + 1;
          }
        if (vek[idx].co_id < val) idx++;
        return false;
      }
};

int main ( void )
{
  ledger b1;
  b1.NewCo( "ABC", "123.456.789" );
  b1.NewCo( "DEF", "123.456" );  //line 85

  return 0;
}

瓦尔格林德：

==6775== Command: ./a.out -g
==6775== 
==6775== Invalid read of size 8
==6775==    at 0x4F597B0: std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::size() const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
==6775==    by 0x401C2A: __gnu_cxx::__enable_if<std::__is_char<char>::__value, bool>::__type std::operator==<char>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (basic_string.h:4913)
==6775==    by 0x40177B: ledger::binsID(std::vector<ledger::company, std::allocator<ledger::company> >, unsigned int&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (main.cpp:66)
==6775==    by 0x40138B: ledger::NewCo(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (main.cpp:14)
==6775==    by 0x40109E: main (main.cpp:85)
==6775==  Address 0x2005ab5d68 is not stack'd, malloc'd or (recently) free'd
==6775== 
==6775== 
==6775== Process terminating with default action of signal 11 (SIGSEGV)
==6775==  Access not within mapped region at address 0x2005AB5D68
==6775==    at 0x4F597B0: std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::size() const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
==6775==    by 0x401C2A: __gnu_cxx::__enable_if<std::__is_char<char>::__value, bool>::__type std::operator==<char>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (basic_string.h:4913)
==6775==    by 0x40177B: ledger::binsID(std::vector<ledger::company, std::allocator<ledger::company> >, unsigned int&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (main.cpp:66)
==6775==    by 0x40138B: ledger::NewCo(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) (main.cpp:14)
==6775==    by 0x40109E: main (main.cpp:85)
==6775==  If you believe this happened as a result of a stack
==6775==  overflow in your program's main thread (unlikely but
==6775==  possible), you can try to increase the size of the
==6775==  main thread stack using the --main-stacksize= flag.
==6775==  The main thread stack size used in this run was 8388608.
==6775== 
==6775== HEAP SUMMARY:
==6775==     in use at exit: 72,896 bytes in 4 blocks
==6775==   total heap usage: 4 allocs, 0 frees, 72,896 bytes allocated
==6775== 
==6775== LEAK SUMMARY:
==6775==    definitely lost: 0 bytes in 0 blocks
==6775==    indirectly lost: 0 bytes in 0 blocks
==6775==      possibly lost: 0 bytes in 0 blocks
==6775==    still reachable: 72,896 bytes in 4 blocks
==6775==         suppressed: 0 bytes in 0 blocks
==6775== Rerun with --leak-check=full to see details of leaked memory
==6775== 
==6775== For counts of detected and suppressed errors, rerun with: -v
==6775== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

Answer 1

您需要检查 binsName() 和 binsID() 方法中的算法。

对于你的第二遍，声明：

end = mid - 1;

正在生成 -1 的 end 值（或者在本例中为 UINT_MAX，因为您使用的是无符号整数），因为 mid 的值是 0.

C ++ - 第二次二进制搜索的分段错误

C++ - segmentation fault on second binary search

c++

valgrind

vector