set和multiset

set有去重；multiset无去重。

multiset可以用来做计时器容器，因为计时器需要按时间排序，而时间戳可能会出现相同的，即同一时刻添加了2个定时任务。

使用set和multiset的易错点：

• 存储的元素需要是const含义的，即添加到容器后，原则上是不能修改的。原因是排序需要。如果添加到容器后用户还能修改容器元素，那么应触发某种全排序，否则容器有序性就丢失了。
• 然而容器没有办法保证用户不可修改元素，所以容易用错。

这个易错点，只能好好记住了，不然迟早酿成bug。如果一定要在添加元素后，对这个元素做修改，那么需要先erase然后再insert回去。

另外的问题是，容器和智能指针结合使用时的易错点。

当元素为shared_ptr包装的类实例时，直接放进(multi)set就有2个潜在问题，一是容器排序的依据是shared_ptr，而不是T，这是很容易误解的，解决这个问题的办法是声明容器时添加一个Comparator参数，例如：

struct TimeEvent
{
    long long id;
    long sec;
    long ms;
    bool operator<(const TimeEvent &rhs) const;
};

struct Compare
{
    bool operator()(const TimeEvent &a, const TimeEvent &b)
    {
        return *a < *b;
    }
};

typedef std::multiset<std::shared_ptr<TimeEvent>, Compare> my_set;

这样子写才会真正地按照T的定义去排序。

然而还有个细节问题：用于容器的Compare或者说operator<，必须满足strict weak ordering。这个概念会贯穿整个STL。

这个东西简单理解就是说，类T必须实现operator<，从而容器sort元素的时候，可以用这个operator<实现==、>比较。

为什么一个<就能实现==呢？这是用了一个有趣的技巧： a==b 可认为等价于 !(a < b) && !(b < a)。

对于只有单个属性的T来说，实现strict weak ordering很简单，只要operator<里写一行a.x < a.x就行了。

对于一个有复合属性的类T，operator<需要小心一点，但也是大同小异。例如：

bool TimeEvent::operator<(const TimeEvent &rhs) const
{
    if (sec == rhs.sec)
    {
        return ms < rhs.ms;
    }
    return sec < rhs.sec;
}

逆序排序的话，<的结果取反即可。所以总之遇到(multi)set排序，重载operator<就对了。