C++ - 推送到指向非POD的指针的优先级队列导致段错误？

Question

我正试图实现一个利用A *算法的4x4滑块拼图求解器。尽管试图尽可能以尽可能完整的方式进行编码，但是段错误会嵌入代码中，指向尝试将指针推向std::priority_queue实例失败。下面是完整的代码，然后我调试的尝试，我不知道如何将它切成工作的测试用例：

#include <iostream> 
#include <iomanip> 

#include <cstring> 
#include <cmath> 

#include <vector> 
#include <set> 
#include <queue> 

#include <functional> 

#include <ctime> 
#include <cstdlib> 

using namespace std; 

const char GOAL_STATE[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}; 

class Puzzle 
{ 
protected: 
    char puzzle[16]; 

    int index(char searched) const 
    { 
     for(int i=0; i<16; i++) 
     { 
      if (puzzle[i]==searched) 
       return i; 
     } 
     return -1; 
    } 

public: 

    Puzzle(const char init[16] = NULL) 
    { 
     if(init!=NULL) 
     { 
      memcpy(puzzle, init, sizeof(char)*16); 
     } 
     else 
     { 
      memcpy(puzzle, GOAL_STATE, sizeof(char)*16); 
     } 
    } 

    void show() const 
    { 
     for(int i=0; i<4; i++) 
     { 
      for(int j=0; j<4; j++) 
      { 
       cout << setw(3) << (int)puzzle[i*4+j] << " "; 
      } 
      cout << endl; 
     } 
    } 

    bool move(int m_pos) 
    { 
     int b_pos = index(0); 
     int b_x = b_pos/4; 
     int b_y = b_pos % 4; 
     int x = m_pos/4; 
     int y = m_pos % 4; 
     if (m_pos < 16 && (
        (x == b_x && (y == b_y + 1 || y == b_y - 1)) || 
        (y == b_y && (x == b_x + 1 || x == b_x - 1)) 
       ) 
      ) 
     { 
      char tmp = puzzle[m_pos]; 
      puzzle[m_pos] = puzzle[b_pos]; 
      puzzle[b_pos] = tmp; 
      return true; 
     } 
     else 
      return false; 
    } 

    int count_correct() const 
    { 
     int ret = 0; 
     for(int i=0; i<16; i++) 
      if ((i<15 && (puzzle[i])==i+1) || (i==15 && puzzle[i]==0)) 
       ret++; 
     return ret; 
    } 

    vector<int> possible_moves() const 
    { 
     vector<int> ret; 
     int b_pos = index(0); 
     int b_x = b_pos/4; 
     int b_y = b_pos % 4; 
     ret.push_back(b_y * 4 + b_x - 1); 
     ret.push_back((b_y - 1) * 4 + b_x); 
     if (b_x<3) 
      ret.push_back(b_y * 4 + b_x + 1); 
     if (b_y<3) 
      ret.push_back((b_y + 1) * 4 + b_x); 
     return ret; 
    } 

}; 

class AStarPuzzle : public Puzzle 
{ 
    int H; 
    int f; 

public: 

    int tried; 

    AStarPuzzle* previous; 

    AStarPuzzle(const char init[16] = NULL, 
      int _f = 0, int _tried = 0, AStarPuzzle* _previous = NULL) : Puzzle(init) 
    { 
     f = _f; 
     tried = _tried; 
     previous = _previous; 
    } 

    AStarPuzzle (const AStarPuzzle& old) : Puzzle(old.puzzle) 
    { 
     f = old.f; 
     tried = old.tried; 
     previous = old.previous; 
    } 

    double heur() const 
    { 
     double ret = 0.0; 
     for (int goalIndex = 0 ; goalIndex<16; goalIndex++) 
     { 
      int tileIndex = index(GOAL_STATE[goalIndex]); 
      ret += abs((double)((goalIndex % 4) - (tileIndex % 4))); 
      ret += abs(floor(goalIndex/4.0) - floor(tileIndex/4.0)); 

     } 

     return 0.1*f + max(ret, (double)count_correct()); 
    } 

    bool operator<(const AStarPuzzle& other) const 
    { 
     return heur()>other.heur(); 
    } 

    int get_f() 
    { 
     return f; 
    } 

    void increase_f() 
    { 
     f++; 
    } 

    AStarPuzzle operator=(const AStarPuzzle& rhs) 
    { 
     cout << "STUB: AStarPuzzle::operator=" << endl; 
    } 

    ~AStarPuzzle() 
    { 
     cout << "STUB: AStarPuzzle::~AStarPuzzle" << endl; 
    } 


    void operator delete(void *p) 
    { 
     cout << "Attempting to delete AStarPuzzle?" << endl; 
    } 

}; 


struct CompareHeuristics : public std::binary_function<AStarPuzzle*, AStarPuzzle*, bool > 
{ 
    bool operator()(AStarPuzzle* lhs, AStarPuzzle* rhs) const 
    { 
     return lhs->heur() > rhs->heur(); 
    } 
}; 

