使用向量时分段故障(Segmentation Fault when using Vectors)

我试图从projecteuler.net解决问题http://projecteuler.net/problem=14

这就是问题：

以下迭代序列是为正整数的集合定义为：

Ñ→N / 2（n为偶数）N→3N + 1（n为奇数）

使用上面的规则，并与13日开始，我们生成顺序如下：

13→40→20→10→5→16→8→4→2→1可以看出，该序列（开始于13，在1精加工）包含10个术语。 虽然尚未证实（在Collat​​z问题），它被认为是所有的起始编号从1结束。

其起始号码，百万下，生产链最长？

注意：一旦开始链条的条款被允许去大于一百万。

我第一次使用递归的解决方案，但经过10万次这样的迭代有一个分段错误。 所以我做了一个迭代的解决方案希望可以解决这个问题。 分割故障发生在同一地点。 我看着堆栈跟踪，发现问题出现了，当值被添加到我的下方标示行矢量。 我以为载体将自动调整，所以我真搞不清楚这个问题。 谢谢你的帮助。 下面的代码：

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
 int ITERATIONS=100000;

int main()
{
vector<int> maxArray;
vector<int> newArray;
int max_size = 0;
int n = 2;
int collatz = n;
while(n <= ITERATIONS){

#Stack trace error# 
newArray.push_back(collatz);
#Stack trace error#

if(collatz == 1){
++n;
if(newArray.size() > max_size){
maxArray.clear();
for(vector<int>::const_iterator i = newArray.begin(); i < newArray.end(); ++i){
maxArray.push_back(*i);
}
max_size = newArray.size();
}
newArray.clear();
collatz = n;
}
else if(collatz%2 == 0)
collatz = collatz/2;
else
collatz = 3*collatz+1;
}
for(vector<int>::const_iterator i = maxArray.begin(); i < maxArray.end(); ++i){
cout << *i << " "; 
}
cout << "\n" << max_size;
}

堆栈跟踪：

#0  0x00132416 in __kernel_vsyscall ()
#1  0x002641df in raise () from /lib/i386-linux-gnu/libc.so.6
#2  0x00267825 in abort () from /lib/i386-linux-gnu/libc.so.6 #3  0x001e013d in __gnu_cxx::__verbose_terminate_handler() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6
#4  0x001dded3 in ?? () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#5  0x001ddf0f in std::terminate() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6
#6  0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#7  0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#8  0x08049362 in __gnu_cxx::new_allocator<int>::allocate (this=0xbffff214, 
__n=536870912) at /usr/include/c++/4.6/ext/new_allocator.h:92
#9  0x0804923c in std::_Vector_base<int, std::allocator<int> >::_M_allocate (
this=0xbffff214, __n=536870912)   at /usr/include/c++/4.6/bits/stl_vector.h:150
#10 0x08048e7f in std::vector<int, std::allocator<int> >::_M_insert_aux (
this=0xbffff214, __position=..., __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/vector.tcc:327
#11 0x08048bdd in std::vector<int, std::allocator<int> >::push_back (
this=0xbffff214, __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/stl_vector.h:834
#12 0x08048897 in main () at iterativeCollatz.cpp:16

Answer 1:

我们提出以下意见：

1. 单最小链只包含数字1其长度为1的。
2. 长链只能通过预先形成x到在任一个开始尾链x/2 （如果x为偶数）或3x+1 （如果x为奇数）。 长链的长度为1加上它的尾巴的长度。
3. 一旦链条开始的条款被允许去大于一百万。
4. 是不是真的需要负数来解决这个问题。
5. 没有链长度为0。

我们到达了以下结论：

