Почему эта программа заканчивается «неизвестным сигналом»? - PullRequest
Новая
       13

Почему эта программа заканчивается «неизвестным сигналом»?

0 голосов
/ 01 января 2019

Следующий код предназначен для вывода комбинаций размером 1, 2, ..., N при заданном наборе входных данных размера 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 s и pop_back s не требуют перераспределения ( это 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

Вопрос :

Может ли кто-нибудь помочь определить, что вызывает сбой этой программы и почему она проявляется как преждевременное завершение, а не как идентифицируемый сигнал, например, SEGV?

Вторичные, но связанные вопросы: почему gdb идентифицирует несколькосоздаваемые потоки - это однопоточное приложение.Я также не знаю, что делать с «неизвестным целевым исключением».

Среда

Средой разработки является cygwin на Windows 10 64-битном ПК Intel: 

$ 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.

1 Ответ

0 голосов
/ 01 января 2019

Согласно трассировке стека, исключение выдается внутри вызова 

results.push_back( interimResults );

и, скорее всего, является исключением типа std::bad_alloc, указывающим, что память для нового элемента для std::deque не может бытьвыделено, вероятно, из-за того, что недостаточно памяти.

Поскольку interimResults всегда снова pop_back, то его размер будет не очень большим.Однако results станет очень большим и будет занимать всю доступную память.

Вы просто не можете хранить столько данных.Вам нужно освободить то, что вам не нужно.

...