c++使用set对自定义类型数据去重(debug)

我的需求是有一个自定义类型Address，它有两个成员变量

//Address的成员变量
string name;
int number;

我想要使用一个set来存储各个Address，Address不能重复（要name和number都不相等才算不等）。由于address并没有大小排序，所以我只是想去重，没有排序的需求。

//存储各个Address，不能重复
set myset;

我一开始参考了c++中std::set自定义去重和排序函数中提到的，“只要你的比较方法能够满足对相等元素永远返回false就满足要求了”，在自定义类型Address 中重载了operator<。因为std::set默认调用的Compare是std::less，而less会调用结构体中的operator<来进行比较。

struct Address{
private:
	string name;
	int number;
public:
	Address() = default;
	Address(string n,int d):name(n),number(d){};
	bool operator< (const struct Address& addr) const{
		return (name

但是通过测试，发现set中有重复的Address，name和number都一样。

查看set中insert源码，它调用_M_insert_unique()，关键代码如下。可以看到它会根据insert_unique_pos()的返回值来判断是否要插入。

typedef pair _Res;
      pair<_Base_ptr, _Base_ptr> __res
	= _M_get_insert_unique_pos(_KeyOfValue()(__v));

      if (__res.second)
	{
	  _Alloc_node __an(*this);
	  return _Res(_M_insert_(__res.first, __res.second,
				 _GLIBCXX_FORWARD(_Arg, __v), __an),
		      true);
	}

      return _Res(iterator(__res.first), false);
    }

insert_unique_pos的关键代码如下，可以看到，要插入的节点__k先一直作为左操作数，与set中的节点进行比较（compare会调用自定义类中的operator<进行比较），并利用红黑树的性质找到应该插入的位置，所以并不会跟所有元素进行比较来去重，而是利用二分法来找到对应的位置（set中最小的比它大的节点）。如果有比它大的，判断该节点是否是set中最小的节点，如果是，将要插入的节点直接插入，否则–j作为要插入的位置。接着将要插入位置的当前节点与要插入的节点k进行比较，这时候是将k作为右操作数，如果还是返回false，说明两个值相等，就不插入，否则插入。

 typedef pair<_Base_ptr, _Base_ptr> _Res;
      _Link_type __x = _M_begin();
      _Base_ptr __y = _M_end();
      bool __comp = true;
      while (__x != 0)		//根据红黑树的性质，找到第一个key比它自己大的节点
	{
	  __y = __x;
	  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
	  __x = __comp ? _S_left(__x) : _S_right(__x);
	}
      iterator __j = iterator(__y);
      if (__comp)		//如果set中有比它大的
	{
	  if (__j == begin())		//如果比它大的是第一个节点，即set中最小的，则直接插入
	    return _Res(__x, __y);
	  else				//否则--j作为要插入的位置
	    --__j;
	}
	//与目前要插入位置的节点相比，并且是左右操作数互换比，如果还是false，说明相等，就不插入，如果是true，就插入
      if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
	return _Res(__x, __y);
      return _Res(__j._M_node, 0);
    }

总结分析：所以问题出在二分法的比较上，由于我的比较中，大小并没有确定，只有相等和不等，所以有可能比较时比较不到相等的那个节点，比如在跟最小的节点比较的时候，就判定要插入的值更小，就直接插入了，没有了后续的步骤，导致出错。所以查看STL文档，发现Compare要实现Strict Weak Ordering。

关于Strict Weak Ordering的具体介绍网上有很多，比如这个。

总而言之是要符合以下四条规则：

1. 对于集合S中的所有x，不存在x
2. 对于集合S中的所有x,y，当x
3. 多于集合S中所有的x,y,z，当x
4. 对于集合S中所有的x，y，z，当x和y不能比较，y与z不能比较时，x与z也不能比较

可以看到我的初始代码就是没有满足第二条规则，导致红黑树插入时出错。

修复很简单，就是不要对两个元素同时比较，而是先比较name，如果name小就更小，再比较number。虽然这个和我们的逻辑不同（因为我们的需求中只有相等和不等，没有大小），但是同样满足我们的需求。

bool operator< (const struct Address& addr) const{
    if (name

PS: 当然，对于我的需求，unordered_set更符合，使用hashtable存储元素，需要对自定义类型实现HashCode。但是这篇笔记是提供一个使用set的方法和思路，以及debug过程。