c++ - 维护 std::multiset 中相等元素的插入顺序

Question

我有一个 std::multiset 排序的自定义对象。多重集中的两个相等对象(基于 < 运算符)可能包含一些不相等的字段。在那种情况下，我需要维护对象在 multiset<> 中的插入顺序。

我知道如果我使用 C++11 这不是问题，但我们目前还没有。

我看到的另一个解决方案使用类中的时间戳字段使用 <ctime>但这给出了 1 秒的分辨率。如果我在同一秒内有 2 个插入，那么我不能在比较操作中使用时间戳。我们没有/不能在这个项目上使用 boost::chrono。

我可以使用其他方法来确保维护广告顺序吗？

Answer 1

这是一个疯狂的想法:正如@Jerry 建议的那样，维护一个计数器。由于这对对象和计数器是唯一的，我们现在可以使用一个集合(按字典顺序排列)。然后我们使用 lower_bound 找到插入点并计算下一个计数器值:

unsigned int const uimax = std::numeric_limits<unsigned int>::max();

typedef std::set<std::pair<T, unsigned int>> pair_set;

void counted_insert(pair_set & s, T const & t)
{
    pair_set::iterator it = s.lower_bound(std::make_pair(t, uimax));

    if (it == s.begin() || !(*--it == t))
    {
        s.insert(it, std::make_pair(t, 0));
    }
    else
    {
        s.insert(it, std::make_pair(t, it->first + 1));
    }
}