1. 从观测1和2：一旦我们发现在开始一个链的长度x ，我们必须memoize的它。 这避免了重新计算尾巴的长度。 此外，我们可以解释的链长度为0 （默认情况下，构造导致std::size ）为“这个长度未被计算尚未”。
2. 从观察3：对于任何x > 1000000 ，如果我们最终需要计算在开始链的长度x ，没有什么可以保证我们会关注每一个链的长度在开始y使得x > y >= 1000000 。 因此，我们应该使用关联的数据结构（如std::map ），而不是std::vector ，用于存储memoized长度：
3. 从观测3和4：我们将用一个无符号整型尽可能地大。 如果不尽可能使用BIGNUM库（如GMP）去，我们想要的类型std::uint64_t 。
4. 从观察5：我们可以使用的0的链长值表示“这个链长度未被计算尚未”。 这是特别方便的，因为当使用C ++的关联容器默认构造一个值operator []与不在容器中存在的键，和一体式的默认构造的值被初始化为0。

将得到的程序，用C ++ 11个构建为了方便写入，是这样的：

#include <iostream>
#include <map>
#include <set>
#include <stack>

int main()
{
  typedef std::uint64_t num;

  // ys[x] is the length of the chain starting at x.
  // xms is the set of numbers that yield the longest chains.
  // ym is the length of the longest chain so far.
  std::map<num, num> ys = {{1,1}};
  std::set<num> xms = {1};
  num ym = 1;

  for (num i = 2; i < 1000000; ++i)
  {
    std::stack<num> xs;
    num x = i, y = ys[x];

    // Compute successive chain elements until
    // a base element is reached whose chain
    // length has already been memoized.
    while (!y)
    {
      xs.push(x);
      x = (x & 1) ? (3*x + 1) : (x/2);
      y = ys[x];
    }

    // The lengths of the newly computed elements
    // can be found by repeatedly incrementing
    // the base element's chain length.
    while (!xs.empty())
    {
      x = xs.top();
      ys[x] = ++y;
      xs.pop();
    }

    // Keep track of which number(s)
    // yield the longest chain(s).
    if (y >= ym)
    {
      if (y > ym)
      {
        xms.clear();
        ym = y;
      }
      xms.insert(x);
    }
  }

  for (num xm : xms)
    std::cout << xm << ' ';

  return 0;
}

Answer 2:

条件i < newArray.end()应该是i != newArray.end() 并且当然同样适用于i < maxArray.end()

Answer 3:

#6  0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6

这调用__cxa_throw表示C ++异常被抛出。

#5  0x001ddf0f in std::terminate() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6

该std::terminate函数立即退出应用程序。 这可能是由于以下几个原因：

1. 唯一的例外是在对象的析构函数被抛出而另一个异常被抛出。
2. 该程序没有一个try ... catch处理程序。

在这种情况下，选择2是最有可能的。 运行程序应该产生这样的：

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Program received signal SIGABRT, Aborted.

这给你的例外（的消息what输出）。

#7  0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6

该行表示分配内存（最有可能是在异常被触发std::bad_alloc ，这表明了内存不足）。

因此，我会检查你是不是分配运行内存不足的大载体。

注意：您可以添加自己的try...catch写类似的处理程序：

try
{
    // Your code here.
}
catch (const std::exception &e)
{
    std::cout << "Error: " << e.what() << std::endl;
}

所述vector实现将增加时，他们不再有任何房间中的向量的大小。 这通常是通过在空间加倍进行（2，4，8，16，...）。 这会变得非常大快，你有2个向量增长，以适应100000元。 同时还要注意不断增长的载体，它需要保持周围的旧数据复制到新的载体。

您可以使用reserve的方法maxArray和newArray循环之前设置所需的大小。 那是：

maxArray.reserve(ITERATIONS);
newArray.reserve(ITERATIONS);

这也将确保清洁性能作为载体不必增加内部数据数组中添加新的元素。

Answer 4:

我测试你的代码并没有SIGSEGV，也许你应该给出更多的信息。

这里是我的建议：

Vector类还具有一个成员函数调用容量（），也许你应该检查了这一点。

文章来源: Segmentation Fault when using Vectors