递归时出现内存错误

Question

这是我的代码.该程序获得一些点坐标,它应该枚举所有路径(将来应该更复杂,但这是本质)

#include <iostream>
#include <utility>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
  Point () {};
  Point (const int &x_, const int &y_) : x{x_}, y{y_} {};
  int x, y;
};

double distance(const Point &a, const Point &b) {
  return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
struct Path {
  vector<Point> points;
  double length;
  Path(vector<Point> &p) : points{p}, length{0.0} {};
  void add_point(Point &p) {
    length += distance(p, points.back());
    points.push_back(p);
  }
};


vector<Path*> enumerate_paths(vector<Point> &coordinates) {
  // assuming coordinates is not empty
  vector<Path*> result;

  unsigned int size = coordinates.size();
  if (size == 1) {
    result = {new Path{coordinates}};
    return result;
  }

  vector<Point> coordinates_copy;
  vector<Path*> recursion_result;

  for(unsigned int i = 0; i < size; ++i) {
    cout << "cycle start" << endl << flush;
    coordinates_copy = coordinates;

    coordinates_copy.erase(coordinates.begin()+i);

    // Get results for one coordinate skipped
    recursion_result = enumerate_paths(coordinates_copy);
    cout << "recursion done" << endl << flush;
    // Add the coordinate to each of those results
    for_each(recursion_result.begin(), recursion_result.end(),
        [&](Path *path) {
          path->add_point(coordinates.at(i));});

    // Concatenate with previous results
    copy(recursion_result.begin(), recursion_result.end(), back_inserter(result));
    cout << "cycle end" << endl << flush;
  }
  cout << "escape recursion" << endl << flush;
  return result;
}

int main() {
  vector<Point> coordinates = { Point(0,0), Point(1,0), Point(0,1), Point(1,1)};
  auto paths = enumerate_paths(coordinates);
  cout << "done!" << flush;
}

我相信算法的想法是正确的,但是我得到了一个我不理解的内存错误 - 双重免费或损坏(out).我用g ++ -Wall -std = c ++ 11编译而没有错误.这里发生了什么？有人可以帮忙吗？

Answer 1

我不能保证你这是唯一的问题,但就在这里:

coordinates_copy.erase(coordinates.begin()+i);

您正在erase使用来自不同向量的迭代器.更改coordinates.begin()到coordinates_copy.begin().

还有,delete记忆你new;).或者更好的是,切换到智能指针.甚至完全忘记指针,依赖于vector移动构造函数和返回值优化.