map中结构体做关键字的注意事项

时间:2022-09-30 13:58:56

序:
今天做一道题,由于递归函数比较恶心,如果用记忆化搜索,数据范围极大却又用不全(二维数组存的话直接炸)。所以决定干脆使用stl::map存储(反正有O2优化),但是执行insert的时候,编译器却莫名其妙的报错,跳到stl的某个库之中。一脸懵逼,弄了半天才搞明白原因。


结构体像这样:

struct qi{
    int x, y;
    qi(){}
    qi(int a, int b):
        x(a), y(b){}
};
map<qi, long long> kongse;

插入语句是这样的:

if(a > b) kongse.insert(map<qi, long long>::value_type(m, f(a-b,b+b)+1));
    else kongse.insert(map<qi, long long>::value_type(m, f(a+a,b-a)+1));

编译器报错了,跳到了这里:

/// One of the @link comparison_functors comparison functors@endlink.
  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

这是一个名为“stl_function.h"的库,看来是专门实现各种函数的库。
仔细看这里:

{ return __x < __y; }

它返回了一个bool类型的值,是通过 '<'实现的。看到这里问题应该就很清楚了:我们的结构体根本就没有定义<,如何能够比较
再回想map是什么,红黑树,是实现内部排序的容器,这也就不足为怪了。
所以解决方法很简单,随意定义一个bool operator < (const & ..) const即可。
如:

bool operator < (const qi &a)const
{
    return x < a.x;
} 

如此问题就解决了。
箜瑟_qi 2017.05.07 19:37