1

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

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

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

我可以使用另一种方法来确保维护插入顺序吗？

4

2 回答 2

1

我只是使用一个每次插入新项目时递增的计数器，并将其用作插入时比较的最后一个字段。在典型情况下，您需要使计数器成为管理集合的类的静态成员。

于 2012-11-02T20:15:32.600 回答
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));
    }
}
于 2012-11-02T20:32:01.443 回答