由 constom 函数引起的运行时错误

Question

我在尝试完成 tsp 问题的 A* 算法时遇到了一些运行时错误。该程序不想到达 main 函数。这是我的代码，它很长。

#include <cmath>
#include <iostream>
#include <memory>
#include <queue>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;
constexpr const size_t R = 200; // Max Vertex number
pair<double, double> coordinate[ R ]{{1, 1}, {2, 2}, {1, 2}, {0, 0}};
// Index Min Priority Queue for double
class IndexMinPQ {
private:
    const size_t maxN;
    size_t n;
    size_t *pq, *qp;
    double* elem;
    void exch(size_t i, size_t j) {
        swap(pq[ i ], pq[ j ]);
        swap(qp[ pq[ i ] ], qp[ pq[ j ] ]);
    }
    void swim(size_t k) {
        while (k > 1 && elem[ pq[ k / 2 ] ] > elem[ pq[ k ] ]) {
            exch(k, k / 2);
            k = k / 2;
        }
    }
    void sink(size_t k) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && elem[ pq[ j ] ] > elem[ pq[ j + 1 ] ]) ++j;
            if (elem[ pq[ k ] ] <= elem[ pq[ j ] ]) break;
            exch(k, j);
            k = j;
        }
    }
    inline void validateIndex(size_t i) const {
        if (i >= maxN) throw invalid_argument("index >= capacity: " + to_string(i));
    }