vector<int> retracePath(AStarPuzzle* c) 
{ 
    vector<int> ret; 
    while (c->previous!=NULL) 
    { 
     c = c->previous; 
     ret.push_back(c->tried); 
    } 
    return ret; 
} 

vector<int> aStar(AStarPuzzle* current) 
{ 
    set<AStarPuzzle*> openList; 
    set<AStarPuzzle*> closedList; 
    std::priority_queue<AStarPuzzle*, std::vector<AStarPuzzle*>, CompareHeuristics> openHeap; 

    int max_corr = 0; 
    int min_step = 0; 


    openList.insert(current); 
    openHeap.push(current); 
    while (openList.size()!=0) 
    { 
     current = openHeap.top(); 
     cout << "An iteration. heur()==" << current->heur() << endl; 
     current->show(); 
     openHeap.top(); 
     if (current->count_correct() == 16) 
     { 
      //return vector<int>(); 
      return retracePath(current); 
     } 
     openList.erase(current); 
     closedList.insert(current); 
     vector<int> directions = current->possible_moves(); 
     for(unsigned int i=0; i<directions.size(); i++) 
     { 
      AStarPuzzle* tile = new AStarPuzzle(*current); 
      tile->move(directions[i]); 
      tile->increase_f(); 

      if (closedList.count(tile)==0) 
      { 
       int corr = tile->count_correct(); 
       int f = tile->get_f(); 
       if (corr > max_corr or (corr == max_corr && f < min_step)) 
       { 
        max_corr = corr; 
        min_step = f; 
        cout << corr << "," << f << endl; 
       } 
       tile->previous = current; 
       if (openList.count(tile)==0) 
       { 
        openList.insert(tile); 
        openHeap.push(tile); 
       } 
      } 

     } 
    } 


    return vector<int>(); 
} 

int main(int argc, char **argv) { 

    char shuffled[16]; 
    memcpy(shuffled, GOAL_STATE, sizeof(char)*16); 
    srand(time(0)); 
    for (int i=0; i<16; i++) { 
     int r = i + (rand() % (16-i)); 
     char temp = shuffled[i]; 
     shuffled[i] = shuffled[r]; 
     shuffled[r] = temp; 
    } 

    shuffled = {0, 3, 7, 5, 9, 12 , 13 , 11, 8, 6 , 14, 4 , 15, 2 , 10 , 1 }; 

    AStarPuzzle* p = new AStarPuzzle(shuffled); 
    p->show(); 
    aStar(p); 

    return 0; 
} 

和gdb的输出：

> gdb ./si-proj2cpp 
GNU gdb (GDB) 7.0.1-debian 
Copyright (C) 2009 Free Software Foundation, Inc. 
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> 
This is free software: you are free to change and redistribute it. 
There is NO WARRANTY, to the extent permitted by law. Type "show copying" 
and "show warranty" for details. 
This GDB was configured as "i486-linux-gnu". 
For bug reporting instructions, please see: 
<http://www.gnu.org/software/gdb/bugs/>... 
Reading symbols from /home/d33tah/workspace/si-proj2cpp/Debug/si-proj2cpp...done. 
(gdb) r 
Starting program: /home/d33tah/workspace/si-proj2cpp/Debug/si-proj2cpp 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 

Program received signal SIGSEGV, Segmentation fault. 
0xb7dab5fc in _int_free (av=<value optimized out>, p=0x80502b0) at malloc.c:4957 
4957 malloc.c: No such file or directory. 
     in malloc.c 
Current language: auto 
The current source language is "auto; currently c". 
(gdb) bt 
#0 0xb7dab5fc in _int_free (av=<value optimized out>, p=0x80502b0) at malloc.c:4957 
#1 0xb7dae8ad in *__GI___libc_free (mem=0x80502b8) at malloc.c:3739 
#2 0xb7f86701 in operator delete(void*)() from /usr/lib/libstdc++.so.6 
#3 0x0804b97b in __gnu_cxx::new_allocator<AStarPuzzle*>::deallocate (this=0xbffff564, __p=0x80502b8) at /usr/include/c++/4.4/ext/new_allocator.h:95 
#4 0x0804ab4b in std::_Vector_base<AStarPuzzle*, std::allocator<AStarPuzzle*> >::_M_deallocate (this=0xbffff564, __p=0x80502b8, __n=16) 
    at /usr/include/c++/4.4/bits/stl_vector.h:146 
#5 0x0804b2a9 in std::vector<AStarPuzzle*, std::allocator<AStarPuzzle*> >::_M_insert_aux (this=0xbffff564, __position=..., __x=@0xbffff554) 
    at /usr/include/c++/4.4/bits/vector.tcc:361 
