将结构向量插入集合时出现错误 2676 和 2784（...无法推断...的模板参数）

Question

当我尝试运行我的程序（在 VS 中）时出现以下构建错误：

Error   10  error C2676: binary '<' : 'const move' does not define this operator or a conversion to a type acceptable to the predefined operator
Error   4   error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'const move'
Error   8   error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'const move'
Error   1   error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const move'
Error   3   error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const move'
Error   5   error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const move'
Error   6   error C2784: 'bool std::operator <(const std::move_iterator<_RanIt> &,const std::move_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::move_iterator<_RanIt> &' from 'const move'
Error   9   error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'const move'
Error   7   error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'const move'
Error   2   error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const move'

我不知道它们为什么会发生，因为我没有在我的 move 结构中定义任何运算符（见下文），我的代码部分也没有任何运算符导致它。

它们似乎是由这个函数（从未调用）引起的：

std::set<solution> solve(grid board, solution prev) {
    std::set<solution> ret = {};
    ret.insert(prev);    
    return ret;
}

我上面用的typedefs/structs：

struct move {
public:
    move(unsigned startX, unsigned startY, unsigned endX, unsigned endY) {
        x0 = startX;
        y0 = startY;
        x1 = endX;
        y1 = endY;
    }
    unsigned x0 : 4, y0 : 4, x1 : 4, y1 : 4;
};

typedef std::vector<std::vector<__int8>> grid;
typedef std::pair<__int8, __int8> point;
typedef std::vector<move> solution;

谁能告诉我为什么会这样，我能做些什么来解决这个问题？

提前致谢！

Answer 1

std::set 默认情况下使用比较运算符 < 在内部创建二叉树，这就是您收到问题中指定的错误的原因。所以 std::set 必须在内部为其所有元素保持顺序。所以每次我们插入时，它都会使用比较运算符检查现有元素中新元素的顺序，并相应地定位它。

在插入 std::set 之前，您必须在 struct move 中如下定义运算符 <。我希望你可以使用 http://en.wikipedia.org/wiki/Euclidean_distance

进行比较

bool move::operator <(struct move & rhs)
{
  return (  sqrt( (this->x1-this->x0)* (this->x1-this->x0) +
                  (this->y1-this->y0) * (this->y1-this->y0) ) <
           sqrt( (rhs.x1-rhs.x0)* (rhs.x1-rhs.x0) +
                  (rhs.y1-rhs.y0) * (rhs.y1-rhs.y0) ) );

}

如果您希望保留自定义比较来代替 <，您可以按如下方式进行。定义比较运算符 'customcompare` 并定义 std::set 如下：

std::set<std::vector<move>,customcompare> ret;

Answer 2

Steephen 的回答中还有两点不合适。第一个主要是正式的，std::set 默认使用 std::less，而不是 operator<。不过，这仅在 cornercases 中很重要，因为 std::less 默认使用 operator<。但是有一个不同的问题，值得不同的答案，因为我无法在评论中正确格式化代码。

将自定义比较器作为第二个模板参数传递给 std::set 时，您必须确保它定义了严格弱排序。这意味着比较器 cmp 必须满足某些要求。特别是 cmp(a, a) = false 和 cmp(a, b) -> not cmp(b, a)，集合使用它们（但也例如 std::map）来确定相等性。如果 cmp(a, b) = false 和 cmp(b, a) = false ("neither is less than the other")，它将把这两个值视为相等。

关于您拥有的向量，一个建议是使用欧氏距离。 (3, 0) 和 (0, 4) 之间的欧氏距离是 5，(0, 3) 和 (4, 0)、(0, 0) 和 (-5, 0) 之间的欧几里得距离也是如此。这意味着不同的向量将被视为相等，这可能不是您想要的。

根据经验，字典顺序排序是一个很好的默认值。为了实现它，您只需将操作数拆分为元组，以便可以对每个元组值进行数值比较。然后实现如下所示：

bool compare_move(move const& m1, move const& m2)
{
    if (m1.x0 != m2.x0) return m1.x0 < m2.x0;
    if (m1.y0 != m2.y0) return m1.y0 < m2.y0;
    if (m1.x1 != m2.x1) return m1.x1 < m2.x1;
    return m1.y1 < m2.y1;
}

这还有一个优点，就是它不使用浮点数学。使用只有 4 位的位域这一事实可以稍微改进一下，因此每次移动仅占用 16 位数据。如果您通过移位和或运算将它们组合成一个整数值，您会得到相同的结果，但我不确定这种微优化是否值得。

将结构向量插入集合时出现错误 2676 和 2784（...无法推断...的模板参数）

Errors 2676 and 2784 (...could not deduce template argument for...) when inserting vector of structs into set

c++

struct

vector

operators