public:
    IndexMinPQ(size_t maxN)
        : maxN(maxN), n(0), pq(new size_t[ maxN + 1 ]), qp(new size_t[ maxN + 1 ]),
          elem(new double[ maxN + 1 ]) {
        for (size_t i = 0; i <= maxN; ++i)
            qp[ i ] = 0;
    }
    IndexMinPQ(const IndexMinPQ& orig)
        : maxN(orig.maxN), n(orig.n), pq(new size_t[ maxN + 1 ]),
          qp(new size_t[ maxN + 1 ]), elem(new double[ maxN + 1 ]) {
        copy(orig.pq, orig.pq + n + 1, pq);
        copy(orig.qp, orig.qp + n + 1, qp);
        copy(orig.elem, orig.elem + n + 1, elem);
    }
    IndexMinPQ& operator=(const IndexMinPQ&) = delete;
    ~IndexMinPQ() {
        delete[] pq;
        delete[] qp;
        delete[] elem;
    }
    void insert(size_t i, double val) {
        validateIndex(i);
        if (n == maxN) throw overflow_error("priority queue is full");
        if (contains(i)) throw invalid_argument("index is already in the priority queue");
        ++n;
        qp[ i ] = n;
        elem[ i ] = val;
        pq[ n ] = i;
        swim(n);
    }
    bool contains(int i) const {
        validateIndex(i);
        return qp[ i ] != 0;
    }
    void delElem(size_t i) {
        validateIndex(i);
        if (!contains(i)) {
            // throw invalid_argument("index is not in the priority queue");
            return;
        }
        int index = qp[ i ];
        exch(index, n--);
        swim(index);
        sink(index);
        elem[ i ] = 0.0;
        qp[ i ] = 0;
    }
    size_t size() const { return n; }
    double minElem() const {
        if (n == 0) throw underflow_error("priority queue is empty");
        return elem[ pq[ 1 ] ];
    }
};
// Weighted Edge
class Edge {
private:
    const size_t no;
    const size_t v;
    const size_t w;
    const double wei;

public:
    Edge(size_t No, size_t v, size_t w, double weight)
        : no(No), v(v), w(w), wei(weight) {}
    double weight() const { return this->wei; }
    size_t No() const { return no; }
    size_t either() const { return v; }
    size_t other(int vertex) const {
        if (vertex == v)
            return w;
        else if (vertex == w)
            return v;
        else
            throw invalid_argument("Inconsistent edge");
    }
};
class Graph {
private:
    const size_t V; // number of Vertexs
    const size_t E; // number of Edges=V*(V-1)/2
    Edge* edges; // All Edges
    vector<size_t>* Adj; // adjcent table
public:
    Graph(size_t V) : V(V), E(V * (V - 1) / 2), Adj(new vector<size_t>[ V ]) {
        allocator<Edge> alloc; // detach memory allocating and item constructing
        edges = alloc.allocate(E);
        size_t cnt = 0;
        for (size_t i = 0; i < V - 1; ++i)
            for (size_t j = i + 1; j < V; ++j) {
                double dx = coordinate[ i ].first - coordinate[ j ].first,
                       dy = coordinate[ i ].second - coordinate[ j ].second;
                // Euclid distance between two Vertexs
                alloc.construct(edges + cnt, cnt, i, j, sqrt(dx * dx + dy * dy));
                cnt++;
            }
        // construct adjcent table
        for (size_t i = 0; i < E; ++i) {
            size_t v = edges[ i ].either(), w = edges[ i ].other(v);
            Adj[ v ].push_back(i);
            Adj[ w ].push_back(i);
        }
    }
    ~Graph() {
        delete[] Adj;
        allocator<Edge> alloc;
        for (size_t i = 0; i < E; ++i)
            alloc.destroy(edges + i);
        alloc.deallocate(edges, E);
    }
    inline size_t sizeV() const { return V; }
    inline size_t sizeE() const { return E; }
    inline const Edge& getEdge(size_t e) const {
        if (e >= E)
            throw invalid_argument("index >= edges: V * (V - 1) / 2 =" + to_string(E));
        return edges[ e ];
    }
    inline const vector<size_t>& adj(size_t v) const {
        if (v >= V) throw invalid_argument("index >= vetexs: " + to_string(V));
        return Adj[ v ];
    }
};
struct Aux {
    const Graph& G;
    vector<size_t> path;
    bool* marked;
    IndexMinPQ pq;
    double dist;
    double evaluate;
    Aux(const Graph& G)
        : G(G), marked(new bool[ G.sizeV() ]), pq(G.sizeE()), dist(0), evaluate(0) {
        for (size_t i = 1; i < G.sizeV(); ++i)
            marked[ i ] = false;
        marked[ 0 ] = true;
        path.push_back(0);
        for (size_t i = G.sizeV() - 1; i < G.sizeE(); ++i)
            pq.insert(i, G.getEdge(i).weight());
    }
    ~Aux() { delete[] marked; }
    Aux(const Aux&) = delete;
    Aux& operator=(const Aux&) = delete;
    Aux(const Aux& orgi, const Edge& e)
        : G(orgi.G), marked(new bool[ G.sizeV() ]), pq(orgi.pq), dist(orgi.dist) {
        copy(orgi.marked, orgi.marked + G.sizeV(), marked);
        size_t v = path.back(), w = e.other(v);
        if (marked[ w ]) throw invalid_argument("already in path");
        dist += e.weight();
        evaluate = dist + (G.sizeV() - path.size() + 1) * pq.minElem();
        for (const size_t& e : G.adj(w))
            pq.delElem(e);
    }
};
vector<size_t> AStar(const Graph& G) {
    auto cmp = [](Aux* lhs, Aux* rhs) -> bool { return lhs->evaluate > rhs->evaluate; };
    priority_queue<Aux*, vector<Aux*>, decltype(cmp)> pq(cmp);
    Aux* t = new Aux(G);
    pq.push(t);
    while (true) {
        Aux* a = pq.top();
        pq.pop();
        if (a->path.size() == G.sizeV()) return a->path;
        size_t v = a->path.back();
        for (size_t ind : G.adj(v)) {
            const Edge& e = G.getEdge(ind);
            size_t w = e.other(v);
            if (!a->marked[ w ]) {
                Aux* t2 = new Aux(*a, e);
                pq.push(t2);
            }
        }
        delete a;
    }
    // throw runtime_error("impossible to reach");
    return vector<size_t>();
}
int main() {
    // AStar(Graph(4));
    system("pause");
    return 0;
}

编译器什么也没说。然而，它不会转到 main 函数并在屏幕上闪烁。我试图设置断点，但它没有命中，gdb 说的是：

(gdb) r
Starting program: D:\cs\c++\exercise\source3.exe
[New Thread 8152.0x1aec]
[New Thread 8152.0x3254]
[New Thread 8152.0x1740]
[New Thread 8152.0x288]
Mingw-w64 runtime failure:
  Unknown pseudo relocation protocol version 256.
[Thread 8152.0x3254 exited with code 3]
[Thread 8152.0x1740 exited with code 3]
[Thread 8152.0x288 exited with code 3]
[Inferior 1 (process 8152) exited with code 03]

然而，在我注释掉函数AStar（第191-213行）之后，问题就消失了。有什么问题？

Answer 1

您在空向量上调用 back()。但是在发帖之前请使用（好的）调试器！ GDB很好，但不是很好用...

size_t v = a->path.back();

由 constom 函数引起的运行时错误

runtime error caused by a constom function

c++

gdb

runtime-error