#6 0x0804a5cf in std::vector<AStarPuzzle*, std::allocator<AStarPuzzle*> >::push_back (this=0xbffff564, __x=@0xbffff554) at /usr/include/c++/4.4/bits/stl_vector.h:741 
#7 0x08049bbb in std::priority_queue<AStarPuzzle*, std::vector<AStarPuzzle*, std::allocator<AStarPuzzle*> >, CompareHeuristics>::push (this=0xbffff564, __x=@0xbffff554) 
    at /usr/include/c++/4.4/bits/stl_queue.h:511 
#8 0x08049054 in aStar (current=0x8050008) at ../main.cpp:248 
#9 0x08049273 in main (argc=1, argv=0xbffff704) at ../main.cpp:275 

正如有人建议，我用的valgrind看看会发生什么：

> valgrind ./si-proj2cpp 
==26655== Memcheck, a memory error detector 
==26655== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al. 
==26655== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info 
==26655== Command: ./si-proj2cpp 
==26655== 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
==26655== Invalid read of size 1 
==26655== at 0x804950E: Puzzle::move(int) (main.cpp:74) 
==26655== by 0x8048F3A: aStar(AStarPuzzle*) (main.cpp:231) 
==26655== by 0x8049272: main (main.cpp:275) 
==26655== Address 0x42ca1ef is 1 bytes before a block of size 32 alloc'd 
==26655== at 0x402471C: operator new(unsigned int) (vg_replace_malloc.c:255) 
==26655== by 0x8048EF6: aStar(AStarPuzzle*) (main.cpp:230) 
==26655== by 0x8049272: main (main.cpp:275) 
==26655== 
==26655== Invalid write of size 1 
==26655== at 0x8049525: Puzzle::move(int) (main.cpp:75) 
==26655== by 0x8048F3A: aStar(AStarPuzzle*) (main.cpp:231) 
==26655== by 0x8049272: main (main.cpp:275) 
==26655== Address 0x42ca1ef is 1 bytes before a block of size 32 alloc'd 
==26655== at 0x402471C: operator new(unsigned int) (vg_replace_malloc.c:255) 
==26655== by 0x8048EF6: aStar(AStarPuzzle*) (main.cpp:230) 
==26655== by 0x8049272: main (main.cpp:275) 
==26655== 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
An iteration. heur()==44 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
(...looks like an infinite loop, so I'm stopping the program with ctr+c) 
    0 3 7 5 
    9 12 13 11 
    8 6 14 4 
15 2 10 1 
^CAn iteration. heur()==44 
==26655== 
==26655== HEAP SUMMARY: 
==26655==  in use at exit: 17,076 bytes in 579 blocks 
==26655== total heap usage: 805 allocs, 226 frees, 21,156 bytes allocated 
==26655== 
==26655== LEAK SUMMARY: 
==26655== definitely lost: 0 bytes in 0 blocks 
==26655== indirectly lost: 0 bytes in 0 blocks 
==26655==  possibly lost: 0 bytes in 0 blocks 
==26655== still reachable: 17,076 bytes in 579 blocks 
==26655==   suppressed: 0 bytes in 0 blocks 
==26655== Rerun with --leak-check=full to see details of leaked memory 
==26655== 
==26655== For counts of detected and suppressed errors, rerun with: -v 
==26655== ERROR SUMMARY: 288 errors from 2 contexts (suppressed: 19 from 8) 

Answer 1

问题实际上与内存无关，正如@Synxis指出的那样，负面的m_pos被传递给Puzzle :: move。它发生的原因是possible_moves（）没有考虑0块在（0,0）时的情况 - 修复possible_moves有帮助。另一个bug与x和y有关，openHeap.top（）被调用两次而不是openHeap.top（），openHeap.pop（）。

Answer 2

你忘了返回AStarPuzzle::operator=的值。然后，Ideone does not report segfault，但超时。也许你应该在更进一步之前纠正无限循环...此外，您使用的int的Puzzle::move为m_pos，并且您没有检查负值。改为使用unsigned int。

编辑：在Visual C++ 2010上测试，没有段错误，无限循环。你应该检查你是否使用正确的运行时。

Answer 3

你有符号整数这里算术

vector<int> possible_moves() const 
{ 
    vector<int> ret; 
    int b_pos = index(0); 
    int b_x = b_pos/4; 
    int b_y = b_pos % 4; 
    ret.push_back(b_y * 4 + b_x - 1); 
    ret.push_back((b_y - 1) * 4 + b_x); 
    if (b_x<3) 
     ret.push_back(b_y * 4 + b_x + 1); 
    if (b_y<3) 
     ret.push_back((b_y + 1) * 4 + b_x); 
    return ret; 
} 

然后使用它作为地址：

vector<int> directions = current->possible_moves(); 
    for(unsigned int i=0; i<directions.size(); i++) 
    { 
     AStarPuzzle* tile = new AStarPuzzle(*current); 
     tile->move(directions[i]); // <<------ here, line 231 
     tile->increase_f(); 

与unsigned int小号替换您int指数，更改代码被编译器所要求，看怎么了。