c++ - 为什么这个程序以 "unknown signal"终止？

Question

给定大小为 N 的输入集，以下代码旨在输出大小为 1、2、...、N 的组合。

#include <iostream>
#include <fstream>
#include <string>
#include <deque>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <exception>

template< typename V >
class Item
{
public:

  Item( const std::string& description,
        const V& value )
    : description_( description )
    , value_( value )
  {
  }

  std::string description() const { return description_; }

  V value() const { return value_; }

private:

  std::string description_;
  V value_;

friend std::ostream& operator<<( std::ostream& os, const Item& item )
{
  os << "{ \"" << item.description_ << "\", " << item.value_ << " }";
  return os;
}
};

template < typename T >
void addCombinationsN( const std::deque<T>& values,
                       std::deque<T>& interimResults,
                       size_t valuesStartIdx,
                       size_t n,
                       std::deque< std::deque<T> >& results )
{
  if ( valuesStartIdx >= values.size() ) { return; }
  if ( interimResults.size() >= n ) { return; }

  for ( int valuesIdx = valuesStartIdx;
        valuesIdx < values.size();
        ++valuesIdx )
  {
    interimResults.push_back( values[valuesIdx] );
    addCombinationsN( values, interimResults, valuesIdx+1, n, results );

    if ( interimResults.size() == n )
    {
      results.push_back( interimResults );
    }
    interimResults.pop_back();
  }
}

template < typename T >
std::deque< std::deque<T> > nChoose( const std::deque<T>& values )
{
  std::deque< std::deque<T> > retVal;
  std::deque<T> interimResults;

  std::cout << "adding all combinations from " << values.size() << " choices" << std::endl;

  for ( size_t n = 1; n <= values.size(); ++n )
  {
    std::cout << "# choices: " << n << std::endl;
    addCombinationsN < T > ( values, interimResults, 0, n, retVal );
  }
  std::cout << "done adding all choices" << std::endl;

  return retVal;
}

template< typename V >
class ItemDecCmp
{
public:
  bool operator()( std::deque< Item< V > >& a,
                   std::deque< Item< V > >& b ) const
  {
    return a.size() > b.size();
  }
};

template< typename V >
void populateChoices( std::deque< Item< V > >& items )
{
  for ( int i = 0; i < 28; ++i )
  {
    items.push_back( Item< V >( std::string( 1, '0' + i ), V(i) ) );
  }
}

int main( int argc, char* argv[] )
{
  std::deque< Item< double > > items;
  populateChoices<double>( items );

  std::deque< std::deque< Item< double > > > nChoices;
  nChoices = nChoose< Item< double > >( items );

  std::sort( nChoices.begin(), nChoices.end(), ItemDecCmp< double >() );
  std::cout << "done" << std::endl;

  for ( std::deque< std::deque< Item< double > > >::iterator i = nChoices.begin();
        i != nChoices.end();
        ++i )
  {
    for ( std::deque< Item< double > >::iterator j = i->begin();
          j != i->end();
          ++j )
    {
      std::cout << *j << " ";
    }
    std::cout << std::endl;
  }

  return 0;
}

该代码为输入容器(即调用 populateChoices() 的结果)生成预期结果，其中的元素略少于 30 个。然而，当输入容器包含更多元素时，它会没有段错误过早终止。

输入 3 个元素的示例输出:

$ g++ -g main.cpp && ./a.exe
adding all combinations from 3 choices
# choices: 1
# choices: 2
# choices: 3
done adding all choices
done
{ "0", 0 } { "1", 1 } { "2", 2 }
{ "0", 0 } { "1", 1 }
{ "0", 0 } { "2", 2 }
{ "1", 1 } { "2", 2 }
{ "0", 0 }
{ "1", 1 }
{ "2", 2 }

输入 28 个元素的示例输出:

$ g++ -g main.cpp && ./a.exe
adding all combinations from 28 choices
# choices: 1
# choices: 2
# choices: 3
# choices: 4
# choices: 5
# choices: 6
# choices: 7
# choices: 8
# choices: 9
# choices: 10
# choices: 11

我已尝试解决问题:

1) 我怀疑由于递归算法，我可能会遇到堆栈溢出(无双关语)。但是，增加堆栈大小并没有改变所描述的行为。

$ ulimit -a
core file size          (blocks, -c) unlimited
data seg size           (kbytes, -d) unlimited
file size               (blocks, -f) unlimited
open files                      (-n) 256
pipe size            (512 bytes, -p) 8
stack size              (kbytes, -s) 2032
cpu time               (seconds, -t) unlimited
max user processes              (-u) 256
virtual memory          (kbytes, -v) unlimited
$
$ ulimit -s 65536
$ ulimit -a
core file size          (blocks, -c) unlimited
data seg size           (kbytes, -d) unlimited
file size               (blocks, -f) unlimited
open files                      (-n) 256
pipe size            (512 bytes, -p) 8
stack size              (kbytes, -s) 65536
cpu time               (seconds, -t) unlimited
max user processes              (-u) 256
virtual memory          (kbytes, -v) unlimited
$ 

2) 这段代码最初使用的是std::vector 而不是std::deque；我怀疑我的问题可能与按需重新分配 std::vector 在后台进行有关。我将容器切换到 std::deque 是因为 push_back 和 pop_back 不会引起重新分配( this Q&A ，其中其他阅读)，但这也没有导致运行时行为发生任何变化。

3) 我通过 gdb 运行了可执行文件，但不知道它的堆栈跟踪告诉我什么:

