尝试编写一个算法来对矩阵的对角线进行排序。我想纠正一个可以访问对角线的迭代器,然后利用 std::sort 执行排序,问题是,在某些测试用例中,std::sort 抛出异常,并且在添加日志后,似乎索引为负数执行运算符--这会导致无效的内存访问。我已尽力了解问题出在哪里,但是没有运气,希望能得到一些出色的帮助:)
以下是源代码:
class Solution {
public:
class Iterator
{
private:
std::vector<std::vector<int>> *data_;
int x_index_;
int y_index_;
public:
using difference_type = int;
using value_type = int;
using pointer = int*;
using reference = int&;
using iterator_category = std::random_access_iterator_tag;
Iterator(std::vector<std::vector<int>>* p, int x_index, int y_index): data_(p), x_index_(x_index), y_index_(y_index){}
Iterator(const Iterator& i): data_(i.data_), x_index_(i.x_index_), y_index_(i.y_index_){
}
friend bool operator==(const Iterator& lhs, const Iterator& rhs)
{
return lhs.x_index_ == rhs.x_index_ && lhs.y_index_ == rhs.y_index_;
}
friend bool operator!=(const Iterator& lhs, const Iterator& rhs)
{
return !(lhs == rhs);
}
reference operator*() const
{
return (*data_)[x_index_][y_index_];
}
pointer operator->() const
{
return &(*(*this));
}
reference operator[](int x) const
{
return (*data_)[x_index_ + x][y_index_+x];
}
Iterator& operator++()
{
x_index_++;
y_index_++;
return *this;
}
Iterator& operator--()
{
x_index_--;
y_index_--;
if(x_index_ < 0 || y_index_ < 0)
{
std::cout << "jjjjj:" << x_index_ << ":" << y_index_ << std::endl;
throw "sdfsdf";
}
return *this;
}
Iterator& operator+=(int x)
{
x_index_ += x;
y_index_ += x;
return *this;
}
Iterator& operator-=(int x)
{
x_index_ -= x;
y_index_ -= x;
return *this;
}
Iterator operator+(int x)
{
Iterator tmp(*this);
tmp += x;
return tmp;
}
Iterator operator-(int x)
{
Iterator tmp(*this);
tmp -= x;
return tmp;
}
friend Iterator operator+(const Iterator& lhs, int x)
{
Iterator tmp(lhs);
return tmp += x;
}
friend Iterator operator+(int x, const Iterator& rhs)
{
Iterator tmp(rhs);
return tmp += x;
}
friend Iterator operator+(const Iterator& lhs, const Iterator& rhs)
{
Iterator tmp(lhs);
tmp.x_index_ += rhs.x_index_;
tmp.y_index_ += rhs.y_index_;
return tmp;
}
difference_type operator-(const Iterator& i)
{
return x_index_ - i.x_index_ ;
}
friend Iterator operator-(const Iterator& lhs, int x)
{
Iterator tmp(lhs);
return tmp -= x;
}
friend bool operator<(const Iterator& lhs, const Iterator& rhs)
{
if(rhs.x_index_ >= (*rhs.data_).size() || rhs.y_index_ >= (*rhs.data_)[0].size())
{
return lhs.x_index_ < rhs.x_index_;
}
return (*lhs) < (*rhs);
}
friend bool operator>(const Iterator& lhs, const Iterator& rhs)
{
if(rhs.x_index_ >= (*rhs.data_).size() || rhs.y_index_ >= (*rhs.data_)[0].size())
{
return lhs.x_index_ > rhs.x_index_;
}
return (*lhs) > (*rhs);
}
friend bool operator>=(const Iterator& lhs, const Iterator& rhs)
{
return !(lhs < rhs);
}
friend bool operator<=(const Iterator& lhs, const Iterator& rhs)
{
return !(lhs > rhs);
}
Iterator operator++(int)
{
Iterator tmp(*this);
++(*this);
return tmp;
}
Iterator operator--(int)
{
Iterator tmp(*this);
--(*this);
return tmp;
}
};
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
for(int i = 0; i < mat[0].size(); ++i)
{
Iterator begin(&mat, 0, i);
int step = std::min(mat.size(), mat[0].size()-i);
Iterator end(&mat, step, i+step);
std::sort(begin, end);
}
for(int i = 1; i < mat.size(); ++i)
{
Iterator begin(&mat, i, 0);
int step = std::min(mat.size() - i, mat[0].size());
Iterator end(&mat, i+step, step);
std::sort(begin, end);
}
return mat;
}
};
在函数Iterator&operator--()中添加了调试日志,似乎索引变为负数,然后导致无效的内存访问。
我想获得有关为什么会发生这种情况的帮助,因为我没有发现迭代器实现有任何问题
问题已解决。我犯了一个愚蠢的错误,受到@PaulMcKenzie 评论的启发,我发现我实现了运算符“">”和“<" incorrectly. The crash get fixed after change it to: return lhs.x_index_ < rhs.x_index_;
顺便说一句,现在的政策很奇怪,代码的帖子被屏蔽了:(