Polynomial模板类非const operator[]实现的断言错误排查

需求背景 #

我需要为已创建的Polynomial模板类实现非const版本的operator[]，满足以下要求：

• 允许设置指定次数项的系数
• 允许读取指定次数项的系数（例如int cv = p[4];可正常运行）
• 多项式度数不变时，操作时间复杂度为O(1)
• 未执行赋值操作时，不改变多项式度数

最后一条要求可通过如下测试验证：

Polynomial<int> p;
p[2] = 1;
ASSERT_EQUAL(p.Degree(), 2);
int x = p[5];
ASSERT_EQUAL(x, 0);
ASSERT_EQUAL(p.Degree(), 2);  // 未对p[5]赋值，多项式度数不变

实现代码 #

#include "test_runner.h"
#include "profile.h"

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

template<typename T>
class Polynomial {
private:
  std::vector<T> coeffs_ = {0};

  void Shrink() {
    while (coeffs_.size() > 1 && coeffs_.back() == 0) {
      coeffs_.pop_back();
    }
  }

public:
  Polynomial() = default;
  Polynomial(std::vector<T> coeffs) : coeffs_(std::move(coeffs)) {
    Shrink();
  }

  template<typename Iterator>
  Polynomial(Iterator first, Iterator last) : coeffs_(first, last) {
    Shrink();
  }

  bool operator ==(const Polynomial& other) const {
    return coeffs_ == other.coeffs_;
  }

  bool operator !=(const Polynomial& other) const {
    return !operator==(other);
  }

  int Degree() const {
    return coeffs_.size() - 1;
  }

  Polynomial& operator +=(const Polynomial& r) {
    if (r.coeffs_.size() > coeffs_.size()) {
      coeffs_.resize(r.coeffs_.size());
    }
    for (size_t i = 0; i != r.coeffs_.size(); ++i) {
      coeffs_[i] += r.coeffs_[i];
    }
    Shrink();
    return *this;
  }

  Polynomial& operator -=(const Polynomial& r) {
    if (r.coeffs_.size() > coeffs_.size()) {
      coeffs_.resize(r.coeffs_.size());
    }
    for (size_t i = 0; i != r.coeffs_.size(); ++i) {
      coeffs_[i] -= r.coeffs_[i];
    }
    Shrink();
    return *this;
  }


  class IndexProxy {
  public:
    IndexProxy(Polynomial& poly, size_t degree) : poly_(poly), degree_(degree) {}
    T& operator =(const T& value) {
      if (degree_ >= poly_.coeffs_.size() && value == 0) {
        static T zero = T(0);
        return zero;
      } else if (degree_ >= poly_.coeffs_.size() && value != 0) {
        poly_.coeffs_.resize(degree_ + 1);
      }

      poly_.coeffs_[degree_] = value;
      return poly_.coeffs_[degree_];
    }


    bool operator ==(const T& other) const {
        return poly_.coeffs_[degree_] == other;
    }
    bool operator !=(const T& other) const {
        return poly_.coeffs_[degree_] != other;
    }

    std::ostream& operator<<(std::ostream& out) const {
        return out << poly_.coeffs_[degree_];
    }



    operator T() const {
      return std::as_const(poly_)[degree_];
    }
    
    private:
      Polynomial& poly_;
      size_t degree_;
  };



  T operator [](size_t degree) const {
    return degree < coeffs_.size() ? coeffs_[degree] : 0;
  }

  IndexProxy operator [](size_t degree) {
    return IndexProxy(*this, degree);
  }


  T operator ()(const T& x) const {
    T res = 0;
    for (auto it = coeffs_.rbegin(); it != coeffs_.rend(); ++it) {
      res *= x;
      res += *it;
    }
    return res;
  }
};

错误现象 #

测试时出现断言错误，测试代码如下：

for (size_t i = 10; i < 50000; ++i) {
      ASSERT_EQUAL(poly[i], 0); // 此处触发断言
      ASSERT_EQUAL(poly.Degree(), 5);
    }

错误提示：TestNonconstAccess fail: Assertion failed: 0 != 0 hint: poly[i] != 0，疑似存在未定义行为，请问我遗漏了什么？

问题分析与修复 #

问题出在IndexProxy类的比较运算符和输出运算符上：当访问的次数degree_大于等于多项式系数向量coeffs_的长度时，直接访问poly_.coeffs_[degree_]属于越界访问，这是C++中的未定义行为，会读取内存中的随机值，导致比较结果不符合预期。

修复方案 #

修改IndexProxy的相关方法，复用已有的正确逻辑处理超出范围的情况：

class IndexProxy {
public:
    // ... 其他代码保持不变 ...

    bool operator ==(const T& other) const {
        // 复用operator T()的逻辑，正确处理超出范围的情况
        return static_cast<T>(*this) == other;
    }
    bool operator !=(const T& other) const {
        return !(*this == other);
    }

    std::ostream& operator<<(std::ostream& out) const {
        // 同样复用operator T()的逻辑
        return out << static_cast<T>(*this);
    }

    // ... 其他代码保持不变 ...
};

或者直接在方法内实现正确的边界判断：

bool operator ==(const T& other) const {
    const T val = (degree_ < poly_.coeffs_.size()) ? poly_.coeffs_[degree_] : T(0);
    return val == other;
}
bool operator !=(const T& other) const {
    return !(*this == other);
}

std::ostream& operator<<(std::ostream& out) const {
    const T val = (degree_ < poly_.coeffs_.size()) ? poly_.coeffs_[degree_] : T(0);
    return out << val;
}

原理说明 #

当执行ASSERT_EQUAL(poly[i], 0)时，poly[i]返回IndexProxy对象，断言函数会调用IndexProxy的operator==与0比较。修复后的代码会正确判断次数是否超出当前系数向量的范围，超出时返回0，避免了越界访问，从而保证比较结果正确。

内容的提问来源于stack exchange，提问作者Daniil Yefimov