(gdb) r
Starting program: /path/to/code/a.exe
[New Thread 11212.0x1884]
[New Thread 11212.0x18cc]
adding all combinations from 28 choices
# choices: 1
# choices: 2
# choices: 3
# choices: 4
# choices: 5
# choices: 6
[New Thread 11212.0x1eb4]
# choices: 7
# choices: 8
# choices: 9
# choices: 10
[New Thread 11212.0x2a5c]
[New Thread 11212.0xfa0]
# choices: 11
gdb: unknown target exception 0x20474343 at 0x7ffccb2754d8

Thread 1 "a" received signal ?, Unknown signal.
0x00007ffccb2754d8 in RaiseException () from /cygdrive/c/WINDOWS/System32/KERNELBASE.dll
(gdb) bt
#0  0x00007ffccb2754d8 in RaiseException () from /cygdrive/c/WINDOWS/System32/KERNELBASE.dll
#1  0x00000003e8ddcbf1 in cyggcc_s-seh-1!_Unwind_RaiseException () from /usr/bin/cyggcc_s-seh-1.dll
#2  0x00000003e8ddccc0 in cyggcc_s-seh-1!_Unwind_Resume_or_Rethrow () from /usr/bin/cyggcc_s-seh-1.dll
#3  0x00000003d0c57fcd in cygstdc++-6!.cxa_rethrow () from /usr/bin/cygstdc++-6.dll
#4  0x0000000100402ef7 in std::_Deque_base<Item<double>, std::allocator<Item<double> > >::_M_initialize_map (this=0x6fff5d6f7a0,
    __num_elements=11) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:707
#5  0x000000010040307a in std::_Deque_base<Item<double>, std::allocator<Item<double> > >::_Deque_base (this=0x6fff5d6f7a0, __a=...,
    __num_elements=11) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:500
#6  0x0000000100405209 in std::deque<Item<double>, std::allocator<Item<double> > >::deque (this=0x6fff5d6f7a0, __x=...)
    at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:949
#7  0x000000010040213f in __gnu_cxx::new_allocator<std::deque<Item<double>, std::allocator<Item<double> > > >::construct<std::deque<Item<double>, std::allocator<Item<double> > >, std::deque<Item<double>, std::allocator<Item<double> > > const&> (this=0xffffcb20,
    __p=0x6fff5d6f7a0, __args#0=...) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/ext/new_allocator.h:136
#8  0x0000000100404506 in std::allocator_traits<std::allocator<std::deque<Item<double>, std::allocator<Item<double> > > > >::construct<std::deque<Item<double>, std::allocator<Item<double> > >, std::deque<Item<double>, std::allocator<Item<double> > > const&> (__a=...,
    __p=0x6fff5d6f7a0, __args#0=...) at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/alloc_traits.h:475
#9  0x0000000100405b04 in std::deque<std::deque<Item<double>, std::allocator<Item<double> > >, std::allocator<std::deque<Item<double>, std::allocator<Item<double> > > > >::push_back (this=0xffffcb20, __x=...)
    at /usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/bits/stl_deque.h:1547
#10 0x0000000100401b08 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=20, n=11, results=...)
    at main.cpp:58
#11 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=17, n=11, results=...)
    at main.cpp:54
#12 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=15, n=11, results=...)
    at main.cpp:54
#13 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=12, n=11, results=...)
    at main.cpp:54
#14 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=10, n=11, results=...)
    at main.cpp:54
#15 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=9, n=11, results=...)
    at main.cpp:54
#16 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=6, n=11, results=...)
    at main.cpp:54
#17 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=5, n=11, results=...)
    at main.cpp:54
#18 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=4, n=11, results=...)
    at main.cpp:54
#19 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=2, n=11, results=...)
    at main.cpp:54
#20 0x0000000100401ae1 in addCombinationsN<Item<double> > (values=..., interimResults=..., valuesStartIdx=0, n=11, results=...)
    at main.cpp:54
#21 0x0000000100401c1f in nChoose<Item<double> > (values=...) at main.cpp:75
#22 0x00000001004010d7 in main (argc=1, argv=0xffffcc20) at main.cpp:108

问题:

有人可以帮助确定导致此程序崩溃的原因以及为什么它只是过早终止而不是可识别的信号，例如电动汽车？

次要但相关的问题:为什么 gdb 识别正在创建的多个线程 - 这是一个单线程应用程序。我也不知道“未知目标异常”是怎么回事。

环境

开发环境是 Windows 10 64 位 Intel PC 上的 cygwin:

$ uname -a
CYGWIN_NT-10.0 My-PC 2.11.2(0.329/5/3) 2018-11-08 14:34 x86_64 Cygwin

PS - 很抱歉提出“帮助我调试”的问题，但在这种情况下，因为我不知道如何理解 gdb 告诉我的内容，我真的在如何识别具体错误方面遇到了心理障碍。我在 Meta 上询问这个问题是否最适合在另一个 Stack Exchange 网站上出现，意见在此处和 Code Review 之间存在分歧。

Answer 1

根据堆栈跟踪，异常是在调用中抛出的

results.push_back( interimResults );

并且很可能是 std::bad_alloc 类型的异常，指示无法为 std::deque 的新元素分配内存，可能是因为没有有足够的内存可用。

因为 interimResults 总是从 pop_back 快速返回，所以它的大小不会很大。但是，results 会变得非常大，并且会耗尽所有可用内存。

您根本无法存储那么多数据。你需要释放你不需要的东西。