std::vector 超出最小堆范围：C++

Question

我有一段时间没有处理这段代码（或任何其他编码项目），所以虽然我知道代码基本上有什么问题，但我一直很难找到矢量的确切位置超出范围。我整个上午都在运行 gdb 上研究它，但无济于事。我正在尝试用 C++ 中的向量 "theData" 创建一个最小堆。

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;
using std::cin;
using std::cout;
using std::swap;
using std::pair;
using std::make_pair;

class HeapBuilder {
     private:
        vector<int> data_;
        vector< pair<int, int> > swaps_;

 void WriteResponse() const {
      cout << swaps_.size() << "\n";
for (int i = 0; i < swaps_.size(); ++i) {
  cout << swaps_[i].first << " " << swaps_[i].second << "\n";
       }
}

 void ReadData() {
        int n;
        cin >> n;
        data_.resize(n);
        for(int i = 0; i < n; ++i)
         cin >> data_[i];
}

  void makeMinHeap(vector<int> &theData, int i, int n) {
    int minIndex;
    int left = 2*i;
    int right = 2*i + 1;
      if (left < n && theData.at(left) < theData.at(i)) {
        minIndex = left;
    }
    else if (right < n && theData.at(right) < theData.at(i)) {
        minIndex = right;
    }

if (minIndex != i) {
    swap(theData.at(i), theData.at(minIndex));
    swaps_.push_back(make_pair(i, minIndex));
    makeMinHeap(theData, minIndex, n);
    }
}

  void GenerateSwaps() {
    swaps_.clear();
    int size = data_.size();
    for (int i = (size/2); i >= 0; i--) {
    makeMinHeap(data_, i, size);
     }

  }

 public:
  void Solve() {
     ReadData();
     GenerateSwaps();
     WriteResponse();
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  HeapBuilder heap_builder;
  heap_builder.Solve();
  return 0;
}

Answer 1

您没有检查 minIndex。看看当你的 left<=n 和 right <=n 都失败时会发生什么，很可能是在整个递归即将停止时，因为你只是检查

 minIndex != i
// ^-- default each time is garbage which in case last>n && right>n leaves it garbage
// hence when it comes to
if(minIndex!=i){
// It's actually true where it was suppose to break out n thus throws out_of_range
}

快速简单的解决方案是添加一个标志检查

bool flagcheck = false;
if(){ flagcheck = true; }
else if(){ flagcheck = true; }
if(minIndex!=i && flagcheck){}

std::vector 超出最小堆范围：C++

std::vector out of range for min-heap: C++

c++

algorithm

heap

vector

outofrangeexception